Diffie-Hellman-Schlüsselaustausch

Ralph Merkle

Whitfield Diffie

Martin Hellman

Beim Diffie-Hellman-Merkle-Schlüsselaustausch handelt es sich um das erste der sogenannten asymmetrischen Kryptoverfahren (auch Public-Key-Kryptoverfahren), das veröffentlicht wurde. Es löst das Schlüsseltauschproblem, indem es ermöglicht, geheime Schlüssel über nicht-geheime, also öffentliche, Kanäle zu vereinbaren.

Den ersten Schritt zur Entwicklung asymmetrischer Verfahren machte Ralph Merkle 1974 mit dem nach ihm benannten Merkles Puzzle, das aber erst 1978 veröffentlicht wurde.[2] Unter dem Einfluss dieser Arbeit entwickelten Whitfield Diffie und Martin Hellman im Jahr 1976 den Diffie-Hellman-Schlüsselaustausch. Sie veröffentlichten die Forschungsarbeit unter dem Titel „New Directions in Cryptography“.[3] Das Verfahren sorgte für einen gewaltigen Schub in der Kryptographie, eine Wissenschaft, die damals noch nicht sehr lange öffentlich betrieben wurde.[4] Ursprünglich nannten die Forscher das Verfahren ax1x2. Martin Hellman schlug 2002 vor, das Verfahren Diffie-Hellman-Merkle-Schlüsselaustausch zu nennen, „wenn schon Namen damit verbunden werden“, in Anerkennung von Ralph Merkles Anteil an der Entwicklung asymmetrischer Verfahren.[5]

Die Bedeutung dieser Entwicklung wird auch mit der kopernikanischen Wende verglichen: „Die Entwicklung der asymmetrischen Verschlüsselung hat für die Kryptographie eine vergleichbare Bedeutung wie die Kopernikanische Wende für die Astronomie und stellt neben der Digitalisierung der Informationen und dem Internet als Kommunikationsplattform ein Fundament des dritten Jahrtausends dar.“[6]

Whitfield Diffie und Martin Hellman prägten mit dem Verfahren auch einen neuen Sicherheitsbegriff in der Kryptographie, der darauf basiert, dass kein effizienter Algorithmus für die Kryptoanalyse existiert: Ein Kommunikationsprotokoll ist sicher, wenn dessen Kryptoanalyse so viel Zeit und Arbeit bedeutet, dass diese in der Praxis nicht ausgeführt werden kann.[7] Die Sicherheit des Diffie-Hellman-Merkle-Schlüsselaustauschs beruht entscheidend darauf, dass die diskrete Exponentialfunktion in gewissen zyklischen Gruppen eine Einwegfunktion (englisch one-way function) ist, so insbesondere in der primen Restklassengruppe. Das heißt, dass in dieser die Exponentiation effizient berechenbar ist, für deren Umkehrung, den diskreten Logarithmus, jedoch bis heute kein effizienter Algorithmus bekannt ist.

Das Diffie-Hellman-Merkle-Verfahren ist mittlerweile nur eines von vielen Verfahren, die die diskrete Exponentialfunktion (mit diskretem Logarithmus als Umkehrung) als Einwegfunktion nutzen. Man spricht in diesem Zusammenhang auch von Krypto-Systemen auf Basis des diskreten Logarithmus oder einfach von DL-Verfahren.[8] So ist es beispielsweise eng verwandt mit dem Elgamal-Verschlüsselungsverfahren, das 1985 vom Kryptologen Taher Elgamal entwickelt wurde. Dieses ist im Prinzip nichts anderes als ein DHM-Schlüsselaustausch mit anschließendem Senden einer Nachricht, die mit dem vereinbarten Schlüssel verschlüsselt ist.[9]

Die Forscher führten in der fundamentalen „New Directions“-Arbeit auch das Konzept einer digitalen Signatur ein: Ein Sender berechnet mit Hilfe eines geheimen Signaturschlüssels (dem Private Key) zu einer digitalen Nachricht (d. h. zu beliebigen Daten) einen Wert, der digitale Signatur genannt wird. Dieser Wert ermöglicht es jedem, mit Hilfe des öffentlichen Verifikationsschlüssels (dem Public Key) die nichtabstreitbare Urheberschaft und Integrität der Nachricht zu prüfen.[10] So entstand als Weiterentwicklung des DHM-Schlüsselaustauschs eine vielfältige Familie an digitalen Signaturen auf Basis des diskreten Logarithmus. Zu den Bekanntesten gehören das Elgamal-Signaturverfahren und der Digital Signature Algorithm.[11]

Neben der Einwegfunktion entwickelten Whitfield Diffie und Martin Hellman auch das Konzept der Falltür (englisch trapdoor). Das ist eine „versteckte Abkürzung“ durch eine Zusatzinformation, mit der die ansonsten schwierige Umkehrung einfach gemacht wird. Auf der Basis von Falltürfunktionen lassen sich asymmetrische Verfahren entwickeln, bei denen die Übertragung eines geheimen Schlüssels nicht mehr notwendig ist. Damit leisteten sie auch wichtige Vorarbeiten zur Entwicklung des RSA-Kryptosystems. Ronald L. Rivest, Adi Shamir und Leonard Adleman versuchten eigentlich zu beweisen, dass es ebensolche Falltürfunktionen nicht geben kann. Bei den Beweisversuchen stießen sie jedoch tatsächlich auf eine solche Einwegfunktion mit Falltür. Das führte 1977 zur Entwicklung des berühmtesten Public-Key-Algorithmus, des nach den Initialen seiner Erfinder sogenannten RSA-Kryptosystems.[12]

Unterschiedliche Varianten des DHM-Verfahrens werden heute für die Schlüsselverteilung in den Kommunikations- und Sicherheitsprotokollen des Internet eingesetzt, wie z. B. IPsec (Internet Protocol Security), IPv6 (Internet Protocol Version 6) und TLS (Transport Layer Security). Diese dienen zur Sicherung bei der Übertragung von Datenpaketen der IP-Protokollschicht bzw. von Daten der Anwendungsebene, beispielsweise in den Bereichen des elektronischen Handels. Dieses Prinzip der Schlüsselverteilung besitzt damit eine wichtige praktische Bedeutung.[13] Der hier automatisch berechnete Schlüssel wird dann als Schlüssel für ein schnelles symmetrisches Verfahren wie Data Encryption Standard (DES) oder Advanced Encryption Standard (AES) verwendet.

Das Konzept der Public-Key-Kryptographie und einige spezifische Methoden waren bis 1997 durch die U.S. Patente 4.200.770 (Hellman, Diffie, Merkle, 1980) und 4.218.582 (Hellman, Merkle, 1980) geschützt, die der Stanford University gehören.[14][15] Für die Entwicklung der Public-Key-Kryptographie und der digitalen Signatur erhielten Whitfield Diffie und Martin Hellman im Jahr 2015 den Turing Award verliehen, der als höchste Auszeichnung in der Informatik gilt, vergleichbar dem Nobelpreis oder der Fields-Medaille.[16]

Clifford Cocks

Wie erst 1997 bekannt wurde, hatte das britische Government Communications Headquarters (GCHQ) schon in den 1960er Jahren den Auftrag erteilt, zur Vermeidung der hohen Kosten bei der damals üblichen Schlüsselverteilung einen anderen Weg zu finden. James H. Ellis formulierte das Konzept der „nicht-geheimen Verschlüsselung“. Daraus entwickelte Clifford Cocks ein Verfahren, das er bereits 1973 in einem internen Dokument beschrieb und das dem RSA-Verfahren sehr ähnlich ist. Somit muss aus heutiger Sicht der Dinge festgehalten werden, dass eigentlich Clifford Cocks als erster ein asymmetrisches Kryptoverfahren entwickelte. Diese Errungenschaft wird ihm nicht allgemein anerkannt, da seine Arbeit per definitionem Verschlusssache war und deshalb damals nicht veröffentlicht wurde. Erst 1997 wurde das interne Dokument auf der Website der Communications Electronics Security Group veröffentlicht.

In diesem Zusammenhang wurde auch bekannt, dass Malcolm Williamson, ein weiterer Mitarbeiter des GCHQs, schon 1975 das Schlüsselaustauschverfahren nach Diffie-Hellman entdeckte. Interessant ist dabei, dass die Entdeckung der beiden Verfahren – RSA und DHM – in der öffentlichen und der geheimen Kryptologie in umgekehrter Reihenfolge stattfand.[17]

Funktion und Umkehrfunktion

Eine Einwegfunktion ist eine mathematische Funktion, die komplexitätstheoretisch „leicht“ berechenbar, aber „schwer“ umzukehren ist.[21] Eine mathematische Einwegfunktion ${\displaystyle f\colon X\to Y}$ muss folgende Eigenschaften aufweisen:

• Die Berechnung des Funktionswerts ${\displaystyle y=f(x)}$ ist „einfach“, d. h. es existiert ein Algorithmus, der ihn in Polynomialzeit berechnen kann.
• Die Berechnung der Umkehrfunktion zu einem gegebenen Funktionswert ${\displaystyle y}$, d. h. einem ${\displaystyle x}$, sodass ${\displaystyle f^{-1}(y)=x}$, ist allerdings „schwer“, d. h. es existiert kein „schneller“ Algorithmus für dieses Problem. „Schnell“ meint hier einen probabilistischen Algorithmus, der in Polynomialzeit läuft.

Einen anschaulichen Vergleich bietet ein klassisches Papier-Telefonbuch einer größeren Stadt: Die auszuführende Funktion ist die, einem Namen die entsprechende Telefonnummer zuzuordnen. Da die Namen alphabetisch geordnet sind, lässt sich dies ziemlich schnell durchführen. Aber ihre Invertierung, also die Zuordnung eines Namens zu einer gegebenen Telefonnummer, ist offensichtlich viel schwieriger.[22]

Man kann zeigen, dass Einwegfunktionen genau dann existieren, wenn P ≠ NP, die berühmte Vermutung aus der Komplexitätstheorie, gilt (siehe P-NP-Problem). Obwohl die Einwegfunktionen in der Kryptographie eine wichtige Rolle spielen, ist bis heute nicht bekannt, ob sie im streng mathematischen Sinne überhaupt existieren.[23]

Die Sicherheit des DHM-Schlüsselaustauschs basiert darauf, dass der diskrete Logarithmus in gewissen zyklischen Gruppen als Einwegfunktion angenommen wird. Es gibt dabei keine Falltür, d. h. eine Zusatzinformation, mit der die Umkehrfunktion leicht zu berechnen wäre. Im Gegensatz dazu verwendet beispielsweise das RSA-Kryptosystem mit der Faktorisierung eine Einwegfunktion mit Falltür.

Die diskrete Exponentialfunktion

${\displaystyle b^{x}\ {\bmod {\ }}m}$

liefert den Rest bei Division von ${\displaystyle b^{x}}$ durch m. Die Umkehrung der diskreten Exponentialfunktion heißt diskreter Logarithmus.

Die diskrete Exponentialfunktion ist auch für große Exponenten effizient berechenbar. Selbst für über hundert Bit lange Zahlen ist bei geschickter Implementierung eine Sekunde auf einem PC ausreichend. Zur effizienten Berechnung kann der Satz von Euler und das Square-&-Multiply-Verfahren verwendet werden.

Für die Umkehrung, also die Berechnung des Exponenten ${\displaystyle x}$, bei gegebener Basis ${\displaystyle b}$, Modul ${\displaystyle m}$ und gewünschtem Ergebnis, ist allerdings bis heute kein schneller Algorithmus bekannt: Selbst mit größtem Hardwareaufwand und den besten bekannten Algorithmen erreicht man bei mehreren Tausend Bit schnell Berechnungszeiten, die über die Lebensdauer unseres Universums hinausgehen.[24]

Bei der diskreten Exponentialfunktion ${\displaystyle f(x)=b^{x}\ {\bmod {\ }}m}$ handelt es sich nach heutigem Kenntnisstand somit um eine Einwegfunktion. Da es jedoch keinen mathematischen Beweis für deren Existenz gibt, wäre es theoretisch möglich, dass eines Tages ein schnelles Verfahren zur Berechnung des diskreten Logarithmus gefunden wird. Da dies jedoch schon seit längerem erfolglos versucht wird, kann man annehmen, dass dieser Fall nie eintreten wird.[24]

Beispiel:

Die diskrete Exponentialfunktion ${\displaystyle f(x)=3^{x}\ {\bmod {\ }}7}$ ordnet einem ${\displaystyle x}$ das Ergebnis von ${\displaystyle 3^{x}\ {\bmod {\ }}7}$ zu. Bei der Rechnung ${\displaystyle {\bmod {\ }}7}$ wird jeweils der Rest bezüglich des Moduls ${\displaystyle m=7}$ gebildet. Dadurch entsteht ein endlicher Zahlenraum ${\displaystyle [0,6]}$. Für die Werte ${\displaystyle x\neq 0}$ ist die Abbildung eindeutig. Der diskrete Logarithmus ist die Umkehrfunktion, also die Zuordnung von ${\displaystyle f(x)}$ nach ${\displaystyle x}$.

Eine Gruppe ist ein Paar ${\displaystyle (G,*)}$, bestehend aus einer Menge ${\displaystyle G}$ und einer assoziativen Verknüpfung ${\displaystyle *}$ auf ${\displaystyle G}$, die ein neutrales Element hat und für die jedes Element von ${\displaystyle G}$ ein inverses Element besitzt. Wenn für eine Gruppe zusätzlich das Kommutativgesetz gilt, spricht man von einer abelschen Gruppe. Eine Untergruppe ${\displaystyle (U,*)}$ einer Gruppe ${\displaystyle (G,*)}$ ist eine Teilmenge ${\displaystyle U}$ von ${\displaystyle G}$, die bezüglich der Verknüpfung ${\displaystyle *}$ selbst wieder eine Gruppe ist.

Beispielsweise bildet die Menge der ganzen Zahlen mit der Addition als Verknüpfung die (abelsche) Gruppe ${\displaystyle (\mathbb {Z} ,+)}$. Das neutrale Element der Addition ist die ${\displaystyle 0}$ (Null) und das additiv Inverse einer Zahl ${\displaystyle a}$ ist ihre Gegenzahl ${\displaystyle -a}$. Die ganzen Zahlen ${\displaystyle \mathbb {Z} }$ sind bezüglich der Addition wiederum eine Untergruppe der rationalen Zahlen ${\displaystyle \mathbb {Q} }$. Demgegenüber bilden die rationalen (und ganzen) Zahlen zusammen mit der Multiplikation keine Gruppe, weil die Zahl ${\displaystyle 0}$ kein inverses Element bezüglich der Multiplikation besitzt. Wenn man jedoch ${\displaystyle 0}$ aus ${\displaystyle \mathbb {Q} }$ entfernt, erhält man die (abelsche) Gruppe ${\displaystyle (\mathbb {Q} \setminus \{0\},\cdot )}$.

Eine zyklische Gruppe ist eine Gruppe, deren Elemente als Potenz eines ihrer Elemente dargestellt werden können. Unter Verwendung der multiplikativen Notation lauten die Elemente einer zyklischen Gruppe

${\displaystyle \ldots ,a^{-3},a^{-2},a^{-1},e=a^{0},a,a^{2},a^{3},\ldots }$,

wobei ${\displaystyle a^{-2}=a^{-1}\cdot a^{-1}}$ meint und ${\displaystyle e}$ das neutrale Element der Gruppe bezeichnet. Das Element ${\displaystyle a}$ wird Erzeuger oder Primitivwurzel der Gruppe genannt. Eine zyklische Gruppe besteht also nur aus Potenzen des Erzeugers ${\displaystyle a}$:

${\displaystyle \left\langle a\right\rangle$ :=\lbrace a^{n}\mid n\in \mathbb {Z} \rbrace .}

Bei einer Gruppe ${\displaystyle (G,*)}$ wird die Mächtigkeit ${\displaystyle |G|}$ auch als Ordnung der Gruppe bezeichnet. Für eine endliche Gruppe ${\displaystyle G=\{a_{1},a_{2},\dotsc ,a_{n}\}}$ ist die Ordnung also einfach die Anzahl ${\displaystyle n}$ der Gruppenelemente. Der Satz von Lagrange besagt, dass die Ordnung jeder Untergruppe einer endlichen Gruppe deren Mächtigkeit teilt.

Die prime Restklassengruppe ist die Gruppe der primen Restklassen bezüglich eines Moduls ${\displaystyle n}$. Sie wird als ${\displaystyle \mathbb {Z} _{n}^{*}}$ oder ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ notiert. Die primen Restklassen sind genau die multiplikativ invertierbaren Restklassen und sind daher endliche abelsche Gruppen bezüglich der Multiplikation. Die Menge ${\displaystyle \mathbb {Z} _{8}=\{0,...,7\}}$ bildet beispielsweise mit der Multiplikation modulo ${\displaystyle 8}$ als Verknüpfung keine Gruppe, selbst wenn die ${\displaystyle 0}$ ausgenommen wird. Es gibt noch weitere Zahlen, die kein inverses Element haben, nämlich ${\displaystyle 2}$, ${\displaystyle 4}$ und ${\displaystyle 6}$. Dies sind genau die Zahlen, die einen echten Teiler mit ${\displaystyle 8}$ gemeinsam haben. Die verbleibenden Elemente bilden schließlich die Multiplikative Gruppe ${\displaystyle \mathbb {Z} _{8}^{*}.}$

In der Kryptographie sind vor allem jene Zahlen ${\displaystyle n}$ von Interesse, für die alle Zahlen zwischen ${\displaystyle 1}$ und ${\displaystyle n-1}$ ein inverses Element modulo ${\displaystyle n}$ haben. Dies ist genau dann der Fall, wenn ${\displaystyle n}$ eine Primzahl ist (weshalb man ${\displaystyle p}$ statt ${\displaystyle n}$ schreibt). Die Zahlen zwischen ${\displaystyle 1}$ und ${\displaystyle p-1}$ bilden also zusammen mit der Modulo-Multiplikation die Gruppe ${\displaystyle \mathbb {Z} _{p}^{*}}$. Eine weitere Aussage, die sich beweisen lässt: Nimmt man ein beliebiges Element ${\displaystyle a}$ aus ${\displaystyle \mathbb {Z} _{p}^{*}}$ und betrachtet die Menge ${\displaystyle \{a,a^{2},a^{3},...,a^{p-1}({\bmod {\ }}p)\}}$, dann erhält man eine Untergruppe (mit ${\displaystyle a}$ als Generator der Untergruppe). Jede Untergruppe von ${\displaystyle \mathbb {Z} _{p}^{*}}$ hat mindestens einen Generator, und damit auch ${\displaystyle \mathbb {Z} _{p}^{*}}$ selbst. Die Gruppe ${\displaystyle \mathbb {Z} _{p}^{*}}$ ist also zyklisch.[25] Zum Beispiel ist ${\displaystyle \mathbb {Z} _{13}^{*}}$ eine zyklische Gruppe mit der ${\displaystyle 2}$ als Generator, denn jede Zahl von ${\displaystyle 1}$ bis ${\displaystyle 12}$ lässt sich als Potenz von ${\displaystyle 2}$ darstellen:[26]

Darstellung der zyklischen Gruppe ${\displaystyle \mathbb {Z} _{13}^{*}}$ mit Exponent ${\displaystyle a}$ außerhalb und den entsprechenden Werten innerhalb der Knoten.

• ${\displaystyle 1=2^{12}\ {\bmod {\ }}13}$
• ${\displaystyle 2=2^{1}\ {\bmod {\ }}13}$
• ${\displaystyle 3=2^{4}\ {\bmod {\ }}13}$
• ${\displaystyle 4=2^{2}\ {\bmod {\ }}13}$
• ${\displaystyle 5=2^{9}\ {\bmod {\ }}13}$
• ${\displaystyle 6=2^{5}\ {\bmod {\ }}13}$
• ${\displaystyle 7=2^{11}\ {\bmod {\ }}13}$
• ${\displaystyle 8=2^{3}\ {\bmod {\ }}13}$
• ${\displaystyle 9=2^{8}\ {\bmod {\ }}13}$
• ${\displaystyle 10=2^{10}\ {\bmod {\ }}13}$
• ${\displaystyle 11=2^{7}\ {\bmod {\ }}13}$
• ${\displaystyle 12=2^{6}\ {\bmod {\ }}13}$

Für ${\displaystyle a=3}$ als Generator erhält man dagegen nur die Untergruppe mit den Elementen ${\displaystyle \{1,3,9\}}$:

• ${\displaystyle 1=3^{3}\ {\bmod {\ }}13=3^{6}\ {\bmod {\ }}13=3^{9}\ {\bmod {\ }}13=3^{12}\ {\bmod {\ }}13}$
• ${\displaystyle 3=3^{1}\ {\bmod {\ }}13=3^{4}\ {\bmod {\ }}13=3^{7}\ {\bmod {\ }}13=3^{10}\ {\bmod {\ }}13}$
• ${\displaystyle 9=3^{2}\ {\bmod {\ }}13=3^{5}\ {\bmod {\ }}13=3^{8}\ {\bmod {\ }}13=3^{11}\ {\bmod {\ }}13}$

Es lässt sich nun leicht nachvollziehen, dass die Gleichung ${\displaystyle a^{x}=b\ {\bmod {\ }}p}$ immer lösbar ist, wenn ${\displaystyle a}$ ein Generator von ${\displaystyle \mathbb {Z} _{p}^{*}}$ ist, wobei dann ${\displaystyle b}$ ein Element von ${\displaystyle \mathbb {Z} _{p}^{*}}$ ist (außer ${\displaystyle 0}$). Der diskrete Logarithmus existiert also in ${\displaystyle Z_{p}^{*}}$ immer dann, wenn die Basis ein Generator von ${\displaystyle \mathbb {Z} _{p}^{*}}$ ist.[27] Stellt man die Zahlen in einem Kreis (Zyklus) der Potenzen dar, scheinen sie willkürlich verteilt zu sein. Dies gibt zumindest eine Vorstellung davon, weshalb der diskrete Logarithmus so aufwändig zu bestimmen ist.[28]

Man nennt ein erzeugendes Element von ${\displaystyle \mathbb {Z} _{p}^{*}}$ auch Primitivwurzel zum Modul ${\displaystyle p}$. Die Zahl ${\displaystyle 2}$ ist also eine Primitivwurzel modulo ${\displaystyle 13}$, die Zahl ${\displaystyle 3}$ dagegen nicht. Es lassen sich alle Elemente ${\displaystyle 1,2,\ldots ,12}$ der primen Restklassengruppe modulo ${\displaystyle 13}$ als Potenzen von ${\displaystyle 2}$ darstellen. In der Folge der Potenzen von ${\displaystyle 3}$ modulo ${\displaystyle 13}$ wiederholen sich jedoch die Reste (siehe oben).

Für eine Primzahl ${\displaystyle p}$ gibt es genau ${\displaystyle \varphi (p-1)}$ Primitivwurzeln ${\displaystyle {\bmod {\ }}p}$, wobei ${\displaystyle \varphi }$ für die Eulersche Phi-Funktion steht, die für jede natürliche Zahl die Anzahl ihrer teilerfremden natürlichen Zahlen angibt.

Für ${\displaystyle p=13}$ ist ${\displaystyle p-1=12}$ und ${\displaystyle \varphi (12)=4}$, woraus folgt, dass es ${\displaystyle 4}$ Primitivwurzeln modulo ${\displaystyle 13}$ gibt (nämlich ${\displaystyle 2}$, ${\displaystyle 6}$, ${\displaystyle 7}$ und ${\displaystyle 11}$).

Es ist zwar bewiesen, dass für jede Primzahl ${\displaystyle p}$ genau ${\displaystyle \varphi (p-1)}$ verschiedene Primitivwurzeln modulo ${\displaystyle p}$ existieren, es ist aber kein Algorithmus bekannt, der auch effizient eine beliebige Primitivwurzel berechnen kann. Wenn ${\displaystyle p}$ gegeben und die Faktorisierung von ${\displaystyle p-1}$ unbekannt ist, so kann man immerhin testen, ob es sich bei einer Zufallszahl ${\displaystyle g}$ um eine Primitivwurzel modulo ${\displaystyle p}$ handelt. Es muss gelten:

${\displaystyle g^{p-1}=1\ {\bmod {\ }}p}$ und ${\displaystyle g^{i}\neq \ 1{\bmod {\ }}p}$ für ${\displaystyle 2\leq i\leq p-2}$.

Für kryptographisch relevante Primzahlen ist eine solche Überprüfung aufgrund der Größe von ${\displaystyle p}$ nicht durchführbar.

Ist dagegen die Primfaktorzerlegung von ${\displaystyle p-1}$ bekannt, so ist ${\displaystyle g}$ genau dann eine Primitivwurzel modulo ${\displaystyle p}$, wenn gilt

${\displaystyle g^{(p-1)/p_{i}}\neq 1\ {\bmod {\ }}p}$ für alle Primfaktoren ${\displaystyle p_{i}}$.

Besonders einfach wird der „Primitivwurzel-Test“, wenn ${\displaystyle p-1=2\times q}$ mit einer Primzahl ${\displaystyle q}$ gilt. Dann braucht man nur zu testen, ob

${\displaystyle g^{2}\neq 1\ {\bmod {\ }}p}$ und ${\displaystyle g^{q}\neq 1\ {\bmod {\ }}p}$

ist. Trifft dies zu, ist ${\displaystyle g}$ eine Primitivwurzel modulo ${\displaystyle p}$.[29]

Beispiel:

Sei ${\displaystyle p=23}$. Dann ist ${\displaystyle p-1=22=11\times 2}$ mit ${\displaystyle q=11}$, also prim. Um zu testen, ob eine beliebige Zahl ${\displaystyle g}$ eine Primitivwurzel modulo ${\displaystyle 23}$ ist, muss ${\displaystyle g^{2}\ {\bmod {\ }}23\neq 1}$ und ${\displaystyle g^{11}\ {\bmod {\ }}23\neq 1}$ überprüft werden. Für ${\displaystyle g=5}$ gilt beispielsweise ${\displaystyle 5^{2}\ {\bmod {\ }}23=2}$ und ${\displaystyle 5^{11}\ {\bmod {\ }}23=22}$. Also ist ${\displaystyle 5}$ eine Primitivwurzel modulo ${\displaystyle 23}$. Die Weiteren sind 7, 10, 11, 14, 15, 17, 19, 20 und 21. Mit ${\displaystyle \varphi (23-1)=\varphi (22)=10}$ lässt sich einsehen, dass damit (alle 10) Primitivwurzeln modulo ${\displaystyle 23}$ gefunden sind.

Zunächst soll die Grundidee des Diffie-Hellman-Merkle-Schlüsselaustauschs anhand von „Farbmischen“ anschaulich dargestellt werden, wie es die Illustration veranschaulicht. In Wirklichkeit wären die Farben Zahlen und das Mischen von Farben entspräche der diskreten Exponentialfunktion.

Das Mischen von Farben wird hier als eine Einwegfunktion aufgefasst: Es ist „leicht“, zwei oder mehrere verschiedene Farben zu mischen. Die Umkehrung, das Zerlegen einer Farbmischung in ihre ursprünglichen Farb-Komponenten, ist jedoch sehr aufwändig, das heißt nicht effizient durchführbar.

Alice und Bob einigen sich zunächst öffentlich auf eine gemeinsame Farbe (im Beispiel Gelb). Außerdem wählt jeder der beiden Kommunikationspartner für sich eine geheime Farbe (Alice Orange und Bob Türkis). Bob und Alice mischen nun jeweils die gemeinsame Farbe mit ihrer geheimen Farbe. Im Beispiel entsteht dabei für Alice Beige und für Bob Graublau. Diese Farbmischungen tauschen Alice und Bob nun über die abhörbare Leitung aus. Einer potenziellen Lauscherin Eve ist es nicht effizient möglich, aus den öffentlichen Informationen (gelb, beige, graublau) auf die geheimen Farben von Alice und Bob zu schließen.

In einem letzten Schritt mischen nun Alice und Bob die Farbmischung ihres Gegenübers mit ihrer eigenen geheimen Farbe. Daraus entsteht wiederum eine neue Farbe (im Beispiel Ockerbraun), die für beide Kommunikationspartner gleich ist (gelb + orange + türkis = gelb + türkis + orange = ockerbraun). Somit haben Alice und Bob eine gemeinsame geheime Farbe. Für Eve ist es unmöglich, diese herauszufinden, da sie Alices und Bobs geheime Farbzutaten nicht kennt.

Prinzip des Diffie-Hellman-Merkle-Schlüsselaustauschs
a: privater Schlüssel von Alice
b: privater Schlüssel von Bob
p: öffentlich bekannte Primzahl
g: öffentlich bekannte natürliche Zahl kleiner als p
A: öffentlicher Schlüssel von Alice
B: öffentlicher Schlüssel von Bob
K: geheimer Sitzungs-Schlüssel für Alice und Bob

Die beiden Kommunikationspartner Alice und Bob wollen über ein unsicheres Medium, etwa eine Kabel- oder Funkverbindung, verschlüsselt kommunizieren. Dazu soll ein symmetrisches Kryptosystem eingesetzt werden, für das beide jedoch zunächst einen gemeinsamen geheimen Schlüssel benötigen. Das DHM-Kommunikationsprotokoll sorgt dafür, dass sie einen geheimen Schlüssel berechnen können, ohne dass Dritte (Eve) diesen erfahren können. Den auf diese Weise errechneten Schlüssel können sie dann in Zukunft verwenden, um verschlüsselt mit einem symmetrischen Kryptosystem zu kommunizieren.

1. Alice und Bob einigen sich zunächst öffentlich auf eine große Primzahl ${\displaystyle p}$ und eine natürliche Zahl ${\displaystyle g}$, die kleiner als ${\displaystyle p}$ ist. Sich öffentlich darauf einigen bedeutet, dass jeder diese beiden Zahlen kennen darf (also auch potenzielle Lauscher wie Eve). Idealerweise handelt es sich bei ${\displaystyle g}$ um einen Erzeuger der zyklischen Gruppe ${\displaystyle \mathbb {Z} _{p}^{*}}$, das Verfahren funktioniert aber auch, wenn ${\displaystyle g}$ einen anderen Wert kleiner ${\displaystyle p}$ annimmt. In der Praxis ist es ohnehin meist so, dass ${\displaystyle g}$ und ${\displaystyle p}$ vorgegeben sind und von vielen Anwendern verwendet werden.[30]
2. Alice und Bob erzeugen jeweils eine geheimzuhaltende Zufallszahl (privater Schlüssel) ${\displaystyle a}$ bzw. ${\displaystyle b}$ aus der Menge ${\displaystyle \{1,\ldots ,p-1\}}$. ${\displaystyle a}$ und ${\displaystyle b}$ werden nicht übertragen, bleiben also potenziellen Lauschern, aber auch dem jeweiligen Kommunikationspartner, unbekannt. Nur Alice kennt die Zahl ${\displaystyle a}$ und nur Bob kennt die Zahl ${\displaystyle b}$.
3. Alice berechnet mit ihrer geheimen Zahl den öffentlichen Schlüssel ${\displaystyle A=g^{a}\ {\bmod {\ }}p}$ und schickt ${\displaystyle A}$ an Bob. Bob berechnet mit seiner geheimen Zahl den öffentlichen Schlüssel ${\displaystyle B=g^{b}\ {\bmod {\ }}p}$ und schickt ${\displaystyle B}$ an Alice.
4. Alice erhält ${\displaystyle B}$ von Bob und berechnet mit ihrem privaten Schlüssel ${\displaystyle a}$ die Zahl ${\displaystyle K_{1}=B^{a}\ {\bmod {\ }}p}$. Bob berechnet mit dem erhaltenen ${\displaystyle A}$ und seinem privaten Schlüssel ${\displaystyle b}$ ebenfalls die Zahl ${\displaystyle K_{2}=A^{b}\ {\bmod {\ }}p}$. Die beiden haben die gleiche Zahl ${\displaystyle K_{1}=K_{2}}$ berechnet. Diese ist somit der gesuchte gemeinsame Schlüssel ${\displaystyle K}$.

Nur Alice und Bob kennen ${\displaystyle K}$. Eve kann aus der abgehörten Kommunikation ${\displaystyle K}$ nicht berechnen. Dazu müsste sie den diskreten Logarithmus lösen, was nach heutigem Kenntnisstand nicht effizient möglich ist, wenn die Zahlen groß genug sind. Alice und Bob können also ${\displaystyle K}$ gefahrlos für eine symmetrische Verschlüsselung nutzen.[30]

Dass beide Kommunikationspartner denselben Wert für ${\displaystyle K}$ berechnen, zeigen die folgenden beiden Restklassengleichungen[31]:

${\displaystyle K_{1}=B^{a}\ {\bmod {\ }}p=(g^{b}\ {\bmod {\ }}p)^{a}\ {\bmod {\ }}p=(g^{b})^{a}\ {\bmod {\ }}p=g^{ba}\ {\bmod {\ }}p}$.

${\displaystyle K_{2}=A^{b}\ {\bmod {\ }}p=(g^{a}\ {\bmod {\ }}p)^{b}\ {\bmod {\ }}p=(g^{a})^{b}\ {\bmod {\ }}p=g^{ab}\ {\bmod {\ }}p}$.

Da die Multiplikation kommutativ ist, gilt des Weiteren

${\displaystyle g^{ba}\ {\bmod {\ }}p=g^{ab}\ {\bmod {\ }}p}$

und somit

${\displaystyle K_{1}=K_{2}}$.

Alice und Bob erhalten also nach ihren jeweiligen Berechnungen die genau gleiche Zahl, nämlich den geheimen Schlüssel ${\displaystyle K=K_{1}=K_{2}}$.

Beispiel:

Das folgende Beispiel dient zur Veranschaulichung und benutzt deshalb sehr kleine Zahlen. In der tatsächlichen Anwendung werden dagegen Zahlen mit mindestens mehreren hundert Stellen benutzt.

1. Alice und Bob einigen sich auf die beiden öffentlichen Schlüssel ${\displaystyle p=13}$ und ${\displaystyle g=2}$ (${\displaystyle 2}$ ist ein Generator der Gruppe ${\displaystyle \mathbb {Z} _{13}^{*}}$, siehe Abschnitt „Gruppentheorie“).
2. Alice wählt die Zufallszahl ${\displaystyle a=5}$ als geheimen Schlüssel und Bob ${\displaystyle b=8}$.
3. Nun berechnet Alice ${\displaystyle A=g^{a}\ {\bmod {\ }}p=2^{5}\ {\bmod {\ }}13=6}$ und sendet ${\displaystyle A}$ an Bob. Bob berechnet ${\displaystyle B=g^{b}\ {\bmod {\ }}p=2^{8}\ {\bmod {\ }}13=9}$ und sendet ${\displaystyle B}$ an Alice.
4. Alice berechnet ${\displaystyle K_{1}=B^{a}\ {\bmod {\ }}p=9^{5}\ {\bmod {\ }}13=3}$. Bob berechnet ${\displaystyle K_{2}=A^{b}\ {\bmod {\ }}p=6^{8}\ {\bmod {\ }}13=3}$.
5. Beide erhalten das gleiche Ergebnis ${\displaystyle K=K_{1}=K_{2}=3}$.

Die Lauscherin Eve kann zwar die Zahlen 13, 2, 6 und 9 mithören, das eigentliche gemeinsame Geheimnis von Alice und Bob ${\displaystyle K=3}$ bleibt ihr aber verborgen. ${\displaystyle K=3}$ kann als Schlüssel für die nachfolgende Kommunikation verwendet werden.

Mit Hilfe der abgefangenen Nachrichten kann Eve immerhin die folgenden Gleichungen aufstellen:

${\displaystyle 6=2^{a}\ {\bmod {\ }}13}$

${\displaystyle 9=2^{b}\ {\bmod {\ }}13}$

Daraus kann sie beispielsweise durch Ausprobieren die beiden geheimen Zahlen ${\displaystyle a=5}$ und ${\displaystyle b=8}$ bestimmen. Den vereinbarten Schlüssel ${\displaystyle K}$ von Alice und Bob kann sie nun mit

${\displaystyle K=g^{ab}\ {\bmod {\ }}p}$

ausrechnen.

Wenn jedoch die Primzahl ${\displaystyle p}$ groß genug gewählt wird und ${\displaystyle g}$ ein Generator der Gruppe ${\displaystyle \mathbb {Z} _{p}^{*}}$ ist, ist es für Eve zu aufwändig, um alle Zahlen zwischen ${\displaystyle 1}$ und ${\displaystyle p-1}$ durchzuprobieren, die als Resultat der modularen Potenz ${\displaystyle g^{a}\ {\bmod {\ }}p}$ in Frage kommen.[32]

Das folgende Programm in der Programmiersprache Python zeigt die Implementierung des Diffie-Hellman-Schlüsselaustauschs für ${\displaystyle p=107}$ und ${\displaystyle g=3}$.

from random import randint

# Festlegung der Gruppe:
p = 107

g = 3
# Zufällige Wahl der geheimen Schlüssel von Alice und Bob:

a = randint(1,p-1)
b = randint(1,p-1)
# Berechnung der Öffentlichen Schlüssel:

A = pow(g, a, p)
B = pow(g, b, p)

print(f'Öffentlicher Schlüssel von Alice: {A=}')
print(f'Öffentlicher Schlüssel von Bob:   {B=}')
# Berechnung des gemeinsamen Geheimnisses:

k_a = pow(B, a, p)
k_b = pow(A, b, p)

print(f'{k_a=}')
print(f'{k_b=}')

Angenommen, die Lauscherin Eve erfährt an der unsicheren Leitung die Zahlen ${\displaystyle p}$, ${\displaystyle g}$, ${\displaystyle A}$ und ${\displaystyle B}$, aber nicht die diskreten Logarithmen ${\displaystyle a}$ von ${\displaystyle A}$ und ${\displaystyle b}$ von ${\displaystyle B}$ zur Basis ${\displaystyle g}$. Mit der Kenntnis von ${\displaystyle a}$ und ${\displaystyle b}$ wäre es für sie eine leichte Aufgabe, den Schlüssel ${\displaystyle K=g^{ab}\ {\bmod {\ }}p}$ zu bestimmen. Die Zahlen ${\displaystyle a}$ und ${\displaystyle b}$ herauszufinden ist jedoch sehr schwer, wenn die Zahlen ${\displaystyle p}$, ${\displaystyle a}$ und ${\displaystyle b}$ sehr groß sind, beispielsweise Zahlen mit mehreren hundert Stellen im Dezimalsystem.[7] Aus dieser Problemstellung ergibt sich das Computational-Diffie-Hellman-Problem:

Wenn ein Element ${\displaystyle g}$ einer Gruppe und die Werte ${\displaystyle A=g^{a}}$ und ${\displaystyle B=g^{b}}$ gegeben sind, welchen Wert hat dann ${\displaystyle K=g^{ab}}$, mit ${\displaystyle a,b}$ unbekannt ?

Da dieses Problem in bestimmten Gruppen nur mit enormem Rechenaufwand zu lösen ist, kann ein Angreifer aus den beiden beim Diffie-Hellman-Merkle-Schlüsselaustausch übertragenen Nachrichten nicht den erzeugten Schlüssel berechnen.

Das Diffie-Hellman-Problem ist eng verwandt mit dem Diskreter-Logarithmus-Problem. Diskrete Logarithmen zu berechnen ist die einzige bekannte Methode, um das DHM-Verfahren zu brechen. Solange dies nicht in vertretbarer Zeit lösbar ist, ist es für einen Angreifer unmöglich, den geheimen Schlüssel zu bestimmen. Es ist allerdings nicht bewiesen, dass dies tatsächlich die einzige Methode ist, ob also jemand, der das Diffie-Hellman-Problem lösen könnte, auch diskrete Logarithmen effizient berechnen könnte.[33] Ueli Maurer hat gezeigt, dass beide Probleme zumindest unter bestimmten Voraussetzungen äquivalent sind.[34]

Soll es für einen Angreifer unmöglich sein, aus den öffentlich verfügbaren Informationen irgendwelche Informationen über den transportierten Schlüssel zu gewinnen, muss das Decisional-Diffie-Hellman-Problem (DDH) unangreifbar sein. Dieses Problem lässt sich folgendermaßen beschreiben:

Ein Angreifer erhält drei Zahlen: ${\displaystyle A=g^{a}\ {\bmod {\ }}p}$, ${\displaystyle B=g^{b}\ {\bmod {\ }}p}$ und ${\displaystyle C=g^{c}\ {\bmod {\ }}p}$. Dabei wurden entweder ${\displaystyle a}$, ${\displaystyle b}$ und ${\displaystyle c}$ zufällig und gleichverteilt in ${\displaystyle \{0,...,p-2\}}$ gewählt oder ${\displaystyle c=ab\ {\bmod {\ }}p}$ gesetzt. Im zweiten Fall heißt ${\displaystyle (A,B,C)}$ Diffie-Hellman-Tripel. Der Angreifer muss entscheiden, ob ein solches Tripel vorliegt oder nicht. Kann er das nicht, ist es ihm unmöglich, aus ${\displaystyle g^{a}}$ und ${\displaystyle g^{b}}$ Rückschlüsse auf ${\displaystyle g^{ab}}$ zu ziehen.[35]

Das Problem besteht also darin, bei gegebenem ${\displaystyle g^{a}\ {\bmod {\ }}p}$, ${\displaystyle g^{b}\ {\bmod {\ }}p}$ und ${\displaystyle g^{c}\ {\bmod {\ }}p}$ zu entscheiden, ob ${\displaystyle g^{c}=g^{ab}}$ ist.

Wer das Computational-Diffie-Hellman-Problem lösen kann, ist offensichtlich auch dazu in der Lage, das Decisional-Diffie-Hellman-Problem zu lösen. Für den umgekehrten Fall ist das nicht klar.

Bei einer Auswahl von ${\displaystyle g}$ als Primitivwurzel kann das Decisional-Diffie-Hellman-Problem angegriffen werden. Dies liegt in folgendem Theorem begründet:

Sei ${\displaystyle p}$ eine Primzahl, sei ${\displaystyle g}$ eine Primitivwurzel modulo ${\displaystyle p}$ und seien ${\displaystyle a,b\in \{0,...,p-2\}}$. Dann ist ${\displaystyle g^{ab}}$ genau dann ein quadratischer Rest modulo ${\displaystyle p}$, wenn ${\displaystyle g^{a}}$ oder ${\displaystyle g^{b}}$ ein quadratischer Rest ist modulo ${\displaystyle p}$.

Das Theorem folgt daraus, dass eine Potenz von ${\displaystyle g}$ genau dann ein quadratischer Rest modulo ${\displaystyle p}$ ist, wenn der Exponent gerade ist.[33]

Ein Angreifer kann also prüfen, ob das Kriterium aus diesem Theorem erfüllt ist. Er kann zwar nicht immer entscheiden, ob ein Diffie-Hellman-Tripel vorliegt, er antwortet aber zu 75 % richtig. Sein Vorteil gegenüber reinem Raten beträgt also 50 %.[36]

Die Sicherheit des Verfahrens basiert nicht zuletzt auf der Länge der gewählten Zahlen. So muss die Primzahl ${\displaystyle p}$ dermaßen gewählt werden, dass diskrete Logarithmen modulo ${\displaystyle p}$ mit derzeit bekannten Methoden nicht (effizient genug) berechnet werden können. Je größer die verwendete Primzahl, desto sicherer das Verfahren, aber auch desto aufwendiger.[37] Das Bundesamt für Sicherheit in der Informationstechnik empfiehlt im Fall eines Einsatzzeitraum[s] über das Jahr 2022 hinaus für ${\displaystyle p}$ eine Schlüssellänge von mindestens 3000 Bit (Stand 2017).[38]

Die DHM-Primzahl ${\displaystyle p}$ muss zudem so gewählt werden, dass Algorithmen zur Berechnung des diskreten Logarithmus kein leichtes Spiel haben. So muss beispielsweise vermieden werden, dass ${\displaystyle p-1}$ nur kleine Primfaktoren hat. Ansonsten kann nämlich der Pohlig-Hellman-Algorithmus angewendet werden, der nicht von der Gruppenordnung, sondern vom größten Faktor der Gruppenordnung abhängt. Außerdem sollte ${\displaystyle p}$ für das Zahlkörpersieb möglichst ungeeignet sein. Dies ist der Fall, wenn es ein irreduzibles Polynom vom Grad 5 gibt, das sehr kleine Koeffizienten und eine Nullstelle ${\displaystyle {\bmod {\ }}p}$ hat.[39]

Die Zahl ${\displaystyle g}$ sollte so gewählt werden, dass alle Zahlen zwischen ${\displaystyle 1}$ und ${\displaystyle p-1}$ als Resultat der modularen Potenz ${\displaystyle g^{a}\ {\bmod {\ }}p}$ in Frage kommen. Erst dann ist es zu aufwändig, alle Zahlen durchzuprobieren (wenn darüber hinaus die Primzahl ${\displaystyle p}$ groß genug gewählt worden ist). Diese Eigenschaft erfüllt die Zahl ${\displaystyle g}$, wenn sie eine Primitivwurzel zum Modul ${\displaystyle p}$ ist, d. h. ein Erzeuger der Gruppe ${\displaystyle \mathbb {Z} _{p}^{*}}$.[26] Wenn Alice und Bob beispielsweise ${\displaystyle g=1}$ wählen, so funktioniert das Verfahren zwar noch immer, doch der Schlüssel ${\displaystyle K}$ ist auf jeden Fall ${\displaystyle 1}$, denn ${\displaystyle 1}$ ist genau der Generator der Untergruppe von ${\displaystyle \mathbb {Z} _{p}^{*}}$ mit einem Element. Ähnlich unsicher ist das Verfahren, wenn Alice und Bob für ${\displaystyle g}$ einen Generator einer anderen kleinen Untergruppe wählen. Bei einem Generator einer großen Untergruppe ist das Verfahren sicherer, am besten wird ein Generator der ganzen Gruppe gewählt.[8]

Wie im Abschnitt „Prime Restklassengruppe und Primitivwurzel“ gezeigt, lässt sich eine Primitivwurzel relativ leicht finden, wenn man die DHM-Primzahl als ${\displaystyle p=2\times q+1}$ mit einer Primzahl ${\displaystyle q}$ wählt. Wie jedoch im vorherigen Abschnitt gezeigt, kann das Decisional-Diffie-Hellman-Problem angegriffen werden, wenn man ${\displaystyle g}$ als Primitivwurzel wählt.

Da die Erzeugung sicherer Primzahlen rechenaufwendig ist, verwenden viele Implementierungen eine feste Primzahl ${\displaystyle p}$.[40] Einige Netzwerkprotokolle wie etwa Internet Key Exchange geben eine Liste von möglichen Gruppen und deren Primzahl vor.

Die Verwendung fester Gruppen und Primzahlen kann ein Angreifer ausnutzen, um einen Großteil der Berechnung zum Brechen des diskreten Logarithmus vorab durchzuführen und um mehrere Ziele gleichzeitig anzugreifen. Der Zahlkörpersieb-Algorithmus besteht aus vier Schritten, wobei die ersten drei Schritte lediglich die Primzahl ${\displaystyle p}$ benötigen. Ist ${\displaystyle p}$ bekannt, kann ein Angreifer somit den Großteil vorberechnen und die Ergebnisse für jeden auf ${\displaystyle p}$ basierenden Schlüsselaustausch wiederverwenden. Dadurch kann zum Beispiel der Logjam-Angriff in TLS, nach einer einwöchigen Vorberechnung, einen 512-Bit-DHM-Schlüsselaustausch in rund 70 Sekunden brechen.[40]

Nach Schätzungen eines Forscherteams kann ein Angreifer mit Vorberechnung der 10 häufigsten 1024-Bit-Primzahlen den Netzwerkverkehr von 66 % der VPNs, 26 % der SSH-Server, 16 % der SMTP-Server und 24 % der HTTPS-Websites im Internet entschlüsseln. Die Forscher schätzen, dass der Rechenaufwand zum Brechen von 1024-Bit-Diffie-Hellman von einem staatlichen Angreifer wie der National Security Agency aufgebracht werden kann.[40]

Der Diffie-Hellman-Merkle-Schlüsselaustausch ist nicht mehr sicher, wenn der Angreifer bei einem Man-in-the-Middle-Angriff Datenpakete verändern kann. Im Alice-und-Bob-Modell heißt ein solcher Angreifer, der aktiv in das Geschehen eingreifen kann, Mallory (von engl. malicious, dt. i. e. hinterhältig, heimtückisch). Mallory fängt bei einem Man-in-the-Middle-Angriff die von Alice und Bob gesendeten Nachrichten ab und sendet stattdessen jeweils seine eigene Nachricht

${\displaystyle Z=g^{z}\mod p}$

weiter, die er aus einer beliebigen Zahl ${\displaystyle z}$ und den öffentlich bekannten Zahlen ${\displaystyle g}$ und ${\displaystyle p}$ berechnet.

Nach dem Schlüsselaustausch besitzen die beiden Kommunikationspartner Alice und Bob unterschiedliche Schlüssel ${\displaystyle K_{A}}$ und ${\displaystyle K_{B}}$. Im Prinzip wurde zweimal ein DHM-Schlüsselaustausch durchgeführt: einmal zwischen Alice und Angreifer Mallory und einmal zwischen Mallory und Bob. Dabei erlangt Mallory Kenntnis der beiden Schlüssel ${\displaystyle K_{A}}$ und ${\displaystyle K_{B}}$.

${\displaystyle K_{A}=Z^{a}{\bmod {p}}=(g^{z})^{a}{\bmod {p}}=(g^{a})^{z}{\bmod {p}}=A^{z}{\bmod {p}}}$

${\displaystyle K_{B}=Z^{b}{\bmod {p}}=(g^{z})^{b}{\bmod {p}}=(g^{b})^{z}{\bmod {p}}=B^{z}{\bmod {p}}}$

Da Alice und Bob im weiteren Verlauf davon ausgehen, mit dem jeweils Anderen zu kommunizieren, kann Mallory die folgende symmetrisch verschlüsselte Kommunikation abhören. Diese leitet er dazu weiterhin über sich selbst um. Daten von Alice entschlüsselt Mallory mit ${\displaystyle K_{A}}$ und verschlüsselt sie wieder mit ${\displaystyle K_{B}}$, bevor er sie an Bob weiterschickt. Dabei kann Mallory den Nachrichteninhalt sowohl lesen als auch unbemerkt verändern. Die gleiche Vorgehensweise wendet er auch für die Gegenrichtung an.

Um einen solchen Man-in-the-Middle-Angriff auszuschließen, müssen die ausgetauschten Nachrichten authentifiziert werden. Dazu wird ein Informationsvorsprung benötigt, der über einen authentifizierten Kanal erreicht wird.[41]

Ein Seitenkanalangriff bezeichnet eine kryptoanalytische Methode, die die physische Implementierung eines Kryptosystems in einem Gerät (z. B. einer Chipkarte, eines Security-Tokens oder eines Hardware-Sicherheitsmoduls) oder in einer Software ausnutzt. Dabei wird nicht das kryptographische Verfahren selbst, sondern nur eine bestimmte Implementierung angegriffen. Das Prinzip beruht darauf, ein kryptographisches Gerät bei der Ausführung der kryptologischen Algorithmen zu beobachten und Korrelationen zwischen den beobachteten Daten und dem verwendeten Schlüssel zu finden.

Im Jahr 1995 veröffentlichte Paul Kocher eine neuartige Methode, mit der es ihm gelang, Implementierungen von Diffie-Hellman, RSA und DSA zu brechen: der Zeitangriff (timing attack).[42]

Ziel des Zeitangriffs ist die diskrete Exponentialfunktion. Wenn eine Krypto-Implementierung ${\displaystyle g^{a}\ {\bmod {\ }}p}$ für irgendwelche größeren Zahlen ${\displaystyle g}$, ${\displaystyle a}$ und ${\displaystyle p}$ berechnet, dann geschieht dies fast immer mit dem Square-and-Multiply-Algorithmus. Bei diesem ist für jedes Bit von ${\displaystyle a}$ eine Aktion festgesetzt: Hat das gerade bearbeitete Bit den Wert ${\displaystyle 1}$, dann ist diese Aktion eine Multiplikation, ansonsten eine Quadrierung. Da die Rechenzeiten für die Multiplikationen länger dauern als für die Quadrierungen, kann Eve aus Zeitmessungen Rückschlüsse auf die Zahl der Einsen in ${\displaystyle a}$ ziehen. Variiert er die Zahl ${\displaystyle g}$, reichen irgendwann die Informationen aus, um ${\displaystyle a}$ zu berechnen. Schon mit einigen Tausend Zeitmessungen lassen sich entsprechende Implementierungen mit 1024-Bit-Schlüsseln brechen.[43]

Um solche Zeitangriffe zu verhindern, müssen jedoch bei der Implementierung lediglich Verzögerungen in den Ver- bzw. Entschlüsselungsprozess eingebaut werden. Mit dem als Blinding genannten Verfahren wird zum Beispiel an einer Stelle des Verfahrens eine Zufallszahl eingerechnet, die an anderer Stelle wieder herausgerechnet wird. Eine andere Möglichkeit besteht darin, den Prozess so zu gestalten, dass er unabhängig vom Eingabewert immer gleich lange dauert.[44]

Bei einem Stromangriff misst ein Oszilloskop den Stromverbrauch eines Verfahrens.

Im Jahr 1998 stellten Paul Kocher, Joshua Jaffe und Benjamin Jun erstmals das Konzept des Stromangriffs vor.[45] Bei Stromangriffen wird nicht nur die Verarbeitungszeit gemessen, sondern mit einem Oszilloskop auch der Stromverbrauch. Besonders Smartcards sind gegenüber Stromangriffen anfällig, da diese auf eine externe Stromversorgung angewiesen sind. Ein Angreifer misst die Ver- und Entschlüsselungsvorgänge und versucht bestimmte Stellen der Stromverbrauchskurve einzelnen Bestandteilen des Verfahrens zuzuordnen. Auch hier ist der Square-and-Multiply-Algorithmus ein geeignetes Ziel, da sich bei diesem Multiplikationen und Quadrierungen am Stromverbrauch oft gut unterscheiden lassen. Stromangriffe sind etwas aufwendiger in der Durchführung als Zeitangriffe, gelten jedoch als wirkungsvoller.[46]

Als Gegenmaßnahme gegen Stromangriffe kann der Hersteller von Krypto-Modulen den Stromverbrauch verschleiern, indem er Dummy-Operationen in einen Ver- bzw. Entschlüsselungsvorgang einbaut. Eine weitere Möglichkeit besteht darin, ein künstliches Stromrauschen zu erzeugen, das den eigentlichen Stromverbrauch überlagert.[47]

Ein Körper ist eine Menge ${\displaystyle K}$ versehen mit zwei inneren zweistelligen Verknüpfungen „${\displaystyle +}$“ und „${\displaystyle \cdot }$“, die meist „Addition“ und „Multiplikation“ genannt werden. Ein Körper ist bezüglich der Addition und der Multiplikation ohne Null eine abelsche Gruppe und es gelten die Distributivgesetze. Der bekannteste Körper ist die Menge der reellen Zahlen ${\displaystyle \mathbb {R} }$, auf der Addition und Multiplikation in üblicher Weise definiert sind.

Für eine Primzahl ${\displaystyle p}$ bildet die Menge der Zahlen zwischen ${\displaystyle 0}$ und ${\displaystyle p-1}$ sowohl mit der Modulo-Addition als auch mit der Modulo-Multiplikation ohne Null eine Gruppe. Die Restklassen ganzer Zahlen modulo ${\displaystyle p}$, geschrieben ${\displaystyle \mathbb {F} _{p}}$ oder ${\displaystyle \operatorname {GF} (p)}$, bilden somit einen endlichen Körper (auch Galoiskörper, engl. Galois field). Außerdem gibt es für jede Primzahl ${\displaystyle p}$ und jede natürliche Zahl ${\displaystyle n}$ (bis auf Isomorphie) genau einen Körper mit ${\displaystyle p^{n}}$ Elementen, der mit ${\displaystyle \mathbb {F} _{p^{n}}}$ oder ${\displaystyle \operatorname {GF} (p^{n})}$ bezeichnet wird. In der Elliptic Curve Cryptography sind insbesondere die beiden Spezialfälle ${\displaystyle n=1}$ und ${\displaystyle p=2}$ von Bedeutung, also ${\displaystyle \operatorname {GF} (p)}$ und ${\displaystyle \operatorname {GF} (2^{n})}$. Mit diesen lassen sich ECC-Verfahren am besten realisieren.[50]

Addition von Punkten P und Q auf einer elliptischen Kurve

Verdoppelung eines Punktes P auf einer elliptischen Kurve

Eine elliptische Kurve (EC) ist eine Menge von Punkten ${\displaystyle (x,y)}$ mit Werten aus einem Körper ${\displaystyle K}$, die eine kubische Gleichung der folgenden Form erfüllen:

${\displaystyle y^{2}=x^{3}+ax+b}$. (Kurze Weierstraß-Gleichung)

Die (reellen) Koeffizienten ${\displaystyle a}$ und ${\displaystyle b}$ müssen dabei die Bedingung ${\displaystyle 4a^{3}+27b^{2}\neq 0}$ erfüllen, um Singularitäten auszuschließen.

Eine elliptische Kurve ist eine glatte algebraische Kurve der Ordnung 3 in der projektiven Ebene. Dargestellt werden elliptische Kurven meist als Kurven in der affinen Ebene, sie besitzen aber noch einen zusätzlichen Punkt im Unendlichen, der hier als ${\displaystyle {\mathcal {O}}}$ (sprich „O“) bezeichnet wird, jedoch nicht mit dem Nullpunkt des Koordinatensystems zu verwechseln ist. Über dem Körper ${\displaystyle K=\mathbb {R} }$ der reellen Zahlen bilden die Punkte eine Kurve in der reellen Ebene.[51]

Eine wichtige Eigenschaft elliptischer Kurven ist folgende: Schneidet eine Gerade eine solche Kurve, dann gibt es genau drei Schnittpunkte. Dabei treten folgende Fälle auf:

• Bei einer Geraden, die parallel zur ${\displaystyle y}$-Achse verläuft, ist einer der drei Schnittpunkte ${\displaystyle {\mathcal {O}}}$.
• Bei einer Geraden, welche die Kurve berührt, wird der Berührpunkt als doppelter Schnittpunkt gezählt.
• Bei allen anderen Geraden sind die Schnittpunkte offensichtlich.[52]

Durch diese Eigenschaft lässt sich mit Hilfe elliptischer Kurven eine Gruppe ${\displaystyle \operatorname {E} (K)}$ definieren:

Sei ${\displaystyle G}$ die Punktmenge einer elliptischen Kurve, vereinigt mit dem Punkt ${\displaystyle {\mathcal {O}}}$ im Unendlichen. Man definiert die Gruppenoperation, die üblicherweise als Punktaddition bezeichnet wird, wie folgt:

• Um die Summe zweier Punkte ${\displaystyle P}$ und ${\displaystyle Q}$ zu berechnen, zeichne eine Gerade durch ${\displaystyle P}$ und ${\displaystyle Q}$ (falls ${\displaystyle P=Q}$, zeichne die Tangente an EC durch ${\displaystyle P}$)
• Finde den dritten Schnittpunkt ${\displaystyle R}$ dieser Geraden mit der Kurve EC. (Falls die Gerade parallel zur ${\displaystyle y}$-Achse läuft, so ist dieser Schnittpunkt ${\displaystyle {\mathcal {O}}}$.)
• Die Summe ${\displaystyle P+Q}$ ist der Punkt von EC, der durch Spiegelung von ${\displaystyle R}$ an der ${\displaystyle x}$-Achse entsteht. Die Spiegelung von ${\displaystyle {\mathcal {O}}}$ ist wiederum ${\displaystyle {\mathcal {O}}}$.[51]

Das neutrale Element der Gruppe ist ${\displaystyle {\mathcal {O}}}$. Es gilt ${\displaystyle P+{\mathcal {O}}={\mathcal {O}}+P=P}$ für alle Punkte ${\displaystyle P}$ der elliptischen Kurve. Das Inverse eines Punktes erhält man, indem man an ihn eine Gerade anlegt, die parallel zur ${\displaystyle y}$-Achse verläuft. Ist diese Gerade eine Tangente, dann ist der Punkt selbst sein inverses Element.[51][52]

Der Punkt ${\displaystyle P+P}$ wird mit ${\displaystyle 2P}$ bezeichnet, entsprechend definiert man ${\displaystyle kP=P+\ldots +P}$ als ${\displaystyle k}$-fache Addition des Punktes ${\displaystyle P}$. Ist ${\displaystyle P}$ nicht der ${\displaystyle {\mathcal {O}}}$-Punkt, kann auf diese Weise jeder Punkt der Kurve E erreicht werden (d. h., zu jedem Punkt ${\displaystyle Q}$ auf der Kurve existiert eine natürliche Zahl ${\displaystyle k}$ mit ${\displaystyle Q=kP}$), wenn man die richtigen Erzeugenden ${\displaystyle P}$ der Gruppe kennt. (Siehe auch Abschnitt Gruppenoperation im Artikel „Elliptische Kurve“)

Die Aufgabe, aus gegebenen Punkten ${\displaystyle P,Q}$ diesen Wert ${\displaystyle k}$ zu ermitteln, wird als Diskreter-Logarithmus-Problem der elliptischen Kurven (kurz ECDLP) bezeichnet. Es wird angenommen, dass das ECDLP (bei geeigneter Kurvenwahl) schwer ist, d. h. nicht effizient gelöst werden kann. Damit bieten sich elliptische Kurven an, um auf ihnen asymmetrische Kryptosysteme zu realisieren.

Sehr anschaulich ist die Konstruktion für ${\displaystyle K=\mathbb {R} }$, da die Punkte in der reellen Ebene ausgedrückt werden können. Diese Konstruktion kann jedoch auf jeden Körper übertragen werden. In der Kryptographie sind elliptische Kurven der Form ${\displaystyle \operatorname {E} (\operatorname {GF} (p))}$ und ${\displaystyle \operatorname {E} (\operatorname {GF} (2^{n}))}$ von Bedeutung.

Beispiel:

Sei die elliptische Kurve

${\displaystyle E:y^{2}=x^{3}+x+1}$

über dem Körper ${\displaystyle K=\operatorname {GF} (5)}$ gegeben.[53]

Es ist also ${\displaystyle a=1}$ und ${\displaystyle b=1}$ und es gilt ${\displaystyle 4a^{3}+27b^{2}=31\ {\bmod {\ }}5=1\neq 0}$. Die Menge aller ${\displaystyle (x,y)}$ mit ${\displaystyle x,y\in \operatorname {GF} (5)}$ und ${\displaystyle y^{2}=x^{3}+x+1}$ ist also zusammen mit ${\displaystyle {\mathcal {O}}}$ eine elliptische Kurve über ${\displaystyle \operatorname {GF} (5)}$.

Daraus ergeben sich die folgenden Punkte:

${\displaystyle x}$	${\displaystyle x^{3}+x+1\ {\bmod {\ }}5}$	${\displaystyle y}$	Punkte
${\displaystyle 0}$	${\displaystyle 1}$	${\displaystyle 1}$ und ${\displaystyle 4(=-1\ {\bmod {\ }}5)}$	${\displaystyle (0,1)}$, ${\displaystyle (0,4)}$
${\displaystyle 1}$	${\displaystyle 3}$	–	–
${\displaystyle 2}$	${\displaystyle 1}$	${\displaystyle 1}$ und ${\displaystyle 4}$	${\displaystyle (2,1)}$, ${\displaystyle (2,4)}$
${\displaystyle 3}$	${\displaystyle 1}$	${\displaystyle 1}$ und ${\displaystyle 4}$	${\displaystyle (3,1)}$, ${\displaystyle (3,4)}$
${\displaystyle 4}$	${\displaystyle 4}$	${\displaystyle 2}$ und ${\displaystyle 3}$	${\displaystyle (4,2)}$, ${\displaystyle (4,3)}$
${\displaystyle {\mathcal {O}}}$	–	${\displaystyle {\mathcal {O}}}$	${\displaystyle {\mathcal {O}}}$

Bei Kryptosystemen auf Basis elliptischer Kurven werden statt Rechenoperationen in ${\displaystyle \operatorname {GF} (p)}$ Rechenoperationen in ${\displaystyle \operatorname {E} (\operatorname {GF} (p))}$ oder ${\displaystyle \operatorname {E} (\operatorname {GF} (2^{n}))}$ verwendet. Wiederum existieren in diesen Körpern effiziente Algorithmen zur Berechnung der Potenzfunktion, für die Berechnung des Logarithmus dagegen nicht.

Statt auf einen Modulus müssen sich Alice und Bob nun auf eine bestimmte elliptische Kurve einigen, d. h. auf einen Körper ${\displaystyle \operatorname {GF} (p)}$ (bzw. ${\displaystyle \operatorname {GF} (2^{n})}$) und eine darauf aufbauende Gruppe ${\displaystyle \operatorname {E} (\operatorname {GF} (p))}$ (bzw. ${\displaystyle \operatorname {E} (\operatorname {GF} (2^{n}))}$). Alle Parameter, die im Exponenten stehen, sind (wie bisher) natürliche Zahlen, während die Basis einer Potenz ein Element von ${\displaystyle \operatorname {E} (\operatorname {GF} (p))}$ ist.[54]

Eine Exponentiation über ${\displaystyle \operatorname {E} (\operatorname {GF} (p))}$ ist aufwendiger als eine Exponentiation über ${\displaystyle \operatorname {GF} (p)}$, da sie sich aus mehreren Rechenoperationen in ${\displaystyle \operatorname {GF} (p)}$ zusammensetzt. Dafür ist auch die Berechnung des Logarithmus in ${\displaystyle \operatorname {E} (\operatorname {GF} (p))}$ wesentlich „schwieriger“. Der zentrale Vorteil bei der Verwendung von ${\displaystyle \operatorname {E} (\operatorname {GF} (p))}$ ist daher, dass Alice und Bob bei gleicher Sicherheit eine Gruppe kleinerer Mächtigkeit verwenden können. Dies hat kürzere Schlüssellängen, kürzere Signaturen und kürzere Rechenzeiten zur Folge.[54]

Die Komplexität des Logarithmus nimmt in ${\displaystyle \operatorname {E} (\operatorname {GF} (p))}$ mit ${\displaystyle p}$ linear zu, in ${\displaystyle \operatorname {GF} (p)}$ dagegen „nur“ logarithmisch. Eine Schlüssellänge von 1.024 Bit auf Basis des diskreten Logarithmus kann beispielsweise durch Verwendung elliptischer Kurven auf 200 Bit verkürzt werden, ohne dass dabei Sicherheitseinbußen entstehen. Die Einsparung an Rechenzeit wird meist um einen Faktor 10 angegeben.[54]