Kryptografie (6) : Diffie-Hellman

Das Verfahren RSA basiert auf das mathematische Problem, dass bis heute keine effizienten Algorithmen bekannt sind, um große Zahlen in Primfaktoren zu zerlegen. Das Schlüsselaustauschverfahren Diffie-Hellman basiert auf ein ähnlich schwieriges Problem, nämlich die Berechnung von diskreten Logarithmen über endliche Körper.

endliche Körper

Ein Beispiel für einen endlichen Körper, ist die Menge aller Zahlen N_p={0,1,...,p-1}, die als Rest bei der Division durch die Primzahl p entstehen. Wir nehmen mal k=7, also N_7={0,1,2,3,4,5,6}. Alle Zahlen von 0 bis 7-1 befinden sich in dieser Menge.
Mehr zu endlichen Körper [1].

diskreter Logarithmus

Das ist etwas komplizierter aber deshalb basiert dieses Verfahren darauf. Grob gesagt bedeutet hier diskret, dass alle Parameter natürliche Zahlen sind, und das Ergebnis des Logarithmus ist ebenfalls eine natürliche Zahl. Zum Vergleich gibt es auch den natürlichen Algorithmus der die Eulersche Zahl als Basis hat. Das Ergebnis ist in der Regel eine reelle Zahl. Für eine genauere Definition [2].

Funktionsweise von Diffie-Hellman

Der Sender sucht sich eine große Primzahl aus, p=23. Diese Zahl wird dem Empfänger mitgeteilt. Der Empfänger wählt dann eine zufällige Zahl g aus dem endlichen Körper Z_23={0,1,2,...,21,22}. Es wird g=5 genommen. Der Sender sucht sich jetzt auch aus Z_23 eine Zahl aus, die er für sich behält, a=6. Weiterhin berechnet er
A = g^a mod p = 5^6 mod 23 = 8. Dieses Ergebnis A wird dem Empfänger übermittelt. Der Empfänger macht nun dasselbe. Aus Z_23 wählt er eine Zahl b=15, die er ebenfalls für sich behält, und berechnet
B = g^b mod p = 5^15 mod 23 = 19. Das Ergebnis B wird dem Sender bekannt gegeben.

Bis jetzt könnte ein Angreifer aller übermittelten Parameter p,g,A und B abfangen, da bis jetzt eine unverschlüsselte (!) Übertragung stattfand. Allerdings hat der Sender ja eine Zahl a berechnet die er für sich behält. Dasselbe gilt für den Empfänger mit seinem geheimen Parameter b. Der Angreifer kennt diese beiden Parameter a und b nicht. Nun haben der Sender und Empfänger alle Parameter die sie benötigen und können nun den symmetrischen Schlüssel berechnen.

Für den Sender gilt : key = B^a mod p = 19^6 mod 23 = 2
Für den Empfänger gilt : key = A^b mod p = 8^15 mod 9 = 2

Der Secret-Key lautet also k=2. Ein Angreifer kann k nicht kennen. Er könnte versuchen alle a und b durchzuprobieren, um irgendwann mal k zu berechnen aber dazu muss er diskrete Logarithmen berechnen können: Er benötigt das a aus g^a mod p oder das b aus g^b mod p.

Nun ist die Grundlage gegeben, um verschlüsselt Kommunizieren zu können. Im nächsten Beitrag wird ein bekanntes Verfahren vorgestellt, welches auf Diffie-Hellman basiert.

• Quelle(n)
  [1] Erkay, Savas et al. Finite Field Arithmetic for Cryptography. In: IEEE Circuits and Systems Magazine, Volume 2, Issue 10, p. 42
  https://www.researchgate.net/publication/224140558_Finite_Field_Arithmetic_for_Cryptography
  [2] Kevin, McCURLY. The Discrete Logarithm Problem. In: Proceedings of Symposia in Applied Mathematics, Volume 42, 1990, pp. 49 - 51
  http://www.mccurley.org/papers/dlog.pdf