Alice und Bob tauschen Schlüssel

Die beiden Informatiker Whitfield Diffie und Martin Hellman beschrieben das später nach ihnen benannte Verfahren bereits 1976. Es lässt sich in Kurzform und vorerst ohne den Einsatz elliptischer Kurven folgendermaßen beschreiben: Zwei Kommunikationspartner, in kryptographischer Tradition nennen wir sie Alice und Bob, wollen einen Schlüssel austauschen, um anschließend ihre Kommunikation zu verschlüsseln. Zunächst einmal haben sie dafür keinen sicheren Kanal. Ein neugieriger Angreifer könnte demnach alles mitlesen, was Alice und Bob hin- und herschicken.

Daher einigen sich die beiden auf eine Primzahl p und eine Zahl g. Während g eine kleine Zahl sein kann, muss p möglichst groß sein. Das Bundesamt für Sicherheit in der Informationstechnik empfiehlt für eine Verwendung über das Jahr 2022 hinaus mindestens 3.000 Bit. Für ein kleines und nachvollziehbares Rechenbeispiel soll aber p hier 11 und g gleich 2 sein. Die beiden Werte können öffentlich bekannt sein, und in der Realität wählen Alice und Bob diese Zahlen auch nicht selbst aus, sondern nutzen standardisierte Werte.

Nachdem sie sich auf die öffentlichen Parameter verständigt haben, wählen beide im Geheimen jeweils eine zufällige Zahl, nennen wir sie a und b, die kleiner als p, also 11 ist. Alice wählt nun die 3, Bob die 5. Sie verraten sich die Zahlen gegenseitig nicht, stattdessen schickt Alice ihrem Kommunikationspartner das Ergebnis der Berechnung g^a modulo p. Modulo bedeutet vereinfacht gesagt: Der Wert wird durch p geteilt, hier 11, und der ganzzahlige Rest ist das Ergebnis.

Das Diskreter-Logarithmus-Problem

Alices Ergebnis lautet: 2^3 mod 11, also 8. Bob kommt auf den Wert 10, denn 2^5 ist 32, geteilt durch 11 bleibt ein Rest von 10. Die beiden Kommunikationspartner verraten sich ihre Rechenergebnisse gegenseitig. Wenn Alice nun die von Bob gesendete Zahl 10 hoch ihrer geheimen Zahl 3 rechnet - wieder modulo 11 - erhält sie den Wert 10. Rechnet Bob die Zahl von Alice hoch 5 kommt er zum gleichen Ergebnis: Die 10 ist ihr gemeinsames Geheimnis, und das kann niemand leicht berechnen - vorausgesetzt, p ist groß genug. Denn dafür müsste der Angreifer einen diskreten Logarithmus bilden können, also die Umkehrfunktion der Potenz.

Bei positiven, reellen Zahlen wäre es erst einmal kein großes Problem, den Logarithmus zu bilden. Vielleicht erinnern sich einige noch an Beispiele aus der Schulmathematik und Näherungsrechnungen. Anders sieht das aus, wenn wir eben nicht reelle Zahlen als Grundlage nehmen, sondern - nicht gleich wegklicken - prime Restklassengruppen wie oben im Beispiel.

Was heißt nun prime Restklassengruppe? Eine Gruppe im Allgemeinen ist nicht viel mehr als eine Menge an Elementen, sagen wir verkürzt der Einfachheit halber Zahlen, die bestimmte Bedingungen erfüllen. Unter anderem muss es eine Verknüpfung zwischen jeweils zwei Zahlen geben, die als Ergebnis wieder eine Zahl der Gruppe ergeben. Nehmen wir an, wir nutzen ganze Zahlen als Menge und nennen die Verknüpfung Addition. 50 addiert mit 13 ist 63, 63 ist ein Element der ganzen Zahlen: Das passt.

Wie auf dem Ziffferblatt einer Uhr

In einer Restklassengruppe modulo 60 ist 50 addiert mit 13 aber 3, denn die Menge an Elementen, die uns zur Verfügung steht, besteht nur aus der 0, 1, 2 bis 59. Eine Analogie dazu wäre der Sekundenzeiger einer Uhr, der nach dem 59. Segment einfach wieder bei der 0 anfängt. Die 3 ist dann der Rest des Teilens durch 60.

Für die Kryptographie sind besonders prime Restklassengruppen modulo einer Primzahl - wie die 11 - interessant, die als Operation die Multiplikation benutzen und einen Generator haben, der auch eine Primzahl ist. Ein Generator ist ein Element, mit dem sich alle anderen Elemente der Gruppe erzeugen lassen. In unserem Alice-und-Bob-Beispiel war der Wert g dieser Generator, also die 2. Potenzieren wir die 2 mit allen anderen Elementen der Gruppe, kommt jedes Element einmal als Ergebnis vor. Die Gruppe lässt sich also mit der 2 generieren.

Diese Restklassen machen es so schwer, den diskreten Logarithmus herauszufinden. Denn wenn ein Zahlenraum, salopp gesagt, immer wieder von vorne anfängt, springen die Ergebnisse. Bei 2^3 mod 11 ist es 8, 2^4 mod 11 = 5 und 2^5 mod 11 ergibt 10.

Man kann erahnen, warum es da so schwer ist, die Ergebnisse abzuschätzen.