Vorlesung im Wintersemester 2004/2005

Kryptologie

Wolfgang K. Seiler

Ort und Zeit: Dienstag, 15.30-17.00, und Mittwoch, 12.00-13.30, C013

Übungen: Dienstag, 12.00-13.30 Uhr, B6, A1.01

• Inhalt der Vorlesung
• Vorläufige Gliederung
• Hörerkreis und Prüfungsrelevanz für die verschiedenen Studiengänge unserer Fakultät
• Vorkenntnisse
• Literaturhinweise
• Ferienliteratur zur Einstimmung

Grundbegriffe:

Hier geht es um Sinn und Zweck der Kryptologie, um deren Anwendungebiete, sowie um die Arten von Angriffen, gegen die sie schützen soll. Insbesondere soll hier auch klarwerden, daß Kryptologie nur ein Aspekt der Datensicherheit ist und daß die Sicherheit eines Systems nicht größer sein kann, als die seines schwächsten Glieds.

Klassische Kryptoverfahren und ihre Kryptanalyse:

Die hier behandelten Verfahren wie Cäsar- und Vigenère-Chiffren, allgemeinere monoalphabetische Substitutionen und Transpositionschiffren waren 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 diese Möglichkeiten unbesehen zu verwerfen. Andererseits läßt sich auch beweisen, daß manche klassische Verfahren wie der one time pad unmöglich geknackt werden können; zumindest im Höchstsicherheitsbereich findet man diese Verfahren auch heute noch.

Nach dem ersten Weltkrieg bis in die sechziger Jahre des zwanzigsten Jahrhunderts war die Verschlüsselung mit Rotormaschinen kryptographischer Standard. Da diese heute nur noch im crypt(1)-Kommando von UNIX eine Rolle spielen, werde ich hierauf nur kurz eingehen. Beispielsweise ist 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.

Die Sicherheit eines Kryptosystems:

Zur Beurteilung der Sicherheit eines Kryptosystems muß man wissen, wieviel Information sich ein Gegner verschaffen kann. Dazu muß zunächst geklärt werden, was Information ist und wie man sie quantifiziert; dies leistet die Informationstheorie. Sie liefert auch einen Ansatz, wie sich ein Gegner mit unbeschränkter Rechenkapazität, der sogenannte Bayessche Gegner, die maximal mögliche Information verschaffen kann. Perfekte Sicherheit liegt genau dann vor, wenn selbst dieser Bayessche Gegner keinerlei Information erhält. Leider besagt ein Satz von Shannon, daß dies höchstens dann möglich ist, wenn der Schlüssel mindestens genauso lang ist wie die Nachricht; dies ist ein Aufwand, den man in der Praxis nur selten treiben kann. Für kürzere Schlüssel zeigt eine genauere Analyse, daß zumindest der Bayessche Gegner den Schlüssel schon anhand recht kurzer Kryptogramme bestimmen kann.

Die meisten heute gebräuchlichen Kryptoverfahren sind damit nicht sicher gegenüber dem Bayesschen Gegner. Daher müssen wir auch andere, schwächere Sicherheitsbegriffe diskutieren, die mit dem Aufwand des Gegners zusammenhängen. Da ein nichtzufällig gewählter Schlüssel jedem Gegner die Arbeit dramatisch erleichtert, müssen wir uns auch überlegen, was ein zufälliger Schlüssel ist und wie man sich so etwas verschafft.

Symmetrische Blockchiffren:

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 soll es in dieser Vorlesung hauptsächlich gehen.

  

Die Arbeitspferde der heutigen Kryptographie sind symmetrische Blockchiffren. Hier wird eine Nachricht in Blöcke von meist 64, 128 oder 256 Bit zerlegt, und diese Blöcke werden als ganzes verschlüsselt. Wegen der Vielzahl möglicher Blöcke erschwert dies statistische Ansätze. Verschiedene Operationsmodi sorgen für Schutz gegen weitere Formen von Attacken. Die Verschlüsselung erfolgt meist in mehreren  Runden, deren jede auf den Shannonschen Prizipien von Konfusion und Diffusion beruht. Als Beispiele sollen DES und AES betrachtet werden.

Der Data Encryption Standard DES:

Auch wenn dieser 1977 eingeführte Standard nicht mehr den heutigen Sicherheitsanforderungen entspricht, dürfte er (teils in modifizierter Form) immer noch das am häufigsten angewandte Kryptoverfahren sein, beispielsweise schützt er (inzwischen als Triple-DES) die Geheimzahlen unserer Geldkarten. Deshalb soll sein Aufbau im Detail untersucht werden, insbesondere auch die Designkriterien der für die Konfusion verantwortlichen sogenannten S-Boxen. Diese h&angen eng zusammen mit dem Schutz vor Attacken via differentieller Kryptanalyse, die z.B. relativ erfolgreich gegen die (schwächer geschützten) SIM-Karten von GSM-Telephonen angewandt werden können. Auch gegen eine leicht verschiedene Attacke, die lineare Kryptanalyse, ist DES ziemlich stabil. Sein Schwachpunkt ist aber der kurze Schlüssel von nur 56~Bit; 1998 stellt die Electronic Frontier Foundation ihren DES-Cracker fertig, der durch massiv parallelisiertes Durchprobieren aller Möglichkeiten in wenigen Stunden bis maximal vier Tagen aus nur zwei Blöcken verschlüsseltem Klartext den Schlüssel findet. Kurze Zeit später wurden in Deutschland die Geldkarten auf Triple-DES umgestellt.

Der Advanced Encryption Standard AES:

Nachdem die kurze Schlüssellänge von DES schon lange kritisiert worden war, begann 1997 die Suche nach einem sichereren Nachfolgealgorithmus. Nach einer internationalen Ausschreibung und mehreren internationalen Konferenzen zur Sichtung der Kandidaten wurde schließlich 2001 der offizielle Standard AES verkündet. Im Gegensatz zu DES beruhrt er nicht mehr auf Konfusion durch tabellarisch vorgegebene Funktionen, sondern verwendet algebraische Operation im und über dem Körper mit 256 Elementen. In diesem Kapitel müssen daher zunächst Körper von Zweipotenzordnung eingeführt werden, zusammen mit den Algorithmen zum Rechnen in solchen Körpern. Dann kann der Algorithmus definiert und seine Sicherheit diskutiert werden.

Das RSA-Verfahren:

Symmetrische Kryptoverfahren haben unter anderem den Nachteil, daß für jedes Paar von Teilnehmern, die miteinander kommunizieren möchten, ein eigener Schlüssel vereinbar werden muß; bei großen Netzen oder gar dem Internet ist das nicht praktikabel. Die assymetrischen Kryptographie verwendet verschiedene, Schlüssel zur Ver- und Entschlüsselung, so daß jeder den öffentlichen Schlüssel kennen darf und damit verschlüsselte Nachrichten versenden kann, die dann nur der Empfäger mit seinem geheimen Schlüssel lesen kann.

Am bekanntesten ist das RSA-Verfahren, dessen Entdecker dafür mit dem Turing-Preis 2002 ausgezeichnet wurden. Seine Sicherheit beruht auf der Schwierigkeit, eine große Zahl in ihre Primfaktoren zu zerlegen. Um das Verfahren zu verstehen und seine Sicherheit abzuschätzen, müssen wir uns daher auch mit den heute bekannten Faktorisierungsverfahren und ihrer Leistungsfähigkeit auf Supercomputern bzw. vielen via Internet kommunizierenden PCs beschäftigen und natürlich auch die dazu notwendigen zahlentheoretischen Grundlagen lernen.

Im Gegensatz zu symmetrischen Blockchiffren läßt sich RSA (wie die meisten asymetrischen Chiffren) nicht nur als Verschlüsselungsverfahren verwenden, sondern auch für elektronische Unterschriften (die in Deutschland rechtsgültig sind), für anonymes elektronisches Bargeld und für sichere Internetverbindungen (SSL, SSH, ...).

Diskrete Logarithmen:

Die zweite große Klasse von asymmetrischen Kryptoverfahren beruht auf diskreten Logarithmen, d.h. auf der Schwierigkeit, die Gleichung a^x= b modulo einer großen Primzahl p zu lösen; wie wir sehen werden, erfordert dies ungefähr denselben Aufwand wie die Faktorisierung einer Zahl in der Größenordnung von p.

Ein Vorteil von diskreten Logarithmen ist, daß sie nicht nur für Zahlen modulo p betrachtet werden können, sondern für Elemente einer beliebigen abelschen Gruppe. Nimmt man als Gruppe speziell die Punkte einer elliptischen Kurve über einem endlichen Körper, erhält man eine Variante, die bei nur einem Zehntel der Schlüsselläge genauso große Sicherheit bietet wie die klassischen Verfahren. In dieser Vorlesung können nur die einfachsten Grundtatsachen über elliptische Kurven behandelt werden; alles weitere folgt in einer Spezialvorlesung im nächsten Semester.

SHA und DSA:

Der große Nachteil der asymmetrischer Verfahren gegenüber den symmetrischen ist ihr erheblich größer Rechenaufwand, so daß sie beim Verschlüsseln üblicherweise nur dazu benutzt werden, Sitzungsschlüssel für symmetrische Verfahren auszutauschen. Bei elektronischen Unterschriften unter längere Dokumente wäre es ebenfalls viel zu aufwendig, jeden Block einzeln zu unterschreiben; stattdessen wird nur ein Hashwert über die gesamte Nachricht unterzeichnet. Dazu sind die klassischen Hashverfahren allerdings völlig ungeeignet, da es hier viel zu einfach wäre, zwei verschiedene Texte mit demselben Hashwert zu produzieren. Gesucht sind also kryptographisch sichere Hashverfahren, wobei die Hashwerte bei vergleichbarer Sicherheit wegen des Geburtstagsparadoxons etwa doppelt solang sein müssen wie die Schlüssel eines symmetrischen Kryptoverfahrens.

In diesem Kapitel soll es, außer um allgemeine Probleme mit kryptographisch sicheren Hashverfahren vor allem um die Familie der SHA-Verfahren (Secure Hash Algorithm) sowie deren Verwendung im Digital Signature Algorithm DSA gehen.

Kryptographische Protokolle:

Kryptographie dient heute nicht nur zur Verschlüsselung und für elektronische Unterschriften, sie hat noch eine ganze Reihe weiterer Anwendungen. Ein wichtiges Beispiel sind Identifikationssysteme, z.B. zur Zugangskontrolle, wobei hier vor allem im Umgang mit weniger vertrauenswürdigen Partnern oft wesentlich ist, daß man die Kenntniss beispielsweise eines Passworts nachweisen kann, ohne dieses preiszugeben. Dazu dienen zero knowledge und minimal disclosure Protokolle. Zumindest kurz erwähnt werden sollen auch noch einige andere Protokolle wie das Werfen einer Münze oder Poker per Telephon. Mathematisch beruhen die hier behandelten Verfahren auf der Theorie der quadratische Reste und der Berechnung von Quadratwurzeln modulo einer Primzahl sowie des Produkts zweier Primzahlen.

Ausblicke:

Hier geht es vor allem um künftige Entwicklungen auf der Grundlage der Quantentheorie. Heute schon existent ist die Quantenkryptographie, die Informationen mittels einzelner Photonen überträgt, deren Zustand ein Gegner nicht messen kann, ohne ihn erkennbar zu manipulieren. Zusammen mit fehlerkorrigierenden Codes läßt sich daraus ein Verfahren machen, das bis auf ein beliebig klein wählbares Restrisiko genauso sicher ist wie der one time pad.

Quantencomputer könnten künftig zu einer dramatischen Umgestaltung der Kryptologie führen: Mit diesen Computern, deren QBits (Quantenbits) gleichzeitig die Werte Null und Eins haben können, kann ein Register der Länge n als Inhalt gleichzeitig alle Zahlen von 0 bis 2ⁿ - 1 haben. Wie Shor gezeigt hat, lassen sich damit sowohl Faktorisierungen als auch Berechnungen diskreter Logarithmen durchführen mit einem Aufwand, der in der Größenordnung des Aufwands einer RSA-Verschlüsselung liegt. Sobald es also Quantencomputer mit mehreren Tausend QBits gibt, sind fast alle heute gebräuchlichen Verfahren der asymmetrischen Kryptographie hinfällig. Der größte heute bekannte Quantencomputer steht bei IBM und hat sieben QBits; damit ist gelungen, die Zahl 15 in ihre Primfaktoren zu zerlegen. Der dort gewählte Ansatz via magnetische Kernresonanz ist allerdings wahrscheinlich nicht für viel größere Anzahlen von QBits verwendbar.

   

Außer Quantencomputer könnten eventuell künftig auch DNS-Computer eine Rolle spielen, die Probleme auf chemischem Weg lösen. Bislang wurde allerdings nur die Lösung eines travelling salesman Problems für sieben Städte demonstriert.

Mit der größten auf dem Gebiet der Kryptologie arbeitenden Organisation, der NSA, beschäftigt sich
Dan Brown: Digital Fortress.
Das Buch ist eher ein Thriller und das meiste, was dort über Kryptologie oder Computer gesagt wird, ist schlichtweg Unsinn. Obwohl die Handlung ähnlich unlogisch ist wie in Browns anderen Büchern, hat der Lübbe-Verlag dieses Buch als einziges nicht in deutscher Übersetzung herausgebracht - vielleicht um die NSA nicht zu ärgern.

Rolf Hochhuth: Alan Turing
beschäftigt sich zwar (in Romanform) mit der gesamten Biographie von Alan Turing, legt aber doch einen gewissen Schwerpunkt auf die Zeit des zweiten Weltkriegs, als Turing maßgeblich an der Kryptanalyse der deutschen Enigma beteiligt war.

Eher ein Geschichtsbuch ist
David Kahn: The Codebreakers, Scribner ²1997;
es beschreibt 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.

Die ersten Anfänge der Quantenkryptographie in der Antike werden beschrieben (nur in ausgewählten deutschen Übersetzungen von)
René Goscinny, Albert Uderzo: Asterix und der Avernerschild