Vorlesung im Wintersemester 2000/2001


Einführung in die Kryptologie

Wolfgang K. Seiler

Ort und Zeit: Montag, 15.30 - 17.00, HS103 (nicht 104!)


Ziel dieser Vorlesung ist eine mathematisch fundierte Einführung in die Kryptologie, die Ver- und Entschlüsselung geheimer Nachrichten also.

Die Vorlesung beginnt mit klassischen kryptographischen Verfahren, die bis etwa zur Zeit des ersten Weltkriegs gebräuchlich und damals auch teilweise sicher waren; heute sind diese Verfahren nur noch in Office-Software und ähnlichen Programmen enthalten und bieten keinerlei Schutz mehr gegen einen ernstzunehmenden Gegner. In diesem Kapitel soll klar werden, daß Werbeaussagen wie "Quadrillionen von Möglichkeiten, für die auch der schnellste heutige Rechner länger bräuchte als das Alter des Universums" keinerlei Schutz bieten, da es die statistischen Eigenschaften natürlicher Sprachen (oder auch von Dateien eines vorgegebenen Formats) oft gestatten, praktisch alle dieser Möglichkeiten sofort auszuschließen. Andererseits läßt sich auch beweisen, daß manche klassische Verfahren unmöglich geknackt werden können; zumindest im Hochsicherheitsbereich werden diese noch heute angewandt.

Leider besagt aber ein Satz von Shannon, daß jedes beweisbar sichere Verfahren zu aufwendig ist, als daß es für Routineanwendungen wie etwa im Bankenbereich oder zur Sicherung der Kommunikation im Internet anwendbar wäre. In der Vorlesung geht es daher fast ausschließlich um Verfahren, die zwar im Prinzip knackbar sind, bei denen aber der Aufwand für die Kryptanalyse entweder unrealistisch hoch ist oder aber zumindest den Wert der zu schützenden Information beträchtlich übersteigt.

Enigma

Nur kurz werde ich 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, über das es im Manual heißt: Methods of attack on such machines are known, but not widely; moreover the amount of work required is likely to be large. Die Kryptanalyse der deutschen Enigma durch die Alliierten ist noch heute interessant als Beispiel, wie ein eigentlich guter Code durch inkompetente Handhabung unsicher werden kann.

Zuse Z1    MARK 1

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 verwendet. Damit entstanden auch neue kryptographische Verfahren, und um diese wird es 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 Kryptanalyse zu bewerten; auch dabei geht es wieder um die bestmögliche Ausnutzung von (bei guten Verfahren minimalen) statistischen Schwankungen. Wenn möglich möchte ich in der Vorlesung auch den DES-Nachfolger AES betrachten, der voraussichtlich in diesem Sommer oder Herbst endgültig festgelegt wird.

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 Kryptanalyseverfahren 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.

Cray X-MP

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

Ziel der Vorlesung ist es nicht, einen kompletten Überblick über die heute eingesetzten kryptographischen Verfahren zu geben; stattdessen möchte ich anhand der wichtigsten dieser Verfahren einen Eindruck von den Möglichkeiten und Grenzen der Kryprtographie geben.


Konkret sieht eine vorläufige Gliederung etwa so aus:

  1. Klassische Kryptosysteme und informationstheoretische Ansätze zu ihrer Kryptanalyse
  2. Symmetrische Blockchiffren (DES und seine Operationsmodi, AES, differentielle und lineare Kryptanalyse, ...)
  3. Das RSA-Verfahren (Asymmetrische Verfahren allgemein, RSA und seine Anwendungen auf elektronische Unterschriften, elektronisches Geld u.ä, Kryptanalyse 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
Hauptinhalt der Vorlesung sind die Kapitel zwei bis vier; wenn die endgültige Entscheidung zwischen den fünf noch verbliebenen AES-Kandidaten erst spät fällt, werde ich Kapitel zwei eventuell auch erst nach den Kapiteln drei und vier behandeln.
Hörerkreis: Studenten im Hauptstudium eines der Studiengänge unserer Fakultät. Im Integrierten Studiengang Mathematik und Informatik kann die Vorlesung im Rahmen des Vertiefungsfachs Algebra gewählt werden.
Vorkenntnisse: Alle benötigten Methoden aus der Statistik, Informationstheorie und Zahlentheorie werden in der Vorlesung selbst entwickelt; die Hörer(innen) müssen also nur mit dem grundlegenden Stoff der Anfängervorlesungen (Analysis I und LA I oder HM I) vertraut sein. Sie sollten sich aber darüber im klaren sein, daß im Laufe der Vorlesung durchaus auch nichttriviale Mathematik eine Rolle spielen wird.


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; zu Teilen der Vorlesung wird es auch ein Skriptum geben. 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, 21994
Bruce Schneier: Applied Cryptography, Wiley 21995, deutsche Übersetzung: Angewandte Kryptographie, Addison-Wesley 1996
A.J. Menezes, P.C. van Oorschot, S.A. Vanstone: Handbook ofs applied cryptography, CRC Press 1997

Speziellere Literatur werde ich in der Vorlesung angeben.


Wer sich in den Ferien mit eher unterhaltender Literatur auf das Gebiet der Kryptologie einstimmen möchte, findet eine Beschreibung sowie eine Kryptanalyse 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 Kryptanalyse des deutschen Enigma-Codes durch Polen und Engländer im zweiten Weltkrieg in

Robert Harris: Enigma

(beides erhältlich in verschiedenen Hardcover- und Taschenbuchausgaben, sowohl englisch als auch deutsch).

Ein sehr dicker Roman, der sich mit Kryptographie sowohl im zweiten Weltkrieg als auch heute beschäftigt, ist
Neal Stephenson: Cryptonomicon, Harper 2000

Eher ein Geschichtsbuch ist
David Kahn: The Codebreakers, Scribner 21997;
es beschreibt aber fast alle bis etwa 1960 gebräuchlichen Verfahren und Ihre Kryptanalyse detailiert. Viele ältere Kryptologen haben die Grundlagen ihres Fachs aus der (fast textgleichen) ersten Auflage dieses Buchs gelernt.


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 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.