Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
| Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung | ||
| ef:kryptographie:schluesseltausch [2023/08/23 19:55] – lehmannr | ef:kryptographie:schluesseltausch [2025/09/18 09:47] (aktuell) – lehmannr | ||
|---|---|---|---|
| Zeile 1: | Zeile 1: | ||
| ~~NOTOC~~ | ~~NOTOC~~ | ||
| <WRAP center 1200px> | <WRAP center 1200px> | ||
| - | ====== | + | ====== |
| ===== 1. Das Schlüsseltausch-Paradoxon ===== | ===== 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). | 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). | ||
| Zeile 27: | Zeile 27: | ||
| ** Aufgabe 1** \\ | ** Aufgabe 1** \\ | ||
| - Warum kann Eve die gemeinsame Farbe nicht reproduzieren, | - Warum kann Eve die gemeinsame Farbe nicht reproduzieren, | ||
| - | - 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? | + | - 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? | - 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. | + | - 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. |
| </ | </ | ||
| Zeile 37: | Zeile 37: | ||
| ==== 2.1 Diskrete Exponentialfunktion und diskreter Logarithmus ==== | ==== 2.1 Diskrete Exponentialfunktion und diskreter Logarithmus ==== | ||
| - | Betrachten | + | Betrachtet |
| 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. | 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. | ||
| Zeile 43: | Zeile 43: | ||
| <WRAP nicebox green> | <WRAP nicebox green> | ||
| ** Aufgabe 2 ** \\ | ** 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? | + | - 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). | - Überlege dir, warum es sehr schwierig ist, für die Funktion von oben die x-Werte zu bestimmen, wenn y gegeben ist (diskreter Logarithmus). | ||
| </ | </ | ||
| Zeile 57: | Zeile 57: | ||
| - Bob erhält die Zahl **<color # | - Bob erhält die Zahl **<color # | ||
| - | {{ :gf2: | + | {{ :ef: |
| <WRAP nicebox green> | <WRAP nicebox green> | ||
| - | ** Aufgaben zum Schlüsselaustausch nach Diffie Hellman** \\ \\ | + | ** 3. Aufgaben zum Schlüsselaustausch nach Diffie Hellman** \\ \\ |
| - Rechne das Beispiel von oben mit Python durch und überlege dir, warum beide dieselbe Zahl erhalten.\\ | - 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 # | - Führe mithilfe von Python den Schlüsseltausch nach Diffie-Hellman durch mit **<color # | ||
| - Führt in Zweiergruppen den Schlüsseltausch mit einem eigenen Beispiel durch. D.h. wählt Zahlen <color # | - Führt in Zweiergruppen den Schlüsseltausch mit einem eigenen Beispiel durch. D.h. wählt Zahlen <color # | ||
| - Finde ein gutes Beispiel für $g$ und $p$, d.h. sodass die diskrete Exponentialfunktion alle Zahlen zwischen 1 und p-1 produziert. | - Finde ein gutes Beispiel für $g$ und $p$, d.h. sodass die diskrete Exponentialfunktion alle Zahlen zwischen 1 und p-1 produziert. | ||
| - | - Schlüpfe in die Rolle von Eve: lass dir von einer Gruppe die Zahlen <color # | + | - Alice und Bob vereinbaren |
| </ | </ | ||
| Zeile 74: | Zeile 74: | ||
| === 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^{q_i} \neq 1 \mod p$ für alle $q_i$. | + | 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> | <WRAP nicebox green> | ||
| - | ** Aufgabe | + | ** Aufgabe |
| - Versuche den Satz von oben zu verstehen. Formuliere in eigenen Sätzen, was du nicht verstehst. | - 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. | - Zeige mit dem Satz von oben, dass $g=23$ und $p=229$ gute Werte sind, d.h. dass $g=29$ ein Generator ist. | ||
| Zeile 85: | Zeile 85: | ||
| <WRAP nicebox blue> | <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. \\ \\ | 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, | ||
| </ | </ | ||
| + | |||
| + | <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" | ||
| + | </ | ||
| + | |||
| [[ef: | [[ef: | ||
| </ | </ | ||