Kryptologie

Übungsblätter

Aufgabenblatt 1 Aufgabenblatt 2 Aufgabenblatt 3 Aufgabenblatt 4 Aufgabenblatt 5 Aufgabenblatt 6 Aufgabenblatt 7 Aufgabenblatt 8 Aufgabenblatt 9 Aufgabenblatt 10 Aufgabenblatt 11 Aufgabenblatt 12


Vorlesungsinhalte SS07

17.4.07: Geschichtlicher "Uberblick [Beu87] S 7 ff, Transpositionchiffre: Skytala, Substitutionschiffre: Caesar, Vigenere, Affine Chiffre [Sti95] S 8, Richelieu, Vernam, Quanten-Kryptographie [BBE92],
18.4.07: RSA [Beu87] S67 ff bzw. [Sti95] S 114 ff: Schl"usselerzeugung, Euklidscher Algorithmus, Satz von Euler-Fermat, Elektronisches Geld mit RSA [Beu87] S99,
24.4.07: Primzahltests [Sti95] S 129 ff bzw. [Kra86]: Sieb des Eratosthenes, Wilson's Test, Lucas's Test, Monte Carlo primzahltests: Fermat-test, Eulersches Kriterium, Jacobi symbol, Solovay-Strassen-test,
25.4.07: Miller-Rabin-test, Pratt's Test: Pimzahlen in NP. Pimzahlen in P. [AKS02]
02.5.07: Pollard's rho Faktorisierung, Pollard's p-1 Faktorisierung, Quadratische Faktorisierung, Quadratisches Sieb, [Sti95] S 138 ff bzw. [MOV90] S 87 ff
08.05.07: Faktorisierung bei bekanntem phi(n), Faktorisierung bei bekanntem RSA-secret-key, Rabin Kryptosystem.
09.05.07: Einwegfunktionen, UP [Pap94] S 281, Starke Einwegfunktionen
15.05.07: schwache Einwegfunktionen [Gol] S 46 ff, Einweg Hashfunktionen [Sti95] S 233 ff oder [Gol] S 35 ff, W"orterbuchangriff, Geburtstagsangriff, Chaum-van Heijst-Pfitzmann Hashfunktion, diskreter Logartihmus, Erweiterung von Hashfunktionen,
16.05.07: Hashfunktion <=> Kryptosystem, ElGamal Kryptosystem [Sti95] S 163, Shanks Alggorithmus f"ur diskreten Logartihmus, Pohlig Hellmann Algorithmus,
22.05.07: Index Calculus Methode, Verallgemainertes ElGamal auf endlichen Koerpern, Polynomring,
23.05.07: Elliptische Kurven [Sti95] S 177, Menezes-Vanstone Kryptosystem [Sti95] S 189,
05.06.07: Signaturschemata [Sti95] S 204ff: ElGamal, DSS, Lamport, Chaum-VanAntwerpen,
06.06.07: Heyst Pedersen, Schl"usselverteilung: Blom's Schema, Diffie-Hellmann Schl"usselverteilung,
12.06.07: Kerberos. [Sti95] S 259,Schl"usselaustausch, intruder-in-the middle-Angriff, STS Protokoll [Sti95] S 269, Needham-Schroeder-Protokoll,
13.06.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),
19.06.07: [Gol] S 153 ff, polynomielle Hierarchie in P^{#P}, Permanente #P-vollst.. LFKN Protokoll zur Pr"ufung der Permanente [Bab90], IP=PSPACE
20.06.07: Kryptosysteme und NP-vollst"andigkeit [EY80], Merkle-Hellmann Knapsack System [Sti95] S 191,
26.06.07: Meet-in-the-middle Algorithmus, L^3 Gitter Basis Reduktion, Knapsack mit geringer Dichte [MOV90] S 118,
27.06.07: Algorithmus von Shamir zum Berechnen eines alternativen geheimen Schl"ussels, McEliece System [Sti95] S 194, nichtverfolgbares elektronisches Geld
03.07.07: nichtverfolgbare elektronische Schecks [CFN88], M"unzwurf per Telephon (Bit-commitment), Kartenspiel "ubers Netz,
04.07.07: Bestimmung des "alteren ohne Altersangabe, Das Teilen von Geheimnissen [Sti95] S 327, verifizierbares Teilen von Geheimnissen.[CGMA85]
10.07.07: Die Verhinderung des Missbrauchs von Kryptosystemen [Des88]. Pseudozufallsgeneratoren, [Sti95] S 361ff, 22, 39
11.07.07: Pseudozufallsgeneratoren, Probabilistische Verschluesselung [Sti95] S 361ff, 22, 39
17.07.07: Visuelle Kryptographie [NS94],
18.07.07: 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)