Der Schlüsselmacher

Wie schafft man es, eine Nachricht an einen bestimmten Empfänger zu schicken, ohne daß ein unbefugter Dritter sie lesen oder gar modifizieren kann? Richtig, man bedient sich der Verschlüsselung. Wie aber funktioniert das genau?

Ich versuche es heute, an kleinen anschaulichen Beispielen zu erklären. Die Protagonisten sollen Anne, die Absenderin der Nachrichten, Bernd, der Empfänger der Nachrichten, und Christian, der potentielle Angreifer, Abfänger der Nachrichten, sein. Später wechselt die Parteizugehörigkeit von Bernd und es kommen noch Dirk und Erik hinzu.

Merkles Rätsel

Vor einiger Zeit ging Anne auf eine Party. Anne ist Psychologie-Studentin, ca. 1,67m groß, schlank, trägt lange dunkle Haare und hat rehbraune Kulleraugen. Auf besagter Party sprach sie ein junger Herr namens Bernd an. Bernd, seines Zeichens BWL-Student, ca. 1,77m groß, ebenfalls schlank, hellblondes ohrlanges Haar, blaue Augen mit einem doch etwas merkwürdigem Gesicht. Aber dafür kann er nichts. Beide tauschten am Ende des Abends ihre Kontaktdaten aus.

Anne scheint von Bernd sehr angetan zu sein. Sie schwärmt ihrer besten Freundin vor, wie beeindruckend er doch sei und möchte sich unbedingt mit ihm wieder treffen. Ihre beste Freundin mahnte an, daß sie Vorsicht walten lassen solle. Immerhin sei Christian, Annes Ex-Freund, immer noch hinter ihr her und würde nichts unversucht lassen, Anne nicht in fremde/neue Hände geraten zu lassen.

Natürlich sah sie das ein, aber der Drang, Bernd wiederzusehen, ist einfach zu groß. So beschließt sie, ihre Nachricht einfach verschlüsselt zu übermitteln. Sie besinnt sich an ein Verfahren von Merkle und umgehend kontaktiert Bernd.

Inzwischen hat Christian davon mitbekommen und läßt Anne das auch gleich spüren, indem er droht, ein geplantes Date zum Platz zu bringen.

Bernd läßt nun seine gewaltigen Kenntnisse aus seinem Nebenfach Wirtschaftsinformatik spielen und generiert 2²⁰ Nachrichten der Form (Rätsel x, Schlüssel y). Frohlockend codiert er nun alle 2²⁰ Nachrichten mit je einem Schlüssel z und schickt Anne diese lange Liste.

Anne wählt willkürlich eine der verschlüsselten Nachrichten aus und wendet das Brute-Force-Verfahren an, um sie zu entschlüsseln bzw. zu knacken. [Mittels Brute-Force werden alle möglichen Varianten durchprobiert.] Dafür braucht ihr Laptop durchaus eine Weile, aber sie wollte derweil eh unter die Dusche springen, sich zurechtmachen und ins Schminktäschchen greifen. Nach ca. 1h vermeldet ihr Laptop schließlich Vollzug und präsentiert ihr das Rätsel und den zugehörigen Schlüssel.

Bernd, auch er hat sich inzwischen geduscht, rasiert und eines leider recht billigen Parfüms bedient, hat das Rätsel x_k von ihr erhalten und kann nun in seiner Liste nachschauen, welcher Schlüssel y der zugehörige zum x ist. Dieses ist somit der geheime Schlüssel, mit den die geheimen Nachrichten zukünftig von beiden entschlüsselt werden können.

Christian hat indes natürlich den gesamten Datenverkehr abgefangen und steht nun vor einem riesigen codierten Datenhaufen. Auch er kennt die Möglichkeiten des Brute-Force-Verfahrens, allerdings muß er sämtliche verschlüsselten Rätsel knacken, ehe er herausfinden kann, welches der verwendete Schlüssel von Anne ist. Dafür müßte er im Durchschnitt 2¹⁹ solcher Angriffe durchführen, die insg. 2¹⁹ Stunden – also knappe 60 Jahre – dauern würden.

Noch am selben Abend treffen sich Anne und Bernd in einer Cocktailbar und genießen die schöne gemeinsame Zeit.

Diffie-Hellman-Schlüsselaustausch

Es vergehen einige Tage, Wochen und Anne will Bernd wiedertreffen. Sie hat allerdings herausgefunden, daß Christian sich einen neuen Computer zugelegt hat, mit welchem er deutlich schneller verschlüsselte Nachrichten knacken kann. So beschließt sie, ein neues Verfahren anzuwenden, bei dem die Schlüsselvereinbarung leichter von statten geht und Christian es schwerer hat, die Nachrichten zu knacken.

Hierfür wählt Anne nun eine große Primzahl p sowie eine weitere große Zahl g aus, die kleiner als die Primzahl p und die sogenannte Primitivwurzel mod p ist. Sie wählt eine weitere große Zahl x aus und berechnet damit X = g^x mod n. Sie verschickt nun das berechnete X, die Primzahl p und die Primitivwurzel g an Bernd.

Er wählt nun eine Zahl y und bestimmt Y = g^y mod p. Dieses Y schickt er wiederum Anne.

Sie berechnet nun k = Y^x mod p und er derweil k = X^y mod p.
Dröselt man diese Formeln auf, stellt man etwas Erstaunliches fest: k = X^y mod p = (g^x mod p)^y mod p.
Das läßt sich verkürzen zu: k = g^xy mod p.
Erweitert man das, erhält man: k = (g^y mod p)^x mod p.
Und das ist nichts anderes als: k = Y^x mod p.
Damit sind beide berechneten k identisch und Anne kann mit Bernd bedenkenlos verschlüsselte Nachrichten austauschen, da nur sie Kenntnis vom k haben, weil das x und das y geheim gehalten werden, die zur Berechnung des k unabdingbar sind. Damit Christian das x bzw. das y berechnen kann, müßte er zunächst den diskreten Logarithmus berechnen. [Für den diskreten Logarithmus besteht bis heute kein effizientes Lösungsverfahren.]

Überwältigt von dieser atemberaubenden Nachrichtenvermittlung, treffen sich Anne und Bernd am nächsten Abend im Kino und schauen sich dort den neusten Tarantino-Film an. Bei einem Bier danach in der Kneipe ihres Vertrauens frohlocken sie über ihren Einfallsreichtum und über den angestauten Ärger von Christian, der keine Möglichkeit mehr hat, die verschlüsselte Kommunikation von den beiden zu belauschen.

Man-in-the-Middle Angriff

Die Zeit streicht ins Land. Anne und Bernd verlebten einige gemeinsame Monate in Eintracht und Harmonie. Doch nichts währt ewig. So ging auch diese Beziehung auf kurz oder lang in die Brüche. Christian hat inzwischen sein Glück woanders finden können, so daß Anne endlich vor ihm Ruhe hat. Leider ist Bernd nun derjenige, der nicht über die Trennung so leicht hinwegkommen kann und paradoxerweise die Position von Christian einnimmt – die des paranoiden Ex-Freundes.

Inzwischen hat Anne nämlich jemand Neues kennengelernt. Es ist Dirk, Jura-Student, 1,87m groß, kräftig, trägt einen neckischen 3-Tage-Bart, hat schwarzes Haar und dunkle Augen. Auf einer WG-Feier von dessen bestem Freund begegneten sich die beiden zufällig vorm Kühlschrank, da sie sich je ein neues Bier holen wollten. Dirk, nicht auf den Mund gefallen, schaffte es auf Anhieb, bei Anne mit einigen flotten Bemerkungen einen bleibenden Eindruck zu hinterlassen.

Es sollte nun das altbekannte Spiel von vorn beginnen. Anne mußte sich einen Weg überlegen, wie sie mit Dirk kommunizieren kann, ohne daß Bernd mithört. Allerdings kommt diesmal erschwerend hinzu, daß eben jener Bernd inzwischen ein versierter Krypt-Analyst geworden ist.

Anne versucht sich nun an einem asymmetrischen Verfahren zum Schlüsselaustausch. Dazu sendet sie Dirk eine Anfrage, daß er ihr seinen öffentlichen Schlüssel k_pubD mitteilt.

Bernd fängt diese Nachricht natürlich ab. Er gibt sich als Dirk aus und schickt ihr seinen öffentlichen Schlüssel k_pubB. Die Nachricht von Anne schickt er an Dirk weiter.

Dirk geht davon aus, die Nachricht stammt von Anne und er schickt seinen öffentlichen Schlüssel k_pubD zurück an Bernd.

Anne verschlüsselt die geheime Terminvereinbarung mit dem öffentlichen Schlüssel k_pubB von Bernd und verschickt sie. Er fängt diese Nachricht wieder ab, kann sie mit seinem privaten Schlüssel k_privB entschlüsseln und damit lesen sowie ggf. modifizieren. Er verschlüsselt sie nun mit Dirks öffentlichem Schlüssel k_pubD und schickt sie an ihn weiter, die Dirks mit seinem privaten Schlüssel k_privD entschlüsseln kann.

Bernd kann so unbemerkt die Inhalte der geheimen Nachrichten von Anne und Dirk mitlesen. Da er dreist genug war und den Termin geändert hat, haben sich Anne und Dirk leider nicht nochmal getroffen. Dirk findet dieses Gehabe um die Geheimhaltung generell überzogen, allerdings weiß er auch nicht um Bernds hinterhältigen Absichten und vergißt Anne wieder, um sich vermeintlich leichteren Frauen zu widmen. Natürlich ist Anne betrübt, aber sie konnte diesmal nichts mehr daran ändern.

Interlock-Protokoll

An einem sommerlichen Herbsttag sitzt in einem Café der langhaarige Erik mit seinem rötlichen Kinnbart an Annes Nachbartisch. Interessiert verfolgt er die erheiternden Gespräche zwischen ihr und ihrer besten Freundin. Irgendwann bringt er sich dezent mit ein. Nur wenig später setzt er sich zu den beiden Damen, da er selbst ursprünglich alleine ins Café gegangen ist, um dort in einem Buch zu schmökern. Unter anderem geht es bei den Gesprächen um das letzte mißglückte Date von Anne. Erik hebt seine linke Augenbraue und merkt an, daß er da eine viel bessere Idee hat, mit der sowas zukünftig nicht mehr passieren würde.

So ganz suspekt ist ihr Erik nicht, aber Anne scheint dennoch irgendwie von seiner Erscheinung fasziniert zu sein. So kommt es, daß sie sich mit ihm wiedertreffen möchte, allerdings mehr deswegen, um seine Idee auszuprobieren. Sollte es nicht gelingen, wäre das für sie nicht so tragisch.

Wenig später senden sich die beiden ihre öffentlichen Schlüssel k_pubA bzw. k_pubE zu, verschlüsseln ihre geheimen Botschaften mit c_A = k_pubE{m_A} und c_E = k_pubA{m_E}. Beide teilen nun ihren Geheimtext in zwei Teile, c_A1 + c_A2 = c_A bzw. c_E1 + c_E2 = c_E.

Anne verschickt nun den ersten Teil c_A1 an Erik und wartet auf dessen ersten Teil c_E1. Danach sendet sie den zweiten Teil c_A2 an ihn und wartet auf seinen zweiten c_E2.

Jetzt können beide die zwei Geheimtextteile zusammensetzen und die geheime Terminvereinbarung entschlüsseln. Bernd ist natürlich wieder zur Stelle, fängt die Nachrichten ab und stellt erstaunt fest, daß sich am Vorgehen etwas geändert hat. Er fängt auch diesmal die öffentlichen Schlüssel k_pubA von Anne und k_pubE von Erik ab, ersetzt sie gegen seinen eigenen k_pubB, kann allerdings c_A1 nicht nicht ohne c_A2 rekodieren, denn das würde die Nachricht zerstören, so daß er sie nicht mehr unerkannt manipulieren kann.

Anne und Erik treffen sich am selben Abend noch ganz unverbindlich in einem Tanzlokal und machen dort zur Feier des Tages – immerhin wurde diesmal Bernd erfolgreich davon abgehalten, sich einzumischen – die Nacht zum Tag. Beide beschließen, sich nun häufiger auf diese Weise zu verabreden.