Elliptische Kurven
Eine elliptische Kurve E(A, B) mit 4 A³ + 27 B² != 0 ist eine Kurve in der Ebene. Sie enthält die Punkte (x y), die die Bedingung y² = x³ + A x + B erfüllen.
Die Menge aller Punkte auf einer elliptischen Kurve zusammen mit dem zusätzlichen Punkt O ("unendlich ferner Punkt") ist mit der Verknüpfung + eine abelsche Gruppe. Dabei ist die Addition zweier Punkte + wie folgt definiert:
Der Punkt O ist das neutrale Element der Addition, also O + Q = Q und P + O = P.
Wenn Px = Qx und Py = -Qy dann P + Q = O.
Sonst ist P + Q = R, mit Rx = m² - Px - Qx und Ry = m (Px - Rx) - Py. Dabei bestimmt sich m als (3 Px² + A) / 2 Py wenn P = Q und (Qy - Py) / (Qx - Px) anderenfalls.
P und Q sind invers zueinander, wenn Px = Qx und Py = -Qy. Der Punkt O ist invers zu sich selbst.
Wenn man die Elemente eines Restklassenrings (siehe Restklassenringe) als Koordinaten für die Punkte verwendet, dann ergibt sich die im Folgenden beschriebene Implementierung. Die Addition für Punkte erfüllt nur die Gruppeneigenschaften, wenn der Restklassenring ein Körper ist.
Die Gruppe wird durch vier Klassen - eine Klasse für die elliptische Kurve und drei Klassen für die Punkte - und zugehörige Methoden implementiert.
Instanzen der Klasse elliptic-curve speichern die Parameter a und b der Kurve und eine Instanz des Punktes in der Unendlichkeit.
(defclass elliptic-curve ())
(defmethod initialize ((this elliptic-curve) (a residue-class) (b residue-class))
(and
(same-ring? a b)
(not (zero?
(+ (* (new residue-class (get-ring a) 4) a a a)
(* (new residue-class (get-ring b) 27) b b)))))
(progn
(.= this a a)
(.= this b b)
(.= this infinite-point (new infinite-point this))
(freeze this)))
Die Methode get-infinite-point liefert den Punkt in der Unendlichkeit.
(defmethod get-infinite-point ((this elliptic-curve))
t
(. this infinite-point))
Die Methode make-point erzeugt einen Punkt aus den angegebenen Koordinaten.
(defmethod make-point ((this elliptic-curve) (x residue-class) (y residue-class))
t
(new finite-point this x y))
Die Methode add-points erzeugt einen Punkt als Summe zweier Punkte. Die beiden Punkte sind durch ihre Koordinaten gegeben. Die Methode ist nur anwendbar, wenn sich nicht der Punkt O als Resultat der Addition ergibt.
(defmethod add-points ((this elliptic-curve) (x1 residue-class) (y1 residue-class) (x2 residue-class) (y2 residue-class))
(not
(and
(= x1 x2)
(= y1 (- (new residue-class (get-ring y2) 0) y2))))
(let
((m (if
(= x1 x2)
(/ (+ (* (new residue-class (get-ring x1) 3) x1 x1) (. this a)) (+ y1 y1))
(/ (- y2 y1) (- x2 x1)))))
(let
((x3 (- (* m m) x1 x2)))
(let
((y3 (- (* (- x1 x3) m) y1)))
(make-point this x3 y3)))))
Die Instanzen der Klassen point, finite-point und infinite-point repräsentieren Punkte, entweder auf der Kurve oder den unendlich fernen Punkt. Der Initialisierer für Punkte prüft, ob die Koordinaten des Punkts zur Kurve passen.
(deftrait point ())
(defclass finite-point (point))
(defclass infinite-point (point))
(defmethod initialize ((this finite-point) (curve elliptic-curve) (x residue-class) (y residue-class))
(with-slots-read-only (a b) curve
(=
(* y y)
(+ (* x x x) (* a x) b)))
(progn
(.= this curve curve)
(.= this x x)
(.= this y y)
(freeze this))))
(defmethod initialize ((this infinite-point) (curve elliptic-curve))
t
(progn
(.= this curve curve)
(freeze this)))
Die Methode get-curve liefert die Kurve zum einem Punkt.
(defmethod get-curve ((this point))
t
(. this curve))
Die Methode same-curve? prüft, ob zwei Punkte zur selben Kurve gehören. Nur dann ist die Addition definiert.
(defmethod same-curve? ((point-1 point) (point-2 point))
t
(= (get-curve point-1) (get-curve point-2)))
Die Methode add addiert zwei Punkte.
(defmethod add ((point-1 infinite-point) (point-2 point))
(same-curve? point-1 point-2)
point-2)
(defmethod add ((point-1 point) (point-2 infinite-point))
(same-curve? point-1 point-2)
point-1)
(defmethod add ((point-1 finite-point) (point-2 finite-point))
(same-curve? point-1 point-2)
(let
((curve (get-curve point-1))
(x1 (. point-1 x))
(y1 (. point-1 y))
(x2 (. point-2 x))
(y2 (. point-2 y)))
(if
(or
(and (= x1 x2) (zero? y1) (zero? y2))
(and (= x1 x2) (not (= y1 y2))))
(get-infinite-point curve)
(add-points curve x1 y1 x2 y2))))
Quellen
http://tools.ietf.org/html/rfc6090
H. W. Lenstra Jr.
"Factoring integers with elliptic curves"
Annals of Mathematics 126 (1987)
Seite 652
Die Menge aller Punkte auf einer elliptischen Kurve zusammen mit dem zusätzlichen Punkt O ("unendlich ferner Punkt") ist mit der Verknüpfung + eine abelsche Gruppe. Dabei ist die Addition zweier Punkte + wie folgt definiert:
Der Punkt O ist das neutrale Element der Addition, also O + Q = Q und P + O = P.
Wenn Px = Qx und Py = -Qy dann P + Q = O.
Sonst ist P + Q = R, mit Rx = m² - Px - Qx und Ry = m (Px - Rx) - Py. Dabei bestimmt sich m als (3 Px² + A) / 2 Py wenn P = Q und (Qy - Py) / (Qx - Px) anderenfalls.
P und Q sind invers zueinander, wenn Px = Qx und Py = -Qy. Der Punkt O ist invers zu sich selbst.
Wenn man die Elemente eines Restklassenrings (siehe Restklassenringe) als Koordinaten für die Punkte verwendet, dann ergibt sich die im Folgenden beschriebene Implementierung. Die Addition für Punkte erfüllt nur die Gruppeneigenschaften, wenn der Restklassenring ein Körper ist.
Die Gruppe wird durch vier Klassen - eine Klasse für die elliptische Kurve und drei Klassen für die Punkte - und zugehörige Methoden implementiert.
Instanzen der Klasse elliptic-curve speichern die Parameter a und b der Kurve und eine Instanz des Punktes in der Unendlichkeit.
(defclass elliptic-curve ())
(defmethod initialize ((this elliptic-curve) (a residue-class) (b residue-class))
(and
(same-ring? a b)
(not (zero?
(+ (* (new residue-class (get-ring a) 4) a a a)
(* (new residue-class (get-ring b) 27) b b)))))
(progn
(.= this a a)
(.= this b b)
(.= this infinite-point (new infinite-point this))
(freeze this)))
Die Methode get-infinite-point liefert den Punkt in der Unendlichkeit.
(defmethod get-infinite-point ((this elliptic-curve))
t
(. this infinite-point))
Die Methode make-point erzeugt einen Punkt aus den angegebenen Koordinaten.
(defmethod make-point ((this elliptic-curve) (x residue-class) (y residue-class))
t
(new finite-point this x y))
Die Methode add-points erzeugt einen Punkt als Summe zweier Punkte. Die beiden Punkte sind durch ihre Koordinaten gegeben. Die Methode ist nur anwendbar, wenn sich nicht der Punkt O als Resultat der Addition ergibt.
(defmethod add-points ((this elliptic-curve) (x1 residue-class) (y1 residue-class) (x2 residue-class) (y2 residue-class))
(not
(and
(= x1 x2)
(= y1 (- (new residue-class (get-ring y2) 0) y2))))
(let
((m (if
(= x1 x2)
(/ (+ (* (new residue-class (get-ring x1) 3) x1 x1) (. this a)) (+ y1 y1))
(/ (- y2 y1) (- x2 x1)))))
(let
((x3 (- (* m m) x1 x2)))
(let
((y3 (- (* (- x1 x3) m) y1)))
(make-point this x3 y3)))))
Die Instanzen der Klassen point, finite-point und infinite-point repräsentieren Punkte, entweder auf der Kurve oder den unendlich fernen Punkt. Der Initialisierer für Punkte prüft, ob die Koordinaten des Punkts zur Kurve passen.
(deftrait point ())
(defclass finite-point (point))
(defclass infinite-point (point))
(defmethod initialize ((this finite-point) (curve elliptic-curve) (x residue-class) (y residue-class))
(with-slots-read-only (a b) curve
(=
(* y y)
(+ (* x x x) (* a x) b)))
(progn
(.= this curve curve)
(.= this x x)
(.= this y y)
(freeze this))))
(defmethod initialize ((this infinite-point) (curve elliptic-curve))
t
(progn
(.= this curve curve)
(freeze this)))
Die Methode get-curve liefert die Kurve zum einem Punkt.
(defmethod get-curve ((this point))
t
(. this curve))
Die Methode same-curve? prüft, ob zwei Punkte zur selben Kurve gehören. Nur dann ist die Addition definiert.
(defmethod same-curve? ((point-1 point) (point-2 point))
t
(= (get-curve point-1) (get-curve point-2)))
Die Methode add addiert zwei Punkte.
(defmethod add ((point-1 infinite-point) (point-2 point))
(same-curve? point-1 point-2)
point-2)
(defmethod add ((point-1 point) (point-2 infinite-point))
(same-curve? point-1 point-2)
point-1)
(defmethod add ((point-1 finite-point) (point-2 finite-point))
(same-curve? point-1 point-2)
(let
((curve (get-curve point-1))
(x1 (. point-1 x))
(y1 (. point-1 y))
(x2 (. point-2 x))
(y2 (. point-2 y)))
(if
(or
(and (= x1 x2) (zero? y1) (zero? y2))
(and (= x1 x2) (not (= y1 y2))))
(get-infinite-point curve)
(add-points curve x1 y1 x2 y2))))
Quellen
http://tools.ietf.org/html/rfc6090
H. W. Lenstra Jr.
"Factoring integers with elliptic curves"
Annals of Mathematics 126 (1987)
Seite 652