Seminar im Sommersemester 1996:

Kryptographie und kryptographische Protokolle

Wolfgang K. Seiler

Ort und Zeit: Dienstag, 15.30-17.00, C225

INHALT: Die Kryptographie, ursprünglich entstanden zur Sicherung von militärischer und diplomatischer Kommunikation, erfüllt inzwischen längst zahlreiche weitere Funktionen: Außer der Sicherung von privater Kommunikation dient sie zum Beweis der Authentizität von Nachrichten, zum Beweis der Urheberschaft (für beide Seiten), zur Sicherung von geistigem Eigentum, zum Identitätsbeweis gegenüber Geldausgabeautomaten und in Personenkontrollsystemen zur Überwachung der Zugangsberechtigung und vieles andere mehr; diskutiert wird unter anderem sogar schon ein elektronisches Bargeld, das (im Gegensatz zu gängigen elektronischen Zahlungssystemen) alle Anonymitätseigenschaften von Geldscheinen hat.

Grundlage der meisten Verfahren sind mathematische Sätze und (oft schwer bis gar nicht beweisbare) Erfahrungstatsachen über die Schwierigkeit spezifischer mathematischer Probleme; auch die Kryptoanalyse, mit der ein interessierter Gegner versucht, das Verfahren zu brechen, beruht praktisch ausschließlich auf Mathematik.

Ziel des Seminars ist es, die wichtigsten derzeit gebräuchlichen kryptographischen Verfahren sowie die Ansätze zu ihrer Kryptoanalyse nebst der dazu notwendigen Mathematik vorzustellen; in den letzten Vorträgen sollen auch bislang nur diskutierte mögliche zukünftige Anwendungen behandelt werden.

Die verwendete Mathematik besteht im wesentlichen aus elementarer Zahlentheorie, etwas Algebra und elementarer Statistik. An Vorkenntnissen reichen zum Zuhören stets die Anfängervorlesungen; falls der Vortragende weitergehende Kenntnisse braucht, ist dies bei den Vortragsbeschreibungen angegeben.

Themenübersicht

(Die Datumsangaben können sich noch ändern; Vorträge ohne Datumsangabe finden voraussichtlich nicht statt.)

W.K. Seiler: Einführung (16. April)
O. Akbal: Klassische Verfahren und ihre Kryptoanalyse (23. April)
D. Fesser:Rotormaschinen und ihre Kryptoanalyse (30. April)
T. Baumgärtel: Der Data Encryption Standard (DES) (7. Mai)
Differentielle Kryptoanalyse des DES und Design der S-Boxen
R. Heller: Das IDEA-Verfahren (14. Mai)
Lineare Kryptoanalyse
J.M. Hans: Asymmetrische Kryptosysteme und ihre Anwendung (21. Mai)
Faktorisierungsalgorithmen (28. Mai)
T. Pepper: Kryptographisch sichere Hashverfahren und ihre Anwendungen (4. Juni)
M.A. Maguire: Interaktive Beweissysteme (11. Juni)
C. Rauscher: Elektronisches Bargeld (18. Juni)
J. Kohlhepp: Anonyme Kommunikation in Rechnernetzen (25. Juni)
M. Bonnet: Quantenkryptographie (2. Juli)
W.K. Seiler: Ausblick: DNS-Computer, Quantencomputer und ihre Auswirkungen auf die Kryptographie (9. Juli)

Vortragsbeschreibungen

W.K. Seiler: Einführung
Begriff des Kryptosystems, Formen der Attacke, Anwendungen der Kryptographie, Sicherheitsfragen; Vorstellung und Verteilung der Vortragsthemen
Zurück zur Themenübersicht
O. Akbal: Klassische Verfahren und ihre Kryptoanalyse
Hier geht es um Verfahren, die zwar in der ernstzunehmenden Kryptographie schon lange keine Rolle mehr spielen, die jedoch (kaum variiert) immer noch den Großteil der Verschlüsselungs- und Passwortverfahren für PCs ausmachen. Um zu zeigen, daß kombinatorische Vielfalt allein kein Schutz ist, sollte für monoalphabetische Substitutionen und für Vigenèrechiffren vorgeführt werden, wie sich diese mit minimalem Aufwand brechen lassen durch Betrachtung von Digrammhäufigkeiten bzw. den Friedmanschen Kappatest. Als Grundlage eignet sich beispielsweise
D. Kahn: The Codebreakers, Macmillan, 1967 (UB: AE3920),
wo die Entschlüsselung monoalphabetischer Substitutionen auf S. 99-105 behandelt wird, Vigenèrechiffren werden aus S. 148-150 diskutiert und ihre Kryptoanalyse mit Kappatest und ähnlichen Verfahren auf S. 377-384. Grundlage aller kryptoanalytischer Ansätze sind hier die Inhomogenitäten der Buchstabenverteilungen natürlicher Sprachen; zur Illustration kann man einige Diagramme und Tabelle zeigen aus den Anhängen der Bücher
L. Sacco: Manuel de Cryptographie, Paris 1951
und
F. Pratt: Secret and Urgent, Indianapolis und New York, 1939 .

Zurück zur Themenübersicht
Rotormaschinen und ihre Kryptoanalyse
Diese Maschinen hatten Ihre Hochzeit im zweiten Weltkrieg und den Jahren danach; noch heute funktioniert das UNIX crypt Kommando nach demselben Prinzip. Man zeige, etwa anhand der Darstellung im dritten Kapitel von
Cipher A. Deavours, L. Kruh: Machine Cryptography and Modern Cryptanalysis, Artech House, 1985 ,
wie die deutsche ENIGMA-Maschine funktionierte und wie sie im zweiten Weltkrieg kryptoanalysiert wurde.
Zurück zur Themenübersicht
Der Data Encryption Standard (DES)
Dies ist das derzeit am häufigsten benutzte Verfahren für seriöse Kryptographie; unter anderem wird es auch bei der Benutzung von EC-Karten an Geldautomaten verwendet sowie (in modifizierter Form) zur Sicherung der Passwörter in UNIX-Systemen. Man erkläre die Struktur des DES-Algorithmus beispielsweise anhand von Abschnitt 6.7 des Buchs
A.G. Konheim: Cryptography: A Primer, Wiley, 1981
und spreche auch kurz die Diskussion des Algorithmus in den folgenden Abschnitten an, insbesondere 6.8, 6.10, je nach Statistikkenntnissen des Vortragenden eventuell auch (ohne Einzelheiten) 6.16-6.18, auf jeden Fall 6.19+20 und (als ersten Versuch einer Kryptoanalyse) den Hellmanschen time-memory trade-off. Außerdem sollten die verschiedenen Operationsmodi in 6.24-6.26 diskutiert werden; eine kurze Diskussion solcher Modi mit den inzwischen standardisierten Bezeichnungen findet man besser auch in
G. Brassard: Modern Cryptology, Lecture Notes in Computer Science 325, 1988, Abschnitt 3.5

Zurück zur Themenübersicht
Differentielle Kryptoanalyse des DES und Design der S-Boxen
Die Sicherheit des DES beruht wesentlich auf den acht S-Boxen, die jeweils eine nichtlineare Abbildung eines 6-bit-Worts auf ein 4-bit-Wort realisieren. Die erst etwa 1990 in der offenen Literatur erschienene differentielle Kryptoanalyse untersucht, welchen Effekt S-Boxen auf die Differenz zweier Nachrichten haben; mehrere DES-ähnliche Verfahren konnten damit gebrochen werden, nicht jedoch DES selbst. Wie inzwischen bekannt wurde, kannten die Designer der DES S-Boxen dieses Verfahren und entwarfen den Algorithmus so, daß er ihm maximalen Widerstand entgegensetzt. Man referiere dies anhand von
D. Coppersmith: The Data Encryption Standard (DES) and its strength against attacks, IBM J. Res. Develop. 38 (1994), 243-250 (UB: ZL 2249) .
Hintergrundliteratur zur differentiellen Kryptoanalyse ist das Buch
E. Biham, A. Shamir: Differential cryptanalysis of the data encryption standard, Springer, 1993
oder die einschlägigen Vortöffentlichungen dieser beiden Autoren, etwa
E. Biham, A. Shamir: Differential Cryptanalysis of the Full 16-Round DES, in: Crypto'92, Lecture Notes in Computer Science 740, S. 487-496 .

Zurück zur Themenübersicht
Das IDEA-Verfahren
Wegen seiner kurzen Schlüssellänge von nur 56 bit war der DES schon zur Zeit seiner Einführung in den siebziger Jahren nicht für Hochsicherheitsanwendungen zugelassen; inzwischen kann man davon ausgehen, daß ihn zumindest Regierungsorganisationen routinemäßig entschlüsseln können. Ein im Aufbau ähnlicher Kandidat für ein Nachfolgeverfahren ist IDEA (International Data Encryption Algorithm), ein Verfahren, das anstelle der eher kombinatorischen Komponenten des DES Operationen in drei verschiedenen Gruppen der Ordnung 2^16 benutzt und das ebenfalls, wie DES, speziell gegen differentielle Kryptoanalyse gesichert wurde. Das Verfahren und seine Designprinzipen sollen erklärt werden anhand von
X. Lai: On the Design and Security of Block Ciphers, ETH Series in Information Processing 1, 1992, 1995 ,
wobei der Schwerpunkt der Darstellung auf den Abschnitten 3.1-3, 3.4.2, 4.4.3 und 5.3 liegen sollte.
Zurück zur Themenübersicht
Lineare Kryptoanalyse
Dieses 1992 eingeführte Verfahren versucht, lineare Beziehungen zwischen Ein- und Ausgabebits einer S-Box und den Schlüsselbit zu finden. Solche Beziehungen existieren zwar bei einem guten Verfahren nicht, aber zum Angriff gegen das Verfahren genügt bereits, daß es solche Beziehungen gibt, die mit einer von 1/2 verschiedenen Wahrscheinlichkeit gelten. Bei hinreichend viel Material lassen sich dann mit hoher Wahrscheinlichkeit hinreichend viele Schlüsselbits finden um das Verfahren zu brechen.
M. Matsui: Linear Cryptanalysis Method for DES Cipher, in: Eurocrypt '93, Lecture Notes in Computer Science 765, 386-396
(Um die Beweise der Lemmata ergänzen zu können, sollte der Vortragende über Grundkenntnisse der Stochastik verfügen; insbesondere sollte er die Binomialverteilung und ihre Approximation durch eine Normalverteilung kennen.) Man erwähne auch kurz das Ergebnis von
M. Matsui: The First Experimental Cryptanalysis of the Data Encryption Standard, in: Crypto '94, Lecture Notes in Computer Science 839, 1-11
und die Diskussion der Anwendbarbeit auf IDEA in Abschnitt 7.2 von
C. Harpes, G.G. Kramer, J.L. Massey: A Generalization of Linear Cryptanalysis and the Applicability of Matsui's Piling-Up Lemma, in: Eurocrypt '95, Lecture Notes in Computer Science 921, 24-38 .
Falls Zeit bleibt, kann man eventuell noch kurz auf die Versuche eingehen, differentielle und lineare Kryptoanalyse unter gemeinsamen statistischen Gesichtspunkten zu betrachten und dadurch zu verallgemeinern; siehe etwa
S. Vaudenay: An Experiment on DES - Statistical Cryptanalysis, 3rd ACM Conferences on Computer Security, 1995 .

Zurück zur Themenübersicht
Asymmetrische Kryptosysteme und ihre Anwendung
Bei asymetrischen Kryptosystemen werden verschiedene Schlüssel zur Verschlüsselung und zur Entschlüsselung benutzt, wobei der zur Verschlüsselung bekannt gemacht werden kann ohne den zur Entschlüsselung zu kompromittieren. Durch Vertauschung der Rolle der beiden Schlüssel lassen sich auf diese Weise auch elektronische Unterschriften realisieren und verschiedene andere Protokolle, beispielsweise das Werfen einer Münze durch zwei Personen an verschiedenen Orten. Man erkläre die entsprechenden Verfahren, insbesondere RSA und DSS, anhand von Kapitel 4, Abschnitt 1-3 von
N. Koblitz: A Course in Number Theory and Cryptography, Graduate Texts in Mathematics 114, 1987, 2. Auflage 1994 .
(DSS ist in der ersten Auflage des Buchs noch nicht enthalten; falls man diese benutzt, kann man dafür auch das Originaldokument
Federal Information Standard Publication 186 (1994 May 16): Specification for the Digital Signature Standard DSS, nachgedruckt beispielsweise in L.J. Hoffmann [Hrsg.]: Building in Big Brother: The cryptographic Policy Debate, Springer 1994, S. 84-86
benutzten.)
Da die gängigen asymmetrischen Kryptoverfahren deutlich langsamer sind als die symmetrischen, werden sie nur selten zur Übermittlung längerer Nachrichten benutzt; meist wird nur ein Schlüssel mit einem asymmetrischen Verfahren übertragen und danach die mit einem symmetrischen Verfahren und diesem Schlüssel kodierte Nachricht. Als Beispiel eines solchen hybriden Verfahren erläutere man das PGP-Programm, das auf RSA und IDEA beruht; siehe etwa
P.R. Zimmermann: The Official PGP User's Guide, MIT Press, 1995
oder
S. Garfinkel: PGP: Pretty Good Privacy, O'Reilly, 1995 .

Zurück zur Themenübersicht
Faktorisierungsalgorithmen
Da die Sicherheit aller auf RSA beruhender Verfahren unmittelbar von der Schwierigkeit des Faktorisierens abhängt, ist es von entscheidender Bedeutung, daß man mit den neuesten Entwicklungen auf diesem Gebiet vertraut ist. Man referiere insbesondere die Pollardschen Methoden, die elliptische Kurvenmethode und das quadratische Sieb und weise auf neuere Entwicklungen (Zahlkörpersieb, Funktionenkörpersieb) hin. Literatur:
N. Koblitz: A Course in Number Theory and Cryptography, Graduate Texts in Mathematics 114, zweite Auflage, 1994 ,
Kapitel V, Abschnitte 2, 3, 5, und Kapitel VI, 4, oder
H. Riesel: Prime numbers and computer methods for factorization, zweite Auflage, Birkhäuser, 1994 ,
Kapitel 6, Abschnitte über p-1, ECM, QS, MPQS mit Ausblicken auf NFS und GNFS.
Für einen aktuellen Überblick eignet sich gut
P. Montgomery: A Survey of Modern Integer Factorization Algorithms, CWI quarterly, 1995 ,
Abschnitte 6 bis 8.
Der Vortragende sollte die Vorlesung Algebra I gehört haben.
Zurück zur Themenübersicht
Kryptographisch sichere Hashverfahren und ihre Anwendungen
Asymmetrische Kryptoverfahren liefern zwar im Prinzip die Möglichkeit, beliebige Dokumente elektronisch zu unterschreiben, der Aufwand ist jedoch viel zu hoch. Stattdessen wird durch ein Hashverfahren eine kurze Nachricht aus dem Dokument extrahiert und nur diese wird unterschrieben. Dieses Verfahren ist natürlich nur anwendbar, wenn es nicht mit vertretbarem Aufwand möglich ist, zwei Dokumente zu erzeugen, aus denen dieselbe Nachricht extrahiert wird. Man erläutere entsprechende Verfahren anhand des 14. Kapitels von
B. Schneier: Applied Cryptography, Wiley 1994, 1995
mit Schwerpunkt auf den Abschnitten 14.1 und 14.7. Durch Kombination mit einem Passwort kann auch ohne elektronische Unterschrift zumindest die Authentizität des Dokuments gewährleistet werden; siehe 14.14. Ebenfalls erwähnt werden sollte die Anwendung von Hashfunktionen zur Erzeugung von Zeitstempeln; siehe dazu ibid. Abschnitt 3.8.
Zurück zur Themenübersicht
Interaktive Beweissysteme
Bei klassischen Identifikationsverfahren, wie sie etwa in einer EC-Karte verwirklicht sind, hat der Überprüfer nach Akzeptanz des Überprüften dessen gesamte Identifikationsinformations und kann diesen daher inpersonifizieren. Smart cards ermöglichen interaktive Beweisverfahren, bei denen der Überprüfer nichts lernt, was über die Identität des Überprüften hinausgeht. Man referiere entsprechende Verfahren anhand von
N. Koblitz: A Course in Number Theory and Cryptography, Graduate Texts in Mathematics 114, zweite Auflage, 1994 ,
Kapitel IV, Abschnitt 5. Zumindest erwähnt werden sollte auch Shamirs Satz, wonach es für jedes mathematische Verfahren, dessen Speicherbedarf höchstens polynomial mit der Länge der Eingabedaten steigt, ein interaktives Beweisverfahren gibt; siehe dazu Abschnitt 8 von
S. Goldwasser: Interactive proofs and applications, Proc. Int. Congr. Math., Kyoto 1990, Vol. II, 1521-1535 .

Zurück zur Themenübersicht
Elektronisches Bargeld
Die meisten heute üblichen elektronischen Zahlungssysteme haben den Nachteil, daß bei regelmäßigem Gebrauch des System sich die kontenführende Bank eine Vielzahl von Informationen über ihren Kunden verschaffen kann, aus denen sie im Extremfall ein ziemlich vollständiges Persönlichkeitsprofil erstellen und verbreiten kann. Als Alternative dazu wurde elektronisches Bargeld eingeführt, das zwar auch von einer Bank garantiert ist, das die Bank aber nicht einem individuellen Kunden zuordnen kann. Einen Überblick findet man in
D. Chaum: Privacy Protected Payments: Unconditional Payer and/or Payee Untraceability, in: smart cards 2000: the future of IC cards, North Holland, 1989, S. 69-93 .
Eher populärwissenschaftlich und mit vielen Bildern versehen ist die Darstellung in
D. Chaum: Security without Identification: Card Computers to make Big Brother Obsolete, Comm. ACM 28 (1985), 1030-1044; erweiterte deutsche Fassung in Informatik-Spektrum 10 (1987), 262-277.
Zusätzliche Probleme treten auf, wenn elektronisches Geld nach der Zahlung nicht zurüch zur Bank geht, sondern von einer Person an die nächste weitergegeben wird; man gehe dazu (relativ kurz) ein auf
D. Chaum, T.P. Pedersen: Transferred Cash Grows in Size, Eurocrypt'92, Lecture Notes in Computer Science 658, 390-407 .
Falls der Vortragende (aber höchstens ganz kurz) auf bestehende Systeme eingehen möchte, findet er Informationen in den beiden Büchern
P. Wayner: Digital Cash, Academic Press, 1995
und
P. Loshin: Electronic Commerce, Charles River Media, 1995
(falls er diese beiden Bücher findet) oder in den Informationen von Banken, die auf echtem Geld basierendes e-cash anbieten, etwa die Mark Twain Banks in St. Louis oder das finnischen EUnets.
Zurück zur Themenübersicht
Anonyme Kommunikation in Rechnernetzen
Selbst wenn ein garantiert unentschlüsselbares Kryptosystem benutzt wird, kann ein Gegner immer noch feststellen, wer mit wem kommuniziert, und oft gibt bereits diese sogenannte Verkehrsanalyse wertvolle Hinweise über Beziehungen, die man eigentlich vor dem Gegner verheimlichen möchte. Daher gibt es Verfahren, um selbst die Tatsache eines Nachrichtenaustauschs zwischen zwei Partnern zu verschleiern. Im Vortrag sollen die wesentlichen Ergebnisse aus
A. Steinacker: Anonyme Kommunikation in Netzen, BI, 1992
referiert werden, insbesondere Kapitel 2 und 3. Auf die zahlreichen Estelle-Spezifikationen soll im Vortrag natürlich nicht eingegangen werden.
Zurück zur Themenübersicht
Quantenkryptographie
Alle bislang behandelten Kryptoverfahren gehen davon aus, daß ein Gegner die Möglichkeit hat, die übermittelte Nachricht unbemerkt zu lesen. Die seit wenigen Jahren zumindest für Entfernungen bis etwa 30km experimentell realisierte Quantenkryptographie benutzt die Tatsache, daß für ein einzelnes Photon andere Regeln gelten als für einen Lichtstrahl, um eine Verbindung aufzubauen, die nicht unbemerkt abgehört werden kann. Man diskutiere den Entwicklungsstand anhand von
S.J.D. Phoenix, P.D. Townsend: Quantum Cryptography: Protecting our Future Networks with Quantum Mechanics, in: Cryptography and Coding, Lecture Notes in Computer Science 1025, 112-131;
für praktische Verfahren um vermutete Abhörversuche wertlos zu machen, behandle man die entsprechenden Abschnitte aus
C.H. Bennett, F. Bessette, G. Brassard, L. Salvail, J. Smolin: Experimental Quantum Cryptography, Journal of Cryptology 5 (1992), 3-28

Zurück zur Themenübersicht
Ausblick: DNS-Computer, Quantencomputer und ihre Auswirkungen auf die Kryptographie
Bei chemischen Prozessen, die auf makroskopischer Ebene ablaufen, sind typischerweise etwa 10^23 einzelne Moleküle beteiligt; vor etwa zwei Jahren zeigte L. Adleman, daß man im Falle von DNS-Strängen diese massive Parallelität ausnutzen kann, um beispielsweise einen (recht einfachen) Fall des (NP-vollständigen) travelling salesman Problems zu lösen:
L. Adleman: Molecular Computation of Solutions to Combinatorial Problems, Science 266, 11. Nov. 1994, S. 1021-1024 .
Mögliche Auswirkungen auf die Kryptographie werden diskutiert bei
B. Cypra: Computer Science Discovers DNA, in: What's Happening in the Mathematical Sciences 3 (1995-1996), 27-37
Derzeit noch reine Theorie sind die bereits von Feynman vorgeschlagenen Quantencomputer, die eine massive Parallelität durch Überlagerung von Zuständen eines einzigen Teilchens realisieren sollen; ein Algorithmus, mit dem ein (bislang noch hypothetischer) Quantencomputer Zahlen faktorisieren und damit RSA brechen könnte, findet sich in
P.W. Shor: Algorithms for Quantum Computation: Discrete Logarithms and Factoring, in: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press 1994, 124-134
Der Vortragende sollte mit dem grundlegenden Aufbau der Desoxyribonukleinsäure und den Grundzügen der Quantentheorie vertraut sein und auch diese kurz darstellen. Mathematisch wird etwas elementare Zahlentheorie und Fourieranalyse benötigt.
Zurück zur Themenübersicht