Kryptografische Protokolle

Zwei Kommunikationspartner A und B wollen einen gemeinsamen geheimen Schlüssel vereinbaren, jedoch kann der zur Verfügung stehende Kommunikationskanal von einem Dritten C abgehört werden. Auf den ersten Blick erscheint dies paradox – wie kann der Schlüssel geheim bleiben, wenn die Kommunikation abgehört wird? Die Lösung besteht in einer indirekten Vereinbarung des Schlüssels mithilfe des Diffie-Hellman-Protokolls [DH 76]. Wir werden sehen, dass es für C zwar theoretisch möglich ist, den Schlüssel zu ermitteln, praktisch aber aufgrund des hohen Rechenaufwandes undurchführbar.

Protokoll

Zu Beginn tauschen A und B öffentlich eine Primzahl p und eine Zahl g aus.

A		C		B
		Primzahl p Zahl g mit 1 < g < p-1
wählt    Zufallszahl u				wählt    Zufallszahl v
berechnet    a = gu mod p				berechnet    b = gv mod p
berechnet    bu mod p = gvu mod p = k				berechnet    av mod p = guv mod p = k

Die Zahl k kann nunmehr A und B als gemeinsamer Schlüssel dienen. Sind die verwendeten Zahlen groß genug, so kann aus der Kenntnis von a sowie p und g nicht u berechnet werden, jedenfalls nicht mit vertretbarem Aufwand (Problem des diskreten Logarithmus). Ein Dritter C kann somit nicht k = b^u mod p berechnen.

Auswahl von g

Die Zahl g darf nicht beliebig gewählt werden, sondern g muss die Ordnung p-1 haben. D.h. g muss die Gruppe ℤ_p* erzeugen und nicht nur eine Untergruppe mit möglicherweise sehr viel weniger Elementen. Denn nur die Elemente der von g erzeugten Gruppe kommen als Ergebnis k in Betracht.

Der Extremfall für eine falsche Wahl von g ist g = 1. Die von g = 1 erzeugte Untergruppe ist {1}, d.h. als Ergebnis für k ist nur 1 möglich. Auch g = p-1 ist eine schlechte Wahl, denn die von p-1 erzeugte Untergruppe ist {1, p-1}, sodass als mögliche Ergebnisse für k nur 1 und p-1 in Betracht kommen. Ein Angreifer braucht also in diesem Fall keine diskreten Logarithmen zu berechnen, sondern nur die Schlüssel k = 1 und k = p-1 auszuprobieren.

Wichtig ist also, dass g kein Element einer echten Untergruppe von ℤ_p* ist. Welche weiteren Untergruppen von ℤ_p* es gibt, hängt von den Teilern der Gruppenordnung ab (in dem hier betrachteten Fall ist p-1 die Gruppenordnung, da p eine Primzahl ist).

Auswahl von p

Zweckmäßigerweise nimmt man in der Praxis für p eine starke Primzahl, d.h. eine Primzahl p, für die gilt

p-1  =  2 · q

mit q Primzahl.

Dann sind nur 2 und q echte Teiler von p-1 und es gibt nur zwei nichttriviale Untergruppen – eine der Ordnung 2 und eine der Ordnung q.

Die Untergruppe der Ordnung 2 ist {1, p-1}, die restlichen Elemente sind je zur Hälfte Elemente der Untergruppe der Ordnung q und erzeugende Elemente der gesamten Gruppe.

Wenn also p-1 = 2·q ist, findet man ein erzeugendes Element von ℤ_p*, indem man zufällig ein Element g mit 1 < g < p-1 wählt und prüft, ob g^q = 1 ist (modulo p gerechnet). Ist dies der Fall, so verwirft man g, denn dann ist g kein erzeugendes Element der gesamten Gruppe, sondern Element der Untergruppe der Ordnung q. Man wählt dann ein neues Element usw. Die Wahrscheinlichkeit, dass man auch nach n Versuchen noch kein erzeugendes Element gefunden hat, beträgt lediglich 1/2ⁿ.

Sicherheit

Die Sicherheit der Diffie-Hellman-Schlüsselvereinbarung beruht darauf, dass es praktisch undurchführbar ist, den Logarithmus einer Zahl modulo p zu berechnen (Problem des diskreten Logarithmus).

Allerdings gibt es eine andere Form des Angriffs: die sogenannte man-in-the-middle attack. Dabei gibt sich der Angreifer C gegenüber A als B und gegenüber B als A aus. Tatsächlich also vereinbart C mit A einerseits und mit B andererseits jeweils einen gemeinsamen Schlüssel. Anschließend schaltet sich C dazwischen, wenn A und B Nachrichten austauschen.

Literatur

Lesenswert ist der Originalartikel

[DH 76]   W. Diffie, M.E. Hellman: New Directions in Cryptography. IEEE Transactions on Information Theory, Vol. IT-22, 644-654 (1976)

Ansonsten findet sich die Diffie-Hellman-Schlüsselvereinbarung in jedem Fachbuch über Kryptografie, so beispielsweise in

[BNS 05]   A. Beutelspacher, H.B. Neumann, T. Schwarzpaul: Kryptografie in Theorie und Praxis. Vieweg (2005)

[Bu 00]   J.A. Buchmann: Introduction to Cryptography. Springer (2000)

[Ert 12]   W. Ertel: Angewandte Kryptographie. 4. Auflage, Hanser (2012)

[KK 10]   C. Karpfinger, H. Kiechle: Kryptologie. Vieweg+Teubner (2010)

[PP 10]   C. Paar, J. Pelzl: Understanding Crytography. Springer (2010)

[Schm 16]   K. Schmeh: Kryptografie. 6. Auflage, dpunkt (2016)

[SSP 08]   J. Swoboda, S. Spitz, M. Pramateftakis: Kryptographie und IT-Sicherheit. Vieweg+Teubner (2008)

[Lan 18]   H.W. Lang: Kryptografie für Dummies. Wiley (2018)

[Weitere Informationen]