Kryptographie

Vorlesung im Wintersemester 2006 an der Technischen Universität Berlin.
Auf dieser Seite werden im Lauf der VL relevante Informationen zur Verfügung gestellt.

Dozenten: Prof. Dr. F. Heß, Dipl.-Math. M. Wagner

Übersicht:

Zeiten und Adressen

Vorlesung:	Di 10-12 im MA650 und Do 12-14 im MA144
Übung:	Fr 8-10 im MA851

Sprechzeiten: F. Heß nach der Vorlesung und nach Vereinbarung, M. Wagner Do 10-12 und nach Vereinbarung.

F. Heß	MA804	hess at math.tu-berlin.de 314-25062
M. Wagner	MA812	wagner at math.tu-berlin.de 314-23761
Teilnehmer der VL Kryptographie		( Email Adresse wegen Spam hier nicht mehr aufgeführt )

Inhalt

Was ist Kryptographie? Die beiden Hauptaufgaben der Kryptographie sind die Verschlüsselung und die digitale Signatur. Bei der Verschlüsselung geht es darum, Daten so zu manipulieren, daß man den ursprünglichen Sinn nur mit Hilfe eines geheimen Schlüssels wieder rekonstruieren kann. Bei der digitalen Signatur geht es darum, die Eigenschaften der herkömmlichen handschriftlichen Unterschrift (und weitere Eigenschaften) in die digitale Welt zu übertragen. Zur Lösung dieser beiden Hauptaufgaben werden mathematische Verfahren, insbesondere aus Algebra und Zahlentheorie, eingesetzt.

Die VL gibt im ersten Teil einen breiten Überblick über die Kryptographie. Behandelt werden unter anderem Verfahren der symmetrischen Kryptographie (Blockchiffren, Stromchiffren, Hashfunktionen, Message Authentication Codes) und der asymetrischen Kryptographie (RSA, DL-basierte Systeme, endliche Körper und elliptische Kurven, Verschlüsselungs- und Signaturverfahren, Angriffsmodelle).

Im zweiten Teil gehen wir je nach Teilnehmerinteresse vertiefend auf gitterbasierte Techniken oder kurvenbasierte Kryptographie ein.

Vorlesungskalendar und Skript

17.10. Organisatorisches. Zielsetzungen der Kryptographie, fachliche Unterteilung, Terminologie und Konzepte der Verschlüsselung. Beispiel: Affin-lineare Blockchiffren. Angriffsmodelle. (ps,pdf)
19.10. Terminologie und Konzepte der digitalen Signatur. Angriffsmodelle. Vergleich Public-Key Kryptographie und Secret-Key Kryptographie. Protokolle. (ps,pdf) Blockchiffren.
24.10. Grundzüge der Wahrscheinlichkeitstheorie (bei Bedarf (ps,pdf)). Ideale Blockchiffren, One Time Pad, Satz von Shannon. (ps,pdf)
26.10. Satz von Shannon zweiter Teil, weitere Bemerkungen. Betriebsarten von Blockchiffren. Meet-in-the-middle Angriff, Mehrfachverschlüsselung. (ps,pdf)
31.10. Design von Blockchiffren. Feistelnetzwerke, Subsitutionspermutationsnetzwerke. DES. (ps,pdf)
2.11. Mathematische Grundlagen zu endlichen Körpern und Polynomringen. AES. Angriffe auf Blockchiffren im Überblick. (ps,pdf)
7.11. Stromchiffren mit Beispielen (LSFR, lineare Kongruenzgeneratoren, Pseudozufallszahlen aus Blockchiffren; RC4). Integrität und Authentizität. Eigenschaften von Hashfunktionen. Zufallsorakelmodell. (ps,pdf)
9.11. Geburtstagparadoxon, Angriffe auf Hashfunktionen im Zufallsorakelmodell. Floyd's Algorithmus. Davies-Meyer Kompressionsfunktion. Merkle-Damgard Konstruktion für Hashfunktionen. Reduktionen im Standardmodell. Hashfunktionen in der Praxis. Beispiel SHA-1. (ps,pdf)
14.11. Message Authentication Codes. Sicherheitsaspekte und Konstruktionen: CBC-MAC, geschachtelte MACs, HMAC. Sicherer Kanal, Passphrasen, Pseudozufallsgeneratoren mittels Hashfunktionen. (ps,pdf)
16.11. Zusammenfassung der bisherigen Themen. Eine prinzipielle Methode der Verschlüsselung mit öffentlichem Schlüssel. (ps,pdf) Mathematische Grundlagen der Kryptographie: Gruppen. (ps,pdf, mit kleinen Änderungen vom 16.11.)
21.11. Mathematische Grundlagen der Kryptographie: Ringe. (ps,pdf)
23.11. Mathematische Grundlagen der Kryptographie: Chinesischer Restsatz. (ps,pdf) Einführung in das RSA Kryptosystem (ps,pdf)
28.11. RSA und RSA Sicherheit (ps,pdf)
30.11. RSA Sicherheit (ps,pdf)
5.12. RSA Paddingverfahren, IND-CCA2 Sicherheit, OAEP. (ps,pdf)
7.12. Miller-Rabin Test. (ps,pdf) Überarbeitete Version vom 11.12. (ps,pdf)
12.12. Quadratisches Sieb. (ps,pdf)
14.12. Quadratisches Sieb, Komplexitätsanalyse. Bemerkungen zum Zahlkörpersieb. Gruppenbasierte Kryptographie. ElGamal Verfahren, Diffie-Hellman Berechnungs- und Entscheidungsproblem. Beziehungen zwischen diesen Problemen. Reduktion der Sicherheit bezüglich OW-CPA und IND-CPA auf das CDH und DDH. (ps,pdf)
19.12. Gruppenbasierte Kryptographie. Angriffe auf Textbook ElGamal gegen Non-Malleability (auch Plaintext awareness) und gegen IND mit CCA2-Angriffen. Fujisaki-Okamoto Transformation. Aussagen zur Bitsicherheit des DLP. Untere Schranke für das DDH in Black-Box Gruppen. Shank's Baby-Step-Giant-Step Algorithmus. Pollard Rho Algorithmus. (ps,pdf)
21.12. Gruppenbasierte Kryptographie. Pohlig-Hellman Algorithmus. Index-Calculus in endlichen Körpern (L[1/2] Verfahren erläutert). Elliptische Kurven über endlichen Körpern. Satz von Hasse-Weil. Gruppengesetz. Übersicht über grundlegende Fragestellungen. (ps,pdf, geändert 09.01.2007)
9.1. Elliptische Kurven über endlichen Körpern. Konstruktion mittels Punkte zählen und komplexer Multiplikation. Angriffe auf das DLP in speziellen Klassen von elliptischen Kurven. Techniken zum effizienten Rechnen mit elliptischen Kurven. (ps,pdf, geändert 09.01.2007)
11.1. Digitale Signaturen. Mit Einwegfunktion mit Falltür (RSA Signaturen, Full Domain Hash und PSS), mit allgemeinen Einwegfunktionen (Lamport One Time Signatures und Merkle Authentifizierungsbaum), mit Einweghomomorphismen (Schnorr Signaturen und Skizze Sicherheitsbeweis im Zufallsorakelmodell, DSA). Blinde Signaturen und Undeniable Signatures. (ps,pdf)
16.1. Diffie-Hellman Schlüsselaustausch, Key Management und Establishment, MQV Protokolle. (ps,pdf)
18.1. Standards. Identifikation, Paßwörter, Einmal-Paßwörter, Challenge-Response Identifikation. Salzen und Strecken. Interaktive Beweissysteme, Zero Knowledge Beweise, Commitment Schemes, weitere Protokolle. (ps,pdf)
23.1. Matrizen über Ringe und Hauptidealringe, Moduln über Hauptidealringen (ps,pdf)
25.1. Gitter und LLL. Grundlegende Definitionen, Beispiele, Diskretheit. (ps,pdf. 13.2. Geringfügige Aktualisierung im Beweis von Satz 35)
30.1. Alternative Definitionen, Grammatrizen, Isometrien. Auszählalgorithmus für nächste und kürzeste Vektoren. Satz von Blichfeldt und Minkowskischer Gitterpunktsatz.
1.2. Schranken für kürzeste Vektoren. Hermitekonstanten. Minkowskische Minima. Obere und untere Schranken für die Minkowskischen Minima.
6.2. Längenreduktion, Paarreduktion, Gaußreduktion.
8.2. Eigenschaften LLL-reduzierter Basen, LLL-Algorithmus.
13.2. Laufzeit des LLL-Algorithmus
15.2. Weitere Eigenschaften des LLL-Algorithmus, Anwendungen. Coppersmith und RSA mit kleinem Exponenten (ps,pdf), rationale Rekonstruktion, NTRU und weiteres.

Übungsblätter, Programme und weitere Unterlagen

Unterlagen zur Vorlesung und zur Übung: Einleitung in die Kryptographie (ps,pdf),
Kurze Einführung in KASH3 (ps,pdf),
KASH3-Beispiele zum affin-linearen Chiffre (Datei1.k)
Ver- und Entschlüsselung für den Meet-in-the-middle Angriff (MITM.k)
KASH3-Vorgaben fü AES (AES.k ) und DES(DES.k)
DES-Beispiel: (des.htm ) DES-Übersicht allgemein (pdf ,ps) und über die DES-Boxen(pdf,ps)
Die Datei AliceMail.k für den Geburtstagsangriff (AliceMail.k )

Übungsblätter zur Vorlesung: 1. Blatt (Abgabe: 27.10.06) (ps,pdf) 2. Blatt (Abgabe: 03.11.06) (ps,pdf) 3. Blatt (Abgabe: 10.11.06) (ps,pdf) 4. Blatt (Abgabe: 17.11.06) (ps,pdf) 5. Blatt (Abgabe: 24.11.06) (ps,pdf) 6. Blatt (Abgabe: 01.12.06) (ps,pdf) 7. Blatt (Abgabe: 08.12.06) (ps,pdf) 8. Blatt (Abgabe: 15.12.06) (ps,pdf) 9. Blatt (Abgabe: 22.12.06) (ps,pdf) 10. Blatt (Abgabe: 12.01.07) (ps,pdf) 11. Blatt (Abgabe: 19.01.07) (ps,pdf) 12. Blatt (Abgabe: 26.01.07) (ps,pdf) 13. Blatt (Abgabe: 02.02.07) (ps,pdf) 14. Blatt (Abgabe: 16.02.07) (ps,pdf)

Scheinmodalitäten

Gruppenarbeit in Zweier-Gruppen. Scheinkriterium: 60% der erreichbaren Punkte in jeder Semesterhälfte. Die Abgabe der praktischen Aufgaben hat am selben Tag zu erfolgen wie die Übungsaufgaben. Ist ein Kash-Programm gefragt, so wird ein lauffähiges Kash-Programm verlangt, das als Attachment per Mail an wagner at math.tu-berlin.de geschickt wird.

Für Informatiker, welche die VL als Wahlfach hören wollen, setzt sich die prüfungsrelevante Studienleistung aus den erreichten Punkten der wöchentlichen Übungsaufgaben und einer mündlichen Prüfung am Ende der VL zusammen.

ERASMUS Studenten beachten bitte, daß die oben genannten Scheinkriterien dem Bestehen der Vorlesung mit Note "ausreichend" gleichkommen. Weniger Punkte bzw. kein Schein bedeuten, daß die Vorlesung nicht bestanden wurde. Bitte auch zum Anfang der VL bei F. Heß oder M. Wagner melden!

Weitere Informationen

Es gibt sehr viele und von der Stoffauswahl und -darstellung sehr unterschiedliche Bücher über Kryptographie. Nachfolgend eine kurze Liste, die ersten vier sind für die Vorlesung am besten geeignet. Darüberhinaus gibt es ebenfalls sehr viel Informationen online im Internet. Am besten passende Suchbegriffe in Google eingeben und schauen, was herauskommt.

Douglas Stinson, Cryptography, Chapman and Hall. Klassisches Lehrbuch.

Nigel Smart, Cryptography. An Introduction., McGraw-Hill Education. Gutes Gemisch zwischen Anwendung und Mathematik.

Johannes Buchmann, Einführung in die Kryptographie, Springer. Schön und anschaulich erklärt, aber nicht so umfassend wie die anderen.

Hans Delfs and Helmut Knebl, Introduction to Cryptography, Springer. Theoretische Konzepte und Anwendungen.

Alfred Menezes, Paul van Oorschot and Scott Vanstone, Handbook of Applied Cryptography., CRC Press. Eine umfangreiche Enzyklopädie. Umsonst zu haben!

Bruce Schneier, Applied Cryptography, John Wiley and Sons. Ebenfalls enzyklopädisch, eher text-basiert und entmathematisiert. Etwas veraltet.

Niels Ferguson und Bruce Schneier, Practical Cryptography, John Wiley and Sons. Neues Buch, wieder text-basiert und entmathematisiert, aber ganz aufschlußreich und gut lesbar.

Oded Goldreich, Foundations of Cryptography. Basic Tools., Cambridge University Press. Betonung auf den theoretischen Grundlagen und Konzepten.

Internetseite:

Wikipedia: WikiProjekt Kryptologie (freie Internet-Enzyklopädie).