Kryptologie und Komplexität
| Dozent |
Klaus Reinhardt |
|
Sprechstunde |
Nach Vereinbarung, Raum 004, Sand 13, Tel. 78964 |
|
Zeit / Ort |
Mo 16-18 MS M2, Mi 15-17 MS N9 |
|
Umfang |
4h |
|
Begin |
14.04.1999 |
|
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:
- ADS93
-
M. Andrasiu, J. Dassow, A. Salomaa, G. Paun. Language-theoretic
problems arising from Richelieu cryptosystems. Theoretical Computer
Science 116, 1993.
- 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
- 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
14.04.99:
Geschichtlicher "Uberblick
[Beu87] S 7 ff,
Transpositionchiffre: Skytala, Substitutionschiffre:
Caesar, Vigenere,
Richelieu, Vernam,
Quanten-Kryptographie
[BBE92],
19.04.99:
RSA
[Beu87] S67 ff bzw. [Sti95]
S 114 ff:
Schl"usselerzeugung, Euklidscher Algorithmus,
Satz von Euler-Fermat,
21.04.99:
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
Pratt's Test: Pimzahlen in NP.
26.04.99: Algorithmus zum Pratt's Test,
Einwegfunktionen [Pap94] S 281, Komplexit"atsklassen
28.04.99: Starke und schwache Einwegfunktionen
[Gol] S 46 ff,
Einweg Hashfunktionen [Sti95] S 233 ff
oder [Gol] S 35 ff,
W"orterbuchangriff, Geburtstagsangriff,
03.05.99: Chaum-van Heijst-Pfitzmann Hashfunktion, diskreter Logartihmus,
Hashfunktion <=> Kryptosystem,
ElGamal Kryptosystem [Sti95] S 163,
Zero-Knowledge Beweissysteme,
Interaktive Beweissysteme [Sti95] S 387 ff
oder [Gol] S 143 ff
05.05.99: NP, BPP \subseteq IP(1), starker, schwacher interaktiver Beweis,
[Sti95] S 387 ff,
[Gol] S 153 ff,
Graph-Nicht-Isomorphismus in IP, Graph-3-colorability in IP
[Sti95] S 403 ff,
[Gol] S 180 ff,
polynomielle Hierarchie in P^{#P}, Permanente #P-vollst..
10.05.99: LFKN Protokoll zur Pr"ufung der Permanente
[Bab90],
Ein Kryptosystem basierend auf Propositionallogik [Kar89],
12.05.99: Kryptosysteme und NP-vollst"andigkeit
[EY80],
Merkle-Hellmann Knapsack System [Sti95] S 191,
17.05.99: Meet-in-the-middle Algorithmus, L^3 Gitter Basis Reduktion,
Knapsack mit geringer Dichte
[MOV90] S 118,
Shanks Algorithmus
[Sti95] S 165,
19.05.99:
Pohlig-Hellmann algorithmus
[Sti95] S 169,
McEliece System
[Sti95] S 194,
26.05.99:
Endliche Koerper und Elliptische Kurven
[Sti95] S 177,
31.05.99:
nichtverfolgbares elektronisches Geld
nichtverfolgbare elektronische Schecks [CFN88],
02.06.99, 07.06.99:
Signaturschemata [Sti95]
09.06.99:
Kartenspiel "ubers Netz, Bestimmung des "alteren ohne Altersangabe,
M"unzwurf per Telephon (Bit-commitment),
14.06.99:
Das Teilen von Geheimnissen [Sti95] S 327,
verifizierbares Teilen von Geheimnissen.[CGMA85]
16.06.99:
Die Verhinderung des Missbrauchs von Kryptosystemen
[Des88].
21.06.99,
23.06.99: Visuelle Kryptographie [NS94]
28.06.99: Schl"usselverteilung:
Blom's Schema, Diffie-Hellmann Schl"usselverteilung.
[Sti95] S 259
Schl"usselvereinbarung [Sti95] S 269
30.06.99,
05.07.99: Pseudozufallsgeneratoren [Sti95] S 361ff, 22, 39
07.07.99: DES [Sti95] S 79ff,
PGP [Sch96] S 664
IDEA [Sch96] S 370
Kryptologie und Komplexität interaktiv
1999-05-05 Klaus Reinhardt
(reinhard (AT) informatik.uni-tueb...)