|
|
| (40 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) |
| Zeile 1: |
Zeile 1: |
| == Beschreibung ==
| | #WEITERLEITUNG [[Diffie Hellman Key Exchanges]] |
| [[Datei:Public key shared secret.svg|mini|Vereinbarung eines gemeinsamen [[Geheimer Schlüssel|geheimen Schlüssels]] über eine abhörbare Leitung mit dem Diffie-Hellman-Merkle-Schlüsselaustausch]]
| |
| | |
| Der '''Diffie-Hellman-Schlüsselaustausch''' oder '''Diffie-Hellman-Merkle-Schlüsselaustausch''' bzw. '''-Schlüsselvereinbarung''' (auch kurz '''DHM-Schlüsselaustausch''' oder '''DHM-Protokoll'''<ref>So u. a. Yiu Shing Terry Tin u. a.: ''Provably Secure Mobile Key Exchange: Applying the Canetti-Krawczyk Approach.'' In: Rei Safavi-Naini, Jennifer Seberry: ''Information Security and Privacy.'' 8th Australasian Conference, ACISP 2003, Springer: Berlin, Heidelberg, 2003, S. 166–179.</ref>) ist ein [[Schlüsselaustauschprotokoll|Protokoll]] zur [[Schlüsselverteilungsproblem|Schlüsselvereinbarung]].
| |
| * Es ermöglicht, dass zwei Kommunikationspartner über eine öffentliche, [[Abhören|abhörbare]] Leitung einen gemeinsamen [[Geheimer Schlüssel|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 [[Kommunikationsprotokoll|Kommunikations-]] und Sicherheitsprotokollen des [[Internet]]s eingesetzt, beispielsweise in den Bereichen des [[Elektronischer Handel|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 [[Asymmetrisches Kryptosystem|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 [[Diskreter Logarithmus|diskreten Logarithmus]] (kurz: DL-Verfahren).
| |
| * Diese basieren darauf, dass die [[diskrete Exponentialfunktion]] in gewissen [[Zyklische Gruppe|zyklischen]] [[Gruppe (Mathematik)|Gruppen]] eine [[Einwegfunktion]] ist.
| |
| * So ist in der [[Prime Restklassengruppe|primen Restklassengruppe]] die diskrete Exponentialfunktion <math>b^x\ \bmod\ p</math>, <math>p</math> [[Primzahl|prim]], auch für große [[Potenz (Mathematik)|Exponenten]] effizient berechenbar, deren [[Umkehrfunktion|Umkehrung]], der diskrete Logarithmus, jedoch nicht.
| |
| * Es existiert bis heute kein „schneller“ [[Algorithmus]] zur Berechnung des Exponenten <math>x</math>, bei gegebener Basis <math>b</math>, Modul <math>p</math> und gewünschtem Ergebnis.
| |
| | |
| Damit prägten die Forscher mit dem Verfahren auch einen neuen [[Informationssicherheit|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 Signatur]]en und [[Message Authentication Code]]s verwenden.
| |
| | |
| Die [[Elliptic Curve Cryptography|Implementierung mittels elliptischer Kurven]] ist als '''Elliptic Curve Diffie-Hellman''' (ECDH) bekannt.
| |
| * Dabei werden die beim Originalverfahren eingesetzten Operationen (Multiplikation und Exponentiation) auf dem [[Endlicher Körper|endlichen Körper]] ersetzt durch Punktaddition und Skalarmultiplikation auf [[Elliptische Kurven|elliptischen Kurven]].
| |
| * Das <math>n</math>-fache Addieren eines Punktes <math>P</math> zu sich selbst (also die Multiplikation mit dem Skalar <math>n</math>) wird mit <math>n P</math> bezeichnet und entspricht einer Exponentiation <math>b^n</math> im ursprünglichen Verfahren.
| |
| * Das Prinzip wurde Mitte der 1980er Jahre von [[Victor S. Miller]] und [[Neal Koblitz]] unabhängig voneinander vorgeschlagen.
| |
| | |
| == Schlüsseltauschproblem ==
| |
| [[Datei:Orange blue symmetric cryptography de.svg|mini|Kryptografie und Entschlüsselung mit demselben Schlüssel (symmetrisches Verfahren)]]
| |
| | |
| Kryptografiesverfahren, bei denen zwei Teilnehmer denselben [[Schlüssel (Kryptologie)|geheimen Schlüssel]] verwenden, nennt man [[Symmetrisches Kryptosystem|symmetrische Verfahren]]. Seien [[Alice und Bob]] [[Sender-Empfänger-Modell|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 Kryptografiesverfahren ist es für Eve unmöglich, eine Nachricht ohne Kenntnis des Schlüssels zu entschlüsseln, selbst bei Kenntnis des Kryptografiesverfahrens. So besagt [[Kerckhoffs’ Prinzip]], dass die Sicherheit eines Verfahrens allein auf der Geheimhaltung eines Schlüssels beruhen muss (und nicht auf der Geheimhaltung des [[Liste von Algorithmen#Kryptographie|Kryptografiesalgorithmus]]). Eine Nachricht, die verschlüsselt wird, heißt [[Klartext (Kryptographie)|Klartext]], der verschlüsselte Text [[Geheimtext]].<ref>Schmeh: ''Kryptografie.'' 5. Aufl., 2013, S. 39–42.</ref>
| |
| | |
| 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 Kryptografiesverfahren 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?<ref name="Ertel-Buchmann">Ertel: ''Angewandte Kryptographie.'' 4. Aufl., 2012, S. 77; Buchmann: ''Einführung in die Kryptographie.'' 3. Aufl., 2004, S. 153.</ref>
| |
| | |
| Ein manueller Schlüsselaustausch hat den Nachteil, dass er recht unübersichtlich wird, wenn eine größere Anwendergruppe untereinander verschlüsselt kommunizieren will. Bei <math>n</math> Kommunikationspartnern sind <math>n \cdot (n-1)/2</math> Schlüssel erforderlich, wenn jeder mit jedem kommunizieren will. Bei 50 Kommunikationspartnern wären somit insgesamt 1.225 Schlüssel nötig.<ref>Schmeh: ''Kryptografie.'' 5. Aufl., 2013, S. 176.</ref>
| |
| | |
| 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.<ref name="Ertel-Buchmann" />
| |
| | |
| == Geschichte und Bedeutung ==
| |
| [[Diffie-Hellman-Schlüsselaustausch/Geschichte und Bedeutung]]
| |
| | |
| == 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 ===
| |
| [[Datei:Bildung der Umkehrfunktion an einem Beispiel.svg|mini|150px|[[Funktion (Mathematik)|Funktion]] und [[Umkehrfunktion]]]]
| |
| | |
| Eine [[Einwegfunktion]] ist eine [[Funktion (Mathematik)|mathematische Funktion]], die [[Komplexitätstheorie|komplexitätstheoretisch]] „leicht“ berechenbar, aber „schwer“ [[Umkehrfunktion|umzukehren]] ist.<ref>Ertel: ''Angewandte Kryptographie.'' 4. Aufl., 2012, S. 98–99; Buchmann: Einführung in die Kryptographie. 3. Aufl., 2004, S. 192.</ref> Eine mathematische Einwegfunktion <math>f \colon X \to Y</math> muss folgende Eigenschaften aufweisen:
| |
| | |
| * Die Berechnung des Funktionswerts <math>y = f(x)</math> ist „einfach“, d. h. es existiert ein [[Algorithmus]], der ihn in [[Polynomialzeit]] berechnen kann.
| |
| * Die Berechnung der Umkehrfunktion zu einem gegebenen Funktionswert <math>y</math>, d. h. einem <math>x</math>, sodass <math>f^{-1}(y) = x</math>, ist allerdings „schwer“, d. h. es existiert kein „schneller“ Algorithmus für dieses Problem. „Schnell“ meint hier einen [[Probabilistischer Algorithmus|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.<ref>Beutelspacher, Schwenk, Wolfenstetter: ''Moderne Verfahren der Kryptographie.'' 8. Aufl., 2015, S. 16.</ref>
| |
| | |
| 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.<ref>Beutelspacher, Schwenk, Wolfenstetter: ''Moderne Verfahren der Kryptographie.'' 8. Aufl., 2015, S. 17 mit Verweis auf Jose L. Balcazar, Josep Diaz, Josep, Joaquim Gabarró: ''Structural Complexity I.'' Springer: Heidelberg, Berlin, 1988.</ref>
| |
| | |
| Die Sicherheit des DHM-Schlüsselaustauschs basiert darauf, dass der [[Diskreter Logarithmus|diskrete Logarithmus]] in gewissen [[Zyklische Gruppe|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 [[Faktorisierungsverfahren|Faktorisierung]] eine Einwegfunktion mit Falltür.
| |
| | |
| === Diskrete Exponentialfunktion und diskreter Logarithmus ===
| |
| Die [[diskrete Exponentialfunktion]]
| |
| :<math>b^x\ \bmod\ m</math>
| |
| liefert den Rest bei Division von <math>b^x</math> durch m. Die Umkehrung der diskreten Exponentialfunktion heißt [[diskreter Logarithmus]].
| |
| | |
| Die diskrete Exponentialfunktion ist auch für große [[Potenz (Mathematik)|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 [[Binäre Exponentiation|Square-&-Multiply]]-Verfahren verwendet werden.
| |
| | |
| Für die Umkehrung, also die Berechnung des Exponenten <math>x</math>, bei gegebener Basis <math>b</math>, Modul <math>m</math> und gewünschtem Ergebnis, ist allerdings bis heute kein schneller Algorithmus bekannt: Selbst mit größtem Hardwareaufwand und den besten bekannten [[Algorithmus|Algorithmen]] erreicht man bei mehreren Tausend Bit schnell Berechnungszeiten, die über die Lebensdauer unseres Universums hinausgehen.<ref name="Schmeh-S184">Schmeh: ''Kryptografie.'' 5. Aufl., 2013, S. 184.</ref>
| |
| | |
| Bei der diskreten Exponentialfunktion <math>f(x)=b^x\ \bmod\ m</math> 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.<ref name="Schmeh-S184" />
| |
| | |
| '''Beispiel:'''
| |
| | |
| Die diskrete Exponentialfunktion <math>f(x) = 3^x\ \bmod\ 7</math> ordnet einem <math>x</math> das Ergebnis von <math>3^x\ \bmod\ 7</math> zu. Bei der Rechnung <math>\bmod\ 7</math> wird jeweils der Rest bezüglich des Moduls <math>m=7</math> gebildet. Dadurch entsteht ein endlicher Zahlenraum <math>[0,6]</math>. Für die Werte <math>x \neq 0</math> ist die Abbildung eindeutig. Der diskrete Logarithmus ist die Umkehrfunktion, also die Zuordnung von <math>f(x)</math> nach <math>x</math>.
| |
| | |
| [[Datei:Diskreter-logarithmus.jpg|400px]]
| |
| | |
| === Gruppentheorie ===
| |
| Eine [[Gruppe (Mathematik)|Gruppe]] ist ein Paar <math>(G,*)</math>, bestehend aus einer [[Menge (Mathematik)|Menge]] <math>G</math> und einer [[Assoziativgesetz|assoziativen]] Verknüpfung <math>*</math> auf <math>G</math>, die ein [[neutrales Element]] hat und für die jedes Element von <math>G</math> ein [[inverses Element]] besitzt. Wenn für eine Gruppe zusätzlich das [[Kommutativgesetz]] gilt, spricht man von einer [[Abelsche Gruppe|abelschen Gruppe]]. Eine [[Untergruppe]] <math>(U, *)</math> einer Gruppe <math>(G, *)</math> ist eine [[Teilmenge]] <math>U</math> von <math>G</math>, die bezüglich der Verknüpfung <math>*</math> selbst wieder eine Gruppe ist.
| |
| | |
| Beispielsweise bildet die Menge der ganzen Zahlen mit der [[Addition]] als Verknüpfung die (abelsche) Gruppe <math>(\Z, +)</math>. Das neutrale Element der Addition ist die <math>0</math> ([[Null]]) und das additiv Inverse einer Zahl <math>a</math> ist ihre Gegenzahl <math>-a</math>. Die ganzen Zahlen <math>\Z</math> sind bezüglich der Addition wiederum eine Untergruppe der [[Rationale Zahlen|rationalen Zahlen]] <math>\Q</math>. Demgegenüber bilden die rationalen (und ganzen) Zahlen zusammen mit der [[Multiplikation]] keine Gruppe, weil die Zahl <math>0</math> kein inverses Element bezüglich der Multiplikation besitzt. Wenn man jedoch <math>0</math> aus <math>\Q</math> entfernt, erhält man die (abelsche) Gruppe <math>(\Q \setminus \{0 \}, \cdot)</math>.
| |
| | |
| Eine [[zyklische Gruppe]] ist eine Gruppe, deren Elemente als [[Potenz (Mathematik)|Potenz]] eines ihrer Elemente dargestellt werden können. Unter Verwendung der multiplikativen Notation lauten die Elemente einer zyklischen Gruppe
| |
| :<math>\ldots, a^{-3}, a^{-2}, a^{-1}, e = a^{0}, a, a^2, a^3, \ldots</math>,
| |
| wobei <math>a^{-2} = a^{-1} \cdot a^{-1}</math> meint und <math>e</math> das neutrale Element der Gruppe bezeichnet. Das Element <math>a</math> wird [[Erzeugendensystem|Erzeuger]] oder [[Primitivwurzel]] der Gruppe genannt. Eine zyklische Gruppe besteht also nur aus Potenzen des Erzeugers <math>a</math>:
| |
| | |
| :<math>\left\langle a \right\rangle := \lbrace a^n \mid n \in \Z \rbrace.</math>
| |
| | |
| Bei einer Gruppe <math>(G,*)</math> wird die [[Mächtigkeit (Mathematik)|Mächtigkeit]] <math>|G|</math> auch als [[Gruppenordnung|Ordnung der Gruppe]] bezeichnet. Für eine [[endliche Gruppe]] <math>G = \{a_1, a_2, \dotsc, a_n\}</math> ist die Ordnung also einfach die Anzahl <math>n</math> 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 [[Teilerfremdheit|primen]] [[Restklasse]]n bezüglich eines Moduls <math>n</math>. Sie wird als <math>\Z_n^*</math> oder <math>(\Z /n\Z )^\times</math> notiert. Die primen Restklassen sind genau die multiplikativ invertierbaren Restklassen und sind daher endliche abelsche Gruppen bezüglich der [[Multiplikation]]. Die Menge <math>\Z_8 = \{0,...,7\}</math> bildet beispielsweise mit der Multiplikation modulo <math>8</math> als Verknüpfung keine Gruppe, selbst wenn die <math>0</math> ausgenommen wird. Es gibt noch weitere Zahlen, die kein inverses Element haben, nämlich <math>2</math>, <math>4</math> und <math>6</math>. Dies sind genau die Zahlen, die einen echten Teiler mit <math>8</math> gemeinsam haben. Die verbleibenden Elemente bilden schließlich die Multiplikative Gruppe <math>\Z_8^*.</math>
| |
| | |
| In der Kryptographie sind vor allem jene Zahlen <math>n</math> von Interesse, für die alle Zahlen zwischen <math>1</math> und <math>n-1</math> ein inverses Element modulo <math>n</math> haben. Dies ist genau dann der Fall, wenn <math>n</math> eine Primzahl ist (weshalb man <math>p</math> statt <math>n</math> schreibt). Die Zahlen zwischen <math>1</math> und <math>p-1</math> bilden also zusammen mit der Modulo-Multiplikation die Gruppe <math>\Z_p^*</math>. Eine weitere Aussage, die sich beweisen lässt: Nimmt man ein beliebiges Element <math>a</math> aus <math>\Z_p^*</math> und betrachtet die Menge <math>\{ a, a^2, a^3, ..., a^{p-1} (\bmod\ p) \}</math>, dann erhält man eine Untergruppe (mit <math>a</math> als Generator der Untergruppe). Jede Untergruppe von <math>\Z_p^*</math> hat mindestens einen Generator, und damit auch <math>\Z_p^*</math> selbst. Die Gruppe <math>\Z_p^*</math> ist also zyklisch.<ref>Schmeh: ''Kryptografie.'' 5. Aufl., 2013, S. 181–183.</ref> Zum Beispiel ist <math>\Z_{13}^*</math> eine zyklische Gruppe mit der <math>2</math> als Generator, denn jede Zahl von <math>1</math> bis <math>12</math> lässt sich als Potenz von <math>2</math> darstellen:<ref name="Freiermuth-S202">Freiermuth u. a.: ''Einführung in die Kryptologie.'' 2. Aufl., 2014, S. 202.</ref>
| |
| | |
| [[Datei:Zyklische-gruppe.jpg|mini|Darstellung der zyklischen Gruppe <math>\Z_{13}^*</math> mit Exponent <math>a</math> außerhalb und den entsprechenden Werten innerhalb der Knoten.]]
| |
| | |
| * <math>1 = 2^{12}\ \bmod\ 13</math>
| |
| * <math>2 = 2^{1}\ \bmod\ 13</math>
| |
| * <math>3 = 2^{4}\ \bmod\ 13</math>
| |
| * <math>4 = 2^{2}\ \bmod\ 13</math>
| |
| * <math>5 = 2^{9}\ \bmod\ 13</math>
| |
| * <math>6 = 2^{5}\ \bmod\ 13</math>
| |
| * <math>7 = 2^{11}\ \bmod\ 13</math>
| |
| * <math>8 = 2^{3}\ \bmod\ 13</math>
| |
| * <math>9 = 2^{8}\ \bmod\ 13</math>
| |
| * <math>10 = 2^{10}\ \bmod\ 13</math>
| |
| * <math>11 = 2^{7}\ \bmod\ 13</math>
| |
| * <math>12 = 2^{6}\ \bmod\ 13</math>
| |
| | |
| Für <math>a=3</math> als Generator erhält man dagegen nur die Untergruppe mit den Elementen <math>\{1, 3, 9 \}</math>:
| |
| | |
| * <math>1 = 3^{3}\ \bmod\ 13 = 3^{6}\ \bmod\ 13 = 3^{9}\ \bmod\ 13 = 3^{12}\ \bmod\ 13</math>
| |
| * <math>3 = 3^{1}\ \bmod\ 13 = 3^{4}\ \bmod\ 13 = 3^{7}\ \bmod\ 13 = 3^{10}\ \bmod\ 13</math>
| |
| * <math>9 = 3^{2}\ \bmod\ 13 = 3^{5}\ \bmod\ 13 = 3^{8}\ \bmod\ 13 = 3^{11}\ \bmod\ 13</math>
| |
| | |
| Es lässt sich nun leicht nachvollziehen, dass die Gleichung <math>a^x = b\ \bmod\ p</math> immer lösbar ist, wenn <math>a</math> ein Generator von <math>\Z_p^*</math> ist, wobei dann <math>b</math> ein Element von <math>\Z_p^*</math> ist (außer <math>0</math>). Der diskrete Logarithmus existiert also in <math>Z_p^*</math> immer dann, wenn die Basis ein Generator von <math>\Z_p^*</math> ist.<ref>Schmeh: ''Kryptografie.'' 5. Aufl., 2013, S. 183.</ref> 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.<ref>Freiermuth u. a.: ''Einführung in die Kryptologie.'' 2. Aufl., 2014, S. 202–203.</ref>
| |
| | |
| Man nennt ein erzeugendes Element von <math>\Z_p^*</math> auch [[Primitivwurzel]] zum Modul <math>p</math>. Die Zahl <math>2</math> ist also eine Primitivwurzel modulo <math>13</math>, die Zahl <math>3</math> dagegen nicht. Es lassen sich alle Elemente <math>1, 2, \ldots, 12</math> der primen Restklassengruppe modulo <math>13</math> als Potenzen von <math>2</math> darstellen. In der Folge der Potenzen von <math>3</math> modulo <math>13</math> wiederholen sich jedoch die Reste (siehe oben).
| |
| | |
| Für eine Primzahl <math>p</math> gibt es genau <math>\varphi(p-1)</math> Primitivwurzeln <math>\bmod\ p</math>, wobei <math>\varphi</math> für die [[Eulersche Phi-Funktion]] steht, die für jede [[natürliche Zahl]] die Anzahl ihrer [[Teilerfremdheit|teilerfremden]] natürlichen Zahlen angibt.
| |
| | |
| Für <math>p = 13</math> ist <math>p-1 = 12</math> und <math>\varphi(12) = 4</math>, woraus folgt, dass es <math>4</math> Primitivwurzeln modulo <math>13</math> gibt (nämlich <math>2</math>, <math>6</math>, <math>7</math> und <math>11</math>).
| |
| | |
| Es ist zwar bewiesen, dass für jede Primzahl <math>p</math> genau <math>\varphi(p-1)</math> verschiedene Primitivwurzeln modulo <math>p</math> existieren, es ist aber kein Algorithmus bekannt, der auch effizient eine beliebige Primitivwurzel berechnen kann. Wenn <math>p</math> gegeben und die [[Faktorisierungsverfahren|Faktorisierung]] von <math>p-1</math> unbekannt ist, so kann man immerhin testen, ob es sich bei einer Zufallszahl <math>g</math> um eine Primitivwurzel modulo <math>p</math> handelt. Es muss gelten:
| |
| | |
| :<math>g^{p-1} = 1\ \bmod\ p</math> und <math>g^i \neq\ 1 \bmod\ p</math> für <math>2 \leq i \leq p-2</math>.
| |
| | |
| Für kryptographisch relevante Primzahlen ist eine solche Überprüfung aufgrund der Größe von <math>p</math> nicht durchführbar.
| |
| | |
| Ist dagegen die Primfaktorzerlegung von <math>p-1</math> bekannt, so ist <math>g</math> genau dann eine Primitivwurzel modulo <math>p</math>, wenn gilt
| |
| | |
| :<math>g^{(p-1)/p_i} \neq 1\ \bmod\ p</math> für alle [[Primfaktorzerlegung|Primfaktoren]] <math>p_i</math>.
| |
| | |
| Besonders einfach wird der „Primitivwurzel-Test“, wenn <math>p-1 = 2 \times q</math> mit einer Primzahl <math>q</math> gilt. Dann braucht man nur zu testen, ob
| |
| | |
| :<math>g^2 \neq 1\ \bmod\ p</math> und <math>g^q \neq 1\ \bmod\ p</math>
| |
| | |
| ist. Trifft dies zu, ist <math>g</math> eine Primitivwurzel modulo <math>p</math>.<ref>Buchmann: ''Einführung in die Kryptographie.'' 6. Aufl., 2016, S. 67–68.</ref>
| |
| | |
| '''Beispiel:'''
| |
| | |
| Sei <math>p=23</math>. Dann ist <math>p-1 = 22 = 11 \times 2</math> mit <math>q=11</math>, also prim. Um zu testen, ob eine beliebige Zahl <math>g</math> eine Primitivwurzel modulo <math>23</math> ist, muss <math>g^2\ \bmod\ 23 \neq 1</math> und <math>g^{11}\ \bmod\ 23 \neq 1</math> überprüft werden. Für <math>g=5</math> gilt beispielsweise <math>5^2\ \bmod\ 23 = 2</math> und <math>5^{11}\ \bmod\ 23 = 22</math>. Also ist <math>5</math> eine Primitivwurzel modulo <math>23</math>. Die Weiteren sind 7, 10, 11, 14, 15, 17, 19, 20 und 21. Mit <math>\varphi(23-1) = \varphi(22) = 10</math> lässt sich einsehen, dass damit (alle 10) Primitivwurzeln modulo <math>23</math> gefunden sind.
| |
| | |
| == Funktionsweise ==
| |
| | |
| === Veranschaulichung der Grundidee anhand gemischter Farben ===
| |
| | |
| [[Datei:Diffie-Hellman Key Exchange (de).svg|mini|links]]
| |
| | |
| 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 ===
| |
| [[Datei:Diffie-Hellman-Schlüsselaustausch.svg|mini|400px|Prinzip des Diffie-Hellman-Merkle-Schlüsselaustauschs<br>
| |
| a: privater Schlüssel von Alice<br>
| |
| b: privater Schlüssel von Bob<br>
| |
| p: öffentlich bekannte Primzahl<br>
| |
| g: öffentlich bekannte natürliche Zahl kleiner als p<br>
| |
| A: öffentlicher Schlüssel von Alice<br>
| |
| B: öffentlicher Schlüssel von Bob<br>
| |
| 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.
| |
| | |
| # Alice und Bob einigen sich zunächst öffentlich auf eine große [[Primzahl]] <math>p</math> und eine natürliche Zahl <math>g</math>, die kleiner als <math>p</math> ist. Sich öffentlich darauf einigen bedeutet, dass jeder diese beiden Zahlen kennen darf (also auch potenzielle Lauscher wie Eve). Idealerweise handelt es sich bei <math>g</math> um einen Erzeuger der [[Zyklische Gruppe|zyklischen Gruppe]] <math>\Z_p</math>, das Verfahren funktioniert aber auch, wenn <math>g</math> einen anderen Wert kleiner <math>p</math> annimmt. In der Praxis ist es ohnehin meist so, dass <math>g</math> und <math>p</math> vorgegeben sind und von vielen Anwendern verwendet werden.<ref name="Schmeh-S185-186">Schmeh: ''Kryptografie.'' 5. Aufl., 2013, S. 185–186.</ref>
| |
| # Alice und Bob erzeugen jeweils eine geheimzuhaltende [[Zufallszahl]] (privater Schlüssel) <math>a</math> bzw. <math>b</math> aus der Menge <math>\{ 1, \ldots, p-1 \}</math>. <math>a</math> und <math>b</math> werden nicht übertragen, bleiben also potenziellen Lauschern, aber auch dem jeweiligen Kommunikationspartner, unbekannt. Nur Alice kennt die Zahl <math>a</math> und nur Bob kennt die Zahl <math>b</math>.
| |
| # Alice berechnet mit ihrer geheimen Zahl den öffentlichen Schlüssel <math>A = g^a\ \bmod\ p</math> und schickt <math>A</math> an Bob. Bob berechnet mit seiner geheimen Zahl den öffentlichen Schlüssel <math>B = g^b\ \bmod\ p</math> und schickt <math>B</math> an Alice.
| |
| # Alice erhält <math>B</math> von Bob und berechnet mit ihrem privaten Schlüssel <math>a</math> die Zahl <math>K_1 = B^a\ \bmod\ p</math>. Bob berechnet mit dem erhaltenen <math>A</math> und seinem privaten Schlüssel <math>b</math> ebenfalls die Zahl <math>K_2 = A^b\ \bmod\ p</math>. Die beiden haben die gleiche Zahl <math>K_1 = K_2</math> berechnet. Diese ist somit der gesuchte gemeinsame Schlüssel <math>K</math>.
| |
| | |
| Nur Alice und Bob kennen <math>K</math>. Eve kann aus der abgehörten Kommunikation <math>K</math> 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 <math>K</math> gefahrlos für eine symmetrische Kryptografie nutzen.<ref name="Schmeh-S185-186" />
| |
| | |
| Dass beide Kommunikationspartner denselben Wert für <math>K</math> berechnen, zeigen die folgenden beiden [[Restklassenring|Restklassengleichungen]]<ref>Freiermuth u. a.: ''Einführung in die Kryptologie.'' 2. Aufl., 2014, S. 199.</ref>:
| |
| :<math>K_1 = B^a\ \bmod\ p = (g^b\ \bmod\ p)^a\ \bmod\ p = (g^b)^a\ \bmod\ p = g^{ba}\ \bmod\ p</math>.
| |
| :<math>K_2 = A^b\ \bmod\ p = (g^a\ \bmod\ p)^b\ \bmod\ p = (g^a)^b\ \bmod\ p = g^{ab}\ \bmod\ p</math>.
| |
| | |
| Da die Multiplikation [[Kommutativgesetz|kommutativ]] ist, gilt des Weiteren
| |
| :<math>g^{ba}\ \bmod\ p = g^{ab}\ \bmod\ p</math>
| |
| und somit
| |
| :<math>K_1 = K_2</math>.
| |
| | |
| Alice und Bob erhalten also nach ihren jeweiligen Berechnungen die genau gleiche Zahl, nämlich den geheimen Schlüssel <math>K = K_1 = K_2</math>.
| |
| | |
| '''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.
| |
| | |
| # Alice und Bob einigen sich auf die beiden öffentlichen Schlüssel <math>p = 13</math> und <math>g = 2</math> (<math>2</math> ist ein Generator der Gruppe <math>\Z_{13}^*</math>, siehe Abschnitt „Gruppentheorie“).
| |
| # Alice wählt die Zufallszahl <math>a = 5</math> als geheimen Schlüssel und Bob <math>b = 8</math>.
| |
| # Nun berechnet Alice <math>A = g^a\ \bmod\ p = 2^5\ \bmod\ 13 = 6</math> und sendet <math>A</math> an Bob. Bob berechnet <math>B = g^b\ \bmod\ p = 2^8\ \bmod\ 13 = 9</math> und sendet <math>B</math> an Alice.
| |
| # Alice berechnet <math>K_1 = B^a\ \bmod\ p = 9^5\ \bmod\ 13 = 3</math>. Bob berechnet <math>K_2 = A^b\ \bmod\ p = 6^8\ \bmod\ 13 = 3</math>.
| |
| # Beide erhalten das gleiche Ergebnis <math>K = K_1 = K_2 = 3</math>.
| |
| | |
| Die Lauscherin Eve kann zwar die Zahlen 13, 2, 6 und 9 mithören, das eigentliche gemeinsame Geheimnis von Alice und Bob <math>K = 3</math> bleibt ihr aber verborgen. <math>K = 3</math> kann als Schlüssel für die nachfolgende Kommunikation verwendet werden.
| |
| | |
| Mit Hilfe der abgefangenen Nachrichten kann Eve immerhin die folgenden Gleichungen aufstellen:
| |
| | |
| :<math>6 = 2^a\ \bmod\ 13</math>
| |
| :<math>9 = 2^b\ \bmod\ 13</math>
| |
| | |
| Daraus kann sie beispielsweise durch Ausprobieren die beiden geheimen Zahlen <math>a=5</math> und <math>b=8</math> bestimmen. Den vereinbarten Schlüssel <math>K</math> von Alice und Bob kann sie nun mit
| |
| | |
| :<math>K = g^{ab}\ \bmod\ p</math>
| |
| | |
| ausrechnen.
| |
| | |
| Wenn jedoch die Primzahl <math>p</math> groß genug gewählt wird und <math>g</math> ein Generator der Gruppe <math>\Z_p^*</math> ist, ist es für Eve zu aufwändig, um alle Zahlen zwischen <math>1</math> und <math>p-1</math> durchzuprobieren, die als Resultat der modularen Potenz <math>g^a\ \bmod\ p</math> in Frage kommen.<ref>Freiermuth u. a.: ''Einführung in die Kryptologie.'' 2. Aufl., 2014, S. 200–202.</ref>
| |
| | |
| === Programmierung ===
| |
| Das folgende Programm in der [[Programmiersprache]] [[Python (Programmiersprache)|Python]] zeigt die Implementierung des Diffie-Hellman-Schlüsselaustauschs für <math>p=107</math> und <math>g=3</math>.
| |
| <syntaxhighlight lang="python">
| |
| | |
| 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=}')
| |
| </syntaxhighlight>
| |
| | |
| == Sicherheit ==
| |
| | |
| === Diffie-Hellman-Problem ===
| |
| | |
| ==== Computational-Diffie-Hellman-Problem (CDH) ====
| |
| | |
| Angenommen, die Lauscherin Eve erfährt an der unsicheren Leitung die Zahlen <math>p</math>, <math>g</math>, <math>A</math> und <math>B</math>, aber nicht die diskreten Logarithmen <math>a</math> von <math>A</math> und <math>b</math> von <math>B</math> zur Basis <math>g</math>. Mit der Kenntnis von <math>a</math> und <math>b</math> wäre es für sie eine leichte Aufgabe, den Schlüssel <math>K=g^{ab}\ \bmod\ p</math> zu bestimmen. Die Zahlen <math>a</math> und <math>b</math> herauszufinden ist jedoch sehr schwer, wenn die Zahlen <math>p</math>, <math>a</math> und <math>b</math> sehr groß sind, beispielsweise Zahlen mit mehreren hundert [[Stellenwertsystem|Stellen]] im [[Dezimalsystem]].<ref name="Freiermuth-S200" /> Aus dieser Problemstellung ergibt sich das Computational-Diffie-Hellman-Problem:
| |
| | |
| : ''Wenn ein Element <math>g</math> einer Gruppe und die Werte <math>A=g^a</math> und <math>B=g^b</math> gegeben sind, welchen Wert hat dann <math>K=g^{ab}</math>, mit <math>a,b</math> 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.<ref name="Buchmann-S190">Buchmann: ''Einführung in die Kryptographie.'' 6. Aufl., 2016, S. 190.</ref> [[Ueli Maurer (Kryptologe)|Ueli Maurer]] hat gezeigt, dass beide Probleme zumindest unter bestimmten Voraussetzungen äquivalent sind.<ref name="MAURER">[[Ueli Maurer (Kryptologe)|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.</ref>
| |
| | |
| ==== 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: <math>A=g^a\ \bmod\ p</math>, <math>B=g^b\ \bmod\ p</math> und <math>C=g^c\ \bmod\ p</math>. Dabei wurden entweder <math>a</math>, <math>b</math> und <math>c</math> zufällig und gleichverteilt in <math>\{0,...,p-2 \}</math> gewählt oder <math>c=ab\ \bmod\ p</math> gesetzt. Im zweiten Fall heißt <math>(A,B,C)</math> Diffie-Hellman-Tripel. Der Angreifer muss entscheiden, ob ein solches Tripel vorliegt oder nicht. Kann er das nicht, ist es ihm unmöglich, aus <math>g^a</math> und <math>g^b</math> Rückschlüsse auf <math>g^{ab}</math> zu ziehen.<ref>Buchmann: ''Einführung in die Kryptographie.'' 6. Aufl., 2016, S. 190. Siehe ferner: 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.</ref>
| |
| | |
| Das Problem besteht also darin, bei gegebenem <math>g^a\ \bmod\ p</math>, <math>g^b\ \bmod\ p</math> und <math>g^c\ \bmod\ p</math> zu entscheiden, ob <math>g^c = g^{ab}</math> 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 <math>g</math> als [[Primitivwurzel]] kann das Decisional-Diffie-Hellman-Problem angegriffen werden. Dies liegt in folgendem Theorem begründet:
| |
| : Sei <math>p</math> eine Primzahl, sei <math>g</math> eine Primitivwurzel modulo <math>p</math> und seien <math>a, b \in \{0,...,p-2 \}</math>. Dann ist <math>g^{ab}</math> genau dann ein quadratischer Rest modulo <math>p</math>, wenn <math>g^a</math> oder <math>g^b</math> ein quadratischer Rest ist modulo <math>p</math>.
| |
| | |
| Das Theorem folgt daraus, dass eine Potenz von <math>g</math> genau dann ein quadratischer Rest modulo <math>p</math> ist, wenn der Exponent gerade ist.<ref name="Buchmann-S190" />
| |
| | |
| 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 %.<ref>Für einen Beweis siehe Buchmann: ''Einführung in die Kryptographie.'' 6. Aufl., 2016, S. 191–192.</ref>
| |
| | |
| === 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 <math>p</math> dermaßen gewählt werden, dass diskrete Logarithmen modulo <math>p</math> 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.<ref>Buchmann: ''Einführung in die Kryptographie.'' 6. Aufl., 2016, S. 192–193.</ref> Das [[Bundesamt für Sicherheit in der Informationstechnik]] empfiehlt im Fall eines ''Einsatzzeitraum[s] über das Jahr 2022 hinaus'' für <math>p</math> eine Schlüssellänge von mindestens 3000 Bit (Stand 2017).<ref>Bundesamt für Sicherheit in der Informationstechnik: [https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Publikationen/TechnischeRichtlinien/TR02102/BSI-TR-02102.pdf?__blob=publicationFile#table.3.1 BSI – Technische Richtlinien: Kryptographische Verfahren: Empfehlungen und Schlüssellängen] Version 2016-01, Stand 15. Februar 2016.</ref>
| |
| | |
| Die DHM-Primzahl <math>p</math> muss zudem so gewählt werden, dass Algorithmen zur Berechnung des diskreten Logarithmus kein leichtes Spiel haben. So muss beispielsweise vermieden werden, dass <math>p-1</math> 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 <math>p</math> 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 <math>\bmod\ p</math> hat.<ref name="Buchmann-S193">Buchmann: ''Einführung in die Kryptographie.'' 6. Aufl., 2016, S. 193.</ref>
| |
| | |
| ==== „Generator“ g ====
| |
| | |
| Die Zahl <math>g</math> sollte so gewählt werden, dass alle Zahlen zwischen <math>1</math> und <math>p-1</math> als Resultat der modularen Potenz <math>g^a\ \bmod\ p</math> in Frage kommen. Erst dann ist es zu aufwändig, alle Zahlen durchzuprobieren (wenn darüber hinaus die Primzahl <math>p</math> groß genug gewählt worden ist). Diese Eigenschaft erfüllt die Zahl <math>g</math>, wenn sie ein Primitivwurzel zum Modul <math>p</math> ist, d. h. ein Erzeuger der Gruppe <math>\Z_p^{*}</math>.<ref name="Freiermuth-S202" /> Wenn Alice und Bob beispielsweise <math>g=1</math> wählen, so funktioniert das Verfahren zwar noch immer, doch der Schlüssel <math>K</math> ist auf jeden Fall <math>1</math>, denn <math>1</math> ist genau der Generator der Untergruppe von <math>\Z_p^{*}</math> mit einem Element. Ähnlich unsicher ist das Verfahren, wenn Alice und Bob für <math>g</math> 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.<ref name="Schmeh-S187" />
| |
| | |
| Wie im Abschnitt „Prime Restklassengruppe und Primitivwurzel“ gezeigt, lässt sich eine Primitivwurzel relativ leicht finden, wenn man die DHM-Primzahl als <math>p = 2 \times q + 1</math> mit einer Primzahl <math>q</math> wählt. Wie jedoch im vorherigen Abschnitt gezeigt, kann das Decisional-Diffie-Hellman-Problem angegriffen werden, wenn man <math>g</math> als Primitivwurzel wählt.
| |
| | |
| {{Zitat|Wählt man statt dessen <math>g</math> so, dass die Restklasse von <math>g</math> modulo <math>p</math> Primzahlordnung <math>q</math> hat mit einer hinreichend großen Primzahl <math>q</math>, dann gilt DDH nach heutiger Auffassung als schwierig.|Johannes Buchmann, 2016<ref name="Buchmann-S193" />}}
| |
| | |
| ==== Verwendung fester Gruppen und Primzahlen ====
| |
| | |
| Da die Erzeugung sicherer Primzahlen rechenaufwendig ist, verwenden viele Implementierungen eine feste Primzahl <math>p</math>.<ref name="Adrian2015">Adrian u. a.: ''Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice.'' In: ''Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security.'' 2015, S. 5–15.</ref> 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 <math>p</math> benötigen. Ist <math>p</math> bekannt, kann ein Angreifer somit den Großteil vorberechnen und die Ergebnisse für jeden auf <math>p</math> basierenden Schlüsselaustausch wiederverwenden. Dadurch kann zum Beispiel der [[Transport Layer Security#Downgrade auf Exportverschlüsselung|Logjam-Angriff]] in TLS, nach einer einwöchigen Vorberechnung, einen 512-Bit-DHM-Schlüsselaustausch in rund 70 Sekunden brechen.<ref name="Adrian2015" />
| |
| | |
| Nach Schätzungen eines Forscherteams kann ein Angreifer mit Vorberechnung der 10 häufigsten 1024-Bit-Primzahlen den Netzwerkverkehr von 66 % der [[Virtual Private Network|VPNs]], 26 % der [[Secure Shell|SSH]]-Server, 16 % der [[Simple Mail Transfer Protocol|SMTP]]-Server und 24 % der [[Hypertext Transfer Protocol Secure|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.<ref name="Adrian2015" />
| |
| | |
| === Man-in-the-Middle-Angriff ===
| |
| {{Hauptartikel|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, [[Alice und Bob#Rollenverteilung|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
| |
| :<math>Z = g^z \mod p</math>
| |
| weiter, die er aus einer beliebigen Zahl <math>z</math> und den öffentlich bekannten Zahlen <math>g</math> und <math>p</math> berechnet.
| |
| | |
| [[Datei:Man-in-the-middle attack of Diffie-Hellman key agreement.svg|Man-in-the-Middle-Angriff]]
| |
| | |
| Nach dem Schlüsselaustausch besitzen die beiden Kommunikationspartner Alice und Bob unterschiedliche Schlüssel <math>K_A</math> und <math>K_B</math>. 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 <math>K_A</math> und <math>K_B</math>.
| |
| :<math>K_A = Z^a \bmod p = (g^z)^a \bmod p = (g^a)^z \bmod p = A^z \bmod p</math>
| |
| :<math>K_B = Z^b \bmod p = (g^z)^b \bmod p = (g^b)^z \bmod p = B^z \bmod p</math>
| |
| | |
| Da Alice und Bob im weiteren Verlauf davon ausgehen, mit dem jeweils Anderen zu kommunizieren, kann Mallory die folgende [[Symmetrische Kryptografie|symmetrisch verschlüsselte]] Kommunikation abhören. Diese leitet er dazu weiterhin über sich selbst um. Daten von Alice entschlüsselt Mallory mit <math>K_A</math> und verschlüsselt sie wieder mit <math>K_B</math>, 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 [[Authentizität|authentifiziert]] werden. Dazu wird ein Informationsvorsprung benötigt, der über einen authentifizierten Kanal erreicht wird.<ref name="GOLDBELL">[[Shafi Goldwasser]], [[Mihir Bellare]]: ''[https://cseweb.ucsd.edu/~mihir/papers/gb Lecture Notes on Cryptography.]'' 2008, Abschnitt 11.1.5 und 11.2.</ref>
| |
| | |
| === Seitenkanalangriffe ===
| |
| | |
| Ein [[Seitenkanalangriff]] bezeichnet eine kryptoanalytische Methode, die die physische Implementierung eines Kryptosystems in einem Gerät (z. B. einer [[Chipkarte]], eines [[Security-Token]]s oder eines [[Hardware-Sicherheitsmodul]]s) 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 C. Kocher|Paul Kocher]] eine neuartige Methode, mit der es ihm gelang, Implementierungen von Diffie-Hellman, RSA und DSA zu brechen: der Zeitangriff (''timing attack'').<ref>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. ([https://citeseerx.ist.psu.edu/doc_view/pid/11e3daf8f3548b6599751235c8c188f89fae1ca6 Online])</ref>
| |
| | |
| Ziel des Zeitangriffs ist die diskrete Exponentialfunktion. Wenn eine Krypto-Implementierung <math>g^a\ \bmod\ p</math> für irgendwelche größeren Zahlen <math>g</math>, <math>a</math> und <math>p</math> berechnet, dann geschieht dies fast immer mit dem Square-and-Multiply-Algorithmus. Bei diesem ist für jedes Bit von <math>a</math> eine Aktion festgesetzt: Hat das gerade bearbeitete Bit den Wert <math>1</math>, 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 <math>a</math> ziehen. Variiert er die Zahl <math>g</math>, reichen irgendwann die Informationen aus, um <math>a</math> zu berechnen. Schon mit einigen Tausend Zeitmessungen lassen sich entsprechende Implementierungen mit 1024-Bit-Schlüsseln brechen.<ref>Schmeh: ''Kryptografie.'' 5. Aufl., 2013, S. 320–321.</ref>
| |
| | |
| 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.<ref>Schmeh: ''Kryptografie.'' 5. Aufl., 2013, S. 321.</ref>
| |
| | |
| ==== Stromangriff ====
| |
| [[Datei:Oscilloscope diagram.png|mini|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.<ref>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-Verlang: Berlin, 1999, S. 388–397.</ref> Bei Stromangriffen wird nicht nur die Verarbeitungszeit gemessen, sondern mit einem [[Oszilloskop]] auch der Stromverbrauch. Besonders [[Smartcard]]s 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.<ref>Schmeh: ''Kryptografie.'' 5. Aufl., 2013, S. 321–322.</ref>
| |
| | |
| 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.<ref>Schmeh: ''Kryptografie.'' 5. Aufl., 2013, S. 323–324.</ref>
| |
| | |
| == Elliptic Curve Diffie-Hellman (ECDH) ==
| |
| | |
| Kryptosysteme auf Basis [[Elliptische Kurve|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 <math>n</math>-fache Addieren eines Punktes <math>P</math> zu sich selbst (also die Multiplikation mit dem Skalar <math>n</math>) wird mit <math>n P</math> bezeichnet und entspricht einer Exponentiation <math>x^n</math> im ursprünglichen Verfahren. Das Prinzip wurde Mitte der 1980er Jahre von [[Victor S. Miller]]<ref>Victor S. Miller: ''Use of Elliptic Curves in Cryptography.'' In: ''Advances in Cryptology – CRYPTO ’85 Proceedings'' (= ''Lecture Notes in Computer Science.'' 218). Springer, 1986, S. 417–426</ref> und [[Neal Koblitz]]<ref>Neal Koblitz: ''Elliptic Curve Cryptosystems.'' In: ''Mathematics of Computation'' 48, Nr. 177, American Mathematical Society, 1987, S. 203–209.</ref> unabhängig voneinander vorgeschlagen.
| |
| | |
| === Körper ===
| |
| | |
| Ein [[Körper (Algebra)|Körper]] ist eine Menge <math>K</math> versehen mit zwei [[Innere zweistellige Verknüpfung|inneren zweistelligen Verknüpfungen]] „<math>+</math>“ und „<math>\cdot</math>“, 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 [[Distributivgesetz]]e. Der bekannteste Körper ist die Menge der reellen Zahlen <math>\R</math>, auf der Addition und Multiplikation in üblicher Weise definiert sind.
| |
| | |
| Für eine Primzahl <math>p</math> bildet die Menge der Zahlen zwischen <math>0</math> und <math>p-1</math> sowohl mit der Modulo-Addition als auch mit der Modulo-Multiplikation ohne Null eine Gruppe. Die Restklassen ganzer Zahlen modulo <math>p</math>, geschrieben <math>\mathbb F_p</math> oder <math>\operatorname{GF}(p)</math>, bilden somit einen [[Endlicher Körper|endlichen Körper]] (auch Galoiskörper, engl. ''Galois field''). Außerdem gibt es für jede Primzahl <math>p</math> und jede natürliche Zahl <math>n</math> (bis auf [[Isomorphismus|Isomorphie]]) genau einen Körper mit <math>p^n</math> Elementen, der mit <math>\mathbb F_{p^n}</math> oder <math>\operatorname{GF}(p^n)</math> bezeichnet wird. In der [[Elliptic Curve Cryptography]] sind insbesondere die beiden Spezialfälle <math>n=1</math> und <math>p=2</math> von Bedeutung, also <math>\operatorname{GF}(p)</math> und <math>\operatorname{GF}(2^n)</math>. Mit diesen lassen sich ECC-Verfahren am besten realisieren.<ref>Schmeh: ''Kryptografie.'' 5. Aufl., 2013, S. 212.</ref>
| |
| | |
| === Elliptische Kurven ===
| |
| [[Datei:Adding P,Q.PNG|mini|hochkant|Addition von Punkten P und Q auf einer [[Elliptische Kurve|elliptischen Kurve]]]]
| |
| [[Datei:Doubling P.PNG|mini|hochkant|Verdoppelung eines Punktes P auf einer elliptischen Kurve]]
| |
| | |
| Eine [[elliptische Kurve]] (EC) ist eine Menge von Punkten <math>(x,y)</math> mit Werten aus einem Körper <math>K</math>, die eine [[kubische Gleichung]] der folgenden Form erfüllen:
| |
| | |
| :<math>y^2 = x^3 + ax + b</math>. ([[Elliptische Kurve#Kurze Weierstraß-Gleichung|Kurze Weierstraß-Gleichung]])
| |
| | |
| Die (reellen) Koeffizienten <math>a</math> und <math>b</math> müssen dabei die Bedingung <math>4a^3 + 27b^2 \neq 0</math> erfüllen, um Singularitäten auszuschließen.
| |
| | |
| Eine elliptische Kurve ist eine glatte algebraische Kurve der Ordnung 3 in der [[Projektive Ebene|projektiven Ebene]]. Dargestellt werden elliptische Kurven meist als Kurven in der [[Affine Ebene|affinen Ebene]], sie besitzen aber noch einen zusätzlichen Punkt im Unendlichen, der hier als <math>\mathcal O</math> (sprich „O“) bezeichnet wird, jedoch nicht mit dem [[Koordinatenursprung|Nullpunkt]] des [[Koordinatensystem]]s zu verwechseln ist. Über dem Körper <math>K = \R</math> der reellen Zahlen bilden die Punkte eine Kurve in der reellen Ebene.<ref name="BSW148">Beutelspacher, Schwenk, Wolfenstetter: ''Moderne Verfahren der Kryptographie.'' 8. Aufl., 2015, S. 148.</ref>
| |
| | |
| 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 <math>y</math>-Achse verläuft, ist einer der drei Schnittpunkte <math>\mathcal O</math>.
| |
| * 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.<ref name="Schmeh214-215">Schmeh: ''Kryptografie.'' 5. Aufl., 2013, S. 214–215.</ref>
| |
| | |
| Durch diese Eigenschaft lässt sich mit Hilfe elliptischer Kurven eine Gruppe <math>\operatorname{E}(K)</math> definieren:
| |
| | |
| Sei <math>G</math> die Punktmenge einer elliptischen Kurve, vereinigt mit dem Punkt <math>\mathcal O</math> im Unendlichen. Man definiert die Gruppenoperation, die üblicherweise als Punktaddition bezeichnet wird, wie folgt:
| |
| * Um die Summe zweier Punkte <math>P</math> und <math>Q</math> zu berechnen, zeichne eine Gerade durch <math>P</math> und <math>Q</math> (falls <math>P=Q</math>, zeichne die [[Tangente]] an EC durch <math>P</math>)
| |
| * Finde den dritten Schnittpunkt <math>R</math> dieser Geraden mit der Kurve EC. (Falls die Gerade parallel zur <math>y</math>-Achse läuft, so ist dieser Schnittpunkt <math>\mathcal O</math>.)
| |
| * Die Summe <math>P + Q</math> ist der Punkt von EC, der durch Spiegelung von <math>R</math> an der <math>x</math>-Achse entsteht. Die Spiegelung von <math>\mathcal O</math> ist wiederum <math>\mathcal O</math>.<ref name="BSW148" />
| |
| | |
| Das neutrale Element der Gruppe ist <math>\mathcal O</math>. Es gilt <math>P + \mathcal O = \mathcal O + P = P</math> für alle Punkte <math>P</math> der elliptischen Kurve. Das Inverse eines Punktes erhält man, indem man an ihn eine Gerade anlegt, die parallel zur <math>y</math>-Achse verläuft. Ist diese Gerade eine Tangente, dann ist der Punkt selbst sein inverses Element.<ref name="BSW148" /><ref name="Schmeh214-215" />
| |
| | |
| Der Punkt <math>P + P</math> wird mit <math>2P</math> bezeichnet, entsprechend definiert man <math>kP = P + \ldots + P</math> als <math>k</math>-fache Addition des Punktes <math>P</math>. Ist <math>P</math> nicht der <math>\mathcal O</math>-Punkt, kann auf diese Weise jeder Punkt der Kurve E erreicht werden (d. h., zu jedem Punkt <math>Q</math> auf der Kurve existiert eine [[natürliche Zahl]] <math>k</math> mit <math>Q = kP</math>), wenn man die richtigen Erzeugenden <math>P</math> der Gruppe kennt. (Siehe auch Abschnitt [[Elliptische Kurve#Gruppenoperation|Gruppenoperation]] im Artikel „Elliptische Kurve“)
| |
| | |
| Die Aufgabe, aus gegebenen Punkten <math>P, Q</math> diesen Wert <math>k</math> 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 <math>K = \R</math>, 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 <math>\operatorname{E}(\operatorname{GF}(p))</math> und <math>\operatorname{E}(\operatorname{GF}(2^n))</math> von Bedeutung.
| |
| | |
| '''Beispiel:'''
| |
| | |
| Sei die elliptische Kurve
| |
| :<math>E: y^2 = x^3 + x + 1</math>
| |
| über dem Körper <math>K=\operatorname{GF}(5)</math> gegeben.<ref>Washington: ''Elliptic Curves.'' 2. Aufl., 2008, S. 95–97.</ref>
| |
| | |
| Es ist also <math>a=1</math> und <math>b=1</math> und es gilt <math>4a^3 + 27b^2 = 31\ \bmod\ 5 = 1 \neq 0</math>. Die Menge aller <math>(x,y)</math> mit <math>x,y \in \operatorname{GF}(5)</math> und <math>y^2 = x^3 + x + 1</math> ist also zusammen mit <math>\mathcal O</math> eine elliptische Kurve über <math>\operatorname{GF}(5)</math>.
| |
| | |
| Daraus ergeben sich die folgenden Punkte:
| |
| | |
| {| class="wikitable"
| |
| |-
| |
| ! <math>x</math> !! <math>x^3 + x + 1\ \bmod\ 5</math> !! <math>y</math> !! Punkte
| |
| |-
| |
| | <math>0</math> || <math>1</math> || <math>1</math> und <math>4 (= -1\ \bmod\ 5)</math> || <math>(0,1)</math>, <math>(0,4)</math>
| |
| |-
| |
| | <math>1</math> || <math>3</math> || – || –
| |
| |-
| |
| | <math>2</math> || <math>1</math> || <math>1</math> und <math>4</math> || <math>(2,1)</math>, <math>(2,4)</math>
| |
| |-
| |
| | <math>3</math> || <math>1</math> || <math>1</math> und <math>4</math> || <math>(3,1)</math>, <math>(3,4)</math>
| |
| |-
| |
| | <math>4</math> || <math>4</math> || <math>2</math> und <math>3</math> || <math>(4,2)</math>, <math>(4,3)</math>
| |
| |-
| |
| | <math>\mathcal O</math> || – || <math>\mathcal O</math> || <math>\mathcal O</math>
| |
| |}
| |
| | |
| === Diffie-Hellman auf Basis elliptischer Kurven ===
| |
| Bei Kryptosystemen auf Basis elliptischer Kurven werden statt Rechenoperationen in <math>\operatorname{GF}(p)</math> Rechenoperationen in <math>\operatorname{E}(\operatorname{GF}(p))</math> oder <math>\operatorname{E}(\operatorname{GF}(2^n))</math> 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 <math>\operatorname{GF}(p)</math> (bzw. <math>\operatorname{GF}(2^n)</math>) und eine darauf aufbauende Gruppe <math>\operatorname{E}(\operatorname{GF}(p))</math> (bzw. <math>\operatorname{E}(\operatorname{GF}(2^n))</math>). Alle Parameter, die im Exponenten stehen, sind (wie bisher) natürliche Zahlen, während die Basis einer Potenz ein Element von <math>\operatorname{E}(\operatorname{GF}(p))</math> ist.<ref name="Schmeh215">Schmeh: ''Kryptografie.'' 5. Aufl., 2013, S. 215.</ref>
| |
| | |
| Eine Exponentiation über <math>\operatorname{E}(\operatorname{GF}(p))</math> ist aufwendiger als eine Exponentiation über <math>\operatorname{GF}(p)</math>, da sie sich aus mehreren Rechenoperationen in <math>\operatorname{GF}(p)</math> zusammensetzt. Dafür ist auch die Berechnung des Logarithmus in <math>\operatorname{E}(\operatorname{GF}(p))</math> wesentlich „schwieriger“. Der zentrale Vorteil bei der Verwendung von <math>\operatorname{E}(\operatorname{GF}(p))</math> 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.<ref name="Schmeh215" />
| |
| | |
| Die Komplexität des Logarithmus nimmt in <math>\operatorname{E}(\operatorname{GF}(p))</math> mit <math>p</math> linear zu, in <math>\operatorname{GF}(p)</math> 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.<ref name="Schmeh215" />
| |
| | |
| == Ephemeral Diffie-Hellman ==
| |
| Im Zusammenhang des [[Kryptografiesprotokoll]]s [[Transport Layer Security]] (TLS) bezeichnet ''Ephemeral Diffie-Hellman'' ({{enS|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-Kryptografiesverfahren]], zum Beispiel [[RSA-Kryptosystem|RSA]].
| |
| | |
| == Literatur ==
| |
| | |
| '''Allgemeiner Überblick'''
| |
| | |
| * [[Albrecht Beutelspacher]]: ''Geheimsprachen. Geschichte und Techniken.'' 3., aktualisierte Auflage, C.H. Beck: München, 2002.
| |
| * 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.
| |
| * [[Johannes Buchmann]]: ''Einführung in die Kryptographie.'' 6. Auflage, Springer Spektrum: Berlin, Heidelberg, 2016.
| |
| * 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.
| |
| * [[Klaus Schmeh]]: ''Kryptografie. Verfahren, Protokolle, Infrastrukturen.'' 5., aktualisierte Auflage, dpunkt.verlag: Heidelberg, 2013.
| |
| * [[Simon Singh]]: ''[[Geheime Botschaften]]. Die Kunst der Kryptografie 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).
| |
| | |
| '''Fachartikel'''
| |
| | |
| * 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. ([https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf 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. ([https://crypto.stanford.edu/~dabo/abstracts/DDH.html Online])
| |
| * [[Whitfield Diffie]], [[Martin E. Hellman]]: ''New Directions in Cryptography.'' In: ''IEEE Transactions on Information Theory'' 22, Nr. 6, 1976, S. 644–654. ([https://www-ee.stanford.edu/~hellman/publications/24.pdf Online])
| |
| * Martin E. Hellman: ''An overview of public key cryptography.'' In: ''IEEE Communications Magazine'' 40, Nr. 5, 2002, S. 42–49 ([https://www-ee.stanford.edu/~hellman/publications/73.pdf Online]). Originalartikel: ''An overview of public key cryptography.'' In: ''IEEE Communications Magazine'' 16, Nr. 6, 1978, S. 24–32 ([https://ee.stanford.edu/~hellman/publications/31.pdf Online])
| |
| * [[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. ([https://citeseerx.ist.psu.edu/doc_view/pid/11e3daf8f3548b6599751235c8c188f89fae1ca6 Online])
| |
| * 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. ([https://courses.csail.mit.edu/6.857/2006/handouts/TimingAttacks.pdf 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. ([https://www.cis.upenn.edu/~nadiah/courses/cis800-02-f13/readings/kocher-jaffe-jun.pdf Online])
| |
| * [[Ueli Maurer (Kryptologe)|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]].
| |
| * [[Ralph C. Merkle]]: ''Secure Communications over Insecure Channels''. In: ''Communications of the ACM'' 21, Nr. 4, April 1978, S. 294–299. ([https://ralphmerkle.com/1974/PuzzlesAsPublished.pdf Online])
| |
| | |
| '''Anwendung'''
| |
| | |
| * Anatol Badach, Erwin Hoffmann: ''Technik der IP-Netze. Internet-Kommunikation in Theorie und Einsatz.'' 3., überarbeitete und erweiterte Auflage, Hanser: München, 2015.
| |
| * [[Wolfgang Ertel (Informatiker)|Wolfgang Ertel]]: ''Angewandte Kryptographie.'' 4. Auflage, Hanser: München, 2012.
| |
| * Patrick Horster (Hrsg.): ''Chipkarten. Grundlagen, Realisierung, Sicherheitsaspekte, Anwendungen.'' vieweg, 1998.
| |
| * 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.
| |
| * Christian Karpfinger, Kurt Meyberg: ''Algebra. Gruppen, Ringe, Körper.'' 3. Auflage, Springer Spektrum: Berlin, Heidelberg, 2013.
| |
| * 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.
| |
| | |
| == Weblinks ==
| |
| * [https://www.bsi.bund.de/DE/Home/home_node.html Bundesamt für Sicherheit in der Informationstechnik] (BSI): [https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Publikationen/TechnischeRichtlinien/TR02102/BSI-TR-02102.pdf?__blob=publicationFile#table.3.1 BSI – Technische Richtlinien: Kryptographische Verfahren: Empfehlungen und Schlüssellängen] Version 2016-01, Stand 15. Februar 2016.
| |
| * ECRYPT II: [https://www.ecrypt.eu.org/ecrypt2/ European Network of Excellence in Cryptology II]
| |
| * Steven Levy: [https://www.wired.com/1999/04/crypto/ The Open Secret] – ''Public key cryptography – the breakthrough that revolutionized email and ecommerce – was first discovered by American geeks. Right? Wrong.'' In: [https://www.wired.com/ WIRED] (veröffentlicht: 4. Januar 1999; abgerufen: 9. Mai 2016)
| |
| | |
| == Einzelnachweise ==
| |
| <references />
| |
| | |
| {{SORTIERUNG:DiffieHellmanSchlusselaustausch}}
| |
| [[Kategorie:Schlüsselaustauschprotokoll]]
| |
| [[Kategorie:Kryptografie]]
| |