Kryptologie: verschlüsseln und entschlüsseln

Vor über zweitausend Jahren verschob Julius Cäsar in seinen Botschaften jeden Buchstaben um drei Stellen im Alphabet. Wer den Brief abfing, las Unsinn.

Heute knackt ein Rechner dieses Verfahren in weniger als einer Tausendstelsekunde, und ein Mensch mit Papier schafft es in fünf Minuten.

Interessant ist nicht, dass es unsicher ist, sondern warum. Denn die Gründe dafür sind bis heute dieselben Gründe, an denen moderne Verfahren gemessen werden. Wer versteht, warum Cäsar scheitert, versteht, was ein sicheres Verfahren leisten muss.

Der lesbare Ausgangstext heißt Klartext, das Ergebnis Geheimtext. Der Vorgang hin heißt Verschlüsseln, der Vorgang zurück Entschlüsseln.

Entscheidend ist der Schlüssel: die Angabe, die zum selben Verfahren gehört, aber geheim bleibt. Verfahren und Schlüssel sind zwei verschiedene Dinge, und diese Trennung ist der wichtigste Gedanke des ganzen Kapitels.

$$\text{Klartext} \xrightarrow{\;\text{Verfahren} + \text{Schlüssel}\;} \text{Geheimtext} \xrightarrow{\;\text{Verfahren} + \text{Schlüssel}\;} \text{Klartext}$$

Beachte außerdem den Unterschied zur Codierung aus Klasse 9: Ein Code, etwa ASCII, soll Daten übertragbar machen und ist allgemein bekannt. Eine Verschlüsselung soll sie geheim halten und braucht dafür einen Schlüssel. Beides sieht für den Uneingeweihten gleich unlesbar aus und verfolgt völlig verschiedene Ziele.

Jeder Buchstabe wird um eine feste Anzahl von Stellen im Alphabet verschoben. Diese Anzahl ist der Schlüssel.

Bei Schlüssel 3:

Klar:   A B C D E F G ... W X Y Z
Geheim: D E F G H I J ... Z A B C

Aus INFORMATIK wird damit LQIRUPDWLN. Am Ende des Alphabets wird vorn weitergezählt: X wird zu A.

Rechnerisch ist es eine Addition mit Rest. Nummeriert man A = 0 bis Z = 25, gilt:

$$\text{Geheim} = (\text{Klar} + s) \bmod 26 \qquad \text{Klar} = (\text{Geheim} - s + 26) \bmod 26$$

Das Zeichen $\bmod$ meint den Rest bei Division durch 26; es sorgt für das Weiterzählen am Alphabetende. Die Addition von 26 in der zweiten Formel verhindert negative Zwischenergebnisse.

Die Menge aller möglichen Schlüssel heißt Schlüsselraum. Bei Cäsar sind es die Verschiebungen 1 bis 25, denn 0 verändert nichts und 26 ist wieder 0.

25 Möglichkeiten. Man probiert sie einfach alle durch, notfalls von Hand. Ein solcher Angriff heißt vollständige Suche oder Brute-Force.

Daraus folgt die erste Anforderung an jedes Verfahren: Der Schlüsselraum muss so groß sein, dass vollständiges Durchprobieren aussichtslos ist. Bei 128 Bit Schlüssellänge sind es $2^{128}$ Möglichkeiten, also eine Zahl mit 39 Stellen; auch alle Rechner der Welt zusammen kämen damit nicht durch.

Ein großer Schlüsselraum allein genügt aber nicht. Das zeigt die monoalphabetische Substitution, bei der jeder Buchstabe durch einen beliebigen anderen ersetzt wird, nicht nur um eine feste Zahl verschoben.

Der Schlüsselraum ist hier gewaltig: $26! \approx 4 \cdot 10^{26}$ mögliche Zuordnungen. Durchprobieren ist chancenlos.

Trotzdem knackt man das Verfahren mit Papier und Bleistift. Der Grund: In jeder Sprache kommen Buchstaben unterschiedlich häufig vor. Im Deutschen:

Weil jeder Klartextbuchstabe immer auf denselben Geheimtextbuchstaben abgebildet wird, überträgt sich diese Verteilung unverändert. Das häufigste Zeichen im Geheimtext ist mit großer Wahrscheinlichkeit das E. Danach nutzt man Wortlängen, doppelte Buchstaben und typische Silben, und der Rest fällt wie ein Kartenhaus.

Daraus folgt die zweite Anforderung: Ein Verfahren darf die Struktur des Klartextes nicht durchscheinen lassen. Genau das ist der eigentliche Schwachpunkt, nicht die Zahl der Schlüssel.

Die Vigenère-Verschlüsselung benutzt statt einer Zahl ein Schlüsselwort. Jeder Buchstabe des Schlüsselworts gibt für eine Position eine eigene Verschiebung an; ist das Wort zu Ende, beginnt es von vorn.

Klartext:     I N F O R M A T I K
Schlüssel:    K E Y K E Y K E Y K
Verschiebung: 10 4 24 10 4 24 10 4 24 10

Der Gewinn ist wesentlich: Dasselbe E wird an verschiedenen Stellen zu verschiedenen Geheimtextzeichen, weil eine andere Verschiebung gilt. Die einfache Häufigkeitsanalyse läuft damit ins Leere.

Auch Vigenère ist heute geknackt, und zwar über die Wiederholung des Schlüsselworts: Wer dessen Länge ermittelt, kann den Text in ebenso viele Teiltexte zerlegen, von denen jeder wieder eine einfache Cäsar-Verschlüsselung ist. Das Verfahren ist also nur so lange stark, wie das Schlüsselwort lang und unregelmäßig ist.

Damit sind wir beim wichtigsten Grundsatz der Kryptologie, formuliert im 19. Jahrhundert:

Die Sicherheit eines Verfahrens darf ausschließlich auf der Geheimhaltung des Schlüssels beruhen, niemals auf der Geheimhaltung des Verfahrens.

Der Grund ist nüchtern und praktisch. Ein Verfahren steckt in Programmen, Geräten und Köpfen; es wird analysiert, nachgebaut, verraten oder durch Zufall bekannt. Ein Schlüssel dagegen ist eine kurze Angabe, die sich wechseln lässt.

Rechne den Unterschied durch: Wird ein Schlüssel bekannt, vergibt man einen neuen und ist wieder sicher. Wird ein geheim gehaltenes Verfahren bekannt, sind alle damit verschlüsselten Nachrichten offen, und ein neues Verfahren muss erst entwickelt, geprüft und überall eingebaut werden.

Deshalb sind moderne Verfahren öffentlich bekannt und werden von Fachleuten weltweit angegriffen. Was jahrelangen Angriffen standhält, ist vertrauenswürdig; ein Verfahren, das niemand prüfen durfte, ist es nicht. „Wir verraten nicht, wie es funktioniert“ ist in der Kryptologie kein Sicherheitsversprechen, sondern ein Warnzeichen.

Die drei Anforderungen, die wir hergeleitet haben, gelten unverändert für heutige Verfahren:

1. Großer Schlüsselraum, damit Durchprobieren aussichtslos ist.
2. Keine durchscheinende Struktur des Klartextes.
3. Offenes Verfahren, geheimer Schlüssel nach Kerckhoffs.

Wie moderne Verfahren das erreichen und wie zwei Menschen einen Schlüssel austauschen, ohne sich je getroffen zu haben, ist Thema der Qualifikationsphase.