Übungen zur Kryptologie und Komplexität

DozentPD. Dr. Klaus Reinhardt
SprechstundeNach Vereinbarung, Raum B 114
ZeitDonnerstags 14:00-14:45 (direkt nach der Vorlesung) Raum A 301

Übungsblätter

Anmeldung zu den Übungen

Matrnr.: Nachname: Vorname:
Gruppe: Studienfach: Fachsemester:
Geburtsdatum (wird für den Schein benötigt) : email:

Vorlesungsinhalte WS07/08

15/18.10.07: Geschichtlicher "Uberblick [Beu87] S 7 ff, Transpositionchiffre: Skytala, Substitutionschiffre: Caesar, Vigenere, Affine Chiffre [Sti95] S 8, Richelieu, Vernam, Quanten-Kryptographie [BBE92],
22.10.07: RSA [Beu87] S67 ff bzw. [Sti95] S 114 ff: Schl"usselerzeugung, Euklidscher Algorithmus, Satz von Euler-Fermat, Elektronisches Geld mit RSA [Beu87] S99,
25.10.07: Primzahltests [Sti95] S 129 ff bzw. [Kra86]: Sieb des Eratosthenes, Wilson's Test, Lucas's Test, ,
29.10.07: Monte Carlo primzahltests: Fermat-test, Eulersches Kriterium, Jacobi symbol, Solovay-Strassen-test, Miller-Rabin-test,
8.11.07: Pratt's Test: Pimzahlen in NP. Pimzahlen in P. [AKS02]
12.11.07: Pollard's rho Faktorisierung, Pollard's p-1 Faktorisierung, Quadratische Faktorisierung, Quadratisches Sieb, [Sti95] S 138 ff bzw. [MOV90] S 87 ff
15.11.07: Faktorisierung bei bekanntem phi(n), Faktorisierung bei bekanntem RSA-secret-key,
19.11.07: Rabin Kryptosystem, Einwegfunktionen, UP [Pap94] S 281, Starke Einwegfunktionen schwache Einwegfunktionen [Gol] S 46 ff,
22.11.07: Einweg Hashfunktionen [Sti95] S 233 ff oder [Gol] S 35 ff, W"orterbuchangriff, Geburtstagsangriff, Chaum-van Heijst-Pfitzmann Hashfunktion,
26.11.07: diskreter Logartihmus, Erweiterung von Hashfunktionen, Hashfunktion <=> Kryptosystem, ElGamal Kryptosystem [Sti95] S 163, Shanks Algorithmus f"ur diskreten Logartihmus, Pohlig Hellmann Algorithmus, Index Calculus Methode,
29.11.07: Verallgemainertes ElGamal auf endlichen Koerpern, Polynomring,
03.12.07: Elliptische Kurven [Sti95] S 177, Menezes-Vanstone Kryptosystem [Sti95] S 189,
06.12.07: Signaturschemata [Sti95] S 204ff: ElGamal, DSS, Lamport,
10.12.07: Chaum-VanAntwerpen, Heyst Pedersen, Schl"usselverteilung: Blom's Schema,
13.12.07: Diffie-Hellmann Schl"usselverteilung, Kerberos. [Sti95] S 259,Schl"usselaustausch,
17.12.07: intruder-in-the middle-Angriff, STS Protokoll [Sti95] S 269, Needham-Schroeder-Protokoll, Gruppen-Diffie-Hellmann
20.12.07: Zero-Knowledge Beweissysteme, Interaktive 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),
07.1.08: [Gol] S 153 ff, polynomielle Hierarchie in P^{#P}, Permanente #P-vollst.. LFKN Protokoll zur Pr"ufung der Permanente [Bab90], IP=PSPACE
10.1.08: Kryptosysteme und NP-vollst"andigkeit [EY80],
14.1.08: Merkle-Hellmann Knapsack System [Sti95] S 191, Meet-in-the-middle Algorithmus, L^3 Gitter Basis Reduktion,
17.1.08: Knapsack mit geringer Dichte [MOV90] S 118, Algorithmus von Shamir zum Berechnen eines alternativen geheimen Schl"ussels,
21.1.08: McEliece System [Sti95] S 194, nichtverfolgbares elektronisches Geld, nichtverfolgbare elektronische Schecks [CFN88],
24.1.08: Kartenspiel "ubers Netz, M"unzwurf per Telephon (Bit-commitment),
28.1.08: Bestimmung des "alteren ohne Altersangabe, Das Teilen von Geheimnissen [Sti95] S 327, verifizierbares Teilen von Geheimnissen.[CGMA85],
31.1.08: Die Verhinderung des Missbrauchs von Kryptosystemen [Des88].,
4.2.08: Pseudozufallsgeneratoren, Probabilistische Verschluesselung [Sti95] S 361ff, 22, 39 Visuelle Kryptographie [NS94], Nichtverfolgbare e-mail, Wahlschemata,

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, 319­327.

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, 383­395.

Des88
Yvo Desmedt. Abuses in Cryptogrphy and How to Fight Them. Proceedings of the CRYPTO88, 374­389.

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 .

2007-04-24 Klaus Reinhardt (reinhard@informatik.uni-tuebingen.de)