Verschlüsselung: von Cäsar zur modernen Kryptografie

Ein Verfahren mit 25 möglichen Schlüsseln ist unsicher, das leuchtet ein. Eines mit $4 \cdot 10^{26}$ Schlüsseln ist es ebenfalls, und das leuchtet zunächst nicht ein.

Genau in dieser Lücke liegt das Interessante. Sicherheit lässt sich nicht an einer einzigen Zahl ablesen, und wer nur den Schlüsselraum vergleicht, kommt zu falschen Schlüssen.

In diesem Kapitel rechnen wir Schlüsselräume aus, sehen uns an, warum große Zahlen allein nicht genügen, und leiten daraus die drei Anforderungen ab, an denen moderne Verfahren gemessen werden.

Vorausgesetzt werden Klartext, Geheimtext, Schlüssel, die Cäsar-Verschlüsselung, die Häufigkeitsanalyse und das Kerckhoffs-Prinzip. Wenn davon etwas unklar ist, lies zuerst Kryptologie.

Neu ist hier die quantitative Seite: Wie groß ist ein Schlüsselraum wirklich, wie lange dauert ein Angriff, und woran misst man Sicherheit?

Der Schlüsselraum ist die Menge aller möglichen Schlüssel. Seine Größe berechnet man, indem man abzählt, wie viele Wahlmöglichkeiten es gibt.

Cäsar: eine Verschiebung zwischen 1 und 25.

$$|K| = 25$$

Monoalphabetische Substitution: Jeder der 26 Buchstaben bekommt ein eigenes Bild. Für den ersten gibt es 26 Möglichkeiten, für den zweiten noch 25 und so fort.

$$|K| = 26! = 26 \cdot 25 \cdot 24 \cdots 1 \approx 4{,}03 \cdot 10^{26}$$

Vigenère mit Schlüsselwort der Länge $\ell$: Jede Stelle des Schlüsselworts kann einen von 26 Buchstaben tragen, unabhängig von den anderen.

$$|K| = 26^{\ell}$$

Bei $\ell = 8$ sind das $26^8 \approx 2{,}1 \cdot 10^{11}$, bei $\ell = 20$ bereits $26^{20} \approx 2 \cdot 10^{28}$.

Moderne Verfahren mit Schlüssellänge $n$ Bit:

$$|K| = 2^{n}$$

Bei 128 Bit sind das $2^{128} \approx 3{,}4 \cdot 10^{38}$.

Aus der Größe des Schlüsselraums und der Prüfgeschwindigkeit folgt die Dauer:

$$t = \frac{|K|}{v}$$

Dabei ist $v$ die Zahl der geprüften Schlüssel je Sekunde. Rechnen wir das für eine sehr schnelle Anlage mit einer Billion Schlüsseln pro Sekunde durch, also $v = 10^{12}$:

| Verfahren | $|K|$ | Dauer bei $10^{12}$ Schlüsseln je Sekunde | |---|---|---| | Cäsar | 25 | unmessbar kurz | | Vigenère, $\ell = 4$ | $4{,}6 \cdot 10^{5}$ | unmessbar kurz | | Vigenère, $\ell = 8$ | $2{,}1 \cdot 10^{11}$ | unter einer Sekunde | | Monoalphabetisch | $4{,}0 \cdot 10^{26}$ | rund 13 Millionen Jahre | | 128 Bit | $3{,}4 \cdot 10^{38}$ | rund $10^{19}$ Jahre |

Zwei Beobachtungen sind wichtig. Erstens: Die monoalphabetische Substitution wäre gegen Durchprobieren sicher, und sie ist trotzdem mit Papier knackbar. Zweitens: Bei 128 Bit übersteigt die Dauer das Alter des Universums um viele Größenordnungen; ein tausendfach schnellerer Rechner ändert daran nichts Wesentliches.

🔴 Daraus folgt die zentrale Einsicht: Ein großer Schlüsselraum ist notwendig, aber nicht hinreichend. Er schützt gegen Durchprobieren, sagt aber nichts über andere Angriffe.

Die Schwäche der monoalphabetischen Verfahren liegt darin, dass ein Klartextbuchstabe immer durch denselben Geheimtextbuchstaben ersetzt wird. Die Häufigkeitsverteilung der Sprache überträgt sich damit unverändert.

Vigenère behebt das, indem die Verschiebung von der Position abhängt. Ein Schlüsselwort gibt für jede Stelle eine eigene Verschiebung an und wiederholt sich dann:

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
Geheimtext:    S  R  D  Y  V  K  K  X  G  U

Der entscheidende Effekt: Das $\texttt{I}$ an Stelle 1 wird zu $\texttt{S}$, das $\texttt{I}$ an Stelle 9 zu $\texttt{G}$. Derselbe Klartextbuchstabe erzeugt verschiedene Geheimtextbuchstaben, und die einfache Häufigkeitsanalyse läuft ins Leere.

Rechnerisch ist es dieselbe Formel wie bei Cäsar, nur mit einer stellenabhängigen Verschiebung $s_i$:

$$g_i = (k_i + s_i) \bmod 26$$

Die Schwachstelle ist die Wiederholung des Schlüsselworts. Hat es die Länge $\ell$, so werden die Stellen $1, 1+\ell, 1+2\ell, \ldots$ alle mit derselben Verschiebung behandelt.

Kennt ein Angreifer $\ell$, kann er den Geheimtext in $\ell$ Teiltexte zerlegen: alle Zeichen an Position $1, 1+\ell, 1+2\ell$ bilden den ersten, und so fort. Jeder dieser Teiltexte ist dann eine einfache Cäsar-Verschlüsselung und in Sekunden geknackt.

Die Schlüssellänge selbst verrät sich durch wiederkehrende Muster: Kommt eine Buchstabenfolge im Klartext mehrfach im selben Abstand vor wie das Schlüsselwort, erscheint sie auch im Geheimtext identisch. Aus den Abständen solcher Wiederholungen lässt sich $\ell$ erschließen.

Daraus folgt: Vigenère ist umso stärker, je länger und unregelmäßiger das Schlüsselwort ist. Im Grenzfall, wenn der Schlüssel so lang ist wie der Klartext, zufällig gewählt und nur einmal verwendet wird, ist das Verfahren sogar beweisbar unknackbar. Praktisch scheitert das daran, dass man diesen Schlüssel erst einmal sicher übertragen müsste, und wäre das möglich, könnte man auch gleich die Nachricht so übertragen.

Der Lehrplan verlangt, ein Verschlüsselungsverfahren als Algorithmus darzustellen. Für Vigenère:

UNTERPROGRAMM verschluessle(klartext, schluessel)
  ergebnis := ""
  FÜR i VON 0 BIS laenge(klartext) - 1 WIEDERHOLE
    k := position(klartext[i])                    // 0 bis 25
    s := position(schluessel[i mod laenge(schluessel)])
    g := (k + s) mod 26
    ergebnis := ergebnis + buchstabe(g)
  ENDE FÜR
  GIB ZURÜCK ergebnis
ENDE UNTERPROGRAMM

Zwei Stellen verdienen Beachtung. Der Ausdruck $\texttt{i mod laenge(schluessel)}$ bewirkt die Wiederholung des Schlüsselworts, ohne dass man es künstlich verlängern müsste. Und das $\bmod\ 26$ erledigt das Weiterzählen am Alphabetende.

Das Entschlüsseln ist dasselbe Unterprogramm mit $(k - s + 26) \bmod 26$. Die Addition von 26 verhindert negative Zwischenergebnisse; sie ändert am Rest nichts, weil 26 der Modulwert ist.

Aus allem Bisherigen ergeben sich drei Bedingungen, an denen jedes Verfahren gemessen wird:

1. Großer Schlüsselraum. Durchprobieren muss aussichtslos sein. Heute gelten mindestens 128 Bit als sicher.

2. Keine durchscheinende Struktur. Aus dem Geheimtext darf sich nichts über den Klartext ablesen lassen. Ideal ist, dass der Geheimtext von zufälligen Daten nicht unterscheidbar ist.

3. Offenes Verfahren, geheimer Schlüssel. Das Kerckhoffs-Prinzip. Die Sicherheit hängt allein am wechselbaren Schlüssel.

Ein Verfahren muss alle drei erfüllen. Die monoalphabetische Substitution erfüllt die erste und scheitert an der zweiten; ein selbst erfundenes Geheimverfahren scheitert an der dritten, unabhängig davon, wie gut es sein mag.

Was moderne Verfahren zusätzlich lösen, nämlich wie zwei Menschen einen gemeinsamen Schlüssel vereinbaren, ohne sich je getroffen zu haben, ist Thema der Qualifikationsphase.