Elliptische Kurven (EC)

3.3 Elliptische Kurven (EC)

3.3.1 Elliptische Kurven über reellen Zahlen $ℝ$

Elliptische Kurven $E (ℝ )$ werden in der Normalform nach WEIERSTRASS durch Gleichungen der Form

y2 = x3+ ax+ b, mit x,y,a,b∈ ℝ

(3.6)

beschrieben. Wegen der (nur) zwei freien Parameter $a$ und $b$ ist jede elliptische Kurve durch zwei Punkte $P ,P 1 2$ eindeutig definiert. Insofern ist jeder weitere Punkt durch die Kenntnis von $P 1$ und $P 2$ festgelegt.

Für $a$ ergibt die Differenz beider Gleichungen

was dann zur Berechnung von $b$ verwendet werden kann.

Abbildung 3.3:

Prinzip der Elliptische Kurve

Zieht man entsprechend Abbildung 3.3) durch $P1$ und $P2$ eine Gerade, so berechnet sich ein dritter (Schnitt-) Punkt $′ ′ P3 = (x3,y3)$ nach der Geradengleichung:

mit dem Anstieg:

y − y y′− y y′− y λ = -2---1 = -3---1 = -3---2. x2− x1 x3− x1 x3− x2

(3.7)

Den Schnittpunkt $′ P3$ mit der elliptischen Kurve

findet man (unter Zuhilfenahme von $α3 − β3 = (α − β)(α2+ α β +β 2)$ ) durch Gleichsetzen:

Aus der Geradengleichung ist nun $y′3$ berechenbar:

und so für den Kurvenpunkt $P3 = (x3,y3)= (x3,− y′3)$ :

2 P3 = (λ − x2− x1,λ[x1− x3]+ y1).

(3.10)

3.3.2 Elliptische Kurven über endlichen Körpern $Fq$

Der kryptographische Anwendungsfall sind elliptische Kurven über endlichen (Restklassen-) Körpern $Fq$ , welche selbst entweder Primzahlenkörper $Fp$ oder auch Binärkörper $F2m$ sind.⁴⁰ Dafür definiert man die Addition zweier Punkte $P ,P 1 2$ zu $P = P + P 3 1 2$ so, daß $P 3$ (wie in Abbildung 3.3 dargestellt) wieder auf der elliptischen Kurve liegt. Die Menge aller dieser Punkte $P3$ soll eine ABELsche Gruppe $(G,+ )$ bilden, d. h. es müssen folgende Bedingungen erfüllt sein:

Die Addition von führt zu . Für die Kurve ergeben sich folgende Formeln:⁴¹
1. Punktaddition:
  
  $P3 = (x3,y3)= (x3,− y′3)= (λ 2− x2− x1,λ [x1− x3]− y1)$ (3.11)
2. Punktverdoppelung:
  Für $P = P = P = (x,y) 1 2$ wird die Tangente angelegt (denn $λ$ kann nicht nach Formel 3.7 berechnet werden), d. h. der Anstieg $λ$ entspricht der ersten Ableitung im Punkt $P$ .
  
  Mit $x= x1 = x2$ ergibt sich aus Additionsformel 3.11 direkt das Ergebnis:
  
  $2 P3 = (x3,y3) = (λ − 2x,λ[x− x3]− y) .$ (3.12)
3. Im Fall $x1 = x2$ und $y2 = − y1$ wird $P3 = (0,0)$ definiert.
Die Addition sei assoziativ: $P + (P + P )= (P + P )+ P 1 2 3 1 2 3$ für $P ,P ,P ∈ G 1 2 3$ .
Es gibt das neutrale Element $O ∈ G$ mit $P +O = O + P = P$ für $P ∈ G$ . Nimmt man an, daß $O = (x1,y1)$ ist, dann muß die Forderung $P3 = P2$ gestellt werden, um $(x1,y1)$ zu ermitteln. Dazu verwendet man $x = λ2 − x − x 3 2 1$ mit $λ → ∞$ , was zu $x = lim λ 2− 2x = ∞ 1 λ→ ∞ 2$ und $y1 = lim λ,x1→ ∞λ (x1 − x2)− y2 = ∞$ führt. Das neutrale Element ist somit $O = (∞,∞)$ , was auch geometrisch einleuchtet.
Zu jedem beliebigen Element $P ∈ G$ findet man $− P ∈ G$ , so daß wieder $(− P )+ P = O$ gilt. Als Folge der Betrachtungen zum neutralen Element (siehe voriger Punkt) ergibt sich: $− P = (x,− y)$

Elliptische Kurven über $F2m$ verwenden die Form $y2+ xy= x3+ ax2 +b$ , funktionieren aber grundsätzlich nach demselben Prinzip. Ohne weiteren Beweis sei hier angegeben (vgl. zum Beispiel [HMV04, 3.1.2], zu den Algorithmen siehe auch [HHM00, BHHM01, FHLM04, Ano07]):

Punktaddition: $P3 = P1+ P2 = (λ2 +λ + x1+ x2+ a,λ[x1+ x3]+ x3+ y1)$
Punktverdoppelung: $2 2 P3 = 2P = (λ +λ + a,x + x3[λ + 1])$ , mit $λ = x+ y∕x$
negativer Punkt: $− P = (x,x+ y)$

Zur Verifikation eines Kurvenpunktes substituiert man $z= y∕x$ und erhält eine quadratische Gleichung in $F m 2$ .⁴²

Die beiden Lösungen sind wegen $2 z + z = z(z+ 1)$ dann $z$ und $z+ 1$ , unterscheiden sich also nur im niederwertigsten Bit [IEE00, A.12.9].

Für die kryptographische Anwendung, insbesondere für Verfahren, die auf dem diskreten Algorithmus basieren, wird zuerst die Gruppenpotenz definiert zu $n y= x = x ◇x◇ x⋅⋅⋅x◇ x$ . Das diskrete Logarithmus Problem besteht nun bekanntermaßen darin die Zahl $n$ zu finden, was bei einer Gruppenaddition per elliptischer Kurve ziemlich schwierig ist. Eines der bekanntesten Beispiele ist die Umsetzung des Diffie-Hellman Schlüsselaustausches (vgl. Abschnitt 3.2) auf elliptische Kurven [Ros99]. Aber auch Signatur- und Public-Key Verfahren können damit realisiert werden [IEE04], [ANS05].