Kryptologie und Komplexität
| Dozent |
Klaus Reinhardt |
|
Sprechstunde |
Nach Vereinbarung, Raum 12, Sand 13, Tel. 77566 |
|
Zeit / Ort |
Mo 12:00 -13:00 A 301 Sand,
Mi 17:00-19:00 grosser Hörsaal Sand 6/7.
|
|
Umfang |
4h |
|
Begin |
erste Semesterwoche |
|
Vorbesprechung |
- |
|
Turnus |
2-jährig |
|
Prüfungsfach |
Theoretische Informatik |
|
Beschreibung:
Kryptologie ermöglicht nicht nur geheime Kommunikation
sondern auch Authentifikation, elektronische Unterschrift/Signatur
und vieles mehr.
Mit der rasanten Entwicklung elektronischer Kommunikationstechniken
wie z.B. e-mail, WWW, Internet-banking, E- Shopping usw.
und der zunehmenden Verbreitung ihrer Anwendungen ist die Nachfrage
nach solchen Sicherheitsdienstleistungen in den
letzten Jahren enorm gestiegen.
Ziel der Vorlesung soll es sein, sowohl die Grundlagen der
Methoden wie z.B. RSA, Einwegfunktionen usw.
zu verstehen, als auch deren Anwendungen
z.B. elektronisches Geld (siehe CFN88), PGP usw. kennenzulernen.
Ferner werden wir Zusammenhänge zu den Komplexitätsklassen NP, RP, UP
und BPP und Zeroknowledge/interaktive Beweissysteme (siehe Bab90)
betrachten.
Voraussetzungen:
- Grundstudium Informatik oder Komplexitätstheorie
Bemerkungen:
Literaturliste: Kopie im Ordner
- 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
- 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 .
Inhalt
13.10.03:
Geschichtlicher "Uberblick
[Beu87] S 7 ff,
Transpositionchiffre: Skytala, Substitutionschiffre:
Caesar, Vigenere, Affine Chiffre [Sti95] S 8,
Richelieu, Vernam,
Quanten-Kryptographie
[BBE92],
15.10.03:
RSA
[Beu87] S67 ff bzw. [Sti95]
S 114 ff:
Schl"usselerzeugung, Euklidscher Algorithmus,
Satz von Euler-Fermat,
20.10.03:
Elektronisches Geld mit RSA [Beu87] S99,
Primzahltests [Sti95] S 129 ff bzw.
[Kra86]:
Sieb des Eratosthenes, Wilson's Test, Lucas's Test,
22.10.03:
Monte Carlo primzahltests: Fermat-test, Eulersches Kriterium,
Jacobi symbol, Solovay-Strassen-test, Miller-Rabin-test
27.10.03:
Pratt's Test: Pimzahlen in NP. Pimzahlen in P.
[AKS02]
29.10.03: Pollard's rho Faktorisierung, F. bei bekanntem phi(n)
03.11.03:
Pollard's p-1 Faktorisierung, F. bei bekanntem RSA-secret-key,
Quadratische Faktorisierung
[Sti95] S 138 ff bzw. [MOV90] S 87 ff
05.11.03:
Quadratisches Sieb, Rabin Kryptosystem.
10.11.03:
Einwegfunktionen, UP [Pap94] S 281,
Starke Einwegfunktionen
12.11.03:
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,
17.11.03:
Erweiterung von Hashfunktionen, Hashfunktion <=> Kryptosystem,
ElGamal Kryptosystem [Sti95] S 163,
Shanks Alggorithmus f"ur diskreten Logartihmus,
19.11.03:
Pohlig Hellmann Algorithmus,
ElGamal Signaturschema, DSS [Sti95] S 206,
24.11.03:
Endliche Koerper und Elliptische Kurven
[Sti95] S 177,
26.11.03:
Menezes-Vanstone Kryptosystem [Sti95] S 189,
Schl"usselverteilung:
Blom's Schema, Diffie-Hellmann Schl"usselverteilung, Kerberos.
[Sti95] S 259
1.12.03:
Schl"usselaustausch, intruder-in-the middle-Angriff,
STS Protokoll [Sti95] S 269,
Zero-Knowledge Beweissysteme,
Interaktive Beweissysteme [Sti95] S 387 ff
oder [Gol] S 143 ff
3.12.03:
Graph-Nicht-Isomorphismus in IP, Graph-3-colorability in IP
[Sti95] S 403 ff,
[Gol] S 180 ff,
NP, BPP \subseteq IP(1), starker, schwacher interaktiver Beweis,
[Sti95] S 387 ff,
[Gol] S 153 ff,
polynomielle Hierarchie in P^{#P}, Permanente #P-vollst..
8.12.03:
LFKN Protokoll zur Pr"ufung der Permanente
[Bab90],
IP=PSPACE
10.12.03:
Kryptosysteme und NP-vollst"andigkeit
[EY80],
15.12.03:
Merkle-Hellmann Knapsack System [Sti95] S 191,
Meet-in-the-middle Algorithmus, L^3 Gitter Basis Reduktion,
17.12.03:
Knapsack mit geringer Dichte [MOV90] S 118,
Gibt es NP-harte Public-Key Kryptosysteme? [EY80],
McEliece System
[Sti95] S 194,
07.01.04:
nichtverfolgbares elektronisches Geld
nichtverfolgbare elektronische Schecks [CFN88],
12.01.04:
Kartenspiel "ubers Netz, Bestimmung des "alteren ohne Altersangabe,
M"unzwurf per Telephon (Bit-commitment),
14.01.04:
Das Teilen von Geheimnissen [Sti95] S 327,
verifizierbares Teilen von Geheimnissen.[CGMA85]
19.01.04, 21.01.04:
Die Verhinderung des Missbrauchs von Kryptosystemen
[Des88].
26.01.04, 28.01.04:
Visuelle Kryptographie [NS94],
Pseudozufallsgeneratoren [Sti95] S 361ff, 22, 39
Kryptologie und Komplexität interaktiv
2001-01-029 Klaus Reinhardt
(reinhard@informatik.uni-tuebingen.de)