ef:kryptographie:schluesseltausch [DokuWiki CSC]

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
~~NOTOC~~
<WRAP center 1200px>
====== II. Das Schlüsseltauschproblem und seine Lösung ======
===== 1. Das Schlüsseltausch-Paradoxon =====
Das zentrale 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 (Eve) 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). 
<WRAP nicebox blue>
** Schlüssel-Austauschproblem **\\  
Wie können Alice und Bob einen gemeinsamen Schlüssel generieren (z.B. eine Zahl), sodass es einer Angreiferin (Eve) unmöglich ist, den Schlüssel zu finden, auch wenn sie jede Kommunikation mithört? 
</WRAP>
Lange dachte man, dass für dieses Problem keine Lösung existiert: \\ Wenn Eve alles mithört, 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** 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: \\ \\ 
{{ :ef:kryptographie:verschluesselung_farben.png?nolink&600|}}
** 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? **
  * A und B starten mit einem leeren Kanister, der drei Liter fasst. Eve wird ihrerseits einen Kanister mit drei Litern Inhalt besorgen.
  * A und B vereinbaren 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 A und B je eine geheime Farbe und mischen einen Liter davon in ihren Kanister. A wählt z.B. Rot und erhält eine dunkelblau-violette Mischung und B 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 B resp. A hinzugefügt haben. 
  * Nach dem Erhalt des Kanisters fügen A und B 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.
  
<WRAP nicebox green>
** Aufgabe 1** \\  
  - Warum kann Eve die gemeinsame Farbe nicht reproduzieren, indem sie jeweils eine Probe aus den Kanistern nimmt und diese mischt?  
  - Wenn man den Vorgang etwas mathematischer formuliert, so wenden Alice und Bob jeweils eine Funktion auf die Meldung (Farbe) $M$ an: Alice erhält $f(M)$ und Bob erhält $g(M)$. Nachdem sie nun jeweils das Ergebnis des Anderen erhalten, wenden sie wieder ihre Funktion darauf an. Welche Eigenschaft müssen dann die Funktionen $f$ und $g$ haben? 
  - Finde zwei mathematische Funktionen, welche diese Eigenschaft aufweisen. Warum sind wohl deine Funktionen für eine konkrete Umsetzung nicht allzu gut geeignet?  
  - Eve war es nicht möglich, die geheimen Farben zu finden, da man zwei Farben zwar sehr leicht mischen kann, aber dieser Prozess ist unheimlich schwer rückgängig zu machen. Finde andere Vorgänge aus dem Alltag, die diese Eigenschaft haben?
</WRAP>

===== 2. Die Umsetzung durch Diffie und Hellman =====

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 Einwegfunktionen bezeichnet werden. Zudem müssen die Funktionen, die Alice und Bob anwenden untereinander kommutativ sein, d.h. die Reihenfolge in welcher sie angewendet werden darf keine Rolle spielen. 

==== 2.1 Diskrete Exponentialfunktion und diskreter Logarithmus ====
Betrachtet man Exponentialfunktionen modulo p (diskrete Exponentialfunktionen) $f(x)=a^x \mod p$, so fällt auf, dass für einige $a$ und $p$ nur sehr wenige y-Werte entstehen, während für andere $a$ und $p$ als y-Werte alle Zahlen von 1 bin p-1 entstehen:  

Für $f(x) = 11^x \mod 19$ erhält man beispielsweise nur die drei Werte 1, 11 und 7 während man für $f(x)=3^x \mod 19$ alle Zahlen von 1 bis 18 erhält.  \\ 

<WRAP nicebox green>
** Aufgabe 2 ** \\ 
  - Bereche mit Python alle y-Werte der Funktion $f(x) = 23^x \mod 229$. Wie gross ist x, wenn man weiss, dass $f(x)$ = 144 ist?
  - Überlege dir, warum es sehr schwierig ist, für die Funktion von oben die x-Werte zu bestimmen, wenn y gegeben ist (diskreter Logarithmus).
</WRAP>

==== 2.2 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 eine private Information, die Alice und Bob für sich behalten. Der Schlüsseltausch funktioniert folgendermassen: \\ 
  - Alice und Bob vereinbaren eine Zahl $g$ und eine Zahl $p$ und tauschen diese aus. \\ Sie definieren damit eine Funktion $f(x) = g^x \mod p$ \\ Sie wählen beispielsweise $g = 53$ und $p = 127$ und erhalten die Funktion $f(x) = 53^x  \mod 127$.
  - Nun wählt jeder für sich eine geheime Zahl. Alice wählt z.B. **<color #ed1c24>A=101</color>** und Bob **<color #ffc90e>B=71</color>**.
  - Alice und Bob setzen ihre Geheimzahl in die Funktion ein. Alice erhält $f(101) = 53^{101} \mod 127 = 97$, Bob erhält $f(71)=53^{71} \mod 127 =48$.
  - Nun tauschen beide ihr Ergebnis aus, d.h. Alice schickt ihre Zahl **<color #264dc7>$\alpha = 97$</color>** an Bob und Bob schickt **<color #22b14c>$\beta = 48$</color>** an Alice.
  - Alice erhält die Zahl **<color #22b14c>$\beta = 48$</color>** von Bob und rechnet diese Zahl hoch ihre **<color #ed1c24>Geheimzahl</color>** (modulo  127). Sie erhält **<color #7f6000>91</color>**.
  - Bob erhält die Zahl **<color #264dc7>$\alpha = 97$</color>** von Alice und rechnet diese Zahl hoch seine **<color #ffc90e>Geheimzahl</color>** (modulo 127). Er erhält **<color #7f6000>91</color>**.

 {{ :ef:kryptographie:diffiehellman1.png?800 |}}

<WRAP nicebox green>
** 3. Aufgaben zum Schlüsselaustausch nach Diffie Hellman** \\ \\ 
  - Rechne das Beispiel von oben mit Python durch und überlege dir, warum beide dieselbe Zahl erhalten.\\  
  - Führe mithilfe von Python den Schlüsseltausch nach Diffie-Hellman durch mit **<color #00a2e8>$g=39, p=211,$</color> <color #ed1c24>$A=67$</color>, <color #ffc90e>$B=191$</color>**. Welchen gemeinsamen Schlüssel erhalten Alice und Bob? \\  
  - Führt in Zweiergruppen den Schlüsseltausch mit einem eigenen Beispiel durch. D.h. wählt Zahlen <color #00a2e8>$g$</color> und <color #00a2e8>$p$</color> und jeweils eine Geheimzahl $A$ bzw. $B$ und generieren Sie einen gemeinsamen Schlüssel.\\
  - Finde ein gutes Beispiel für $g$ und $p$, d.h. sodass die diskrete Exponentialfunktion alle Zahlen zwischen 1 und p-1 produziert. 
  - Alice und Bob vereinbaren g=1299 und p=1909. Sie tauschen Alpha=19 und Beta=1572 aus. Knacke das System, d.h. finde den gemeinsamen Schlüssel.
</WRAP>

==== 2.3 Welche Werte für g und p sind gut? ====
Wie kann man nun entscheiden, welche Kombination von g und p gut ist, d.h. wie weiss man, dass $f(x) = g^x \mod p$ alle Zahlen von 1 bis p-1 generiert ohne alle Zahlen ausrechnen zu müssen? Man spricht dann davon, dass $g$ ein Generator der Gruppe {1,2,3,... p-1} (Z modulo p) ist.

Hierfür gibt es den folgenden Satz:
=== Satz ===

Ist $q_1^{k1}\cdot q_2^{k2}\cdot q_3^{k3}\cdot ... q_n^{kn}$ die Primfaktorzerlegung von $p-1$, so ist $g$ genau dann ein Generator von Z modulo p, wenn $g^{(n-1)/q_i} \neq 1 \mod p$ für alle $q_i$. 

<WRAP nicebox green>
** Aufgabe 4** \\ \\ 
  - Versuche den Satz von oben zu verstehen. Formuliere in eigenen Sätzen, was du nicht verstehst. 
  - Zeige mit dem Satz von oben, dass $g=23$ und $p=229$ gute Werte sind, d.h. dass $g=29$ ein Generator ist. 
  - Nimm deine eigenen Beispiele aus der Aufgabe 2 und prüfe, ob die $g$- und $p$-Werte gut sind. 
</WRAP>

<WRAP nicebox blue>
Durch das Verfahren von Diffie und Hellman konnte das Schlüsselaustauschproblem gelöst werden: Alice und Bob können einen gemeinsamen Schlüssel erstellen, ohne dass Eve in der Lage ist, diesen Schlüssel nachzubilden. Danach können Alice und Bob geheime Botschaften mit einer symmetrischen Verschlüsselung und dem generierten Schlüssel sicher austauschen. \\ \\ 
Umgemünzt in unsere digitalisierte Welt bedeutet dies: Ein Client (mein Browser, die Whatsapp-App auf dem Handy etc.) kann mit einem Server (gmail-Server, Server von Whatsapp, etc.) einen Schlüssel erstellen (z.B. den 64Bit Hauptschlüssel für die DES-Verschlüsselung) und danach können die Daten mit diesem symmetrischen Verfahren ver- und entschlüsselt werden (wie erwähnt wird heute natürlich eher AES verwendet).
</WRAP>

<WRAP nicebox red>
Ein grundlegendes Problem wird durch den Schlüsselaustausch nach Diffie-Hellman **nicht** gelöst: die Möglichkeit einer **Man-in-the-middle-Attacke**.
Beschreibe, was eine "Man in the middle"-Attacke ist, und wie diese konkret beim Diffie-Hellman-Schlüsseltausch eingesetzt werden kann. 
</WRAP>


[[ef:start|Zurück zur Übersicht]]
</WRAP>