serious-cool

 

In diesem Kapitel möchte ich Euch zeigen was sich hinter dem Diffi-Hellman Schlüsseltausch verbirgt. Dieses/r Protokoll / Algorithmus verbirgt sich beispielsweise hinter dem TLS/SSL Handshake eures Webbrowsers. Der beitrag knüpft an das Thema zyklische Gruppen an.

Gegeben sei eine Zyklische Gruppe G der Ordnung n mit dem primitiven Element α und einem beliebigen Element a aus G.

Diskrete Logarithmus Problem - DLP

Aufgabe: Bestimme die Ganzzahl i, 1 <= i <= n; so dass a = αⁱ gilt.

Beispiel: Z₁₁^* , a = 3

3 = 2ⁱ mod 11  um i zu bestimmen können wir nicht einfach unseren Taschenrechner verwenden und Log₂( 3 ) berechnen. (Dieser wäre ungefähr 1,585.) Wir befinden uns schließlich innerhalb unserer zyklischen Gruppe Z₁₁^*. Wir legen uns eine Tabelle an:

i	1	2	3	4	5	6	7	8	9	10
2i	2	4	8	5	10	9	7	3	6	1

Dieser Tabelle können wir entnehmen dass i = 8 sein muss um 3 = 2ⁱ mod 11 zu erfüllen.

Das DLP ist rechen-technisch in einigen Gruppen sehr schwer zu lösen. Dies bedeutet dass das DLP in diesen Gruppen eine Einwegfunktion bildet.

Einwegfunktion bedeutet dass y = f(x) einfach aber x = f^-1(y) praktisch unmöglich ist. Beim RSA Algorithmus ist diese Einwegfunktion beispielsweise multiplizieren.

In der Praxis kommen insbesondere zwei zyklische Gruppen für das DLP zum Einsatz:

1. Z_p^* mit p > 1024 Bit
2. sogenannte elliptisch Kurven
3. ferner exotische DL-Kryptosysteme

Diffi-Hellmann Schlüsseltausch

• vorgeschlagen 1976
• löst im wesentlischen das Schlüsselverteilungsproblem.

Das Prinzip dürfte klar sein: Alice will Bob eine verschlüsselte Nachricht zukommen lassen ohne dass Oscar die Nachricht lesen kann. Das Problem ist dabei nicht die Verschlüsselung sondern die Übertragung des Schlüssels von Alice zu Bob. Der Schlüssel soll ja über das gleiche Medium übertragen werden wie die später die verschlüsselte Nachricht. Dieses Problem löst der Diffi-Hellmann Schlüsseltausch.

Ablauf des Schlüsseltausches

Initialisierungsphase

1. Wähle eine große Primzahl P
2. Wähle ein primitives Element α aus Z_P^*
   
3. α und P sind öffentliche Systemparameter

Schlüsselgenerierung und Übertragung

Alice	Bob
wählt einen KA_privat = δ aus { 2, 3, ...., P-2}	wählt einen KB_privat = φ aus { 2, 3, ...., P-2}
berechnet öffentlichen Schlüssel KA_pub = A = αδ	berechnet öffentlichen Schlüssel KB_pub = B = αφ
Sende KA_pub an Bob	Sende KB_pub an Alice
Berechne Sitzungsschlüssel Ksitzung = KB_pubδ	Berechne Sitzungsschlüssel Ksitzung = KA_pubφ
Y = AESKsitzung(x) ->	-> AES-1Ksitzung(y) = x

 

Sicherheit

Kann Oscar K_sitzung berechnen?

Oscar kennt zwar die Systemparameter und das Protokoll, aber die beiden privaten Schlüssel sind geheim. Auf Grund des DLP kann Oscar auch nicht einfach den Weg K_{A_privat} = Log_α (K_{A_pub}) mod P und K_sitzung = K_{B_pub}^KAprivat  mod P gehen. Es ist allerdings auch nicht bekannt ob eine Abkürzung um das DLP existiert. Falls sie existiert wurde sie jedoch noch nicht gefunden.

Folgerungen

1. Wenn der Angreifer das DLP in Z_P^* berechnen kann, kann er den DH-Austausch brechen.
2. Berechnung des DLP und Berechnung von K_sitzung sind nicht notwendigerweise äquivalent.

Praktische Bemerkungen

• P sollte zwischen 1024 und 4096 Bit lang sein
• Rekord für die DLP Berechnung 600 Bit langes P . Verdopplung des Rechenaufwandes alle 40 Bit.
• Diffi-Hellmann wird in sehr vielen Anwendungen eingesetzt. z.B. in SSL / TLS
• Diffi-Hellmann ist nur gegen passive Angriffe sicher.