Vorlesung im Wintersemester 1998/1999

Einführung in die Kryptologie

Wolfgang K. Seiler

Oft wird gesagt, es gebe zwei klar unterscheidbare Arten von Kryptographie:

• Verfahren, mit denen man seine kleine Schwester am Lesen seines Tagebuchs hindert
• Verfahren, mit denen man ernsthafte Kommunikation im Geschäftsleben oder auch das private Bankkonto sichert.

Aus diesem Grund beginnt die Vorlesung mit klassischer Kryptologie: Wir betrachten die statistischen Eigenschaften natürlicher Sprachen (oder auch von Dateien eines gegebenen Formats) und werden sehen, wie sich daraus sehr einfache Methoden zur (unbefugten) Entschlüsselung von Verfahren ableiten lassen, die wegen Ihrer Quadrillionen verschiedener möglicher Schlüssel von ihren Anhängern als unknackbar bezeichnet werden. Einige dieser Verfahren waren noch während des ersten Weltkriegs sicher, können mit heutigen Methoden aber problemlos gebrochen werden. Andererseits wird uns der statistische Ansatz aber auch auf beweisbar unknackbare Codes führen, die zumindest im Hochsicherheitsbereich noch heute meist Mittel der Wahl sind.

Nur kurz werden wir auf die Sicherheitsaspekte von Rotormaschinen eingehen; diese waren zwar während des zweiten Weltkriegs und teilweise noch in der Nachkriegszeit das allgemein übliche kryptographische Werkzeug; sie spielen heute aber nur noch im crypt(1)-Kommando von UNIX eine Rolle, für dessen Sicherheit denn auch jegliche Haftung abgelehnt wird. Die Kryptoanalyse der deutschen Enigma durch die Alliierten ist noch heute interessant als Beispiel, wie ein eigentlich guter Code durch inkompetente Handhabung unsicher werden kann.

Sobald es die ersten Computer gab, wurden diese zum Knacken von Codes eingesetzt; seit Computer weitverbreitet und vernetzt sind, werden Sie auch zur Verschlüsselung und (legitimen) Entschlüsselung eingesetzt. Damit entstanden auch neue kryptographische Verfahren, und um diese wird es hier in der Vorlesung hauptsächlich gehen.

Als erstes sind Verfahren wie der dem EC-Karten-System zugrundeliegende DES und verwandte Systeme zu betrachten und vor dem Hintergrund von Analyseverfahren wie der differentiellen und der linearen Kryptoanalyse zu bewerten; auch dabei geht es wieder um die bestmögliche Ausnutzung von (bei guten Verfahren minimalen) statistischen Schwankungen.

Das Jahr 1979 brachte eine neue Entwicklung der Kryptographie mit Verfahren, bei denen der Verschlüsselungsalgorithmus allgemein bekannt ist und nur der Entschlüsselungsalgorithmus geheimgehalten werden muß. Die Sicherheit solcher Verfahren ist natürlich nicht mehr absolut, da prinzipiell jede Nachricht durch Probieren entschlüsselt werden könnte. Die Sicherheit der Verfahren hängt daran, daß dies nicht mit realistischem Aufwand möglich ist: Leider gibt es aber kein Verfahren, bei dem man dies wirklich bewiesen hätte. Deshalb ist es für die Beurteilung der Sicherheit dieser Verfahren unabdingbar, daß man den Stand der möglichen Kryptoanalyseverfahren genau kennt; dies wird uns auf Probleme der Zahlentheorie führen und auf die Abschätzung der Leistungsfähigkeit von Supercomputern sowie von verteilten Berechnungen im Internet.

Zum Schluß der Vorlesung möchte ich dann noch kurz darauf eingehen, wie DNA-Computer, Quantencomputer und Quantenkryptography in Zukunft vielleicht die Kryptologie verändern könnten.

1. Klassische Kryptosysteme und informationstheoretische Ansätze zu ihrer Kryptoanalyse
2. Symmetrische Blockchiffren (DES und seine Operationsmodi, differentielle und lineare Kryptoanalyse, Ansatz von Davies, ...)
3. Das RSA-Verfahren (Asymmetrische Verfahren allgemein, RSA und seine Anwendungen auf elektronische Unterschriften, elektronisches Geld u.ä, Kryptoanalyse durch Faktorisierung und andere Ansätze)
4. Kryptographische Anwendungen diskreter Logarithmen (Diffie-Hellman Verfahren zum Schlüsselaustausch, ElGamal, elliptische Kurven, der baby step - giant step Algorithmus zur Berechnung diskreter Logarithmen)
5. Ausblick: Quantenkryptographie, Quantencomputer und DNA-Computer

Literatur: Leider gibt es kein einzelnes Buch, an das sich eine zweistündige Vorlesung halten könnte, die einen Überblick über die heute relevanten Aspekte der Kryptologie geben möchte. Ich werde deshalb Stoff aus mehreren Büchern und teilweise auch aus Originalarbeiten verwenden. Vier Bücher, die gemeinsam einen großen Teil des Vorlesungsstoffs abdecken, von denen aber jedes auch viel Stoff enthält, der in dieser Vorlesung keine Rolle spielen wird, sind
Alan G. Kohnheim: Cryptography: A primer, Wiley 1981
Neal Koblitz: A Course in Number Theory and Cryptography, Springer 1987, ²1994
Bruce Schneier: Applied Cryptography, Wiley ²1997
A.J. Menezes, P.C. van Oorschot, S.A. Vanstone: Handbook of applied cryptography, CRC Press 1997

Wer sich in den Ferien mit eher unterhaltender Literatur auf das Gebiet der Kryptologie einstimmen möchte, findet eine Beschreibung sowie eine Kryptoanalyse der (moderat nichttrivialen) Playfair-Chiffre in
Dorothy L. Sayer: Have his carcase (deutsche Titel: Zur fraglichen Stunde und Der Fund in den Teufelsklippen)
und eine (nicht sehr technische) Beschreibung der Kryptoanalyse des deutschen Enigma-Codes durch Polen und Engländer im zweiten Weltkrieg in
Parker: Enigma
(beides erhältlich in verschiedenen Hardcover- und Taschenbuchausgaben). Ein eher als Geschichtsbuch geschriebenes Werk, das aber fast alle bis etwa 1960 gebräuchlichen Verfahren und Ihre Kryptoanalyse detailiert beschreibt, ist
David Kahn: The Codebreakers, Scribner ²1997;
fast alle älteren Kryptologen haben die Grundlagen ihres Fachs aus diesem Buch gelernt.

Speziellere Literatur werde ich in der Vorlesung angeben.

Interessenten können auch die ausführlich kommentierte Vortrags- und Literaturliste eines ehemaligen Seminars zu diesem Thema konsultieren; die Angaben dort sind zwar nicht mehr unbedingt ganz aktuell, und auch die Stoffauswahl ist etwas verschieden von der der Vorlesung; für einen ersten Überblick sollte es aber doch nützlich sein.