Diffie-Hellman-Schlüsselaustausch

Der Diffie-Hellman-Schlüsselaustausch oder Diffie-Hellman-Merkle-Schlüsselaustausch bzw. -Schlüsselvereinbarung (auch kurz DHM-Schlüsselaustausch oder DHM-Protokoll^[1]) ist ein Protokoll zur Schlüsselvereinbarung. Es ermöglicht, dass zwei Kommunikationspartner über eine öffentliche, abhörbare Leitung einen gemeinsamen geheimen Schlüssel in Form einer Zahl vereinbaren können, den nur diese kennen und ein potenzieller Lauscher nicht berechnen kann. Der dadurch vereinbarte Schlüssel kann anschließend für ein symmetrisches Kryptosystem verwendet werden (beispielsweise Data Encryption Standard oder Advanced Encryption Standard). Unterschiedliche Varianten des Diffie-Hellman-Merkle-Verfahrens werden heute für die Schlüsselverteilung in den Kommunikations- und Sicherheitsprotokollen des Internets eingesetzt, beispielsweise in den Bereichen des elektronischen Handels. Dieses Prinzip hat damit eine wichtige praktische Bedeutung.

Das Verfahren wurde von Whitfield Diffie und Martin Hellman entwickelt und im Jahr 1976 unter der Bezeichnung ax1x2 veröffentlicht. Es handelt sich um das erste der sogenannten asymmetrischen Kryptoverfahren (auch Public-Key-Kryptoverfahren), das veröffentlicht wurde. Wichtige Vorarbeiten leistete Ralph Merkle mit dem nach ihm benannten Merkles Puzzle. Wie erst 1997 bekannt wurde, entwickelten bereits in den frühen 1970er-Jahren Mitarbeiter des britischen Government Communications Headquarters (GCHQ) als Erste asymmetrische Kryptosysteme. Das GCHQ hat allerdings wegen der Geheimhaltung und wegen des für die Briten aus Sicht der frühen 1970er Jahre fraglichen Nutzens nie ein Patent beantragt.

Der DHM-Schlüsselaustausch zählt zu den Krypto-Systemen auf Basis des diskreten Logarithmus (kurz: DL-Verfahren). Diese basieren darauf, dass die diskrete Exponentialfunktion in gewissen zyklischen Gruppen eine Einwegfunktion ist. So ist in der primen Restklassengruppe die diskrete Exponentialfunktion ${\displaystyle b^{x}\ {\bmod {\ }}p}$, ${\displaystyle p}$ prim, auch für große Exponenten effizient berechenbar, deren Umkehrung, der diskrete Logarithmus, jedoch nicht. Es existiert bis heute kein „schneller“ Algorithmus zur Berechnung des Exponenten ${\displaystyle x}$, bei gegebener Basis ${\displaystyle b}$, Modul ${\displaystyle p}$ und gewünschtem Ergebnis.

Damit prägten die Forscher 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. Das Problem, aus den beiden Nachrichten der Kommunikationspartner den geheimen Schlüssel zu berechnen, wird als Diffie-Hellman-Problem bezeichnet.

Der DHM-Schlüsselaustausch ist allerdings nicht mehr sicher, wenn sich ein Angreifer zwischen die beiden Kommunikationspartner schaltet und Nachrichten verändern kann. Diese Lücke schließen Protokolle wie das Station-to-Station-Protokoll (STS), indem sie zusätzlich digitale Signaturen und Message Authentication Codes verwenden.

Die Implementierung mittels elliptischer Kurven ist als Elliptic Curve Diffie-Hellman (ECDH) bekannt. Dabei werden die beim Originalverfahren eingesetzten Operationen (Multiplikation und Exponentiation) auf dem endlichen Körper ersetzt durch Punktaddition und Skalarmultiplikation auf elliptischen Kurven. Das ${\displaystyle n}$-fache Addieren eines Punktes ${\displaystyle P}$ zu sich selbst (also die Multiplikation mit dem Skalar ${\displaystyle n}$) wird mit ${\displaystyle nP}$ bezeichnet und entspricht einer Exponentiation ${\displaystyle b^{n}}$ im ursprünglichen Verfahren. Das Prinzip wurde Mitte der 1980er Jahre von Victor S. Miller und Neal Koblitz unabhängig voneinander vorgeschlagen.

Geschichte und Bedeutung

Öffentliche Kryptologie

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]

Geheime Kryptologie

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]

Schlüsseltauschproblem

Verschlüsselungsverfahren, bei denen zwei Teilnehmer denselben geheimen Schlüssel verwenden, nennt man symmetrische Verfahren. Seien Alice und Bob Sender und Empfänger von Nachrichten über einen abhörbaren Kanal und sei Eve (von engl. eavesdropper, zu deutsch Lauscher/Lauscherin) ein Lauscher, der versucht, Nachrichten mitzulesen. Bei einem guten Verschlüsselungsverfahren ist es für Eve unmöglich, eine Nachricht ohne Kenntnis des Schlüssels zu entschlüsseln, selbst bei Kenntnis des Verschlüsselungsverfahrens. So besagt Kerckhoffs’ Prinzip, dass die Sicherheit eines Verfahrens allein auf der Geheimhaltung eines Schlüssels beruhen muss (und nicht auf der Geheimhaltung des Verschlüsselungsalgorithmus). Eine Nachricht, die verschlüsselt wird, heißt Klartext, der verschlüsselte Text Geheimtext.^[18]

Wichtige Voraussetzung für eine sichere symmetrische Kommunikation ist also, dass der Schlüssel zwischen Alice und Bob bereits über einen sicheren Weg ausgetauscht wurde, beispielsweise durch einen vertrauenswürdigen Kurier oder bei einem direkten Treffen. Beim Schlüsseltauschproblem stellt sich nun folgendes Problem: Alice will mit Bob, der sich beispielsweise in Übersee befindet, mit einem symmetrischen Verschlüsselungsverfahren kommunizieren. Die beiden sind über eine unsichere Leitung verbunden und haben keinen Schlüssel ausgetauscht. Wie vereinbaren nun Alice und Bob über einen unsicheren Kanal einen gemeinsamen geheimen Schlüssel?^[19]

Ein manueller Schlüsselaustausch hat den Nachteil, dass er recht unübersichtlich wird, wenn eine größere Anwendergruppe untereinander verschlüsselt kommunizieren will. Bei ${\displaystyle n}$ Kommunikationspartnern sind ${\displaystyle n\cdot (n-1)/2}$ Schlüssel erforderlich, wenn jeder mit jedem kommunizieren will. Bei 50 Kommunikationspartnern wären somit insgesamt 1.225 Schlüssel nötig.^[20]

Das Diffie-Hellman-Verfahren liefert eine elegante Lösung für diese Probleme: Es erlaubt Alice und Bob, einen geheimen Schlüssel über die öffentliche, nicht gesicherte Leitung zu vereinbaren, ohne dass Eve den Schlüssel erfährt.^[19]

Mathematische Grundlagen

Hinweis: Die folgenden Betrachtungen vermitteln mathematische Grundlagen asymmetrischer Kryptoverfahren auf Basis des diskreten Logarithmus. Die einzelnen Abschnitte beschränken sich insbesondere auf die wesentlichen Aspekte, die für den Entwurf und die Sicherheitsanalyse des Diffie-Hellman-Merkle-Schlüsselaustauschs notwendig sind. Um eine gewisse Verständlichkeit zu wahren, werden einige Aspekte vereinfacht dargestellt. Für tiefergehendere Betrachtungen und Beweise sei auf die Literatur zu den mathematischen Grundlagen im Literaturabschnitt verwiesen.

Einwegfunktionen

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.

Diskrete Exponentialfunktion und diskreter Logarithmus

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}$.

Gruppentheorie

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.

Prime Restklassengruppe und Primitivwurzel

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]

• ${\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.

Funktionsweise

Veranschaulichung der Grundidee anhand gemischter Farben

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.

Mathematische Funktionsweise

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]

Programmierung

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=}')

Sicherheit

Diffie-Hellman-Problem

Computational-Diffie-Hellman-Problem (CDH)

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]

Decisional-Diffie-Hellman-Problem (DDH)

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]

Wahl der öffentlichen Zahlen

DHM-Primzahl p

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]

„Generator“ g

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 ein 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.

Verwendung fester Gruppen und Primzahlen

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]

Man-in-the-Middle-Angriff

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]

Seitenkanalangriffe

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.

Zeitangriff

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]

Stromangriff

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]

Elliptic Curve Diffie-Hellman (ECDH)

Kryptosysteme auf Basis elliptischer Kurven (kurz ECC-Verfahren, von engl. Elliptic Curve Cryptography) sind keine eigenständige kryptographische Verfahren, sondern bekannte DL-Verfahren, die auf besondere Weise implementiert werden. Jedes Verfahren, das auf dem diskreten Logarithmus in endlichen Körpern basiert, lässt sich in einfacher Weise auf elliptische Kurven übertragen und somit zu einem Elliptic-Curve-Kryptosystem umformen. Dabei werden die beim Originalverfahren eingesetzten Operationen (Multiplikation und Exponentiation) auf dem endlichen Körper ersetzt durch Punktaddition und Skalarmultiplikation auf elliptischen Kurven. Das ${\displaystyle n}$-fache Addieren eines Punktes ${\displaystyle P}$ zu sich selbst (also die Multiplikation mit dem Skalar ${\displaystyle n}$) wird mit ${\displaystyle nP}$ bezeichnet und entspricht einer Exponentiation ${\displaystyle x^{n}}$ im ursprünglichen Verfahren. Das Prinzip wurde Mitte der 1980er Jahre von Victor S. Miller^[48] und Neal Koblitz^[49] unabhängig voneinander vorgeschlagen.

Körper

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]

Elliptische Kurven

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:

Diffie-Hellman auf Basis elliptischer Kurven

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]

Ephemeral Diffie-Hellman

Im Zusammenhang des Verschlüsselungsprotokolls Transport Layer Security (TLS) bezeichnet Ephemeral Diffie-Hellman (englisch ephemeral: kurzlebig, flüchtig) die Verwendung von Diffie-Hellman mit jeweils neuen Parametern für jede neue TLS-Sitzung. Bei statischem Diffie-Hellman werden für jede TLS-Sitzung dieselben Parameter wiederverwendet, die sich aus einem Public-Key-Zertifikat herleiten. In beiden Fällen wird derselbe Algorithmus verwendet und lediglich die Parameter unterscheiden sich.

Die Verwendung von Ephemeral Diffie-Hellman zur Aushandlung eines symmetrischen Sitzungsschlüssels bietet Forward Secrecy, im Gegensatz zur verschlüsselten Übertragung eines Sitzungsschlüssels mit einem Public-Key-Verschlüsselungsverfahren, zum Beispiel RSA.

Literatur

Allgemeiner Überblick

• Karin Freiermuth, Juraj Hromkovič, Lucia Keller, Björn Steffen: Einführung in die Kryptologie. Lehrbuch für Unterricht und Selbststudium. 2. Auflage, Springer Vieweg: Wiesbaden, 2014.
• Simon Singh: Geheime Botschaften. Die Kunst der Verschlüsselung von der Antike bis in die Zeiten des Internet. 13. Auflage, dtv Verlagsgesellschaft: München, 2016 (Englische Originalausgabe: The Code Book. The Science of Secrecy from Ancient Egypt to Quantum Cryptography. Fourth Estate: London, 1999).
• Albrecht Beutelspacher, Jörg Schwenk, Klaus-Dieter Wolfenstetter: Moderne Verfahren der Kryptographie. Von RSA zu Zero-Knowledge. 8. Auflage, Springer Spektrum: Berlin, Heidelberg, 2015.
• Thomas Borys: Codierung und Kryptologie. Facetten einer anwendungsorientierten Mathematik im Bildungsprozess. Vieweg+Teubner: Wiesbaden, 2011.
• Albrecht Beutelspacher: Geheimsprachen. Geschichte und Techniken. 3., aktualisierte Auflage, C.H. Beck: München, 2002.
• Klaus Schmeh: Kryptografie. Verfahren, Protokolle, Infrastrukturen. 5., aktualisierte Auflage, dpunkt.verlag: Heidelberg, 2013.
• Johannes Buchmann: Einführung in die Kryptographie. 6. Auflage, Springer Spektrum: Berlin, Heidelberg, 2016.

Fachartikel

• Paul C. Kocher: Cryptanalysis of Diffie-Hellman, RSA, DSS, and Other Systems Using Timing Attacks. In: Advances in Cryptology, CRYPTO '95 (15th Annual International Cryptology Conference), Springer-Verlag, 1995, S. 27–31. (Online)
• Whitfield Diffie, Martin E. Hellman: New Directions in Cryptography. In: IEEE Transactions on Information Theory 22, Nr. 6, 1976, S. 644–654. (Online)
• Ueli Maurer: Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms. In: Advances in Cryptology – Crypto '94. Springer-Verlag, 1994, S. 271–281, doi:10.1007/3-540-48658-5_26.
• Paul C. Kocher: Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In: Advances in Cryptology, CRYPTO '96 (Lecture Notes in Computer Science, Vol. 1109), Springer-Verlag, 1996, S. 104–113. (Online)
• David Adrian, Karthikeyan Bhargavan, Zakir Durumeric, Pierrick Gaudry, Matthew Green, J. Alex Halderman, Nadia Heninger, Drew Springall, Emmanuel Thomé, Luke Valenta, Benjamin VanderSloot, Eric Wustrow, Santiago Zanella-Béguelin, Paul Zimmermann: Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. ACM, New York 2015, S. 5–17. (Online)
• Paul Kocher, Joshua Jaffe, Benjamin Jun: Introduction to Differential Power Analysis and Related Attacks. In: Advances in Cryptology—CRYPTO ’99, 19th Annual International Cryptology Conference. (Lecture Notes in Computer Science, Vol. 1666) Springer-Verlag: Berlin, 1999, S. 388–397. (Online)
• Martin E. Hellman: An overview of public key cryptography. In: IEEE Communications Magazine 40, Nr. 5, 2002, S. 42–49 (Online). Originalartikel: An overview of public key cryptography. In: IEEE Communications Magazine 16, Nr. 6, 1978, S. 24–32 (Online)
• Dan Boneh: The Decision Diffie–Hellman Problem. In: Proceedings of the Third Algorithmic Number Theory Symposium (Lecture Notes in Computer Science, Vol. 1423) Springer-Verlag, 1998, S. 48–63. (Online)
• Ralph C. Merkle: Secure Communications over Insecure Channels. In: Communications of the ACM 21, Nr. 4, April 1978, S. 294–299. (Online)

Anwendung

• Patrick Horster (Hrsg.): Chipkarten. Grundlagen, Realisierung, Sicherheitsaspekte, Anwendungen. vieweg, 1998.
• Wolfgang Ertel: Angewandte Kryptographie. 4. Auflage, Hanser: München, 2012.
• Anatol Badach, Erwin Hoffmann: Technik der IP-Netze. Internet-Kommunikation in Theorie und Einsatz. 3., überarbeitete und erweiterte Auflage, Hanser: München, 2015.
• Michael Welschenbach: Kryptographie in C und C++. Zahlentheoretische Grundlagen, Computer-Arithmetik mit großen Zahlen, kryptographische Tools. 2., überarbeitete und erweiterte Auflage, Springer: Berlin, Heidelberg, 2012.

Mathematische Grundlagen

• Eric Bach, Jeffrey Shallit: Algorithmic Number Theory. Volume 1: Efficient Algorithms. MIT Press: Cambridge (MA), London, 1996.
• Ramanujachary Kumanduri, Cristina Romero: Number Theory with Computer Applications. Pearson: Prentice Hall, 1998.
• Paulo Ribenboim: Die Welt der Primzahlen. Geheimnisse und Rekorde. 2., vollständig überarbeitete und aktualisierte Auflage, Springer: Berlin, Heidelberg, 2011.
• Lawrence C. Washington: Elliptic Curves. Number Theory and Cryptography. Second Edition, Chapman & Hall / CRC Press: Boca Raton (FL), 2005, S. 95–97.
• Christian Karpfinger, Kurt Meyberg: Algebra. Gruppen, Ringe, Körper. 3. Auflage, Springer Spektrum: Berlin, Heidelberg, 2013.

Weblinks

• Bundesamt für Sicherheit in der Informationstechnik (BSI): BSI – Technische Richtlinien: Kryptographische Verfahren: Empfehlungen und Schlüssellängen Version 2016-01, Stand 15. Februar 2016.
• Steven Levy: The Open Secret – Public key cryptography – the breakthrough that revolutionized email and ecommerce – was first discovered by American geeks. Right? Wrong. In: WIRED (veröffentlicht: 4. Januar 1999; abgerufen: 9. Mai 2016)
• ECRYPT II: European Network of Excellence in Cryptology II

Einzelnachweise