gf2: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>
======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 **.
<WRAP nicebox green> 
** Aufgabe ** \\ \\ 
Bearbeiten Sie die folgenden Fragen mündlich in Partnerarbeit
  - Was ist bei den uns bekannten Verfahren (Skytale, Fleissner, Gartenzaun, Monoalphabetische Verschlüsselung, Vigenère) jeweils der Schlüssel?
  - Begründen Sie, ob für die genannten Verfahren die Maxime von Kerckhoff jeweils erfüllt ist.
  - Was genau ist bei all diesen Verfahren genau das Schlüsselparadoxon? Erklären Sie kurz.
</WRAP>

===== 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
{{ youtube>_ZTWLAqYf9c}}


<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, 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 ====
{{ :gf2:martin-hellman.jpg?direct&100|}} {{ :gf2:whitfield_diffie_royal_society.jpg?direct&80|}} \\  \\ 
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: \\ \\ 
{{ :gf2: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? **
  * 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.
  
<WRAP nicebox green>
** Aufgaben zum Schlüsselparadoxon** \\ \\ 
  - Warum kann Eve die gemeinsame Farbe nicht reproduzieren, indem sie jeweils eine Probe aus den Kanistern nimmt und diese mischt? Hier kann der folgende [[https://www.inf-schule.de/kryptologie/modernechiffriersysteme/exkurs_diffie | Link]] helfen, das Farbbeispiel mit eigenen Farben durchzuprobieren =) \\ {{ :gf2:bob_farben_oeffentlich_privat.png?nolink&100|}} \\ \\ 
  - Bob hat die geheime Farbe in blau und hat mit Alice die gemeinsame Farbe Orange abgemacht. Wie gelingt es Ihnen, mit der Information der Farbmischung von Alice in Olivgrün die geheime Farbe von Alice herauszufinden? Warum ist dies nur möglich, wenn von Bob beide Informationen (gemeinsame und geheime Farbe) bekannt sind? Begründen Sie! {{ :gf2:alice_farbmischung.png?nolink&50|}}\\ \\ \\ \\ 
  - 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. Finden Sie andere Vorgänge aus dem Alltag, die diese Eigenschaft haben?
</WRAP>
<accordion>
<panel title="Lösung von Aufgabe 2:">
{{:gf2:loesung1.png?direct&400 |}} {{ :gf2:loesung2.png?direct&400|}}
</panel>
</accordion>
==== Die Umsetzung durch Diffie und Hellman ====
<figure Einwegfunktion>
{{:gf2:one_way_function.png?direct&400 |[[ https://computersciencewiki.org/index.php/One-way_function| Quelle]]}}
 <caption> [[ https://computersciencewiki.org/index.php/One-way_function| Quelle]] </caption>
</figure>



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\}$. \\ 
{{ :gf2:uhrzeiten.png?direct&200|}}

Telefonieren 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**.
----
<WRAP nicebox green>
** Aufgaben zu Modulo** \\ \\ 
  - Berechne jeweils die Lösung modulo 7: \\ \\ a)$ \quad 5+8 =  \hspace{1cm} b)\quad 8*5 =  \hspace{1cm} c)\quad 32*11 = \hspace{1cm} d)\quad 1234533 =  \hspace{1cm} e)\quad 2^{13} =  \hspace{1cm} f)\quad 5^{-1} =  $ \\ \\ 
  - Python rechnet mit dem %-Zeichen modulo. \\ Die Rechnung 17 modulo 5 wäre in Python also ''17 % 5''. Und $3^8$ modulo 7 wäre ''(3%%**%%8) % 7'' . \\ Wir betrachten die Funktion $f(x) = 11^x \mod 19$. Berechne mit Python alle y-Werte für $x=1,2,3,4...19$. (Thonny oder einen Python-online-Editor) \\ 
  - Nun betrachten wir die Funktion $f(x) = 3^x \mod 19$. Berechne wieder alle y-Werte, setzten Sie dazu die x-Werte in die Funktion ein. Was fällt dir auf? Halten Sie die wichtigsten Erkenntnisse in eigenen Worten fest. \\ \\ 
  - Man weiss, dass die Funktion $f(x) = 7^x \mod 97$ ist und dass der y-Wert 23 ist. Finden Sie den x-Wert? Welche Strategien zum Finden von x gibt es? Halten Sie die wichtigsten Erkenntnisse in eigenen Worten fest. 
</WRAP>
<accordion>
<panel title="Lösungen">
Aufgabe 1 auf Papier \\ 
Aufgabe 2 \\
Hier kann das kurze Pythonprogramm helfen: \\

<code python>
def funktion(base,mod):
    for i in range (20):
        print (base**i%mod)
</code>

Für Basis 11 und mod 19 fällt auf, dass es nur die drei Werte 1, 11 und 7 ergibt. (Es gibt somit nur drei sog. Restklassen) \\ 
Aufgabe 3 \\ 
Für die Basis 3 und mod 19 fällt auf, dass es alle Werte zwischen 1 und 19 einmal ergibt (somit wäre diese Wahl der Basis besser, da es mehr Restklassen gibt).\\ 
Aufgabe 4
Gemeinsam diskutieren ;)
</panel>
</accordion>

Link zum Video: https://youtu.be/bjWOG50PfdI
{{ youtube>bjWOG50PfdI}}

<WRAP nicebox blue>
**Feststellung:** Der grosse Vorteil der Modulo-Rechnung verglichen mit anderen Funktionen ist, dass diese nicht umkehrbar ist. Ist eine Zahl durch die Modulo-Funktion verändert worden, ist das Wiederherstellen dieser Zahl sehr schwierig. Eine einfach anwendbare Einwegfunktion ist gefunden!
(Diskretes Logarithmusproblem)
</WRAP>

==== Der Schlüsseltausch nach Diffie/Hellman ====
{{ verschluesselung_farben.png?nolink&600|}}
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:
  - Alice und Bob vereinbaren eine Zahl **<color #00a2e8>g</color>** und eine Zahl **<color #00a2e8>p</color>** und tauschen diese aus. \\ Sie definieren damit eine Funktion $f(x) = g^x$ und beschliessen, alles modulo p zu rechnen. \\ Sie wählen beispielsweise **<color #00a2e8>g = 53</color>** und **<color #00a2e8>p = 127</color>** und erhalten die Funktion $f(x) = 53^x$ und rechnen alle Resultate modulo **<color #00a2e8>127</color>**.
  - 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} \text{ mod } 127 = 97$, Bob erhält $f(71)=53^{71} \text{ 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>**.

 {{ :gf2:diffiehellman1.png?800 |}}

<WRAP nicebox green>
** Aufgaben zum Schlüsselaustausch nach Diffie Hellman** \\ \\ 
  - Rechnen Sie das Beispiel von oben mit Python durch und überlegen Sie sich, warum beide dieselbe Zahl erhalten.\\ \\ 
  - Führen Sie mit Hilfe 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ühren Sie jeweils in Zweiergruppen den Schlüsseltausch mit einem eigenen Beispiel durch. D.h. wählen Sie ein gemeinsame Zahlen <color #00a2e8>$g$</color> und <color #00a2e8>$p$</color> und jeweils eine Geheimzahl $A$ bzw. $B$ und generieren Sie einen gemeinsamen Schlüssel.\\ 
  - Schlüpfen Sie in die Rolle von Eve: lassen Sie sich von einer Gruppe die Zahlen <color #00a2e8>$g, p,$</color> <color #ed1c24>$\alpha$</color>, <color #ffc90e>$\beta$</color> geben, und versuchen Sie den Schlüssel dieser Gruppe zu knacken.
  - Kann <color #00a2e8>$p$</color> frei gewählt werden oder nicht? Was muss bei der Wahl von <color #00a2e8>$p$</color> beachtet werden, damit die Verschlüsselung nicht leicht zu knacken ist? Erfüllt ihr gewähltes<color #00a2e8> $g$</color> dieses Kriterium? Erklären Sie in eigenen Worten und anhand eines eigenen Beispiels.
  - Mit dem folgenden [[https://www.inf-schule.de/kryptologie/modernechiffriersysteme/exkurs_diffie|Link]] (unterer Teil der Website) kann das Diffie-Hellmann-Prinzip weiter geübt werden! 
  - Alice und Bob tauschen die Zahlen $g=29$ und $p=127$ aus. Danach sendet Alice $\alpha= 101$ an Bob und Bob $\beta = 83$ an Alice. Du als Eve hast dies alles mitbekommen. Knacke den Schlüssel von Alice und Bob mithilfe von Python.
</WRAP>
<WRAP nicebox blue>
Durch das Verfahren zum Schlüsselaustausch kann 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üsseulung und dem generierten Schlüssel sicher austauschen. \\ \\ 
Dies wird dadurch erreicht, dasss Alice und Bob sowohl eine öffentliche Information austauschen (p und g bzw. die Farbe Hellblau), als auch eine private Information für sich behalten (die Werte für die Geheimzahlen A und B, bzw. die geheimen Farben Gelb und Rot).
</WRAP>
</WRAP>

Weiter zu [[gf2:asymetrie_u_signatur|Asymmetrische Kryptographie und Digitale Signatur]]