Diffie–Hellman: Ein Geheimnis in aller Öffentlichkeit

Alice sendet gᵃ mod p, Bob sendet gᵇ mod p, und beide gelangen zu gᵃᵇ mod p, ohne dass einer von ihnen diese Zahl verschickt hätte. Eve sieht jede Zahl auf der Leitung. Verfolge erst den Schlüsseltausch, dann ihren Angriff, und verändere p sowie g: Finde heraus, was ihre Suche so drastisch verkürzt.

Rechenbeispiel — Diffie–Hellman: Ein Geheimnis in aller Öffentlichkeit

Alices öffentliche Zahl	8
Bobs öffentliche Zahl	19
Das gemeinsame Geheimnis	2
Mögliche Werte des gemeinsamen Geheimnisses	22 von 22
Brute-Force-Versuche für dieses A	7 (im ungünstigsten Fall 22)
Pohlig–Hellman-Versuche für dieses A	8 (im ungünstigsten Fall 13)
Eves Geheimnis, berechnet aus ihrem x	2

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Diffie–Hellman: Ein Geheimnis in aller Öffentlichkeit

Beim Diffie–Hellman-Schlüsselaustausch vereinbaren zwei Parteien eine geheime Zahl über einen Kanal, den jeder mitlesen kann. Öffentlich legen sie eine Primzahl p und eine Basis g fest. Jede Seite wählt einen privaten Exponenten, veröffentlicht g hoch diesen Exponenten mod p und potenziert die Zahl der Gegenseite mit dem eigenen Geheimnis: (gᵇ)ᵃ = (gᵃ)ᵇ = gᵃᵇ mod p. Um das zu knacken, muss man einen diskreten Logarithmus lösen: Finde zu gegebenem A = gᵃ mod p ein x mit gˣ ≡ A (mod p). Diffie und Hellman hielten 1976 fest, dass sie keinen Weg sahen, das gemeinsame Geheimnis ohne diesen Logarithmus aus den öffentlichen Zahlen zu gewinnen – und ebenso wenig einen Beweis hatten, dass es keinen solchen Weg gibt. Die Ordnung von g ist das kleinste n ≥ 1 mit gⁿ ≡ 1 (mod p); g heißt Erzeuger, wenn seine Ordnung genau p − 1 beträgt.

Was die einzelnen Symbole bedeuten

p: der Primzahlmodul, öffentlich
g: die Basis, öffentlich
a, b: Alices und Bobs private Exponenten
A, B: ihre öffentlichen Zahlen, gᵃ mod p und gᵇ mod p
x: der von Eve gefundene Exponent; jedes x mit gˣ ≡ A genügt, sie bestimmt also a modulo der Ordnung von g
ord(g): die Ordnung von g: Anzahl der verschiedenen Werte, die das gemeinsame Geheimnis annehmen kann

Setzt voraus: p ist eine Primzahl von 5 bis 1.999, g eine beliebige Basis von 2 bis p − 2, und a sowie b liegen zwischen 1 und p − 2. Als Versuch zählt jeder Vergleich einer berechneten Potenz mit dem Zielwert; beide Zählungen schließen den erfolgreichen Treffer ein. Jede Ziffer bei Pohlig–Hellman wird ermittelt, indem die Kandidaten der Reihe nach getestet werden – genau so beschreiben Pohlig und Hellman das Vorgehen für kleine Faktoren. Für große Faktoren skizzieren sie ein Verfahren, das Speicher gegen Laufzeit abwägt; die Seite verzichtet darauf. Diffie und Hellmans eigenes Rechenbeispiel nutzte eine Primzahl von etwa 200 Bit, für die sie den Aufwand eines Logarithmus auf rund 2¹⁰⁰ Operationen bezifferten.

Bei 257 lässt die Basis 2 nur sechzehn Geheimnisse zu 🖖

Klick auf Zyklus der Länge 16. Weil 257 eine Primzahl ist, wirken A und B zunächst wie beliebige Werte unter 256 Möglichkeiten. Doch 2⁸ = 256 ≡ −1 mod 257, folglich ist 2¹⁶ = 1. Die Potenzen von 2 kreisen daher in einer Schleife aus nur 16 Werten: 1, 2, 4, 8, 16, 32, 64, 128, 256, 255, 253, 249, 241, 225, 193, 129. Genau das sind die markierten Felder. Welche Werte a und b auch haben: gᵃᵇ ist immer einer dieser Reste, hier 129. Eves Brute-Force-Angriff bricht nach 14 Versuchen ab und braucht grundsätzlich nie mehr als 16. Das gefundene x = 13 ist zwar nicht Alices 77, stimmt aber mod 16 mit ihr überein – mehr gibt der Exponent schlicht nicht her. Ein Primzahlmodul allein schützt dich davor nicht. Von den 254 Basen zwischen 2 und 255 sind 126 keine Erzeuger; zwei von ihnen, 16 und 241, lassen sogar nur vier Geheimnisse übrig. Bei 263 wiederum, wo p − 1 = 2 × 131 gilt, hat jede Basis von 2 bis 261 die Ordnung 131 oder 262.

Primzahlzwillinge: 811 Versuche gegen 21 🖖

Klick auf p − 1 in kleinen Teilen. 1621 ist eine Primzahl und 1620 = 2² · 3⁴ · 5, deshalb durchsucht Pohlig–Hellman keineswegs die 1.620 Potenzen von g. Der Algorithmus bestimmt a mod 4 mit je zwei Kandidaten, a mod 81 mit je drei und a mod 5 unter fünf. Anschließend setzt der Chinesische Restsatz die Teile zusammen: im ungünstigsten Fall 2·2 + 4·3 + 5 = 21 Versuche, hier sogar nur 15, wo Brute-Force 1.235 Versuche braucht. Wähle nun 1619 in der Tabelle der Primzahlen nahe p. Sie ist um zwei kleiner, doch 1618 = 2 × 809: ein einziger Teil mit 809 Kandidaten, im schlimmsten Fall 811 Versuche und 427 für dasselbe a. Eves Aufwand wird vom größten Primfaktor von p − 1 bestimmt, nicht von der Größe von p. Bei den 301 Primzahlen dieser Seite liegt Pohlig–Hellmans Maximalaufwand nie mehr als 25 über diesem Faktor; bei 172 davon beträgt er weniger als ein Zehntel von Brute-Force, und bei 146 von 300 Schritten zur nächsten Primzahl sinkt er sogar. Pohlig und Hellman formulierten es 1978 unmissverständlich: Wenn p − 1 nur kleine Primfaktoren besitzt, ist die modulare Exponentiation „keine gute Einwegfunktion“.

Die sicherere Basis ist kein Erzeuger 🖖

Klick auf Basis mit Primordnung. Bei 263 ist die Basis 2 kein Erzeuger: Ihre Potenzen wiederholen sich bereits nach 131 Schritten, also sind nur 131 Geheimnisse möglich. Setze g = 5, einen Erzeuger, und es werden doppelt so viele. Schau dir den ungünstigsten Fall für Pohlig–Hellman an: 133 Versuche, davon 2 für die letzte Binärziffer von a. Denn A¹³¹ ergibt 1, wenn a gerade ist, und 262 (also −1), wenn a ungerade ist. Ein Erzeuger verrät diese Ziffer bei jeder ungeraden Primzahl, da p − 1 stets gerade ist. Wechsle zurück zu g = 2. Dessen Ordnung 131 ist eine Primzahl. Pohlig–Hellman kann hier nichts zerlegen, der Maximalaufwand liegt bei 131 Versuchen, genauso viel wie bei Brute-Force. Der Erzeuger verdoppelte zwar die Zahl der möglichen Geheimnisse, schenkte Eve aber völlig umsonst ein Bit des Geheimnisses: Schon aus A und B kann sie erkennen, ob der Wert ein Quadrat mod 263 ist. Jede Potenz von 2 ist ein Quadrat; bei g = 2 lässt sich daraus also nichts ableiten.

Aufgabe vollständig gelöst

Alices Geheimnis bei p = 101 aufdecken 5 Schritte
Alice und Bob wählen p = 101 und g = 2. Eve sieht A = 12 sowie B = 53. Bestimme mit Pohlig–Hellman ein x mit 2ˣ ≡ 12 (mod 101), zähle die Versuche und berechne mit x das gemeinsame Geheimnis. Gib anschließend an, welchen Aufwand derselbe Angriff bei p = 65.537 erfordern würde.

Öffne diese Aufgabe im Tool
1. 100 = 2² · 5², folglich ist x durch x mod 4 und x mod 25 eindeutig bestimmt. Die Ordnung von 2 teilt 100. Da 2⁵⁰ = 100 und 2²⁰ = 95 beide ungleich 1 sind, ist die Ordnung 100 selbst: 2 ist ein Erzeuger.
  
  $100 = 2^{2} \cdot 5^{2}, 2^{50} \equiv 100, 2^{20} \equiv 95 (both \neq = 1) \Rightarrow ord (2) = 100$
2. Modulo 4 ist γ = 2⁵⁰ = 100 ≡ −1. Die erste Binärziffer: 12⁵⁰ = 100, also d = 1 im zweiten Versuch. Herausrechnen: 12 · 2⁻¹ = 12 · 51 = 612 ≡ 6, und 6²⁵ = 100, womit auch die nächste Ziffer 1 ist, wieder im zweiten Versuch. x ≡ 1 + 1 · 2 = 3 (mod 4).
  
  $1 2^{50} \equiv 100 \Rightarrow d_{0} = 1; 12 \cdot 2^{- 1} = 12 \cdot 51 \equiv 6, 6^{25} \equiv 100 \Rightarrow d_{1} = 1; x \equiv 3 (mod 4)$
3. Modulo 25 ist γ = 2²⁰ = 95 mit den Potenzen 1, 95, 36, 87, 84. Die erste Ziffer zur Basis 5: 12²⁰ = 95, also d = 1 im zweiten Versuch. Herausrechnen: 6⁴ = 1.296 ≡ 84, somit ist die nächste Ziffer 4, im fünften Versuch. x ≡ 1 + 4 · 5 = 21 (mod 25).
  
  $9 5^{0..4} = 1, 95, 36, 87, 84; 1 2^{20} \equiv 95 \Rightarrow d_{0} = 1; 6^{4} = 1296 \equiv 84 \Rightarrow d_{1} = 4; x \equiv 21 (mod 25)$
4. Unter 100 lassen die Zahlen 21, 46, 71 und 96 bei Division durch 25 den Rest 21; von diesen ergibt nur 71 den Rest 3 mod 4. Also ist x = 71, nach 2 + 2 + 2 + 5 = 11 Versuchen, während der Maximalaufwand 2·2 + 2·5 = 14 beträgt. Brute-Force hätte 0 bis 71 durchprobiert, also 72 Versuche gebraucht. Das gemeinsame Geheimnis lautet 53⁷¹ mod 101 = 35.
  
  $x \in {21, 46, 71, 96}, x \equiv 3 (mod 4) \Rightarrow x = 71; 2 + 2 + 2 + 5 = 11 tries, at worst 2 \cdot 2 + 2 \cdot 5 = 14$
5. 65.537 = 2¹⁶ + 1 ist prim, und p − 1 = 2¹⁶. Pohlig–Hellman ermittelt die sechzehn Binärziffern nacheinander mit je zwei Kandidaten: im schlechtesten Fall 32 Versuche, wo Brute-Force bis zu 65.536 Versuche brauchen könnte. Pohlig und Hellman behandelten genau diesen Fall p = 2ⁿ + 1 noch vor dem allgemeinen Verfahren.
  
  $s = B^{x} = 5 3^{71} mod 101 = 35; 65537 = 2^{16} + 1 : at worst 16 \cdot 2 = 32 tries$
Antwort

x = 71 nach 11 Versuchen (im ungünstigsten Fall 14), und das gemeinsame Geheimnis lautet 35. Bei p = 65.537 erfordert der Angriff höchstens 32 Versuche. Die Seite endet bei 1.999, diese Zahl entstammt also der Rechnung und keinem Durchlauf.

$x = 71, 11 tries, s = 35$

Lernpfad

Wie Chiffren gebrochen werden

Quellen (2)

The exchange itself, the definition's sentence that its authors could see no way round a logarithm and had no proof, and the 200-bit example in `assumes`: Whitfield Diffie and Martin E. Hellman, "New Directions in Cryptography," IEEE Transactions on Information Theory 22(6), 644–654, November 1976. §III, p. 649.
The second insight's quotation, the digit-by-digit search the page runs, and the worked problem's p = 2ⁿ + 1: Stephen C. Pohlig and Martin E. Hellman, "An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance," IEEE Transactions on Information Theory 24(1), 106–110, January 1978. §III–IV, pp. 107–110.

Vom 42Math-Team · Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.