| Dozent |
Klaus Reinhardt |
|
Sprechstunde |
Nach Vereinbarung, Raum 140, Sand 13, Tel. 77566 |
|
Zeit / Ort |
Mo 15:15-17, Mi 15:15-17 Morgenstelle N8 |
|
Umfang |
4h |
|
Begin |
23.04.2001 |
|
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.
- 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
23.04.01:
Geschichtlicher "Uberblick
[Beu87] S 7 ff,
Transpositionchiffre: Skytala, Substitutionschiffre:
Caesar, Vigenere, Affine Chiffre [Sti95] S 8,
Richelieu, Vernam,
Quanten-Kryptographie
[BBE92],
25.04.01:
RSA
[Beu87] S67 ff bzw. [Sti95]
S 114 ff:
Schl"usselerzeugung, Euklidscher Algorithmus,
Satz von Euler-Fermat,
30.04.01:
Elektronisches Geld mit RSA [Beu87] S99,
Primzahltests [Sti95] S 129 ff bzw.
[Kra86]:
Sieb des Eratosthenes, Wilson's Test, Lucas's Test,
02.05.01:
Monte Carlo primzahltests: Fermat-test, Eulersches Kriterium,
Jacobi symbol, Solovay-Strassen-test, Miller-Rabin-test
07.05.01:
Pratt's Test: Pimzahlen in NP.
09.05.01:
Faktorisierung: Pollard's rho. , p-1, bei bekanntem phi(n) oder bekanntem RSA-secret-key
[Sti95] S 138 ff bzw. [MOV90] S 87 ff
14.05.01:
Quadratisches Sieb, Rabin Kryptosystem.
16.05.01:
Einwegfunktionen [Pap94] S 281, Komplexit"atsklassen,
21.05.01: Starke und 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,
23.05.01:
Hashfunktion <=> Kryptosystem, diskreter Logartihmus,
Shanks Alggorithmus, Pohlig Hellmann Algorithmus,
ElGamal Kryptosystem [Sti95] S 163,
ElGamal Signaturschema [Sti95] S 206,
28.05.01:
Weitere Signaturschemata [Sti95]
30.05.01:
Endliche Koerper und Elliptische Kurven
[Sti95] S 177,
06.06.01:
Schl"usselverteilung:
Blom's Schema, Diffie-Hellmann Schl"usselverteilung, Kerberos.
[Sti95] S 259
11.06.01:
Schl"usselaustausch [Sti95] S 269,
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,
13.06.01:
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..
LFKN Protokoll zur Pr"ufung der Permanente
[Bab90],
18.06.01:
IP=PSPACE
20.06.01: Kryptosysteme und NP-vollst"andigkeit
[EY80],
Merkle-Hellmann Knapsack System [Sti95] S 191,
25.06.01:
Meet-in-the-middle Algorithmus, L^3 Gitter Basis Reduktion,
Knapsack mit geringer Dichte [MOV90] S 118,
27.06.01:
Gibt es NP-harte Public-Key Kryptosysteme? [EY80],
McEliece System
[Sti95] S 194,
02.07.01:
nichtverfolgbares elektronisches Geld
nichtverfolgbare elektronische Schecks [CFN88],
04.07.01:
Kartenspiel "ubers Netz, Bestimmung des "alteren ohne Altersangabe,
M"unzwurf per Telephon (Bit-commitment),
09.07.01:
Das Teilen von Geheimnissen [Sti95] S 327,
verifizierbares Teilen von Geheimnissen.[CGMA85]
11.07.01:
Visuelle Kryptographie [NS94]
Kryptologie und Komplexität interaktiv
2001-01-029 Klaus Reinhardt
(reinhard@informatik.uni-tuebingen.de)