DHM KEX ist ein Schlüsselaustauschverfahren, mit dem zwei nicht authentifizierte Parteien über öffentliche, nicht verschlüsselte Kanäle sicher einen gemeinsamen Schlüssel generieren können. Es ist benannt nach den beiden Entwicklern Diffie und Hellman die den Algorithmus 1976 publizierten. Manchmal wird auch der Name Merkle hinzugefügt um anzuerkennen, dass der britische Geheimagent Merkle den Algorithmus eigentlich schon früher entwickelt hatte, ihn aber nicht veröffentlichen durfte.

Auch dieser Algorithmus funktioniert auf einem Restklassenkörper Z/pZ. Seine Sicherheit ist definiert über dem Problem des diskreten Logarithmus. Dabei wird angenommen, dass es nicht möglich ist eine bestimmte Hochzahl b der Gleichung a^b mod p = c zu berechnen.

Das Verfahren benötigt eine große Primzahl p und eine Basiszahl g. Die Basiszahl ist mathematisch betrachtet ein sogenanntes erzeugendes Element bezüglich der Restklasse Z/pZ. Die Primzahl und die Basiszahl muss aber nicht jedes mal neu gesucht bzw. berechnet werden. Man kann einfach auf bestehende Paare zurückgreifen, denn die Kenntnis dieser Zahlen für eineN BelauscherIn (in der Kryptographie gerne "Eve" - von eavesdropping - benannt) keinerlei Vorteile wie wir noch sehen werden.

Wollen Alice und Bob einen gemeinsamen geheimen Schlüssel generieren, so können sie Dank DHM wie folgt vorgehen:

1. Alice und Bob einigen sich auf eine gemeinsame Primzahl p und die Basiszahl g (nicht geheim!).
2. Beide denken sich jeweils getrennt eine weitere Zufallszahl (muss nicht prim sein!) q_A und q_B, jeweils kleiner als (p-1) aus. Dies sind ihre privaten Schlüssel die sie geheim halten.
3. Nun tauschen sie wieder öffentlich Zwischenergebnisse aus:
   • Alice sendet Bob das Ergebnis: r_A = g^q_A mod p
   • Bob sendet Alice das Ergebnis: r_B = g^q_B mod p
   Es gibt wie gesagt keine bekannte Methode um q_A bzw. q_B aus r_A bzw. r_B schneller als ausprobieren zu berechnen.
4. Nun können beide daraus eine Zahl berechnen:
   • Alice berechnet: r_B^q_A mod p = g^q_B*q_A mod p =: K
   • Bob berechnet: r_A^q_B mod p = g^q_A*q_B mod p =: K

Auf diese Art und Weise errechnen Alice und Bob getrennt voneinander die selbe Zahl K. Die Berechnung dieser Zahl ist, wie du dir leicht überlegen kannst, mit Eves Kenntnis von nur g, p und den Zwischenergebnissen r_A und r_B unmöglich. Ihr fehlt eine der beiden Geheimzahlen q_A oder q_B.

Damit wird mit Hilfe der Restklassen auf eine einfache Art ein allgemein schwieriges Problem gelöst: eine geheime Zahl zwischen zwei Personen auszutauschen.

Berechne nun in deinem Lerntagebuch nach obigen Schema einen Schlüsselaustausch. Nimm an, p=23, g=5, q_A=6 und q_B=15

Kommst du auch auf die Lösung K=2?

Kannst du nun, nachdem du alle Kapitel durchgearbeitet hast, dieses Rätsel lösen?