Kryptografische Protokolle

Diffie-Hellman-Schlüsselvereinbarung

Zwei Kommunikationspartner A und B wollen sich auf einen gemeinsamen Schlüssel einigen. Der zur Verfügung stehende Kommunikationskanal kann jedoch von einem Dritten C abgehört werden.

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 `x`		wählt Zufallszahl `y`
berechnet `a` = `g`^x mod `p`		berechnet `b` = `g`^y mod `p`

berechnet `b`^x mod `p` = `g`^yx mod `p` = `k`		berechnet `a`^y mod `p` = `g`^xy 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 x berechnet werden, jedenfalls nicht mit vertretbarem Aufwand (Problem des diskreten Logarithmus). Ein Dritter kann somit nicht k = b^x mod p berechnen.

Die Zahl g darf nicht beliebig gewählt werden, sondern g muss die Ordnung p-1 haben. D.h. g muss die Gruppe ganze Zahlen _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}, so dass 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 ganze Zahlen _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).

Aufgabe 1: Sei p = 19. Geben Sie die von g = 7 erzeugte Untergruppe von ganze Zahlen ₁₉* an.

Aufgabe 2: Sei p = 7. Geben Sie ein Element an, das ganze Zahlen ₇* erzeugt.

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.

Beispiel: Sei p = 11. Offenbar ist p eine starke Primzahl. Die Menge ganze Zahlen ₁₁* besteht dann aus folgenden Elementen:

ganze Zahlen ₁₁* = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Die Elemente der Untergruppe der Ordnung 2 sind blau gekennzeichnet, die Elemente der Untergruppe der Ordnung 5 sind rot gekennzeichnet (die 1 ist rot und blau = violett gekennzeichnet). Die restlichen Elemente sind erzeugende Elemente von ganze Zahlen ₁₁*.

Wenn also p-1 = 2·q ist, findet man ein erzeugendes Element von ganze Zahlen _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ⁿ.