· 

Das One-Time-Pad

1. Einführung

Es gibt eine Vielzahl verschiedener Verschlüsselungsverfahren (z. B. das RSA-Verfahren), die in der Praxis ziemlich sicher sind. Die Betonung liegt hier auf der Praxis. In der Theorie sind diese Verfahren nämlich alle knackbar. 

Was bedeutet in diesem Zusammenhang praktisch sicher? D. h. mit modernen Rechnern ist es nicht in hinreichend kurzer Zeit möglich, die Verschlüsselung zu knacken. Nehmen wir als Beispiel die Primfaktorzerlegung, die zum Knacken des RSA-Verfahrens nötig ist. Es gibt bislang keinen Polynomialzeitalgorithmus, der dieses Problem löst, d. h. der Aufwand zum Knacken ist so hoch, dass man selbst bei Akquirierung aller auf diesem Planeten zur Verfügung stehenden Rechenkapazitäten länger bräuchte als das Universum alt ist, um die Primfaktorzerlegung zu finden. 

Du denkst dir vielleicht, dass ein Computer doch sehr schnell rechnet und das mag für Zahlen, die du aus der Schule kennst auch stimmen, allerdings wird es ziemlich lange dauern, bis du die Primfaktorzerlegung von z. B. dieser Zahl gefunden hast: 

114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541

Wir reden nämlich von Primzahlen mit mehreren hundert Stellen, die in der Praxis für das RSA-Verfahren eingesetzt werden. Mehr zur genauen Funktionsweise des RSA-Verfahrens findest du in meinem Video zu diesem Thema.

Man kann mit probabilistischen Primzahlentests zwar sehr schnell herausfinden, ob eine gegebene Zahl tatsächlich eine Primzahl ist, d. h. du wirst keine Jahrhunderte brauchen um (mit einer bestimmten Fehlerwahrscheinlichkeit) sagen zu können, dass 

5533560204899578487112594480354737234891979899692379913185949648481993669656140225694297567305628143

eine Primzahl ist, doch eine Primfaktorzerlegung von hundertstelligen Zahlen ist deshalb noch lange nicht so einfach möglich!

Dieses Problem der nur praktischen Sicherheit hat quasi jedes gängige Verschlüsselungsverfahren. Doch was ist, wenn irgendwann Quantencomputer auf dem Markt sind? Würde das nicht die aktuelle Sicherheit im Internet massiv gefährden, da ihnen bekanntlich immense Rechenfähigkeiten zugeschrieben werden? Dazu mache ich noch ein eigenes Video, doch so viel vorab: mit der Einführung von Quantencomputern per se den Untergang der Sicherheit vorherzusagen, ist völlig überzogen, da Quantencomputer nur in bestimmten Bereichen effizienter arbeiten als klassische Computer. Außerdem wird in der Quantenkryptographie jetzt bereits an Algorithmen geforscht, die praktisch sicher gegenüber Quantencomputern sind. 

Gibt es denn kein Verfahren, das auch theoretisch nicht geknackt werden kann, sondern perfekte Sicherheit bietet? Doch, so ein Verfahren gibt es: das One-Time-Pad (OTP). Die Abkürzung OTP sollte nicht mit der für das One-Time-Password (ebenfalls OTP) verwechselt werden.


2. Funktionsweise des One-Time-Pads

Die Idee des One-Time-Pads ist ziemlich einfach: Man verschlüsselt jede Informationseinheit (bei Texten z. B. einzelne Buchstaben) mit einem Teil des Schlüssels, d. h. der Schlüssel muss (mindestens) genau so lange wie die Information sein, die es zu verschlüsseln gilt. Es handelt sich bei diesem Verfahren um eine symmetrische Verschlüsselung, die von dem Mathematiker Claude Shannon im Jahr 1882 vorgeschlagen wurde.

Ich habe bewusst von einer "Information" und nicht nur konkret von Texten gesprochen. Mit dem One-Time-Pad können nämlich nicht nur Texte, sondern auch Bilder oder Dateien verschlüsselt werden. Betrachten wir als Beispiel den folgenden Text, den wir mit dem One-Time-Pad verschlüsseln wollen:

GEHEIMTEXT

Der Einfachheit wegen betrachten wir nur Großbuchstaben. Als erstes werden diese Buchstaben gemäß ihrer Position im Alphabet in einen Zahlencode umgewandelt. Wir beginnen dabei (wie in der Informatik üblich) bei 0 zu zählen, d. h. es ergibt sich für den Klartext "GEHEIMTEXT" der Zahlencode

6 4 7 4 8 12 19 4 23 19

Nun erzeugen wir ein zufälliges Wort, das genau so lang ist wie der zu verschlüsselnde Text: 

PADUGSNQHG

Auch dieses Wort rechnen wir in einen Zahlencode um, der dann wie folgt lautet: 

15 0 3 20 6 18 13 16 7 6

Wir addieren nun zur Zahlendarstellung des Klartextes die Zahlendarstellung des zufällig erzeugten Schlüssels und rechnen das Ergebnis in Buchstaben um. 

21 4 10 24 14 30 32 20 30 25

Das Problem ist, dass einige Ergebnisse nicht in Buchstaben umgerechnet werden können, da z. B. 30 kein Pendant im Alphabet hat. Das Problem lösen wir, indem wir die Ergebnisse modulo 26 rechnen. Was heißt das? a modulo b bedeutet so viel wie "gib mir den Rest der ganzzahligen Division von a geteilt durch b. 5 modulo 2 ist also 1, denn 5 geteilt durch 2 ist 2 Rest 1. 10 modulo 7 ist 3, denn 10 geteilt durch 7 ist 1 Rest 3. 25 modulo 5 ist 0, denn 25 geteilt durch 5 ist 5 Rest 0 (d. h. die Division geht auf). Warum machen wir das? Auf diese Weise erhält man ausschließlich Ergebnisse von 0 bis (einschließlich) 25. Näheres zur Modulo-Rechnung erfährst du in meiner Playlist zur Kryptologie. 

Wenn wir das Ergebnis der Addition modulo 26 nehmen, dann erhalten wir:

21 4 10 24 14 4 6 20 4 25

Wenn wir diesen Zahlencode nun in ein Wort zurückübersetzen, dann erhalten wir: 

VEKYOEGUEZ

Wie du siehst, erinnert dieser verschlüsselte Text nicht im Entferntesten mehr an das Original. Sogar die doppelten Buchstaben an den entsprechenden Stellen sind verschwunden! Nur, wenn man den Schlüssel kennt, kann man den verschlüsselten Text wieder in das ursprüngliche Wort übersetzen. Hierfür nimmst du quasi die Umkehroperation der Addition, nämlich die Subtraktion und subtrahierst von jeder Zahl in der Zahlendarstellung des Geheimtextes die entsprechende Zahl im Schlüssel.  Auf diese Weise erhältst du: 

6 4 7 4 8 -14 -7 4 -3 19

Jetzt haben wir das Problem, dass auf einmal negative Zahlen auftauchen. Das liegt daran, dass du das Ergebnis natürlich wieder modulo 26 rechnen musst. Dadurch ergibt sich: 

6 4 7 4 8 12 19 4 23 19

Übersetzt in Buchstaben ergibt sich wieder GEHEIMTEXT. Man hätte statt eines Schlüsselworts auch direkt einen Zahlencode generieren können, doch in Lehrbüchern wird das One-Time-Pad oft so eingeführt. Der von uns gewählte Zufallsschlüssel darf übrigens nicht erneut verwendet werden, es sei denn, er kommt noch einmal zufällig zustande. Wenn man immer denselben Schlüssel nutzt, öffnet das wieder Tür und Tor für statistische Analysen, wie wir bei anderen Verfahren noch sehen werden.

Nach Claude Shannon ist diese OTP-Verschlüsselung unknackbar (und somit theoretisch sicher), wenn der Schlüsselbitstrom (also die zufällige Bitfolge, die den Schlüssel bildet) die folgenden Bedingungen erfüllt: 

  1. Der Schlüssel ist ein echter Zufallsschlüssel. Es dürfen keine Perioden o. ä. enthalten und erkennbar sein.
  2. Der Schlüssel ist genauso lang wie der Klartext.
  3. Der Schlüssel wird nur einmal benutzt (deshalb auch One-Time-Pad).
  4. Der Schlüssel muss außerdem geheim bleiben.

Das One-Time-Pad erfüllt damit das Kerckhoffsche Prinzip, nach dem die Sicherheit eines Kryptosystems nicht von der Geheimhaltung des Algorithmus abhängen darf, sondern nur von der Geheimhaltung des Schlüssels. 

Die Variante mit den Texten ist eine von vielen Möglichkeiten der Implementierung des One-Time-Pads. Wie würde das aber für Dateien funktionieren? Mal angenommen, du hast eine PDF-Datei, die du perfekt sicher an jemanden übertragen möchtest. Wie kannst du diese PDF-Datei in ein Format bringen, auf das man das One-Time-Pad anwenden kann? Nun, der Computer rechnet ja bekanntlich nur mit Nullen und Einsen, d. h. jede Datei ist eine Ansammlung aus 8er-Paketen (Bytes) von Nullen und Einsen (Bits). Du überführst also zunächst die Datei in Nullen und Einsen. Danach generierst du dir einen zufälligen Schlüssel aus Nullen und Einsen. Da der Schlüssel genauso groß sein muss wie das "Wort" (hier also die Darstellung der zu verschlüsselnden Datei mit Nullen und Einsen), werden ggf. sehr viele Bits benötigt. Für eine 1 MB große PDF-Datei sind 1048576 Bytes (also 8388608 Bit) vonnöten. Um einen echten Zufallsschlüssel zu verwenden, kannst du einen Quantencomputer Bits erzeugen lassen oder Hardware-Module kaufen, die bspw. mit der Polarisation von Photonen Zufallszahlen erzeugen.

Wenn nun die Original-Datei und der Schlüssel vorliegen, dann führst du eine sogenannte XOR-Operation durch. Das ist eine logische Operation, die wie folgt funktioniert: 

  • Es gibt zwei Einganssignale (A und B). 
  • Wenn A und B beide 0 sind, dann ist auch A XOR B gleich 0.
  • Wenn A gleich 0 und B gleich 1 ist, dann ist A XOR B gleich 1.
  • Wenn A gleich 1 und B gleich 0 ist, dann ist A XOR B gleich 1.
  • Wenn A und B beide 1 sind, dann ist A XOR B gleich 0.

Die XOR-Operation (oder auch das "Exklusiv-Oder") funktioniert im Grunde wie eine Oder-Verknüpfung, nur dass im Fall, dass sowohl A, als auch B beide 1 sind, 0 herauskommt. 

Eine schöne Eigenschaft des XOR ist, dass es bei zweimaliger Ausführung das ursprüngliche Ergebnis liefert. D. h. wenn du einen Klartext A mit dem Schlüssel K durch Anwendung der XOR-Operation verschlüsseln möchtest, dann kannst du den entstandenen Geheimtext A'=A XOR K wieder entschlüsseln, indem du auf A' erneut die XOR-Operation mit dem Schlüssel K anwendest. 


3. Vor- und Nachteile

Vorteile

  • Das Verfahren ist perfekt sicher und gegen jeden mathematischen Angriff geschützt.
  • Das Verfahren ist unter Einhaltung der Schlüsselregeln auch resistent gegen Brute-Force-Angriffe. 

Nachteile/Angriffsmöglichkeiten

  • Das Verfahren ist sehr aufwendig und speicherintensiv. Wenn man z. B. eine 2 GB große Datei mit dem One-Time-Pad verschlüsseln möchte, dann muss man sich 2 GB randomisierte Daten erzeugen und diese auch speichern. Die Erzeugung des Zufallsschlüssels ist (je nach Verfahren) ebenfalls sehr rechen- und laufzeitintensiv.
  • Eine große Schwachstelle dieses Verfahrens ist der Schlüsselaustausch. Sobald jemand den Schlüssel in Erfahrung bringt, kann er den Geheimtext ebenfalls entschlüsseln. Das ist aber ein Problem der konkreten Umsetzung und nicht des mathematischen Gedankens dieses Verfahrens an sich. 
  • Je nach Wahl der Verschlüsselungsfunktion (z. B. das Verschieben von Buchstaben oder die bitweise XOR-Operation) werden Ergebnisse produziert, die nicht "verschlüsselt genug" sind. Hierzu in einem anderen Video mehr.