One-Time-Pad
Es gibt ein Verschlüsselungsverfahren, das sich nachweislich nicht brechen lässt, auch nicht mit unbegrenzter Rechenleistung. Der Preis dafür ist ein Schlüssel, der so lang ist wie die Nachricht.
Definition
Das One-Time-Pad (deutsch: Einmalschlüssel-Verfahren) ist ein symmetrisches Verschlüsselungsverfahren. Der Klartext wird Zeichen für Zeichen mit einem Schlüssel verknüpft, der zufällig erzeugt wurde, mindestens so lang ist wie der Klartext und nur ein einziges Mal verwendet wird.
Verknüpft wird je nach Darstellung des Textes
- bitweise mit XOR wie bei der XOR-Verschlüsselung oder
- buchstabenweise mit der Addition modulo 26 wie beim Vigenère-Verfahren.
Bedingungen
Das Verfahren ist nur sicher, wenn alle vier Bedingungen erfüllt sind:
- Der Schlüssel ist mindestens so lang wie die Nachricht.
- Der Schlüssel ist echt zufällig. Jedes Schlüsselzeichen ist unabhängig von den anderen gewählt.
- Der Schlüssel wird nur einmal verwendet.
- Der Schlüssel bleibt geheim und ist nur Sender und Empfänger bekannt.
Sicherheit und Grenzen
Sind die Bedingungen erfüllt, ist das One-Time-Pad perfekt sicher: Zu einem Geheimtext passt jeder Klartext derselben Länge, je nachdem, welchen Schlüssel man annimmt. Weil jeder Schlüssel gleich wahrscheinlich ist, ist auch jeder Klartext gleich gut möglich. Ein Brute-Force-Angriff liefert alle denkbaren Klartexte und damit keine Information. Häufigkeitsanalyse und Kasiski-Test finden keinen Ansatz, weil sich im Schlüssel nichts wiederholt.
In der Praxis wird das Verfahren trotzdem selten eingesetzt:
- Schlüsselverteilung: Sender und Empfänger müssen vorher so viel Schlüsselmaterial sicher austauschen, wie sie später an Nachrichten senden. Das Schlüsselverteilungsproblem wird also nicht gelöst, sondern nur verlagert.
- Zufall: Echte Zufallsfolgen in großer Menge sind aufwendig zu erzeugen.
- Disziplin: Wird ein Schlüssel doch zweimal verwendet, ist die Sicherheit verloren.
- Kein Schutz der Integrität: Ein Angreifer kann einzelne Bits des Geheimtextes umkehren. Damit ändert er gezielt die entsprechenden Bits des Klartextes, ohne den Schlüssel zu kennen.
Beispiele
Bitmuster mit einem Einmalschlüssel verschlüsseln
Die Nachricht JA besteht aus 16 Bit. Der Einmalschlüssel ist eine zufällige Bitfolge derselben Länge: 1011 0011 0101 1100.
| Zeichen | J | A |
|---|---|---|
| Klartext | 0100 1010 | 0100 0001 |
| Einmalschlüssel | 1011 0011 | 0101 1100 |
| Geheimtext | 1111 1001 | 0001 1101 |
Der Geheimtext lautet 1111 1001 0001 1101. Der Schlüssel wird danach vernichtet und nie wieder verwendet.
Zu einem Geheimtext passt jeder Klartext
Hier wird mit Buchstaben gerechnet wie beim Vigenère-Verfahren, der Schlüssel ist aber zufällig und so lang wie die Nachricht. Eve fängt den Geheimtext YRSTSD ab.
| Möglicher Schlüssel | Klartext dazu |
|---|---|
ORYOOQ |
KAUFEN
|
RRHAOQ |
HALTEN
|
Beide Schlüssel sind gleich wahrscheinlich, denn der Schlüssel wurde zufällig gewählt. Zu jedem Klartext aus sechs Buchstaben gibt es einen passenden Schlüssel. Der Geheimtext verrät deshalb nichts über den Klartext außer seiner Länge.
Einen Schlüssel doppelt verwenden
Derselbe Schlüssel 1011 0011 0101 1100 verschlüsselt nacheinander die Nachrichten JA und OK:
| Bitmuster | |
|---|---|
| Geheimtext 1 | 1111 1001 0001 1101 |
| Geheimtext 2 | 1111 1100 0001 0111 |
| Geheimtext 1 ⊕ Geheimtext 2 | 0000 0101 0000 1010 |
| Klartext 1 ⊕ Klartext 2 | 0000 0101 0000 1010 |
Die beiden letzten Zeilen sind gleich: Der Schlüssel hebt sich auf. Eve erfährt so die Verknüpfung der beiden Klartexte, ohne den Schlüssel zu kennen. Kennt oder errät sie einen der beiden Klartexte, hat sie auch den anderen.