Kryptografische Protokolle

Diffie-Hellman-Schlüsselvereinbarung

 aufwärts

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 Rechen­aufwandes undurch­führ­bar.

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
   
   
Bild 1: Diffie-Hellman-Schlüsselvereinbarung

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 = bu 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 ganze Zahlenp* erzeugen und nicht nur eine Untergruppe mit möglicher­weise 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 Zahlenp* ist. Welche weiteren Untergruppen von ganze Zahlenp* es gibt, hängt von den Teilern der Gruppen­ordnung ab (in dem hier betrachteten Fall ist p-1 die Gruppen­ordnung, da p eine Primzahl ist).

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

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

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 nicht­triviale 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 Zahlen11* besteht dann aus folgenden Elementen:

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

Die Untergruppe der Ordnung 2 besteht aus den Elementen 1 und 10, die Untergruppe der Ordnung 5 besteht aus den Elementen 1, 3, 4, 5, 9. Die Elemente 2, 6, 7, 8 sind erzeugende Elemente von ganze Zahlen11*.

Wenn also p-1 = 2·q ist, findet man ein erzeugendes Element von ganze Zahlenp*, indem man zufällig ein Element g mit 1<g<p-1 wählt und prüft, ob gq = 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 Wahr­schein­lich­keit, dass man auch nach n Versuchen noch kein erzeugendes Element gefunden hat, beträgt lediglich 1/2n.

Sicherheit

Die Sicherheit der Diffie-Hellman-Schlüssel­vereinbarung beruht darauf, dass es praktisch undurch­führ­bar 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

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

 

Weiter mit:   [ElGamal-Verschlüsselung]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 19.05.1998   Updated: 11.06.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik