Verschlüsselung auf Zeit

Vor ein paar Wochen stellte Klaus Schmeh in Klausis Krypto Kolumne ein Time-Lock-Verschlüsselungsverfahren vor. Um das Prinzip richtig zu begreifen, habe ich das alles nachprogrammiert, und wenn ich mir so viel Mühe mache, dann soll auch ein Blogeintrag dabei herauskommen. Ich bin kein Mathematiker oder Kryptologe und es ist nicht unwahrscheinlich, dass ich irgendwo Fehler drin habe; über Berichtigungen freue ich mich.

1. Wie man mit einem One-Time-Pad verschlüsselt

Cäsarische Schlüssel

Man verschiebt bei diesem Verfahren den Klartext zum Beispiel um eins nach rechts im Alphabet. Aus A wird B, aus B wird C, aus Z wird wieder A. So wird HALLO zu IBMMP.

Natürlich kann man auch um zwei nach rechts verschieben, dann wird aus HALLO: JCNNQ.
Es gibt, wenn wir von 26 Buchstaben ausgehen, 26 solche Cäsarsischen Schlüssel, einschließlich der Verschiebung um 0. Man sagt auch, der A‑Schlüssel verschiebt um 0 (weil A zu A wird), der B‑Schlüssel um 1 (weil A zu B wird), der C‑Schlüssel um 2 (weil A zu C wird), der Z‑Schlüssel um 25 (weil A zu Z wird).

Diese einfache Verschlüsselung ist überhaupt nicht sicher. Der häufigste Buchstabe im Deutschen ist “e”, und der häufigste Buchstabe in dem derart verschlüsselten Text wird dann wohl dem “e” entsprechen, und das gilt für die restlichen Buchstaben ebenso.

Vigenère-Verschlüsselung

Sicherer ist das Verfahren, wenn man nicht jeden Buchstaben um den gleichen Wert verschiebt. Das geht am einfach mit einem geheimen Schlüsselwort, sagen wir: HALLO. Dabei entspricht H dem Cäsarischen H‑Schlüssel, A dem A‑Schlüssel, und so weiter. Man schreibt das Schlüsselwort wiederholt unter den Klartext und verschiebt dann den Buchstaben des Klartexts jeweils so, wie es dem entsprechenden Cäsar-Schlüssel darunter entspricht.

Klartext:  ICHBINGEHEIM
Schlüssel: HALLOHALLOHA
Geheim:    PCSMWUGPSSPM

Das ist schon schwerer zu knacken, aber auch lösbar. Wenn man erst einmal herausgefunden hat, wie lang das Schlüsselwort ist, geht das dann wie oben durch Häufigkeitsanalyse.

Das One-Time-Pad

Ganz sicher, und prinzipiell nicht zu knacken, ist diese Art der Verschlüsselung dann, wenn das Schlüsselwort genau so lang wie der Klartext ist, oder auch noch länger. Außerdem muss es aus wirklich zufälligen Zeichen bestehen, darf also sicher kein Wort oder Text der deutschen Sprache sein, und darf natürlich nur ein einziges Mal benutzt werden. Für die nächste Nachricht reißt man dann den nächsten langen Schlüssel von seinem Block.
Dann heißt das Verfahren “One-Time-Pad”. Das Problem ist dabei nur, wie bei allen symmetrischen Verschlüsselungsverfahren, dass Sender und Empfänger beide über das gleiche One-Time-Pad verfügen müssen, das auf einem sicheren Weg übermittelt werden muss und nicht abgefangen werden darf.

2. Das gleiche nochmal mit Zahlen

Eigentlich machen sie eh alles mit Zahlen und sind nur so nett, diese Zahlen für uns als Buchstaben oder Grafiken auf dem Bildschirm darzustellen. Nach einem standardisierten Codierungsverfahren entspricht dem Buchstaben “H” etwa die Zahl 72. Und die Zahl 72 wird intern im Computer im Binärsystem als 1001000 dargestellt (8 bit lang) – für Menschen etwas übersichtlicher ist die Darstellung im Hexadezimalsystem als 48.

Das Wort HALLO in verschiedenen Darstellungsformen:

(1) Text:        H  A  L  L  O
(2) Dezimal:     72 65 76 76 79
(3) Hexadezimal: 48 41 4c 4c 4f
(4) Binär:       1001000 1000001 1001100 1001100 1001111

Dabei ist (1) das für den Menschen am leichtesten lesbar und (4) das für den Computer am leichtesten. Man trifft sich oft in der Mitte bei (3) – dabei entsprechen den 8 einzelnen bit im Binärsystem jeweils zwei Ziffern im Hexadezimalsystem (wo es 16 Ziffern gibt, 0–9 und A‑F).

Der Klartext ICHBINGEHEIM sieht dann so aus:

Klartext:       I  C  H  B  I  N  G  E  H  E  I  M 
Klartext (hex): 49 43 48 42 49 4e 47 45 48 45 49 4d

Das Ver- und Entschlüsseln läuft über Zahlen, also eigentlich über das Binärsystem, aber lesbarer ist das im Hexadezimalsystem. Da sieht die Verschlüsselung mit einem Schlüsselwort, das mindestens so lang ist wie der Klartext (also einem One-Time-Pad entspricht), so aus: Der Klartext wird erst in Zahlen umgewandelt, dann wird das Schlüsselwort – ebenfalls eine Zahl – darauf angewendet, und die entstandene Zahl ist dann der Geheimtext:

Klartext:       I  C  H  B  I  N  G  E  H  E  I  M 
Klartext (hex): 49 43 48 42 49 4e 47 45 48 45 49 4d
Schlüsselwort:  43 c2 43 47 33 32 c1 1f 5d c9 39 e2
Geheimtext:     0a 81 0b 05 7a 7c 86 5a 15 8c 70 af

Dabei funktioniert das Verschieben über die XOR-Funktion. Schauen wir uns das erste I an: Aus dem Klartext 49 wird unter Anwendung des Schlüssels 43 der Geheimtext 0a. Binär ausgedrückt:

    1001001 ("I" binär)
    1000011 (Schlüssel binär)
-----------
    0001010 (Ergebnis der XOR-Funktion, entspricht 0a hexadezimal)

Die XOR-Funktion ist hier wie eine Addition ohne Übertrag: Aus 1 und 1 wird 0, aus 0 und 0 ebenso; aus 1 und 0 (oder 0 und 1) wird 1.

Zusammengefasst:
Klartext => Umwandlung in Zahl => XOR-Verechnung mit Schlüsselzahl (ensteht: Geheimtext als Zahl)

Die Entschlüsselung läuft dann einfach rückwärts ab:
Geheimtext als Zahl => XOR-Verechnung mit Schlüsselzahl => Umwandlung in Text (entsteht: Klartext)

3. Das Time-Lock-Puzzle

Die Aufgabe

Ron Rivest verschlüsselte 1999 einen Text, dessen Entschlüssselung prinzipiell lösbar ist, die aber 35 Jahre kontinuierlicher Berechnung braucht, die nach dem Mooreschen Gesetz (Wikipedia) zu erwartenden Fortschritte im Bereich der Computerentwicklung inbegriffen. Man kann mit dem Verfahren im Prinzip einstellen, wie lange die Entschlüsselung eines Textes dauern soll. (Hier ist der ursprüngliche Beitrag von Ron Rivest, in dem dieser das Rätsel erklärt und Java-Code zu Erzeugen ähnlicher Aufgaben zur Verfügung stellt.)
So ein Time-Lock-Rätsel ist also quasi das genaue Gegenteil des in Agentenkreisen beliebten “Diese Nachricht zerstört sich in nach einer festgelegten Zeitspanne selber”, nämlich ein: “Diese Nachricht wird in einer festgelegten Zeitspanne lesbar (wenn man fleißig rechnet)”.

Also: Gegeben ist der verschlüsselte Geheimtext, als Zahl, so wie oben gezeigt. Gesucht ist das geheime Schlüsselwort, mindestens so lang wie der Klartext, siehe oben, ebenfalls als Zahl. Wenn man das Schlüsselwort gefunden hat, wendet man die XOR-Funktion auf die beiden Zahlen an und wandelt das Ergebnis in Text um (nach dem ASCII-Standard, der bestimmt, welche Zahl welchem Buchstaben entspricht).

Das Schlüsselwort ist allerdings keine beliebige, völlig zufällige Zahl, wie das bei einer echten Einmalverschlüsselung der Fall wäre. Sondern man erhält Hinweise, wie man die Schlüsselwort-Zahl berechnen kann, nur dass das eben 35 Jahre dauert, wenn man 1999 angefangen hätte. Diese Angaben bestehen aus einer Zahl t und einer Zahl n. Dann muss man nur berechnen:

$latex w = 2^{(2^t)} \mod{n}&s=3$

Dabei steht mod für “Modulo” und entspricht dem Rest, der bei der Teilung durch n übrig bleibt. Man muss also zuerst das vordere berechnen, dann durch n teilen, und der Rest, der bei der Teilung übrig bleibt, ist die gesuchte Zahl w – der Schlüssel.

Warum das 35 Jahre dauert

Wenn die Zahlen t und w klein sind, geht das Berechnen schnell. Sie müssen also schon groß sein. Und wenn die Zahlen bestimmte bekannte Eigenschaften haben, gibt es mathematische Abkürzungen, wie man das schnell lösen kann, auch wenn die Zahlen groß sind; dazu später mehr.
Allgemein ist das Problem: $latex 2^{(2^t)} \&s=1$ kann man mit dem Computer überhaupt nicht berechnen, wenn t einigermaßen groß ist. Irgendwann reicht der Speicherplatz nicht mehr aus, um die Zahl überhaupt nur zu speichern.
Aber uns geht es ja auch nicht um $latex 2^{(2^t)} \&s=1$, sondern um $latex 2^{(2^t)}\mod{n}&s=1$ – und das lässt sich sehr wohl berechnen. Man rechnet 2 * 2 * 2 * 2… und zwischendrin immer wieder mal modulo n. So wird die Zahl, mit der der Computer arbeitet, nie größer als 2*n. Allerdings muss der Computer das wieder und wieder und wieder machen, es geht um 2t-1 Multiplikationsvorgänge jeweils gefolgt von einer Modulo-Division – bei den enstprechenden Werten von n und t eben 35 Jahre lang.

In der Originalaufgabe von Rivest werden übrigens folgende Werte verwendet:

n = 631446608307288889379935712613129233236329881833084137558899
    077270195712892488554730844605575320651361834662884894808866
    350036848039658817136198766052189726781016228055747539383830
    826175971321892666861177695452639157012069093997368008972127
    446466642331918780683055206795125307008202024124623398241073
    775370512734449416950118097524189066796385875485631980550727
    370990439711973361466670154390536015254337398252457931357531
    765364633198906465140213398526580034199190398219284471021246
    488745938885358207031808428902320971090703239693491996277899
    532332018406452247646396635593736700936921275809208629319872
    7008292431243681

t = 79685186856218

Damit gilt es, folgenden Geheimtext zu entschlüsseln (hier in Dezimalschreibweise, nicht hexadezimal):

z = 427338526681239414707099486152541907807623930474842759553127
    699575212802021361367225451651600353733949495680760238284875
    258690199022379638588291839885522498545851997481849074579523
    880422628363751913235562086585480775061024927773968205036369
    669785002263076319003533000450157772067087172252728016627835
    400463807389033342175518988780339070669313124967596962087173
    533318107116757443584187074039849389081123568362582652760250
    029401090870231288509578454981440888629750522601069337564316
    940360631375375394366442662022050529545706707758321979377282
    989361374561414204719371297211725179287931039547753581030226
    7611143659071382

Man berechnet w, wendet dann die XOR-Funktion auf w und z an, wandelt die entstandene Zahl in eine Hexadezimalzahl um und diese wiederum nach dem ASCII-Standard in Text, wo jeweils zwei Hexadezimalziffern einen Buchstaben ergeben.

Das Verschlüsseln und der Trick bei der Sache

Die Verschlüsselung funktioniert dann, wenn n das Produkt zweier (sinnvollerweise: hoher) Primzahlen p und q ist. Wer den verschlüsselten Text erstellt, wählt zwei hohe Primzahlen aus, multipliziert die, um n zu erhalten, berechnet dann w und verschlüsselt den Klartext damit. Dann gibt er sowohl den Geheimtext als auch n und t weiter.

Aber Moment – es geht doch gerade darum, dass der Schlüssel

$latex w = 2^{(2^t)} \mod{n}&s=3$

so schwer zu berechnen ist. Wie macht man das dann beim Verschlüsseln, da braucht man den Schlüssel doch auch? Wie gesagt: wenn n das Produkt zweier (hoher) Primzahlen p und q ist, dann lässt sich Formel für w auch so schreiben:

$latex w = 2^{(2^t\mod{(p‑1)(q‑1))}} \mod{pq}&s=3$

(Das ist so wegen Mathematik und ich muss es erst mal glauben.)

Und während die erste Formel schwer zu berechnen ist, weil entweder die Zahlen zu hoch werden oder 2t Schritte dafür nötig sind, ist die zweite Formel für den Computer ein Klacks. (Allerdings: Völlig trivial ist das Werkeln mit so hohen Zahlen auch nicht; glücklicherweise bringt Java die entsprechenden Funktionen dafür gleich mit.)
Das heißt, wenn man die beiden Faktoren p und q weiß, aus denen n zusammengesetzt ist, dann lässt sich w leicht berechnen. Sonst nicht.

Mögliche Abkürzungen

1. Kann man das abkürzen, indem man mehrere Rechner oder Prozessoren parallel daran arbeiten lässt?

Nein. Man muss das wirklich der Reihe nach berechnen.
Aus Rivests Beispiel (mit n = 11 * 23 = 254 und t = 10):

              2^(2^1) = 2^2 = 4 (mod 253)
              2^(2^2) = 4^2 = 16 (mod 253)
              2^(2^3) = 16^2 = 3 (mod 253)
              2^(2^4) = 3^2 = 9 (mod 253)
              2^(2^5) = 9^2 = 81 (mod 253)
              2^(2^6) = 81^2 = 236 (mod 253)
              2^(2^7) = 236^2 = 36 (mod 253)
              2^(2^8) = 36^2 = 31 (mod 253)
              2^(2^9) = 31^2 = 202 (mod 253)
w = 2^(2^t) = 2^(2^10) = 202^2 = 71 (mod 253)

Da kann einem kein anderer Rechner einen nennenswerten Teil der Arbeit abnehmen.

2. Könnte man nicht einfach n faktorisieren, also p und q herausfinden?

In dem Fall könnte man die schnellere Formel verwenden, ja. Aber diese Faktorisierung ist schwieriger, als man denkt, wenn es um eine Zahl geht, die das Produkt zweier hoher Primzahlen ist. Die Zerlegung einer solche Zahl mit 200 Dezimalstellen dauerte vor zehn Jahren noch anderthalb Jahre, achtzig Rechner waren daran beteiligt (Wikipedia). Die Faktorisierung einer Zahl mit 616 Stellen (so viele hat das n in Rivests ursprünglichem Rätsel oben) ist zur Zeit noch nicht möglich; die Zahl ist ungefähr 2048 bit lang und damit noch auf einige Jahre sicher – die Bundesnetzagentur empfiehlt noch bis zum Jahr 2020 Schlüssel der Länge 2048 bit, in Zukunft werden aber wohl 3000 bit verlangt werden (Wikipedia).

Und wenn irgendwann mal Quantencomputer mit großem Speicher kommen sollten, sieht das alles nochmal ganz anders aus, aber davon verstehe ich zu wenig.

(Anhang: BlueJ-Projekt zum Spielen, als Ergänzung zu Rivests eigenem Javacode, siehe oben.)

5 Antworten auf „Verschlüsselung auf Zeit“

  1. Ich habe diesen Beitrag mal meinem Freund Otto Forster von der LMU weiter geleitet, seines Zeichens emeritierter, aber noch aktiver Matheprofessor. Der hat sich, glaube ich, mal viel mit Verschlüsselung befasst.

  2. Das sieht genau nach den Grundlagen aus, von denen ich zumindest auch ein bisschen gehört habe. Beim RSA-Algorithmus, dem einzigen Beispiel, zu dem ich in der Schule manchmal komme, geht es genau um das gleiche Produkt zweier Primzahlen wie hier.

  3. An diesem Text ist rein gar nichts verschlüsselt, und noch weniger verklausuliert. Spannende Zusammenhänge, die mir immer ein wenig rätselhaft erschienen, auf verständliche Art und Weise dargestellt. Meinen Dank dafür!

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.