Benutzer:Didia/DHM

Elliptic Curve Diffie-Hellman

Elliptic Curve Diffie-Hellman (ECDH)

Körper

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

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

Elliptische Kurven

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

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

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

Über dem Körper $K=\mathbb {R}$ der reellen Zahlen bilden die Punkte eine Kurve in der reellen Ebene.

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 ${\mathcal {O}}$ (sprich „0“) bezeichnet wird, jedoch nicht mit dem Nullpunkt des Koordinatensystems zu verwechseln ist.

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 y-Achse verläuft, ist einer der drei Schnittpunkte ${\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.

Durch diese Eigenschaft lässt sich mit Hile elliptischer Kurven eine Gruppe $E(K)$ definieren:

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

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

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

Sehr anschaulich ist die Konstruktion für $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 $E(GF(p))$ und $E(GF(2^{n}))$ von Bedeutung.

Beispiel:

Sei die elliptische Kurve

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

über dem Körper $K=GF(5)$ gegeben.

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

Daraus ergeben sich die folgenden Punkte:

tbd

Diffie-Hellman auf Basis elliptischer Kurven

TBD