Mathematische Verfahren in mki-M2, Hochschule Reutlingen

Inhalt:
02.10.09: Geschichtlicher "Uberblick [Beu87] S 7 ff, Transpositionchiffre: Skytala, Substitutionschiffre: Caesar, Vigenere, Affine Chiffre [Sti95] S 8, Richelieu, Vernam, Quanten-Kryptographie [BBE92], RSA [Beu87] S67 ff bzw. [Sti95] S 114 ff: Schl"usselerzeugung, Euklidscher Algorithmus,
09.10.09: Square-and-multiply, Satz von Euler-Fermat, Elektronisches Geld mit RSA [Beu87] S99, Primzahltests [Sti95] S 129 ff bzw. [Kra86]: Sieb des Eratosthenes, Wilson's Test, Lucas's Test,
16.10.09: Monte Carlo primzahltests: (Fermat-test,) Eulersches Kriterium, Quadratische Residuen, Jacobi symbol, Solovay-Strassen-test, Miller-Rabin-test,
23.10.09: Primzahlzertifikate, Faktorisierungsalgorithmen [Sti95] S 138 ff bzw. [MOV90] S 87 ff
30.10.09: Rabin Kryptosystem, Einwegfunktionen, Einweg Hashfunktionen [Sti95] S 233 ff oder [Gol] S 35 ff, W"orterbuchangriff, Geburtstagsangriff, Chaum-van Heijst-Pfitzmann Hashfunktion,
6.11.09: ElGamal Kryptosystem [Sti95] S 163, Shanks Algorithmus f"ur diskreten Logartihmus, Pohlig Hellmann Algorithmus, Index Calculus Methode,
13.11.09: Verallgemainertes ElGamal auf endlichen Koerpern, Polynomring, Elliptische Kurven [Sti95] S 177,
20.11.09: Menezes-Vanstone Kryptosystem [Sti95] S 189, Signaturschemata [Sti95] S 204ff: ElGamal, DSS, Chaum-VanAntwerpen,
27.11.09: 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,
04.12.09: Gruppen-Diffie-Hellmann, Interaktive Beweissysteme, Zero Knowledge Beweissysteme, Merkle-Hellmann Knapsack System [Sti95] S 191, Meet-in-the-middle Algorithmus,
11.12.09: Codierungstheorie Skript (knapp erste Hälfte davon) bis Seite 19,
18.12.09: Seite 20...,
8.1.10: Syndromdecodierung, McEliece Kryptoystem, [Sti95] S 194, Vortrag: Linguistische Steganographie
15.1.10: Datenkompression LZ77, LZW, ... Skript Vortrag: Huffman Code
22.1.10: Vortrag: Münzwurf per Telefon, Vortrag: Secret sharing, Vortrag: Data Encryption Standard, STVF-Codes.
29.1.10: Restliche Vorträge

Übungsaufgaben:
ÜA 1: Welche Nachricht verbirgt sich hinter folgender Shiftchiffre: KOTLGINFAKTZYINRAKYYKRT
Ü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:Das RSA-Verfahren soll (warum auch immer) mit dem Produkt von 3 statt nur 2 Primzahlen berechnet werden. Wird dies ebenfalls funktionieren ? (Begr"undung) Sei n = 7 * 13 * 19. Wie lautet phi(n)? Wie lautet der Umkehrschl\"ussel zu (5,n) (unter Verwendung des erweiterten Euklidischen Algorithmus zu berechnen).
ÜA 5: Welche Zahlen sind quadratische Residuen modulo 17 ?
ÜA 6: Welche Zahlen sind quadratische Residuen modulo 21 ?
ÜA 7: Welche Zahlen sind quadratische Residuen modulo 25 ?
ÜA 8: Wieviele quadratische Residuen gibt es modulo pⁱ für eine Primzahl p?
ÜA 9: Wieviele quadratische Residuen gibt es modulo n=p q für Primzahlen p, q?
ÜA 10: Zeige mittels des Eulerschen Kriteriums daß 507 zusammengesetzt ist.
ÜA 11: Untersuche 5051 und 5053 mit Millers Algorithmus auf Primalität
ÜA 12: Wie lautet ein Pratt- Primalitätszertifikat für 937 ?
ÜA 13: Faktorisiere 1751 mit der Rho-Faktorisierung
ÜA 14: Faktorisiere 401963 mit dem Wissen, dass \phi(401963)=400680.
ÜA 15: Welche Wurzeln hat 1 modulo 31 * 17 ?
ÜA 16: Seien \omega_1 und \omega_2 die nichttrivialen Wurzeln von 1 für das n aus dem Rabin-Schlüssel K=(n,p,q,B) und x die Nachricht. Was sind die 3 anderen Werte, die die Entschlüsselung von e_K(x) liefert?
ÜA 17: Seien f und g injektive Einwegfunktionen. Ist dann auch h mit h(x)=f(g(x)) Einwegfunktion?
ÜA 18: 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 19: Verschlüssle die Nachricht 42 mit dem ElGamal Schlüssel (97,2,11,11) und entschlüssle das Ergebnis wieder.
ÜA 20: Berechne für p=97 den diskreten Logarithmus von 24 zur Basis 2 Mod 96 mit Shank's Algorithmus.
ÜA 21: Berechne für p=61 den diskreten Logarithmus von 53 zur Basis 2 Mod 60 mit dem Pohlig-Hellman Algorithmus.
ÜA 22: 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 23: 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 24: Welche Polynome in \Z₂[x] vom Grad 4 sind irreduzibel?
ÜA 25: Was geht schief, wenn versehentlich modulo eines reduziblen Polynoms f(x) gerechnet wird?
ÜA 26: Aus welchen Punkten besteht die elliptische Kurve E mit p=13, a=2, b=3 ?
ÜA 27: 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 28: 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 29: 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 30: 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 31: 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 32: 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 33: Bei Blom's Schlüsselverteilungsschema mit k=1 werde p=7873 verwendet. Die Benutzer U,V,W.X haben die öffentlichen Werte r_U=2365, r_V=6648, r_W=1837, r_X=2186 und die geheimen Poynome g_W(x)=7601+7802x und g_X(x)=635+6828. Wie berechnet W den Schlüssel K_{W,X}? Wie können X und W gemeinsam K_{U,V} berechnen?
ÜA 34: 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 35: 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 36: Löse die Subset Sum Instanz (6892, 7557, 524, 4982, 1888, 3904, 1677, 4438), T=18014 mit dem meet-in-the-middle Algorithus.
ÜA 37: 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 38: Sei F Quelle mit p_F(a₀)=p_F(a₁)=1/2 und G ein Kanal mit p(b₀|a₀)=p(b₃|a₁)=1/2 und p(b₁|a₀)=p(b₁|a₁)= p(b₂|a₀)=p(b₂|a₁)=1/4 und p(b₃|a₀)=p(b₀|a₁)=0. Wie ist die Entropie H(G) beim Empfänger? Wie ist der bedingte Informationsgehalt I(b₁|a₁)? Wie ist die Streuentropie H(G|F)? Wie ist die mittlere Transinformation I(F,G)? Wie ist die Kapazität des Kanals (Begründung) ?
ÜA 39: Gegeben sei der McEliece Schlüssel aus dem Beispiel aus der Vorlesung. Ver- und entschlüssle die Nachricht x=(1,0,1,0) mit e=(0,0,1,0,0,0,0). Warum würde es mit e=(0,0,1,0,1,0,0) nicht funktionieren?
ÜA 40: Komprimiere "ballballblablablablablabla" mit dem LZ77 Verfahren. Beide Puffer sollen 6 Zeichen lang sein.
ÜA 41: Komprimiere "ballballblablablablablabla" mit dem LZW Verfahren.
ÜA 42: Konstruiere den Suffixbaum zu "ballballblablablablablabla".
ÜA 43: Komprimiere "ballballblablablablablabla" mit dem STVF code mit 3 Bits.

Literatur/Skripte:

Kryptologie & Komplexität, interaktives Skript mit Applets