Mathematische Verfahren in mki-M2, Hochschule Reutlingen

Inhalt:
08.10.10: Geschichtlicher "Uberblick [Beu87] S 7 ff, Transpositionchiffre: Skytala, Substitutionschiffre: Caesar, Vigenere, Affine Chiffre [Sti95] S 8, Richelieu, Vernam, Quanten-Kryptographie [BBE92], Euklidscher Algorithmus,
19.10.10, 12:30 Raum 9-128: RSA [Beu87] S67 ff bzw. [Sti95] S 114 ff: Schlüsselerzeugung, Square-and-multiply, Satz von Euler-Fermat,

26.10.10, 9:15 Raum 9-128: Elektronisches Geld mit RSA [Beu87] S99, Primzahltests [Sti95] S 129 ff bzw. [Kra86]: Sieb des Eratosthenes, Wilson's Test, Lucas's Test, 25.03.10: Primzahlzertifikate (Pratt-sequenz),

29.10.10, 13:15 Raum 9-128: Monte Carlo primzahltests: (Fermat-test,) Eulersches Kriterium, Quadratische Residuen, Jacobi symbol, Solovay-Strassen-test, Miller-Rabin-test,

5.11.10, 13:15 Raum 9-128: Faktorisierungsalgorithmen [Sti95] S 138 ff bzw. [MOV90] S 87 ff

12.11.10, 13:15 Raum 9-128: Rabin Kryptosystem, Chinesischer Restklassenesatz, Einwegfunktionen, Einweg Hashfunktionen [Sti95] S 233 ff oder [Gol] S 35 ff,

19.11.10, 13:15 Raum 9-128: W"orterbuchangriff, Geburtstagsangriff, Chaum-van Heijst-Pfitzmann Hashfunktion, ElGamal Kryptosystem [Sti95] S 163, Shanks Algorithmus f"ur diskreten Logarithmus,


(26.11. wird verschoben auf)
25.11.10, 9:15 Raum 9-128: Pohlig Hellmann Algorithmus, (Index Calculus Methode,) Verallgemainertes ElGamal auf endlichen Koerpern, Rechnen modulo irreduziblen Polynomen,

3.12.10, 13:15 Raum 9-128: Elliptische Kurven, Signaturschemata [Sti95] S 204ff: ElGamal, DSS, Chaum-VanAntwerpen unbestreitbare Unterschriften,



10.12.10, 13:15 Raum 9-128: Schl"usselverteilung: (Blom's Schema,) Diffie-Hellmann Schl"usselverteilung, Kerberos. [Sti95] S 259,Schl"usselaustausch, intruder-in-the middle-Angriff, STS Protokoll [Sti95] S 269, Needham-Schroeder-Protokoll,

17.12.10, 13:15 Raum 9-128: Merkle-Hellmann Knapsack System [Sti95] S 191, Meet-in-the-middle Algorithmus, Codierung: ISBN, EAN-13, Hammingdecodierung

14.1.11, 13:15 Raum 9-128: Referate, Datenkompression: Entropie, LZ77, LZW, Skript

21.1.11, 13:15 Raum 9-128: Referate

Übungsaufgaben:
ÜA 1: Welche Nachricht verbirgt sich hinter folgender Shiftchiffre: DPSCWPTNSEKFPYEDNSWFPDDPWY
ÜA 2: Wieviele mögliche Affine Chiffren gibt es für ein Alphabet der Größe 64 ?
ÜA 3: Welche Nachricht verbirgt sich hinter folgender affinen Chiffre: XFFPCUJLIUXLIGRLIZPCSVPUGRLIQVPRRPQU
ÜA 4: Berechne das multiplikativ Inverse zu 31 modulo 101; d.h. gesucht ist x mit 31 x ≡ 1 (mod 101).(Zwischenergebnisse angeben)
ÜA 5: Wieviele modulare Multiplikationsschritte sind notwendig um x¹⁵ Mod n zu berechnen. Demonstriere dies am Beispiel x=3 und n=23.
ÜA 6:Das RSA-Verfahren soll (warum auch immer) mit dem Produkt von 3 statt nur 2 Primzahlen berechnet werden. Wird dies ebenfalls funktionieren ? (Begründung) Sei n = 7 * 13 * 19. Wie lautet phi(n)? Wie lautet der Umkehrschlüssel zu (5,n) (unter Verwendung des erweiterten Euklidischen Algorithmus zu berechnen).
ÜA7 : Die Ordnung von g in einer Gruppe (Z_n^*, ×) ist das kleinste t mit g^t ≡ 1 (mod n). Wie ist die Ordnung von 2 in (Z₄₁^*, ×)? Wie ist die Ordnung von 3 in (Z₄₁^*, ×)? Welche Ordnungen koennen in (Z₄₁^*, ×) auftreten? (Welche Ordnungen koennen allgemein in (Z_n^*, ×) auftreten?)
ÜA8 : Beweise dass a und das multiplikativ inverse a^-1 immer die gleiche Ordnung haben.
ÜA9 : Wie lautet ein Pratt- Primalitätszertifikat für 937 ?

ÜA 10: Welche Zahlen sind quadratische Residuen modulo 17 ?
ÜA 11: Welche Zahlen sind quadratische Residuen modulo 21 ?
ÜA 12: Welche Zahlen sind quadratische Residuen modulo 25 ?
ÜA 13: Wieviele quadratische Residuen gibt es modulo pⁱ für eine Primzahl p? (lerne an dem Beispiel der vorherigen Aufgabe)
ÜA 14: Wieviele quadratische Residuen gibt es modulo n=p q für Primzahlen p, q? (lerne an dem Beispiel der Aufgabe 11)
ÜA 15: Zeige mittels des Eulerschen Kriteriums dass 507 zusammengesetzt ist.
ÜA 16: Untersuche 5051 und 5053 mit Millers Algorithmus auf Primalität
ÜA 17: Faktorisiere 1751 mit der Rho-Faktorisierung
ÜA 18: Faktorisiere 401963 mit dem Wissen, dass \phi(401963)=400680.
ÜA 19: Faktorisiere 200290099 mit dem Wissen, dass 40029² ≡ 7² mod 200290099.
ÜA 20: Faktorisiere 90937103 mit Hilfe des RSA Schlüsselpaars (3533,90937103) (76584197,90937103).
ÜA 21: Welche Wurzeln hat 1 modulo 31 * 17 ?
ÜA 22: Gegeben sei der Rabin-Schlüssel K=(2021,43,47,10) und die Nachricht x=42. Wie lautet die Chiffre e_K(x) Was sind die 3 anderen Werte, die die Entschlüsselung von e_K(x) liefert?
ÜA 23: Seien f und g injektive Einwegfunktionen. Ist dann auch h mit h(x)=f(g(x)) Einwegfunktion?
ÜA 24: Die gleiche Nachricht m wurde mit 3 verschiedenen RSA-Schlüsseln mit Exponent 3 verschlüsselt. Es sei e_(3,205)(m)=10, e_(3,319)(m)=254 und e_(3,391)(m)=213. Wie lautet m?
ÜA 25: (knifflig) Die gleiche Nachricht m wurde mit 2 verschiedenen RSA-Schlüsseln (e,n) und (g,n) mit gleichem Modulus n verschlüsselt. Wie kann Eve (der Lauscher) m bestimmen?
ÜA 26: Berechne die Chaum-vanHejst-Pfitzmann Hashfunktion von dem Paar (8,16) mit p= 107, \alpha =2, \beta =7. Dieses kollidiert mit dem Paar (51,15). Wie ergibt sich daraus log₂ 7 ?
ÜA 27: Verschlüssle die Nachricht 42 mit dem ElGamal Schlüssel (97,2,11,11) und entschlüssle das Ergebnis wieder.
ÜA 28: Berechne für p=97 den diskreten Logarithmus von 24 zur Basis 2 Mod 96 mit Shank's Algorithmus.

ÜA 29: Berechne für p=61 den diskreten Logarithmus von 53 zur Basis 2 Mod 60 mit dem Pohlig-Hellman Algorithmus.
ÜA 30: Welche Bits des diskreten Logarithmus für p=10009 können leicht berechnet werden? Wie lauten diese im Fall des diskreten Logarithmus von 17 zur Basis 11 ?
ÜA 31: Das verallgemeinerte ElGamal Public-key Kryptosystem werde mit der Gruppe (\Z_n,+) verwendet. Wie würde ein Algorithmus (Pseudocode) aussehen, der das System bricht, also ohne Kenntniss des geheimen Schlüssels entschlüsseln kann?
ÜA 32: Welche Polynome in \Z₂[x] vom Grad 4 sind irreduzibel?
ÜA 33: Was geht schief, wenn versehentlich modulo eines reduziblen Polynoms f(x) gerechnet wird?

ÜA 34: Aus welchen Punkten besteht die elliptische Kurve E mit p=13, a=2, b=3 ?
ÜA 35: Sei sei E wie in letzter Aufgabe, \alpha =(0,4) und a=7 der geheime Exponent. Ver- und entschlüssle die Nachricht x=(6,7) mit k=3.
ÜA 36: Sei sei E, \alpha und a wie in letzter Aufgabe. Ver- und entschlüssle die Nachricht x=(11,11) mit dem Menezes-Vanstone Kryptosystem.
ÜA 37: Unterschreibe die Nachricht x=3001 mit dem DSS-Schlüssel K=(p=7879,q=101,\alpha=170,a=75,\beta=4567) und k=17. Prüfe die Unterschrift.
ÜA 38: Bob und Claire hatten eine Affäre. Alice präsentiert Claire nun eine von Bob unbestreitbar unterschriebene Nachricht, in der Bob schreibt, dass er sie (Alice) liebt und die Affäre mit Claire beendet ist und er sie bittet ihn nicht zu enterben. (Alice hat diese aber selbst noch nicht verifiziert.) Da Bob nicht mit Claire spricht, bietet Alice Claire an, das Verifikationsprotokoll auf dem Umweg über sie (Alice) durchzuführen, d.h. Claire darf e_1, e_2 bestimmen und die Nachrichten überwachen. Kann Claire dadurch überzeugt werden?
ÜA 39: Claire hatte Alice's Angebot vorhergesehen. In Wirklichkeit hatte Bob an Alice geschrieben, dass er sich wegen Claire von ihr (Alice) scheiden lassen will und auf den Anteil an ihrem Vermögen verzichtet. Diese Nachricht hatte Claire aber abgefangen und durch die aus vorheriger Aufgabe mit einer gefälschten Unterschrift ersetzt um Alice davon abzuhalten, Bob, wie beabsichtigt, aus ihrem Testament zu streichen. Kann Claire's Täuschung auf diese Weise gelingen indem sie e_1, e_2 so bestimmt, dass die Verifikation durch Alice positiv ausgeht? Warum?
ÜA 40: Einige Tage später wird Alice ermordet aufgefunden und die Polizei findet die Nachricht auf Alice's Computer und verhaftet zunächst Bob unter dem Verdacht auf das Erbe aus zu sein. Wie kann Bob sich vor Gericht entlasten?

ÜA 41: Dem Angreifer W sei der intruder-in-the-middle Agriff auf die Diffie-Hellman Schlüsselübereinkunft zwischen U und V gelungen. Nun bittet U V die im vereinbarten Schlüssel auf die Ziffernfolge 728635956278 folgenden 8 Ziffern zu seinem Geburtstag (Format ttmmjjjj) zu addieren und an U zurückzuschicken. Kann W, der das Datum nicht kennt, verhindern dass der Angriff dadurch erkannt wird?


ÜA 42: Gegeben sei s=(1,2,6,11,26,50,100,204,420), p=1033, a=1000 für das Merkle-Hellman Kryptosystem. Berechne t, ver- und entschlüssle die Nachricht x=(0,1,1,1,0,0,1,0,1).
ÜA 43: Löse die Subset Sum Instanz (6892, 7557, 524, 4982, 1888, 3904, 1677, 4438), T=18014 mit dem meet-in-the-middle Algorithus.
ÜA 44: Beim ISBN-Prüfzifferncode werde Mod 10 statt Mod 11 gerechnet. Konstruiere ein Beispiel in dem die Änderung einer Ziffer nicht bemerkt würde. Konstruiere ein Beispiel in dem die Vertauschung zweier Ziffern nicht bemerkt würde.
ÜA 45: Überprüfe den Barcode auf einer Verpackung aus dem letzten Einkauf auf Richtigkeit.
ÜA 46: Gegeben seien die folgenden Wahrscheinlichkeiten für das Alphabet {a,b,c,d,e,f}: P(a)=0,25; P(b)=0,0625; P(c)=0,0625; P(d)=0,0625; P(e)=0,4375; P(f)=0,125. Wie groß ist die Entropie? Konstruiere dazu einen Huffman-Code. Wie ist die erwartete Codewortlänge?
ÜA 47: Komprimiere "ballballblablablablablabla" mit dem LZ77 Verfahren. Beide Puffer sollen 6 Zeichen lang sein.
ÜA 48: Komprimiere "ballballblablablablablabla" mit dem LZW Verfahren.

Vorschläge zu Vortragthemen:
Huffman Code, Online Banking, Visuelle Kryptographie, Data Encryption Standard (DES), Elliptische Kurven, Quantenkryptographie, Java Applets zum Brechen von Vigenene Chiffre ..., Münzwurf per Telefon, Secret sharing (Teilen von Geheimnissen), Byzantinische Übereinkunft, AES, Biometrische Verfahren, Kryptographische Wahlschemata, Nichtverfolgbare e-mail, Enigma, Bild-datenkompresson bei Faxgeräten, ...
Bereits vergeben:

Note:
Je 1/3 Vortrag, Ausarbeitung und Beteiligung an den Übungen.

Literatur/Skripte:

Kryptologie, interaktives Skript mit Applets

Codierung und Verschluesselung, Skript von Prof. Dr. P. Hauck