Symmetrische und Assymetrische Schlüssel

Symmetrische Kryptografie

Wie wir in den vorangegangenen Kapiteln gesehen haben, ist die Geschichte der Kryptologie geprägt durch den Kampf zwischen der Kryptografie und der Kryptoanalyse. Als sicher geltende Verfahren wurden durch clevere Kryptoanalytiker geknackt und mussten stetig angepasst und verbessert werden. Alle bisher betrachteten Verfahren basieren auf einem gemeinsamen Prinzip: Mithilfe eines Schlüssels wird eine Nachricht durch Alice verschlüsselt und mithilfe desselben Schlüssels kann die Nachricht durch Bob entschlüsselt werden. Diese Art der Verschlüsselungstheorie nennt man deswegen symmetrische Verschlüsselung .

Das Schlüssel-Austauschproblem

Ein zentrales Problem der symmetrischen Kryptografie besteht darin, wie Alice und Bob einen gemeinsamen Schlüssel vereinbaren können, ohne dass jemand anderes in den Besitz dieses Schlüssels gelangt. Man muss dabei davon ausgehen, dass der Kanal zwischen Alice und Bob unsicher ist, d.h. dass jemand jede Kommunikation zwischen Alice und Bob mithört (wäre der Kanal sicher, könnte man ja direkt die Meldung darüber verschicken und man müsste keine Verschlüsselung verwenden).

Link zum Video: https://youtu.be/_ZTWLAqYf9c

Lange dachte man, dass für dieses Problem keine Lösung existiert: Wenn Eve alles mithört, was Alice und Bob vereinbaren, dann hat sie genau dieselben Informationen wie Alice und Bob und sie kann doch den Schlüssel ihrerseits auch erstellen? Man dachte also, dass die einzige Lösung sei, den Schlüssel selbst verschlüsselt zu übertragen, wofür man wiederum einen Schlüssel benötigen würde u.s.w. Man spricht deshalb auch vom Schlüsselaustausch-Paradoxon. Lange Zeit wurden die Schlüssel somit persönlich übergeben, was natürlich sehr umständlich ist.

Ein Gedankenexperiment zur Lösung des Schlüsseltauschproblems

Zirka vor fünfzig Jahren gab es einige verwegene Kryptografen, die daran glaubten, dass es eine Lösung für das Schlüssel-Austauschproblem geben könnte. Zwei von ihnen waren Whitfield Diffie und Martin Hellman (Siehe Video oben, Abbildungen rechts, Bildquelle: Wikipedia). Ihre leidenschaftliche Suche nach einer Lösung für das Schlüsselproblem führte die beiden zusammen und die Ergebnisse ihrer gemeinsamen Bemühungen sollten schliesslich in die Geschichte der modernen Kryptografie eingehen.

Das folgende, einfache Gedankenexperiment liess Diffie und Hellman hoffen, dass es eine Lösung für das Problem geben könnte:

Angenommen der Schlüssel bestehe aus einer bestimmten Farbmischung. Wie können Alice und Bob eine gemeinsame Farbe mischen, ohne dass Eve dieselbe Mischung herstellen kann?

• Alice und Bob starten mit einem leeren Kanister, der drei Liter fasst. Eve wird ihrerseits einen Kanister mit drei Litern Inhalt besorgen.
• Alice und Bob entscheiden sich für eine bestimmte Farbe (beispielsweise Hellblau) und füllen einen Liter dieser Farbe in den Kanister.
• Da Eve alles mithört, wird auch sie einen Liter Hellblau in ihren Kanister geben.
• Nun wählen Alice und Bob je eine geheime Farbe und mischen einen Liter davon in ihren Kanister. Alice wählt z.B. Rot und erhält eine dunkelblau-violette Mischung und Bob wählt Gelb und erhält eine grüne Mischung.
• Die beiden Kanister werden ausgetauscht.
• Eve sieht die Kanister mit den Farbmischungen, doch sie kann die Mischungen nicht „trennen“, d.h. sie kann nicht herausfinden, welchen Farbton Bob resp. Alice hinzugefügt haben.
• Nach dem Erhalt des Kanisters fügen Alice und Bob jeweils einen Liter ihrer geheimen Farbe hinzu und so erhalten beide genau dieselbe Farbe: eine Mischung aus 1 Liter Hellblau, 1 Liter Rot und 1 Liter Gelb. Alice und Bob haben also eine gemeinsame Farbe (Braun) generiert, ohne dass es Eve möglich ist, diese Farbe herauszufinden.

Die Umsetzung durch Diffie und Hellman

Quelle

Um die Idee aus dem Gedankenexperiment mit den Farbmischungen umsetzen zu können, benötigt man eine Funktion, die leicht auf eine Zahl angewendet werden kann, die aber nur sehr schwer rückgängig gemacht werden kann. Diese Funktionen können als Einwegfunktionene bezeichnet werden. Wir suchen somit eine Funktion, die nicht oder nur sehr schwer rückgangig gemacht werden kann. Versuchen wir es z.B. einmal mit der Quadratfunktion

Alice und Bob vereinbaren die Funktion $f(x) = x^2$ (gemeinsame Farbe). Alice nimmt die Geheimzahl $A=11$ und Bob die Geheimzahl $B=13$ (entspricht den geheimen Farben Rot/Gelb). Wenn nun beide ihre Geheimfarbe mit der vereinbarten Farbe „mischen“ (d.h. die Funktion ausführen) erhalten sie:

$ \alpha = f(11) = 11^2 = 121 $ (Alice) bzw. $ \beta = f(13) = 13^2=169 $ (Bob).

Wenn diese beiden Zahlen $\alpha, \beta$ (die gemischten Kanister) ausgetauscht werden, kann Eve die Geheimzahlen sehr einfach finden, da die abgemachte Quadratfunktion viel zu einfach rückgängig gemacht werden kann. Eve würde einfach rechnen:

$ a = \sqrt{121} = 11 \text{ bzw. } b = \sqrt{169} = 13 $ und schon hätte Eve die geheimen Informationen von Alice und Bob geknackt.

Die Quadratfunktion $f(x)=x^2$ eignet sich also nicht - sie ist viel zu einfach umkehrbar - und zwar durch die Wurzelfunktion $g(x) = \sqrt{x}$. Damit wir eine geeignete Funktion finden können, benötigen wir die sogenannte Modulo-Arithmetik.

Einführung in die Modulo-Arithmetik

Wie bereits erwähnt verschrieben sich Diffie und Hellman der Kryptographie, dem Schlüsselparadoxon und damit auch der Suche von diesen Einwegfunktionen (Hashfunktionen). 1976 veröffentlichten die beiden Ihre Idee eines sicheren Schlüsselaustausch im Paper „New Directions in Cryptography“, in welchem die beiden Ihre Idee von den Einwegfunktionen mit Hilfe der Modulo-Arithmetik und dem Lösen des Schlüsselproblems beschrieben.

Was genau bedeutet der Begriff „Modulo-Arithmetik“?

Beispiel zum Starten

Im Prinzip rechnen wir tagtäglich mit der Modulo-Arithmetik. Betrachten wir nämlich die vollen Stunden der Tageszeit, so stehen uns 24 Zahlen zum Rechnen zur Verfügung: $\{0,1,2,3..,22,23\}$.

Telefonieren nun zwei Freunde miteinander um 16:00 Uhr und beschliessen, sich in fünf Stunden zu treffen, so rechnen beide 16 + 5 = 21. Sie treffen sich also um 21:00 Uhr. Die Rechnung bezüglich der Tagesstunden entspricht genau derjenigen bezüglich der ganzen Zahlen.

Würden die beiden Freunde jedoch bei diesem Telefonat ein Treffen in elf Stunden vereinbaren, so sähe die Rechnung anders aus: 16 + 11 = 27 = 24 + 3 = 3. D.h. die Zwei würden sich um 3:00 Uhr treffen. Die Zeit wird modulo 24 gerechnet. Wird „der Bereich überschritten“, so beginnt es wieder von vorne und jede Rechnung ergibt Werte zwischen 0 und 23. Die Zahl 27 existiert also in diesem System gar nicht, sie ist mit der Zahl 3 identisch. Wenn wir also modulo 24 rechnen, so gilt 16+11 = 3.

Wenn die zwei Freunde um 15:00 Uhr telefonieren und ein Treffen in 139 Stunden vereinbaren, dann wird das Treffen (an einem bestimmten Tag) um 10:00 Uhr stattfinden:

15 + 139 = 154 ⇒ Sie treffen sich also um „154:00 Uhr“, da man aber immer bei 24 neu mit der Zählung beginnt, muss man sich überlegen, wie oft die 24 Stunden in den 154 Stunden Platz finden: Die Zahl 24 hat 6 Mal in 154 Platz und es bleiben 10 als Rest übrig: 154 = 6 · 24 + 10. D.h. das Ergebnis von 154 modulo 24 ist 10. Die Freunde treffen sich um 10:00 Uhr.

Natürlich kann man nicht nur modulo 12 oder modulo 24 rechnen, jede andre natürliche Zahl kann als „Modulozahl“ gewählt werden. Es geht wie bei den obigen Beispielen somit immer darum, den ganzzahlingen Rest der Division durch diese Modulozahl zu bestimmen, falls man eine „Zahl mod Modulozahl“ rechnet.

Beispiel zum Starten

19 mod 5 = 4, da 19:5=3 Rest 4 ergibt.
Anders gesagt 19-5-5-5=4 gleich $19-3 \cdot 5$=4, um so viel ist 19 grösser als die nächstkleinere durch 5 teilbare Zahl.

Link zum Video: https://youtu.be/bjWOG50PfdI

Der Schlüsseltausch nach Diffie/Hellman

Nun wollen wir uns an einem Beispiel den Schlüsseltausch nach Diffie und Hellman anschauen. Genau wie im Gedankenexperiment mit den Farben gibt es eine öffentliche Information, die Alice und Bob austauschen und es gibt eine private Information, die Alice und Bob für sich behalten. Der Schlüsseltausch funktioniert folgendermassen:

1. Alice und Bob vereinbaren eine Zahl g und eine Zahl p und tauschen diese aus.
   Sie definieren damit eine Funktion $f(x) = g^x$ und beschliessen, alles modulo p zu rechnen.
   Sie wählen beispielsweise g = 53 und p = 127 und erhalten die Funktion $f(x) = 53^x$ und rechnen alle Resultate modulo 127.
2. Nun wählt jeder für sich eine geheime Zahl. Alice wählt z.B. A=101 und Bob B=71.
3. Alice und Bob setzen ihre Geheimzahl in die Funktion ein. Alice erhält $f(101) = 53^{101} \text{ mod } 127 = 97$, Bob erhält $f(71)=53^{71} \text{ mod } 127 =48$.
4. Nun tauschen beide ihr Ergebnis aus, d.h. Alice schickt ihre Zahl $\alpha = 97$ an Bob und Bob schickt $\beta = 48$ an Alice.
5. Alice erhält die Zahl $\beta = 48$ von Bob und rechnet diese Zahl hoch ihre Geheimzahl (modulo 127). Sie erhält 91.
6. Bob erhält die Zahl $\alpha = 97$ von Alice und rechnet diese Zahl hoch seine Geheimzahl (modulo 127). Er erhält 91.