Lernziele

• Sie haben mit unserem Vigenère-Cipher einen Schlüsseltausch erlebt und können erklären, wieso beide Parteien am Schluss den gleichen Schlüssel haben.
• Sie können das diskrete Logarithmusproblem beschreiben und was es zu einer "mathematischen Einbahnstrasse" macht. (Die Bedingungen für p und g werden nicht abgefragt.)
• Sie haben einen Diffie-Hellman-Schlüsselaustausch mit einfachen Zahlen absolviert und können ihn erklären.
• Sie verstehen den mathematischen Beweis der modularen Arithmetik und können die Denk-Abkürzung anwenden.
• Sie können zwei konkrete Beispiele nennen, die Diffie-Hellman-Schlüsselaustausche (oder moderne Weiterentwicklungen davon) verwenden.

Wir haben das Kerckhoffs-Prinzip kennengelernt: "Ein kryptografisches System sollte auch dann sicher sein, wenn alles darüber bekannt ist, ausser dem geheimen Schlüssel." Da stellt sich natürlich die Frage: Wie tauschen wir die Schlüssel aus?

Experiment mit unserem Vigenère-Cipher

Testen Ihres Programms

Wir werden die Grundidee zuerst mit unserem Vigenère-Cipher demonstrieren. Testen Sie, ob Sie das Verfahren gleich implementiert haben. Verschlüsseln Sie dazu folgenden Satz mit dem Schlüssel MeinSchluessel.

Wir treffen uns im Cybercafe, follow the white rabbit.

Sie sollten den gleichen Ciphertext wie Ihre Partnerin oder Ihr Partner erhalten. Wenn Sie den Cipher exakt nach der Vorgabe implementiert haben, erhalten Sie Eo|/hvns|k#4{{a&s|sG#o{xwulry&p~`px%6z|y&%Vo~tsvjoxo)B

Demonstration

Zur Veranschaulichung werden in der Kryptologie oft die Pseudonyme "Alice" und "Bob" verwendet. Nehmen wir an, die beiden kommunizieren ausschliesslich über offene Kanäle. Das bedeutet, dass Ihre gesamte Kommunikation ständig abgehört werden könnte! Wie könnten sich zwei Parteien trotzdem auf einen gemeinsamen geheimen Schlüssel einigen?

Befolgen Sie beide folgende Schritte:

1. Überlegen Sie sich als Einzelperson einen geheimen Schlüssel. Jede Person hat also einen Schlüssel, den nur sie kennt.
2. Vereinbaren Sie ein Startwort über den offenen Kanal. Dieses Startwort kennt also die ganze Welt!
3. Verschlüsseln Sie einzeln für sich das Startwort mit Ihrem privaten Schlüssel.
4. Schicken Sie Ihrer Partnerin oder Ihrem Partner Ihren Ciphertext. Die ganze Welt hört mit und sieht diesen Ciphertext!
5. Verschlüsseln Sie nun den Ciphertext, den Sie erhalten haben, mit Ihrem privaten Schlüssel.
6. Vergleichen Sie den Ciphertext, den Sie nun beide generiert haben. Sie sollten beide den gleichen Ciphertext erhalten! Das ist Ihr Schlüssel, den Sie nun beide für Ihre geheime Kommunikation verwenden können.

Besprechen und analysieren Sie!

1. Wieso funktioniert das? Diskutieren und erklären Sie sich das.
2. Was für Schwächen gibt es?

Lösung

1. Warum funktioniert das? Vigenère basiert mathematisch auf der fortlaufenden Verschiebung (Addition) von Zeichen. Die Addition ist kommutativ, d.h. die Reihenfolge spielt keine Rolle, z.B. $A + B = B + A$. Das Endergebnis ist identisch, egal ob zuerst Alices und dann Bobs Schlüssel angewendet wird oder umgekehrt.
2. Was für Schwächen gibt es? Unser Vigenère-Cipher ist als Schlüsselaustausch sehr schwach: Mit den ausgetauschten Ciphertexten und dem offenen Originalstartwort ist es ein Leichtes, die privaten Schlüssel von Alice und Bob herzuleiten. Man müsste bloss die Verschiebung der Buchstaben zählen und würde so direkt die geheimen Schlüssel der beiden Parteien erhalten.

Das Diskrete Logarithmusproblem (DLP)

Das Diskrete Logarithmusproblem (DLP) ist ein mathematisches Problem, das im Folgenden und in der Kryptografie generell eine zentrale Rolle spielt. Es besagt, dass es schwierig ist, den Exponenten $k$ zu finden, wenn man die Basis $g$, den Modulo $p$ und das Ergebnis $K$ kennt:

In anderen Worten, selbst wenn man $g$, $p$ und $K$ kennt, ist es schwierig, $k$ herauszufinden. Das DLP ist schwierig, weil es keine effizienten Algorithmen gibt, um den Exponenten $k$ zu berechnen, wenn $g$, $p$ und $K$ bekannt sind. Man kann nicht einfach herleiten, wie oft $k$ die Zahl um die Uhr von $\mod p$ gedreht hat.

Einfacher gesagt, ist das DLP wie eine Einbahnstrasse: Es ist sehr einfach, in eine Richtung zu kommen. Aber der Rückweg, also wieder herauszufinden, dass $k = 3$, ist aufwendig schwer.

Eine Analogie, die sich anbietet, ist folgende:

• Aus Kaffeebohnen und Milch einen Cappuccino zu machen, ist relativ einfach (wenn man es kann... 🧐).
• Aus einem Cappuccino wieder Kaffeebohnen und Milch zu machen, ist für Menschen unmöglich.

Bedingungen für p und g

Damit diese Einbahnstrasse sicher ist, sollte man p und g wie folgt wählen.

• Die Primzahl $p$ sollte gross sein, um die Sicherheit des Verfahrens zu gewährleisten. Eine typische Grösse für $p$ ist mindestens 2048 Bits. Das heisst: $2^{2048}$. Diese Zahlen sind extrem gross und werden in der Kryptografie verwendet, um sicherzustellen, dass es für Angreifer praktisch unmöglich ist, die Zahl zu erraten oder zu berechnen.

$2^{2048}$ als Zahl ausgeschrieben

32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656

Die Zahl hat 617 Stellen.

• Die Basis $g$ muss kleiner als $p$.
• $g$ sollte ein sogenannter "Generator" für $p$ sein. Das bedeutet, dass die Potenzen $g^k\mod{p}$ alle möglichen Reste (die zyklische Gruppe $\mathbb{Z}_p^*$) durchlaufen sollten.

Zusatz: Wann ist $g$ ein Generator $\mod{p}$?

$g$ ist ein Generator $\mod{p}$, wenn $g$ eine "primitive Wurzel" $\mod{p}$ ist. Das bedeutet: Die kleinstmögliche Potenz $k$, für die $g^k\mod{p} \equiv 1$, muss $p-1$ sein. Wieso? Weil das garantiert, dass alle Potenzen bis dahin $\mod{p}$ unterschiedliche Resultate erzeugen.

Zum Beweis überlegen Sie das kontrafaktisch: Stellen Sie sich vor, es gäbe zwei deckungsgleiche Potenzen $g^i \equiv g^j \mod{p}$ im Bereich $0 \leq i < j < p-1$. Daraus würde folgen, dass $g^{j-i} \equiv 1 \mod{p}$, also dass es eine Potenz $k$ gäbe, die $g^k\mod{p} \equiv 1$ erfüllt, aber kleiner als $p-1$ ist.

• In unseren Beispielen verwenden wir oft die Zahlen $g=2$ oder $g=5$, da diese Werte einfach zu berechnen sind und in vielen Fällen als Generatoren funktionieren.

Diffie-Hellman-Key-Exchange

Martin Hellman (links) und Whitfield Diffie (rechts) im Jahr 1977. (Bild: Chuck Painter/Stanford News Service)

Der Diffie-Hellman-Key-Exchange wurde 1976 von Martin Hellman und Whitfield Diffie veröffentlicht und revolutionierte die Kryptografie. Das Verfahren nutzt die Einbahnstrasse des DLP für den Schlüsselaustausch.

Schritte des Diffie-Hellman-Key-Exchanges

1. Vereinbarung der öffentlichen Parameter:

   • Eine Primzahl $p$ und eine Basis $g$ werden öffentlich bekannt gegeben.
   • Diese Parameter werden von beiden Parteien verwendet.

2. Erstellung der privaten Schlüssel:

   • Jede Partei wählt einen privaten Schlüssel $a$ (für Alice) und $b$ (für Bob).
   • Diese privaten Schlüssel bleiben geheim.

3. Berechnung der öffentlichen Schlüssel:

   • Alice berechnet $g^a \mod p = A$.
   • Bob berechnet $g^b \mod p = B$.

4. Austausch der öffentlichen Schlüssel:

   • Alice sendet $A$ an Bob.
   • Bob sendet $B$ an Alice.

5. Berechnung des gemeinsamen geheimen Schlüssels:

   • Alice berechnet $B^a \mod p = K_{ba}$
   • Bob berechnet $A^b \mod p = K_{ab}$
   • Beide berechnen den gleichen Schlüssel, da $K_{ab} =K_{ba}$

6. Schlussfolgerung und Fragestellung:

   • Zusammengefasst heisst das: $(g^a \mod p)^b \mod p = (g^b \mod p)^a \mod p$.

Interaktives Beispiel

Spielen Sie den Schlüsselaustausch gleich selbst durch, indem Sie die Schritte von Alice und Bob nachvollziehen. Bestimmen Sie gemeinsam mit einer Partnerin oder einem Partner die öffentlichen Werte $p$ und $g$ und definieren Sie dann Ihre eigenen privaten Parameter $a$ und $b$. Überprüfen Sie mit dem Modulo-Rechner, ob Sie zum gleichen gemeinsamen Schlüssel gelangen.

Geben Sie dazu im Rechner jeweils Schritt für Schritt die Basis, den Exponenten und die Modulo-Zahl ein.

Wieso funktioniert das?

Wir haben gesehen, dass $(g^a \mod p)^b \mod p = (g^b \mod p)^a \mod p$.

Intuitiv erinnert Sie das vielleicht an das Potenzgesetz: $(g^a)^b = (g^b)^a = g^{ab}$. Aber können wir uns sicher sein, dass das auch mit Modulo funktioniert?

Der Kern, wieso das funktioniert, ist eine Einsicht der modularen Arithmetik. Experimentieren Sie dazu zunächst selbst:

• Wählen Sie eine Zahl auf dieser Modulo-Uhr für $\mod{7}$ und rechnen Sie die Zahl hoch 2. Markieren Sie die Zahl, die Sie erhalten haben.
• Wählen Sie eine zweite Zahl aus dem gleichen Sektor und rechnen Sie die Zahl ebenfalls hoch 2.
• Wählen Sie eine dritte Zahl aus dem gleichen Sektor und rechnen Sie die Zahl ebenfalls hoch 2.

Was fällt auf?

Lösung

Alle Ergebnisse liegen in ein und demselben Sektor!

Herleitung

Wenn Sie Zahlen aus demselben Ursprungssektor mit der gleichen Zahl potenzieren, werden auch die Ergebnisse immer in einem gemeinsamen Ergebnissektor liegen.

Wieso?

Nehmen wir als Basis die Zahl 2 und potenzieren Sie mit 2.

$2^2 = 4$

Wenn wir nun die Zahlen aus demselben Ursprungssektor wie 2 anschauen, sind die alle um ein Vielfaches der Primzahl 7 grösser, z.B.

$$\begin{aligned} \textcolor{#9333ea}{0*7}+2&=2\\ \textcolor{#9333ea}{1*7}+2&=9\\ \textcolor{#9333ea}{2*7}+2&=16\\ \textcolor{#9333ea}{3*7}+2&=23\\ \textcolor{#9333ea}{4*7}+2&=30\\ ... \end{aligned}$$

Alle Zahlen des Sektors sind also ein Vielfaches von Sieben + 2. Der Modulo wird das Vielfache von Sieben immer eliminieren - sodass nach dem Modulo immer $2^2$ alleine stehen bleiben wird.

Mathematisch elegant bewiesen

Schauen wir das mal nicht nur für 7 sondern für alle möglichen Primzahlen $p$ an und versuchen wir, unsere These zu beweisen. Wie im 7ner-Beispiel oben unterscheiden sich also alle Zahlen desselben Sektors auf einer Modulo-Uhr $\mod{p}$ um ein Vielfaches von $p$. Ein solches Vielfaches können wir als $kp$ ausdrücken, wobei $k$ eine beliebige ganze Zahl ist ($k \in \mathbb{Z}$).

Die These lautet also:

$$(2+kp)^2 \equiv 2^2 \pmod{p}.$$

Klammern wir dazu mit der binomischen Formel aus:

$$(2+kp)^2 = 2^2 + 4kp + (kp)^2 = 2^2 + p(4k + k^2 p)$$

Der Term $p(4k + k^2 p)$ ist ein Vielfaches von $p$ — er fällt also beim Modulo $p$ immer weg. Übrig bleibt immer nur $2^2 = 4$.

Die Schönheit der Mathematik zeigt sich, wenn Sie bemerken:

• Das gilt ja nicht nur für den Exponenten 2! Für jeden Exponenten $n$ ergibt das Ausmultiplizieren von $(2+kp)^n$:

  $$(2+kp)^n = 2^n + \underbrace{\text{(Terme, die alle mindestens einen Faktor } kp \text{ enthalten)}}_{\text{Vielfaches von } p}$$

  Jeder dieser Terme ist also ein Vielfaches von $p$ und verschwindet beim Modulo. $\mod p$ bleibt immer nur $2^n$ übrig!

• Das gilt nicht nur für 2 - sondern für alle möglichen Restwerte von $p$ ! Mit 3 wäre das:

  $$(3+kp)^2 \equiv 3^2 \pmod{p}$$

Abkürzen dank modularer Arithmetik

Wenn Sie dieses Prinzip verinnerlicht haben, können Sie folgende Frage relativ einfach beantworten:

In welchem Sektor der 7-Modulo-Uhr liegt das Ergebnis von $51^3$ ?

51 liegt im Sektor 2, weil $51\mod{7} = 2$.

Sie können $\textcolor{red}{51}^3\mod{7}$ also auf $\textcolor{red}{2}^3\mod{7}$ abkürzen, also $8\mod{7}=1$.

Diffie-Hellman im Alltag

Nach all dieser Theorie drängt sich die Frage auf: "Wann benutze ich das jemals?" Die Antwort lautet: Jeden Tag, auf unzähligen Geräten! Der Diffie-Hellman-Schlüsselaustausch (oder moderne Weiterentwicklungen davon) ist das Rückgrat unserer alltäglichen digitalen Sicherheit. Schauen wir uns zwei prominente Beispiele aus Ihrer Lebenswelt an, bei denen Sie Kryptologie hautnah erleben.

1. Messenger-Apps (Signal, WhatsApp)

Wenn Sie eine Nachricht über Signal oder WhatsApp verschicken, ist diese „Ende-zu-Ende" verschlüsselt. Das bedeutet, nur Sie und Ihr Chat-Partner können die Nachrichten lesen – nicht einmal die Betreiber der App. Die technische Grundlage dafür bildet das sogenannte „Double Ratchet"-Protokoll. In diesem Protokoll kommt Diffie-Hellman zum Einsatz – aber nicht nur einmal bei der Anmeldung, sondern fortlaufend während des Chatverlaufs.

Das Prinzip lässt sich so zusammenfassen: Jede Nachricht hat ein eigenes Schloss, das danach weggeworfen wird.

Konkret arbeitet das Double Ratchet mit zwei Mechanismen zusammen:

• Erstens einem DH-Ratchet, bei dem periodisch ein neuer Diffie-Hellman-Austausch stattfindet und frisches Schlüsselmaterial erzeugt.
• Zweitens einer symmetrischen Schlüsselkette (KDF-Chain), aus der für jede einzelne Nachricht ein frischer Einmal-Schlüssel deterministisch abgeleitet wird.

Dieser Mechanismus bietet, was man Forward Secrecy nennt („Geheimhaltung nach vorne" in die Zukunft): Selbst wenn eine Angreiferin heute Ihren privaten Schlüssel stiehlt, oder später Ihr Schlüssel bekannt wird, können Ihre vergangene Nachrichten trotzdem nicht entschlüsselt werden! Die alten Schlüssel wurden für immer vernichtet.

2. Sicheres Surfen (HTTPS mit TLS-Handshake)

Jedes Mal, wenn Sie im Internet surfen und oben in der Adresszeile das kleine Schloss-Symbol sehen (HTTPS), baut Ihr Browser eine sichere Verbindung zum Server auf. Hier passiert der sogenannte TLS-Handshake (Transport Layer Security) in den ersten Millisekunden der Verbindung.

Bei praktisch allen modernen Webseiten kommt dabei eine Form des Diffie-Hellman-Austauschs zum Einsatz, am häufigsten ECDHE (Elliptic Curve Diffie-Hellman Ephemeral). Das kleine "E" (Ephemeral = flüchtig, kurzlebig) bedeutet auch hier, dass genau wie bei Signal für jede neue Verbindung ein neuer, einmaliger Schlüssel ausgehandelt wird. Das sichert Forward Secrecy im Browser.

Übung: Schlüsselaustausch live im Browser untersuchen

Sie müssen das nicht einfach glauben – Sie können diesen unsichtbaren Schlüsselaustausch direkt nachprüfen!

1. Öffnen Sie in Ihrem Browser (z.B. Chrome, Edge, Firefox) eine neue Webseite, idealerweise eine mit sensiblen Daten wie Ihre Bank, oder auch einfach Wikipedia.
2. Öffnen Sie die Entwicklertools (Chrome/Edge: Drücken Sie F12 oder Ctrl+Shift+I / Cmd+Option+I auf dem Mac).
3. Suchen Sie oben im neuen Entwickler-Fenster den Reiter Security (Sicherheit). Wenn er nicht direkt sichtbar ist, klicken Sie auf das Doppel-Pfeil-Symbol >> um weitere Tabs anzuzeigen.
4. Klicken Sie im linken Menü (falls vorhanden) auf die Haupt-URL (Main origin) der Webseite, um die Verbindungsdetails aufzurufen.
5. Schauen Sie unter der Überschrift "Connection" (Verbindung).
6. Achten Sie auf den Key Exchange (Schlüsselaustausch). Ziemlich sicher werden Sie dort ein Krypto-Kürzel wie ECDHE oder X25519 finden. Das ist Diffie-Hellman, der gerade eben für Ihren speziellen Aufruf verhandelt wurde!

Surfen Sie auf verschiedene Seiten und vergleichen Sie den Key Exchange. Nutzen alle modernste Verfahren? Finden Sie Unterschiede?