Hinweise und Übungen zur Kryptologie

Dozent	PD. Dr. Klaus Reinhardt
Sprechstunde	Nach Vereinbarung, Raum B 114
Zeit	direkt nach der Vorlesung d.h. entweder Montag 18:00 oder Dienstag 16:00 Hörsaal 2

Übungsblätter

Aufgabenblatt 1.
Aufgabenblatt 2.
Aufgabenblatt 3.
Aufgabenblatt 4.
Zu Beginn der Übungsstunde geht eine Votierliste um, in der jeder die Aufgaben, die er vorrechnen kann, ankreuzt.

Vorlesungsinhalte WS09/10

19.10.09: Geschichtlicher Überblick [Beu87] S 7 ff, Transpositionchiffre: Skytala, Substitutionschiffre: Caesar, Vigenere, Affine Chiffre [Sti95] S 8, Richelieu, Vernam, Quanten-Kryptographie [BBE92],
20.10.09: RSA [Beu87] S67 ff bzw. [Sti95] S 114 ff: Schl"usselerzeugung, Euklidscher Algorithmus, Square-and-multiply, Satz von Euler-Fermat,
26.10.09: Elektronisches Geld mit RSA [Beu87] S99, Primzahltests [Sti95] S 129 ff bzw. [Kra86]: Sieb des Eratosthenes,
27.10.09: Wilson's Test, Lucas's Test, Primzahlzertifikate, Monte Carlo primzahltests: (Fermat-test,) Eulersches Kriterium, Quadratische Residuen, Jacobi symbol, Solovay-Strassen-test,
02.11.09: Miller-Rabin-test, Alg. von Miller, Komplexitätsklassen
03.11.09: Pimzahlen in P [AKS02], Faktorisierungsalgorithmen: Pollard's rho Faktorisierung, Pollard's p-1 Faktorisierung, [Sti95] S 138 ff bzw. [MOV90] S 87 ff
09.11.09: Quadratische Faktorisierung, Quadratisches Sieb,
10.11.09: Faktorisierung bei bekanntem phi(n), Faktorisierung bei bekanntem RSA-secret-key, Rabin Kryptosystem,
16.11.09: Einwegfunktionen, UP [Pap94] S 281, Starke Einwegfunktionen schwache Einwegfunktionen [Gol] S 46 ff,
17.11.09: Einweg Hashfunktionen [Sti95] S 233 ff oder [Gol] S 35 ff, W"orterbuchangriff, Geburtstagsangriff, Chaum-van Heijst-Pfitzmann Hashfunktion,
23.11.09: Visuelle Kryptographie [NS94],
24.11.09: ElGamal Kryptosystem [Sti95] S 163, Shanks Algorithmus f"ur diskreten Logartihmus, Pollard's \rho Alg.
30.11.09: Pohlig Hellmann Algorithmus,
1.12.09: Index Calculus Methode,
7.12.09: Verallgemainertes ElGamal auf endlichen Koerpern, Polynomring, Elliptische Kurven [Sti95] S 177,
8.12.09: Menezes-Vanstone Kryptosystem [Sti95] S 189, Signaturschemata [Sti95] S 204ff: ElGamal,
14.12.09: DSS, Lamport, Chaum-VanAntwerpen Unbestreitbare Unterschrift,
15.12.09: Schl"usselverteilung: Blom's Schema,
11.1.10: Diffie-Hellmann Schl"usselverteilung, Kerberos. [Sti95] S 259,Schl"usselaustausch, intruder-in-the middle-Angriff, STS Protokoll [Sti95] S 269,
12.1.10: Diffie-Hellmann Schl"usselaustausch, intruder-in-the middle-Angriff, STS Protokoll [Sti95] S 269, Needham-Schroeder-Protokoll, Gruppen-Diffie-Hellmann,
18.1.10: Interaktive Beweissysteme, Zero Knowledge Beweissysteme, [Sti95] S 387 ff oder [Gol] S 143 ff Graph-Nicht-Isomorphismus in IP, Graph-3-colorability in IP [Sti95] S 403 ff, [Gol] S 180 ff, NP, BPP \subseteq IP(1),
19.1.10: [Gol] S 153 ff, polynomielle Hierarchie in P^{#P}, Permanente #P-vollst.. LFKN Protokoll zur Pr"ufung der Permanente [Bab90], IP=PSPACE
25.1.10: Merkle-Hellmann Knapsack System [Sti95] S 191, Meet-in-the-middle Algorithmus,
26.1.10: L^3 Gitter Basis Reduktion, Knapsack mit geringer Dichte [MOV90] S 118,
1.2.10: McEliece System [Sti95] S 194, Kryptosysteme und NP-vollst"andigkeit [EY80],
2.2.10: nichtverfolgbares elektronisches Geld, nichtverfolgbare elektronische Schecks [CFN88] Kartenspiel "ubers Netz,
8.2.10: M"unzwurf per Telephon (Bit-commitment), Bestimmung des "alteren ohne Altersangabe, Das Teilen von Geheimnissen [Sti95] S 327,
9.2.10: verifizierbares Teilen von Geheimnissen.[CGMA85],
15.2.10: Pseudozufallsgeneratoren, Probabilistische Verschluesselung [Sti95] S 361ff, 22, 39
16.2.10: Nichtverfolgbare e-mail

Literaturliste:

ADS93: M. Andrasiu, J. Dassow, A. Salomaa, G. Paun. Language-theoretic problems arising from Richelieu cryptosystems. Theoretical Computer Science 116, 1993.
AKS02: M. Agarwal, N. Kayal , N. Saxena. PRIMES is in P.2002.
Bab90: Lazlo Babai. E-mail and the unexpected power of interaction. Proceedings of the 5-th Structure, 1990.
BBE92: C. H. Bennett, G. Brassard, A. K. Ekert. Quanten-Kryptographie. Spectrum der Wissenschaft Dec. 1092
Beu87: Albrecht Beutelspacher. Kryptologie. Vieweg, 1987.
BSW95: Beutelspacher, J. Schwenk und K.-D. Wolfenstetter. Moderne Verfahren der Kryptographie. Vieweg, 1995.
CFN88: D. Chaum, A. Fiat, M. Naor. Untracable Electronic Cash. Proceedings of the CRYPTO88, 319327.
CGMA85: B. Chor, S. Goldwasser, S. Micaili, B. Awerbuch. Verifiable Secrect Sharing and Achieving Simultaneity in the Presence of Faults. Proceedings of the FOCS'85, 383395.
Des88: Yvo Desmedt. Abuses in Cryptogrphy and How to Fight Them. Proceedings of the CRYPTO88, 374389.
EY80: Shimon Even, Yacov Yacobi. Cryptocomplexity and NP-Completeness. 7-th ICALP 90, 195--207, 1980.
FS86: A. Fiat, A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. Proceedings of the CRYPTO'86, 186-194.
Gol: Oded Goldreich. Foundations of Cryptography. Postscript File
Kar89: J. Kari. A Cryptosystem Based on Propositional Logic. Proceedings of the 5th IMYCS' 89, LNCS 381, 210--219, 1989
Kob98: Neal Koblitz. Algebraic Aspects of Cryptography. Springer, 1998
Kra86: Evangelos Kranakis. Primality and cryptography. Stuttgart, Teubner, 1986
Mao04: Wenbo Mao. Modern Cryptography. Prentice Hall, 2004
MOV90: A. A. J. Menzes, P. C. van Oorschot and S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1997.
NS84: M. Naor, A. Shamir. Visual Cryptography. Proceedings of the Eurocrypt'94, 1-12. [ps]
Pap94: Christos H. Papadimitriou. Computational complexity. Addison-Wesley, 1994
Riv90: Ronald L. Rivest. Cryptographie. in L. van Leeuwen: Handbook of Theoretical Computer Science Volume A, The MIT Press/Elsevier, 1990.
Sal90: Arto Salomaa. Public-key Cryptographie. EATCS monographs on theoretical computer science, Springer, 1990.
Sch96: B. Schneier. Angewandte Kryptographie. Addison-Wesley, 1996.
Sti95: Douglas R. Stinson. Cryptography - Theory and Practice. CRC Press, 1995. ISBN 0-8493-8521-0.
Zu diesem Buch existiert auch eine Fehlerliste .

2009-11-2 Klaus Reinhardt (reinhard@informatik.uni-tuebingen.de)