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:
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
=== 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 ==
== Ephemeral Diffie-Hellman ==
Version vom 2. März 2023, 12:05 Uhr
Beschreibung
Vereinbarung eines gemeinsamen 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[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.
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.
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
Es existiert bis heute kein „schneller“ Algorithmus zur Berechnung des Exponenten , bei gegebener Basis , Modul 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.
Dabei werden die beim Originalverfahren eingesetzten Operationen (Multiplikation und Exponentiation) auf dem endlichen Körper ersetzt durch Punktaddition und Skalarmultiplikation auf elliptischen Kurven.
Das -fache Addieren eines Punktes zu sich selbst (also die Multiplikation mit dem Skalar ) wird mit bezeichnet und entspricht einer Exponentiation im ursprünglichen Verfahren.
Das Prinzip wurde Mitte der 1980er Jahre von Victor S. Miller und Neal Koblitz unabhängig voneinander vorgeschlagen.
Schlüsseltauschproblem
Kryptografie und Entschlüsselung mit demselben Schlüssel (symmetrisches Verfahren)
Kryptografiesverfahren, bei denen zwei Teilnehmer denselben geheimen Schlüssel verwenden, nennt man symmetrische Verfahren. Seien Alice und BobSender 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 Kryptografiesalgorithmus). Eine Nachricht, die verschlüsselt wird, heißt Klartext, der verschlüsselte Text Geheimtext.[2]
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?[3]
Ein manueller Schlüsselaustausch hat den Nachteil, dass er recht unübersichtlich wird, wenn eine größere Anwendergruppe untereinander verschlüsselt kommunizieren will. Bei Kommunikationspartnern sind Schlüssel erforderlich, wenn jeder mit jedem kommunizieren will. Bei 50 Kommunikationspartnern wären somit insgesamt 1.225 Schlüssel nötig.[4]
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.[3]
Im Zusammenhang des KryptografiesprotokollsTransport Layer Security (TLS) bezeichnet Ephemeral Diffie-Hellman (: 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.
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)
Einzelnachweise
↑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.
