Kryptologie und Komplexität im SS97
| Dozent |
K. Reinhardt |
| Sprechstunde |
Nach Vereinbarung, Raum 004, Sand 13, Tel. 78964 |
| Zeit |
Mi 1012 |
| Umfang |
2+0 |
| Beginn |
16.04.96 |
| Ort |
Morgenstelle B1 01 (im Keller des Pharma-baus) |
| Turnus |
2-jährig |
| Prüfungsfach |
Theoretische Informatik |
Beschreibung:
Behandelt werden sollen folgende Ziele und Methoden der Kryptologie:
Vertraulichkeit, Authentifikation, elektronische Unterschriften, simultaner
Austausch, öffentliche Schlüssel, RSA, Zahlentheorie, Primzahltests,
Pseudozufallsgeneratoren, Einwegfunktionen, Falltürfunktionen, elektronisches
Geld [CFN88], Zeroknowledge Beweissysteme, interaktive Beweissysteme
[Bab90], Kartenspiel übers Netz, Münzwurf per Telefon,
Bestimmung des Älteren ohne Altersangabe, das Teilen von Geheimnissen,
Verhinderung des Misbrauchs von Kryptosystemen [Des88]. Ferner
werden wir Zusammenhänge zu den Komplexitätsklassen NP, RP, UP
und BPP, zu Propositionallogik und zu formalsprachlichen Problemen
[ADS93]
betrachten.
Voraussetzungen:
Grundstudium Informatik oder Komplexitätstheorie I
Bemerkungen:
Ein
interaktives Kurzmanuskript
befindet sich im Aufbau - es wird um Mitwirkung gebeten.
Ein Skript ist zu finden bei
Miroslaw Kutylowski
oder bei
Dietmar W"atjen
oder bei
http://www.digicash.com/publish/bigbro.html
Literatur:
- 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.
- 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.
- 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
- Kra86
-
Evangelos Kranakis. Primality and cryptography.
Stuttgart, Teubner, 1986
- 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.
- Sti95
-
Douglas R. Stinson.
Cryptography - Theory and Practice.
CRC Press, 1995. ISBN 0-8493-8521-0.
Zu diesem Buch existiert auch eine
Fehlerliste .
Inhalt
16.04.97:
Geschichtlicher "Uberblick
[Beu87] S 7 ff,
Transpositionchiffre: Skytala, Substitutionschiffre:
Caesar, Vigenere,
Richelieu, Vernam,
Quanten-Kryptographie
[BBE92]
,
Affine Chiffre [Sti95] S 8
23.04.97:
RSA
[Beu87] S67 ff bzw. [Sti95]
S 114 ff:
Schl"usselerzeugung, Euklidscher Algorithmus,
Satz von Euler-Fermat,
30.04.97:
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.
07.05.97: Algorithmus zum Pratt's Test,
Einwegfunktionen [Pap94] S 281, Komplexit"atsklassen
14.05.97: Einweg Hashfunktionen [Sti95] S 233 ff
oder [Gol] S 35 ff,
W"orterbuchangriff, Geburtstagsangriff, Chaum-van Heijst-Pfitzmann
Hashfunktion.
Zero-Knowledge Beweissysteme,
Interaktive Beweissysteme [Sti95] S 387 ff
oder [Gol] S 143 ff
21.05.97: 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}.
28.05.97: LFKN Protokoll zur Pr"ufung der Permanente
[Bab90],
Ein Kryptosystem basierend auf Propositionallogik,
04.06.97: Rabin Kryptosystem [Sti95] S 145,
EIGamal Kryptosystem [Sti95] S 163,
Merkle-Hellmann Knapsack System [Sti95] S 191,
nichtverfolgbares elektronisches Geld [CFN88],
11.06.97: nichtverfolgbare elektronische Schecks [CFN88],
Kartenspiel "ubers Netz, Bestimmung des "alteren ohne Altersangabe,
18.06.97: Man-in-the-middle Angriff, Interlock Protokoll,
Schl"usselverteilung:
Blom's Schema, Diffie-Hellmann Schl"usselverteilung.
[Sti95] S 261
25.06.97: Schl"usselvereinbarung [Sti95] S 269
02.07.97: M"unzwurf per Telephon (Bit-commitment),
das Teilen von Geheimnissen [Sti95] S 327,
verifizierbares Teilen von Geheimnissen.[CGMA85]
02.07.97: Die Verhinderung des Missbrauchs von Kryptosystemen
[Des88].
Kryptologie und Komplexität interaktiv
1997-30-05 Klaus Reinhardt
(reinhard@informatik.uni-tuebingen.de)