Verschlüsselungstechniken - eine einfache Erklärung des Diffie-Hellman-Verfahrens

Verschlüsselung ist in aller Munde und die Frage, die sich dann immer wieder stellt ist die, ob man ihr wirklich trauen kann. Was macht die Verschlüsselung eigentlich sicher? Warum kann man die nicht knacken? Oder kann man das vielleicht doch? Hat vielleicht der CIA oder sogar der KGB eine Geheimrechner irgendwo stehen, mit dem er alles knackt?

Nun über die Rechenleistungskapazitäten der Geheimdienste selbst kann ich nicht viel sagen. Lediglich einige wenige Details stehen öffentlich zur Verfügung. Aber vielleicht sehen wir uns doch einfach einmal an, was solch ein Verschlüsselungsverfahren macht und wie es das macht und dann überlegen wir uns einmal, ob das knackbar ist.

Diffie-Hellman-Verfahren als Beispiel eines Verschlüsselungsverfahrens

Im folgenden Beitrag wird ausschließlich das Diffie-Hellman-Verfahren zu Grunde gelegt. Andere Verschlüsselungsverfahren arbeiten ähnlich aber eine gemeinsame Abhandlung wäre einfach zu überladen für einen solchen Beitrag. Weiterhin soll auch hier auf die Mathematik so weit wie möglich verzichtet werden. Es wird einfach ein Rezept genannt, wie es anzuwenden ist und vom “Rezept” aus argumentiert.

Dabei ist ein ganz klein wenig Mathematik unvermeidbar. Neben den Grundrechenarten müssen wir uns klar sein, was ein Exponent ist. Dieser ist eine einfache Schreibweise für eine mehrfach ausgeführte Multiplikation. Eine Rechnung 3⁵ wäre damit auch schreibbar als 3 * 3 * 3 * 3 * 3. Und was wir noch brauchen, dass ist der Divisionsrest. Man spricht von einer Modulo-Funktion und schreibt mod. Dabei gilt zum Beispiel 7 mod 3 = 1 eben weil das größte ganzzahlige Vielfache von 3, dass gleichzeitig noch kleiner ist als sieben die sechs ist. Und 7-6 ist eben eins.

Die goldene Regel der Verschlüsselung, die wir hier kennen lernen werden, die lautet: Berechenbar ist alles, alleine der Aufwand unterscheidet sich. Der legale Mithörer bekommt einen wirtschaftlich vertretbaren Aufwand zugeordnet, der Illegale muss einen erheblichen Mehraufwand treiben.

Wir sprechen also nie über einen absoluten Schutz, den gibt es nicht, wir sprechen nur über eine wirtschaftliche Schranke, die es zu überschreiten gilt.

Weiterhin geht es in diesem Verfahren um eine Zahl, die nur zwei Teilnehmern bekannt sein soll und die den übrigen Mithörern verborgen ist. Mehr ist an dieser Stelle nicht nötig, denn mit dieser Zahl werden die weiter zu übertragenden Informationen dann verschlüsselt. Diese Geheimzahl ist dabei der Schlüssel, der auf beiden Seiten gleichermaßen verwendet werden muss.

Man unterscheidet dabei grundsätzlich den Schlüsselaustausch und die eigentliche Kommunikation und das wollen wir hier auch tun und uns nur auf den Schlüsselaustausch beschränken.

Informationsaustausch beim Diffie-Hellman-Verfahren

Der erste Schritt des Schlüsselaustauschs besteht aus:

1. Festlegen einer Primzahl
2. Festlegen einer Primitivwurzel zu der gewählten Primzahl
3. Dem öffentlichen Austausch von beidem

Nur der “öffentliche Austausch” dieser Zahlen, also die Vermutung “Feind hört mit” macht an dieser Stelle überhaupt einen Sinn.

Dann wählt jede Partei eine Zufallszahl, die größer ist als 1 und kleiner als die Primzahl-2. Nehmen wir zwei Teilnehmer A und B und A wählt z_A=4 und B die Zahl z_B=6. Dann müssen beide intern und natürlich nach außen Geheim die Berechnung ausführen (Primitivwurzel^z mod Primzahl). Auch hier darf das Ergebnis wieder öffentlich ausgetauscht werden, also der dh-Wert der Zahl dh(z), in keinem Fall aber die Zahl z.

Nun schauen wir uns einmal eine Tabelle zur Primzahl 13 an mit der Primitivwurzel 2. Mit einem z von 5 müsste man 6 übertragen und mit einem z von 7 den Wert 11.

Primzahl: 7 Primitivwurzel: 3	Primzahl: 13 Primitivwurzel: 2
Zahlenwert Rest 1 3 2 2 3 6 4 4 5 5 6 1 7 3	Zahlenwert Rest 1 2 2 4 3 8 4 3 5 6 6 12 7 11 8 9 9 5 10 10 11 7 12 1 13 2

Auf den ersten Blick fallen ein paar Dinge auf.

1. Das Ergebnis der Berechnung mit dem Wert 1 ist immer die Primitivwurzel.
2. Der letzte Wert in jeder Spalte ist immer die Primitivwurzel
3. Der vorletzte Wert in jeder Spalte ist immer 1

Diese auffälligen Dinge kann man in der Mathematik allgemein beweisen. Diesen Beweis bleibe ich an dieser Stelle schuldig und behaupte nun einfach, dass dies allgemein gültig ist und dass man bei dieser Berechnung nur alle anderen Zahlen 1 < z <= (Primzahl-2) wirklich verwenden darf.

Auf den zweiten Blick fällt dann auf:

1. In der ersten Spalte stehen die Zahlen 2 bis 11 in geordneter Reihenfolge
2. In der zweiten Spalte stehen die Zahlen 3 bis 12 in einer scheinbar zufälligen Reihenfolge.

Auch das kann man allgemein beweisen und man hat damit eine Rechenvorschrift, die Absender und Empfänger mit einer jeweils beliebigen Zahl nur einmal ausführen müssen. Ein Lauscher dagegen muss im Durchschnitt etwa die Hälfte der Zahlen berechnen bis er von einem beliebigen mitgelesenen df(z) den richtigen Wert dann auch kennt.

Zusammenfassend wird der Schlüsselaustausch folgendermaßen eingeleitet. Der Absender muss z.B.:

1. Primzahl festlegen
2. Primitivwurzel festlegen
3. Beliebige Zahl z₁ (1 < z₁ <= (Primzahl-2)) festlegen
4. “Diffie-Hellman”-Werte dh(z₁) berechnen
5. Mitteilen Primzahl, Primitivwurzel und dh(z)

Ein Gegenüber muss nun:

1. Primzahl zur Kenntnis nehmen
2. Primitivwurzel zur Kenntnis nehmen
3. Den fremden dh(z)-Wert zu Kenntniss nehmen
4. Selbst eine beliebige (anderen!) Zahl z₂ (1 < z₂ <= (Primzahl-2)) festlegen
5. “Diffie-Hellman”-Werte dieser Zahl berechnen dh(z₂)
6. Mitteilen des “Diffie-Hellman”-Werte der eigenen Zahl.

Jeder Teilnehmer kennt nun die eigene Geheimzahl und den Diffie-Hellman-Wert des Gegenübers.

Berechnung der “gemeinsamen Diffie-Hellman-Zahl”, dem Verbindungsschlüssel

Nennen wir die eigene Zahl z_e und den Diffie-Hellmann-Wert des anderen z_a, dann liefert (z_a^(z_e) mod Primzahl) für beide Seiten eine weitere Zahl gemeinsame zahl.

Wikipedia nennt hier ein schönes Beispiel. In dem eine Alice und ein Bob Zahlen austauschen, um eine Verbindung verschlüsseln zu können.

1. Alice und Bob einigen sich auf die Primzahl 13 und die Primitivwurzel 2.
2. Alice wählt die Zufallszahl a = 5. Bob wählt die Zufallszahl b = 7.
3. Alice berechnet A = 2⁵ mod 13 = 6 und sendet dieses Ergebnis an Bob.
4. Bob berechnet B = 2⁷ mod 13 = 11 und sendet dieses Ergebnis an Alice.
5. Alice berechnet K = 11⁵ mod 13 = 7.
6. Bob berechnet K = 6⁷ mod 13 = 7.
7. Beide erhalten das gleiche Ergebnis K = 7.

Die eigentliche Schlüsselzahl ist also weder der Wert, den Alice noch Bob festgelegt haben. Er ist zu Beginn beiden unbekannt und auch einem potenziellen Lauscher. Diese Zahl ist Ergebnis von zwei Internen Berechnungsschritten auf beiden Seiten und der Schlüsselwert, mit dem alle anderen Botschaften verschlüsselt werden.

Dieser Wert hängt von zwei Werten ab, die jeweils die eine und auch die andere Seite zufällig ausgesucht haben. Damit kann auch der gemeinsame Wert nur ein zufälliger sein.

Wie kann ein Lauscher den gemeinsamen Diffie-Hellman-Schlüssel knacken?

Nun eine Methode habe ich oben angegeben. Es ist eine Tabelle zu erstellen, wobei für jede Primzahl mit entsprechender Primitivwurzel eine bestimmte Zahlenpermutation auftritt. Da der Lauscher die Primzahl kennt und auch die Primitivwurzel, ist dieser Vorgang technisch einfach und naheliegend. Bei der Primzahl 13 ist das überdies auch sehr einfach, denn hier sind nur 10 Berechnungen wirklich nötig, die jedes Excel im Handumdrehen erledigt. Aber bei größeren Primzahlen steigt der Rechenzeitbedarf schon sehr schnell an.

Nehmen wir zum Beispiel die im Jahre 1588 entdeckte Primzahl 2¹⁷ – 1 mit dem Zahlenwert 131.071, so sind hier immerhin schon 131.069 Berechnungen auszuführen für die gesamte Tabelle. Das war für damalige Verhältnisse sehr viel, für heutige Verhältnisse darf man das aber nicht mehr als “wirklich problematisch” ansehen.

Damit sind wir bei einer wichtigen Eigenschaft einer Internetverbindung, nämlich die, dass der Verschlüsselungsschutz temporär ist. Wenn der Lauscher den Traffic aufzeichnet, dann kann er ihn vielleicht nicht jetzt aber denn doch in einigen Jahren knacken. Wenn Sie also irgendwo in einem Shop etwas einkaufen, dann reicht der normale im Browser mitgelieferte Verbindungsschutz allemal aus. Wollen Sie dagegen mit Ihrem Beichtvater über den Mord sprechen, den Sie vor kurzem begangen haben, dann müssen Sie eine Schlüsseltechnik verwenden, die mindestens 30 Jahre “dicht” hält.

Die Fachleute sind übrigens schon bei Primzahlgrößen angekommen mit 9,8 Millionen Ziffern. Wenn Sie also etwas entdeckt haben, dass aussieht wie eine Primzahl, dann sollte die Zahl (also nur diese!) in einer ASCII-Datei zu einer Dateigröße führen von fast 10 MB, dann haben Sie die Chance, dass dem jemand Beachtung schenkt. Und denken Sie daran, jedes Byte dieser Datei verzehnfacht den Aufwand für einen potenziellen Angreifer.

Wir müssen eigentlich anders fragen:

1. Welche Primzahlen werden eingesetzt? und
2. Wie viele Primitivwurzeln gibt es eigentlich für eine Primzahl?

Beginnen wir mit der zweiten Frage.

Wie viele Primitivwurzeln gibt es eigentlich für eine Primzahl?

Hier kann man einfach langatmigen Erklärungen aus dem Weg gehen und salopp sagen “sehr viele”. In der Humbold-Universität-Berlin hat sich ein Student einmal daran gemacht und einen kleinen Online-Rechner für Primitivwurzeln installiert, der für jede Primzahl alle Möglichkeiten durchrechnet.

Im Falle 13 wären 6, 7 und 11 weitere Primitivwurzeln.

Welche Primzahlen werden eingesetzt?

Hier beginne ich mit einem Zitat

Die Anzahl der Dezimalstellen von Modulus und geheimen Schlüssel muss in der Größenordnung von ein-/ bis mehreren hundert Stellen liegen, damit nicht durch systematisches “durchprobieren” (brute force) aller Möglichkeiten der Schlüssel mittels schneller Rechner innerhalb von Minuten bis Tagen “geknackt” werden kann!!!

Und dann sind wir mitten drin in unserem Problemfeld:

Wie beweist man eigentlich, dass eine Zahl eine Primzahl ist? Hier bleibt nur das Sieb des Eratostenes und damit eben eine gewaltige Rechenleistung.

Im obigen Spiegel-Beitrag zu der Rekordprimzahl lautet es daher auch:

Diese Zahl von einem einzigen Computer berechnen zu lassen, hätte laut Gimps mehr als 4000 Jahre gedauert.

Und in linslernet wiederum wird gesagt:

Zur Verschlüsselung werden heute große Zahlen bereits als Primzahlen angenommen, wenn es sich “mit hoher Wahrscheinlichkeit” um solche handelt?!?

D.h. Primzahlen werden mit einer Art “Restrisiko” ermittelt:

Und damit haben wir das Problem im Grunde “auf den Punkt” gebracht. Die Qualität einer Verschlüsselung steht und fällt mit der Länge der Primzahl auf der einen Seite und der Rechenpower, die auf der anderen Seite aufgebracht wird, bzw. aufgebracht werden kann. Die Qualität steht und fällt aber auch mit der Qualität der Primzahl. Daher die Frage:

Was passiert eigentlich, wenn ich keine Primzahl nehme.

Zu einer Nichtprimzahl gibt es eigentlich keine Primitivwurzel. Wenn man also eine Zahl nimmt, von der man annimmt, dass es sich um eine Primitivwurzel handelt, sie es aber nicht ist, dann passiert folgendes:

Verwenden einer “Nichtprimitivwurzel”

Zahlenwert	Rest [zahl+0]	Rest [zahl+10]
1	3	3
2	9	9
3	1	1
4	3	3
5	9
6	1
7	3
8	9
9	1

Hier habe ich die 13 als Primzahl genommen und nur eine falsche Zahl als Primitivwurzel eingesetzt (3 ist keine Primitivwurzel von 13). Das führt dazu, dass man nun alle Ausgangszahlen nur noch auf die Zahlen 1, 3 und 9 abbilden kann. Wenn man also zum Beispiel die Zahl 5 wählt, dann müsste man die neun übertragen. Wählt man die 8, wäre es ebenfalls die 9. Die eigene Auswahl von zwei unterschiedlichen Zahlen führt dann zur gleichen Schlüsselzahl. Der Angreifer muss aber nur eine von beiden Zahlen kennen. Er kann aufhören, wenn er bei 2 die 9 erhält. Dann hat er die entscheidende Information und kann mit dem Diffie-Hellman-Wert der Geheimzahl des anderen Teilnehmers die gemeinsame Schlüsselzahl ebenfalls ermitteln.

Fazit: Der Angreifer muss nun nicht mehr 10 Werte durchrechnen, sondern nur noch drei.

Wir können uns auch ein paar andere Beispiele ansehen:

Es gibt die Primzahl 5 – mit der könnte man die Werte 2, 3 übermitteln (also ein Angreifer hätte die “Auswahl zwischen zwei Zahlen”. Diese Zahl hat die Primitivwurzeln 2 und 3. Weiterhin gibt es die Primzahl 7 – mit der könnte man 2, 3, 4, und 5 übermitteln und diese hat die Primitivwurzeln 3 und 5. Wir können uns also nun einfach einmal alle Kombinationen veranschaulichen.

Wir gehen also davon aus, das die 35 eine sehr große Zahl ist, von der wir nach einigen Tests fälschlicherweise annehmen, dass diese eine Primzahl ist. Aus welchen Gründen auch immer gelingt es uns nun die Primitivwurzeln 2, 3 und 5 zu ermitteln.

Die 35 mit der “Primitivwurzel” 2

Zahlenwert	Rest [zahl+0]	Rest [zahl+10]	Rest [zahl+20]	Rest [zahl+30]
1	2	18	22	23
2	4	1	9	11
3	8	2	18	22
4	16	4	1	9
5	32	8	2	18
6	29	16	4
7	23	32	8
8	11	29	16
9	22	23	32
10	9	11	29

Klar erkennbar ist eine Periodizität in den Ergebnisse, die bei 13 und 25 sich wiederholt. Bei einer “Primzahl” mit dem Wert 35 könnte man 33 verschiedene Möglichkeiten übertragen, man überträgt aber nur 1/3 davon, also 11.

Genau besehen darf man allerdings drei Werte nie übertragen und diese drei Werte waren im Fall einer echten Primzahl (1 < z <= (Primzahl-2)) die Primitivwurzel nicht (erhält man bei z=1 und z=Primzahl) und auch nicht die 1 (erhält man bei z = Primzahl – 1). Hier darf man also die 1 nicht übertragen und auch die zwei nicht. Hätte man das Ergebnis müsste man eine andere Zahl festlegen.

Mit anderen Worten: Wenn man keine sichere Primzahl hat und ggf. nur eine große Zahl, dann muss man dem Ergebnis noch ein paar Tests unterziehen. Es könnte 1 als Ergebnis herauskommen oder der Wert der Primitivwurzel und dann muss man auf eine andere Zahl ausweichen. Und man muss sich darüber klar sein, dass ein Restrisiko besteht und die Zahl der Möglichkeiten drastisch schrumpft.

Die 35 mit der “Primitivwurzel” 3

Zahlenwert	Rest [zahl+0]	Rest [zahl+10]	Rest [zahl+20]	Rest [zahl+30]
1	3	12	13	17
2	9	1	4	16
3	27	3	12	13
4	11	9	1	4
5	33	27	3	12
6	29	11	9
7	17	33	27
8	16	29	11
9	13	17	33
10	4	16	29

Auch hier ist klar erkennbar eine Periodizität vorhanden, an den gleichen Stellen und ebenfalls mit der Folge einer Reduktion der Möglichkeiten auf 1/3.

Letztes Beispiel, die 35 mit der “Primitivwurzel” 5

Zahlenwert	Rest [zahl+0]	Rest [zahl+10]	Rest [zahl+20]	Rest [zahl+30]
1	5	10	20	15
2	25	15	30	5
3	20	5	10	25
4	30	25	15	20
5	10	20	15	30
6	15	30	5
7	5	10	25
8	25	15	20
9	20	5	30
10	30	25	10

Hier Entdecken wir sogar eine Periode der Länge 7 und damit 5 Wiederholungen. Damit wird die Zahl der Möglichkeiten auf 1/5 reduziert. Ein Angreifer hätte hier in der Summe nur 5 Zahlen zu berechnen.

Das potenziert sich auch auf große Primzahlen. Wir hatten die Cataldi-Primzahl 2¹⁷-1 bereits genannt und eine weitere Cataldi-Primzahl aus dem gleichen Jahr lautet 2¹⁹-1. Dezimal geschrieben sind das 131.071 und 524.287 mit dem Produkt 68.718.821.377. Nach dem hier Gelernten liegt bestenfalls die größere Primzahl vor und das auch nur dann, wenn man eine Primitivwurzel der kleineren Primzahl verwendet. Ob und in welchem Umfang das allgemein gilt, das kann ich zur Zeit nicht sagen. Wichtig ist nur: Es werden gute Primzahlen gebraucht!

Wenn gute Primzahlen eine Verbindung “gut” machen, dann machen “schlechte Primzahlen” – also Zahlen die einfach nur “groß” sind eine Verbindung auch unsicher. Wenn man eine große Primzahl mit der Cataldi-1-Primzahl verknüpft und ein Primitivwurzel der großen Primzahl verwendet oberhalb von 131.071, dann hat man zwar große und toll aussehende Zahlen. Aber für einen Lauscher ist das dann nur noch ein Spaziergang.

Primzahlen und die zugehörigen Primitivwurzeln sind daher ein sicherheitskritisches Gut und ggf. sollte man diese auch prüfen [können]. Dabei sprechen wir von Primzahlen mit einer Länge von 100 Stellen und mehr.

Wenn man diese dann hat und vor allem sichergestellt hat, dass es tatsächliche Primzahlen sind, dann gibt es eine Unzahl an Zahlenkombinationen, die öffentlich übertragen werden können und die zu einem Austauschschlüssel führen, der wirtschaftlich unknackbar ist. Und nur das ist wirklich erreichbar, eine wirtschaftliche Unknackbarkeit. Dabei sollte man aber beachten, dass es in den USA eben doch Rechnernetze gibt, die erstaunliche Rechenpower bieten und dass so es nach einem Export derselben solche dann einmal in China geben dürfte. Beides zieht die wirtschaftlichen Grenzen immer mehr nach unten und dürfte über kurz oder lang schon zu ernsthaften Problemen führen.

Damit bleibt einfach nur der Rat: Holen Sie aus der Verschlüsselungstechnik raus, was rauszuholen ist. Und wenn Sie die Zahlen nicht selbst geprüft haben, dann übertragen Sie nichts über das Internet, was wirklich geheim ist.

---