Ein Geheimnis vereinbaren, während alle zuhören
Das letzte Kapitel endete vor einer Mauer. Du und dein Freund braucht denselben Schlüssel, aber du kannst ihn nicht verschicken — dann liest der Lauscher mit. Verschlüsselt verschicken geht auch nicht, denn dafür brauchst du schon wieder einen Schlüssel. 1976 zeigten zwei Mathematiker, dass es diese Mauer gar nicht gibt. Du kannst ein Geheimnis vereinbaren, während alle mithören. Um nichts anderes geht es in diesem Kapitel, und am Ende hast du es selbst gemacht.
Wörter, die du gleich brauchst
- Schlüsselaustausch
- Zu zweit bei derselben geheimen Zahl landen, ohne dass diese Zahl jemals über die Leitung geht. Nicht: einen Schlüssel verschicken. Sondern: jeder rechnet sich getrennt einen aus, und die sind zufällig gleich.
- Gemeinsames Geheimnis
- Die Zahl, bei der ihr beide landet. Daraus machst du danach einen AES-Schlüssel, und dann bist du zurück im letzten Kapitel.
- Diffie–Hellman
- Der Name dieses Tricks, nach Whitfield Diffie und Martin Hellman, die ihn 1976 veröffentlichten. Oft zu DH abgekürzt.
- Uhrenrechnen (Modulo)
- Rechnen, bei dem du nach einer Grenze wieder bei 0 anfängst, so wie
eine Uhr nach 12 Stunden wieder bei 1 anfängt.
17 mod 12 = 5. Klingt nach einem Trick für Kinder; es ist der Motor unter dieser ganzen Sache, und du siehst gleich, warum.
Der Zaubertrick mit Farbe
Mit diesem Bild haben es die Erfinder selbst erklärt:
- Du und deine Freundin sucht euch zusammen und laut eine Farbe aus: Gelb. Alle hören das.
- Jeder von euch wählt heimlich eine eigene Farbe. Du Rot, sie Blau. Das sagst du niemandem.
- Jeder mischt seine geheime Farbe mit Gelb und schickt die Mischung zum anderen. Alle sehen Orange und Grün vorbeikommen.
- Du mischst das Grün, das du bekommen hast, mit deinem Rot. Sie mischt dein Orange mit ihrem Blau. Ihr landet beide bei genau demselben Braun.
Der Lauscher hat Gelb, Orange und Grün gesehen. Aber Farbe entmischen geht nicht — euer geheimes Rot und Blau bekommt er da nicht wieder heraus. Ihr habt ein gemeinsames Geheimnis, und sonst hat es niemand.
Von Farbe zu Zahlen
Farbe mischen ist leicht, entmischen unmöglich. Es gibt eine Rechnung mit genau dieser Eigenschaft: Potenzieren auf einer Uhr. Ersetz die Farben durch Zahlen, und du bekommst das hier, mit einer Uhr von 23:
| Farbe | Zahl | Wer weiß es? |
|---|---|---|
| Gelb (vereinbart) | g = 5 und p = 23 | alle |
| dein Rot | a | nur du |
| ihr Blau | b | nur sie |
| dein Orange | A = 5a mod 23 | alle, es geht über die Leitung |
| ihr Grün | B = 5b mod 23 | alle, es geht über die Leitung |
| das Braun | Ba mod 23 = Ab mod 23 | nur ihr beide |
Diese letzte Zeile ist der ganze Trick, und sie stimmt aus einem Grund, den du aus dem Matheunterricht schon kennst: (5b)a und (5a)b sind beide 5a·b. Du und sie, ihr macht dieselbe Multiplikation in einer anderen Reihenfolge, also landet ihr beim Gleichen.
Probier es selbst
Alles passiert in deinem Browser. Es wird nichts an den Server geschickt.
- Klick auf Ein Geheimnis vereinbaren. Die Demo spielt dich und Noor gleichzeitig: beide eine geheime Zahl, beide eine Rechnung.
- Schau dir die zwei untersten Zeilen an. Verschiedene Rechnungen, dieselbe Antwort.
- Klick noch ein paar Mal. Andere geheime Zahlen, anderes Ergebnis, und trotzdem links und rechts immer gleich.
- Klick auf Jetzt mit echten Schlüsseln. Derselbe Trick, aber auf der Kurve aus dem nächsten Kapitel und mit einem Geheimnis von 256 Bit.
Warum der Lauscher hängen bleibt
Er hat alles gesehen außer a und b. Er weiß, dass A = 5a mod 23 ist, und er will a. Auf einer Uhr von 23 ist das schnell erledigt: Er probiert 51, 52, 53… bis es passt. Höchstens 22 Versuche — so viele Exponenten gibt es.
Aber ohne Uhr wäre es genauso schnell erledigt — dann steigt das Potenzieren ordentlich an, und er kann einfach raten, wie groß a ungefähr ist. Es ist das Uhrenrechnen, das ihm alles kaputtmacht: Durch dieses Modulo springen die Ergebnisse kreuz und quer durcheinander, und die Größe von A sagt nichts mehr über a. Setz p auf eine Zahl mit 600 Stellen, und es gibt keinen anderen Weg, als alle durchzuprobieren. Das ist die Mauer, gegen die er läuft.
Was das löst und was nicht
| Löst es | Löst es nicht |
|---|---|
| Zwei Menschen, die sich nie getroffen haben, landen beim selben Schlüssel, und alle stehen daneben. | Mit wem du diesen Schlüssel vereinbart hast. An der Zahl klebte kein Name. Dafür brauchst du Kapitel 7.1. |
| Der Schlüssel geht nie über die Leitung, also kann er nicht abgefangen werden. | Jemandem etwas schicken, der nicht online ist. Das hier verlangt zwei Parteien, die gleichzeitig mitmachen. |
Diese erste Lücke ist keine Kleinigkeit. Wenn sich jemand in die Mitte setzt und mit euch beiden getrennt ein Geheimnis vereinbart, dann denkt ihr, ihr redet miteinander, während er alles mitliest. Er heißt Man-in-the-Middle, und ihn draußen zu halten ist ein Problem für sich — Kapitel 7.1.
Das hier ist keine Verschlüsselung. Es wurde nichts verschlüsselt und nichts entschlüsselt. Du hast nur einen Schlüssel vereinbart. Was du danach mit diesem Schlüssel machst, ist ganz normales AES aus Kapitel 4. Verwechsle das also nicht mit dem nächsten Kapitel, wo wirklich direkt mit einem Schlüssel verschlüsselt wird, den jeder haben darf. Zwei verschiedene Ideen, beide aus denselben Jahren, und sie werden ständig durcheinandergebracht.
Das ist Mathematik: der diskrete Logarithmus
Ein gewöhnlicher Logarithmus ist der Rückweg vom Potenzieren: Aus 5x = 125 holst du x = 3, und dein Taschenrechner macht das im Handumdrehen. Bau eine Uhr drumherum, und dieser Rückweg verschwindet. Aus 5x mod 23 = 8 folgt x = 6, aber es gibt keine Formel, die dir das gibt — du kannst nur probieren. Das heißt das diskrete-Logarithmus-Problem.
Das Verrückte ist: Niemand hat bewiesen, dass es schwer ist. Es hat nur in fünfzig Jahren niemand einen schnellen Weg gefunden. Die ganze Sicherheit des Internets ruht auf einer Vermutung — und darauf, dass sehr viele kluge Leute es versucht haben. Das ist Zahlentheorie, und sie ist eines der wenigen Fächer, in denen „niemand weiß es“ eine brauchbare Antwort ist.