Addition auf elliptischen Kurven
Haftungsausschluss: Dies wird dem reichen Thema der elliptischen Kurven nicht gerecht. Es ist sehr vereinfacht. Da elliptische Kurven in letzter Zeit im Zusammenhang mit der Verschlüsselung viel Medieninteresse fanden, wollte ich einen kleinen Einblick geben, wie das "Berechnen" auf einer elliptischen Kurve tatsächlich funktioniert.
Einführung
Elliptische Kurven sind Punktmengen (x,y)
in der Ebene der Form y^2 = x^3+Ax+B
. (Außerdem, 4A^3+27B^2 ≠ 0
um unangenehme Singularitäten zu vermeiden.) Sie können diese Kurven in jedem Feld berücksichtigen. Wenn Sie das Feld der reellen Zahlen verwenden, können die Kurven visualisiert werden und sie sehen folgendermaßen aus:
Das Besondere an diesen Kurven ist, dass sie eine eingebaute arithmetische Operation haben, die das Analogon der Addition ist. Sie können Punkte hinzufügen und subtrahieren. Diese Operation ist sowohl assoziativ als auch kommutativ (eine abelsche Gruppe).
Wie funktioniert die Addition?
Hinweis: Das Hinzufügen von Punkten auf elliptischen Kurven ist nicht intuitiv. Diese Art der Addition wird so definiert, wie sie ist, weil sie bestimmte schöne Eigenschaften hat. Es ist komisch, aber es funktioniert.
Da elliptische Kurven eine Gruppe bilden, gibt es eine additive Identität , die gleich 0 ist. Das Hinzufügen 0
zu einem beliebigen Punkt ändert also nichts am Ergebnis. Diese additive Identität ist der "Punkt" im Unendlichen. Alle Linien in der Ebene enthalten diesen Punkt im Unendlichen. Das Hinzufügen macht also keinen Unterschied.
Nehmen wir an, dass eine gegebene Linie die Kurve an drei Punkten schneidet 0
, und dass die Summe dieser drei Punkte ist 0
. Beachten Sie dies, und schauen Sie sich dieses Bild an.
Nun ist die natürliche Frage, was ist P+Q
? Na ja, wenn P+Q+R = 0
, dann P+Q = -R
(alternativ geschrieben als R'
). Wo liegt -R
? Es ist , wo R + (-R) = 0
, die auf der anderen Seite der x-Achse aus ist , R
so dass die Linie , die durch sie vertikal ist, nur sich schneidende R
, -R
, und 0
. Sie können dies im ersten Teil dieses Bildes sehen:
Eine andere Sache, die Sie in diesen Bildern sehen können, ist, dass die Summe eines Punktes mit sich selbst bedeutet, dass die Linie die Kurve tangiert.
So finden Sie Schnittpunkte von Linien und elliptischen Kurven
Im Fall von zwei verschiedenen Punkten
Im Allgemeinen gibt es genau eine Linie durch zwei Punkte P=(x0,y0), Q=(x1,y1)
. Vorausgesetzt, es ist nicht vertikal und die beiden Punkte sind verschieden, können wir es als schreiben y = m*x+q
. Wenn wir die Schnittpunkte mit der elliptischen Kurve finden wollen, können wir einfach schreiben
0 = x^3+Ax+B-y^2 = x^3+Ax+B-(m*x+q)^2
Das ist ein Polynom dritten Grades. Diese sind im Allgemeinen nicht so einfach zu lösen, aber wir kennen bereits zwei Nullen dieses Polynoms: Die zwei x
Koordinatenx0, x1
der beiden Punkte, die wir hinzufügen möchten!
Auf diese Weise bereinigen wir die linearen Faktoren (x-x0)
und (x-x1)
und erhalten einen dritten linearen Faktor, dessen Wurzel die x
Koordinate des Punktes ist R
. ( -R
Auch wegen der Symmetrie. Man beachte , dass , wenn R = (x2,y2)
dann -R = (x2,-y2)
. Die-
aus der Gruppe ist; es ist kein vektorielles Minus.)
Im Falle des Hinzufügens eines Punktes P
zu sich selbst
In diesem Fall müssen wir den Tangens der Kurve bei berechnen P=(x0,y0)
. Wir können direkt schreiben m
und q
in Bezug auf A,B,x0,y0
:
3*x0^2 + A
m = ------------
2*y0
-x0^3 + A*x0 + 2*B
q = --------------------
2*y0
Wir bekommen die Gleichung y = m*x+q
und können genauso vorgehen wie im obigen Absatz.
Ein vollständiger Fallbaum
Dies ist eine vollständige Liste, wie mit all diesen Fällen umgegangen wird:
Sei P,Q
Punkte auf der elliptischen Kurve (einschließlich des "Unendlich" -Punkts 0
)
- Wenn
P = 0
oderQ = 0
, dannP+Q = Q
oderP+Q = P
jeweils - Sonst
P ≠ 0
undQ ≠ 0
, also lassP = (x0,y0)
undQ = (x1,y1)
:- Wenn
P = -Q
(das bedeutetx0 = x1
undy0 = -y1
) dannP+Q = 0
- Sonst
P ≠ -Q
- Wenn
x0 = x1
dann haben wirP=Q
und berechnen wir den Tangens (siehe Abschnitt oben), um zu bekommenR
. DannP+Q = P+P = 2P = -R
- Sonst: Wir können eine Linie der Form
y = m*x+y
durch diese beiden Punkte konstruieren (siehe Abschnitt oben), um zu berechnenR
. DannP+Q=-R
- Wenn
- Wenn
Endliche Felder
Bei dieser Herausforderung werden nur Felder mit der Größe berücksichtigt, bei p
denen p
(und wegen einiger Details p ≠ 2, p ≠ 3
) die höchste Priorität vorliegt . Dies hat den Vorteil, dass Sie einfach rechnen können mod p
. Die Arithmetik in anderen Bereichen ist viel komplizierter.
Dies setzen wir in diesem Beispiel p = 5
und alle Gleichungen hier sind Kongruenzen mod 5
.
2+4 ≡ 6 ≡ 1
2-4 ≡ -2 ≡ 3
2*4 ≡ 8 ≡ 3
2/4 ≡ 2*4 ≡ 3 because 4*4 ≡ 16 ≡ 1, therefore 1/4 ≡ 4
Herausforderung
Wenn die Parameter A,B
einer elliptischen Kurve gegeben sind, geben eine Hauptfeldcharakteristik p
und zwei Punkte P,Q
auf der elliptischen Kurve ihre Summe zurück.
- Sie können davon ausgehen, dass die Parameter
A,B
tatsächlich eine elliptische Kurve beschreiben, das heißt, dass4A^3+27B^2 ≠ 0
. - Sie können davon ausgehen, dass
P,Q
es sich tatsächlich um Punkte auf der elliptischen Kurve oder dem0
-Punkt handelt. - Sie können davon ausgehen, dass dies
p ≠ 2,3
eine Primzahl ist.
Testfälle
Ich habe eine (nicht sehr elegante) Implementierung in MATLAB / Octave gemacht, die Sie für Ihre eigenen Testfälle verwenden können: ideone.com Ich hoffe, es ist richtig. Es hat zumindest ein paar Berechnungen reproduziert, die ich von Hand gemacht habe.
Beachten Sie die einfachen Testfälle, die für alle hier betrachteten Kurven funktionieren:
Null hinzufügen: P+0 = P
Umgekehrtes hinzufügen:(x,y) + (x,-y) = 0
Für p = 7, A = 0, B = 5
die beiden Punkte P = (3,2)
und Q = (6,2)
auf der elliptischen Kurve. Dann gilt folgendes:
2*Q = Q+Q = P
2*P = P+P = (5,2)
3*P = P+P+P = (5,2)+P = (6,5)
4*P = P+P+P+P = (5,2)+(5,2) = (6,5)+(5,2) = Q
Alle Punkte auf der elliptischen Kurve sind (3,2),(5,2),(6,2),(3,5),(5,5),(6,5),0
Denn p = 13, A = 3, B = 8
wir bekommen
(1,8)+(9,7) = (2,10)
(2,3)+(12,11) = (9,7)
2*(9,6) = (9,7)
3*(9,6) = 0
Für p = 17, A = 2, B = 2
und P=(5,1)
wir bekommen
2*P = (6,3)
3*P = (10,6)
4*P = (3,1)
5*P = (9,16)
6*P = (16,13)
7*P = (0,6)
8*P = (13,7)
9*P = (7,6)
10*P = (7,11)
Wenn Sie wirklich ehrgeizig sind, nehmen Sie
p = 1550031797834347859248576414813139942411
A = 1009296542191532464076260367525816293976
x0 = 1317953763239595888465524145589872695690
y0 = 434829348619031278460656303481105428081
x1 = 1247392211317907151303247721489640699240
y1 = 207534858442090452193999571026315995117
und versuchen, eine natürliche Zahl zu finden, n
so dass n*(x0,y0) = (x1,y1)
. Weitere Informationen hier.
Blinddarm
Zunächst ein großes Dankeschön an @ El'endiaStarman für die Überprüfung und Bearbeitung meines Entwurfs!
Warum elliptische Kurven?
Nun, es mag wie eine Art willkürliche Gleichung erscheinen, aber es ist nicht so, es ist ganz allgemein: Im Allgemeinen betrachten wir diese geometrischen "Formen" in der Projektionsebene (das ist, woher die "Unendlichkeit" kommt. Dort betrachten wir alle als homogen Polynome dritten Grades (Die Polynome niedrigeren oder höheren Grades wären zu schwierig oder nur trivial zu untersuchen.) Nachdem einige Einschränkungen angewendet wurden, um die gewünschten guten Eigenschaften zu erhalten, und nachdem diese Polynome dehomogenisiert wurden (Projektion in eine von drei affinen Ebenen) ) Am Ende haben wir Gleichungen wiey^2+a*x*y+b*y = x^3+c*x^2+d*x+e
Dies ist eine elliptische Kurve in der langen Weierstraßform. Dies sind im Grunde die gleichen Kurven, die wir betrachtet haben, aber nur etwas schief. Mit einer linearen Koordinatentransformation können Sie leicht eine kurze Weierstras-Gleichung daraus erstellen. B. die noch alle interessanten Eigenschaften enthalten.
Warum haben wir ausgeschlossen p=2,3
?
Dies hat damit zu tun, dass wir für die kurze Weierstrass-Form die Einschränkung benötigen 4A^3+27B^2 ≠ 0
, um Singularitäten zu vermeiden (dazu weiter unten mehr). In einem Feld des Merkmals 2 haben wir 4 = 0
und in einem Feld des Merkmals 3 haben wir 27 = 0
, macht es dies unmöglich, Kurven in kurzer Weierstrass-Form für diese Arten von Feldern zu haben.
Was sind Singularitäten?
Wenn die Gleichung 4A^3+27B^2=0
gilt, haben wir folgende Singularitäten: Wie Sie an diesen Punkten sehen, können Sie keine Ableitung und daher keine Tangente finden, die die Operation "tötet". Sie könnten sich die Gleichungen y^2 = x^3
oder anschaueny^2 = x^3-3*x+2
Warum heißen sie eigentlich elliptische Kurven ?
Der Grund ist, dass Gleichungen dieser Form in elliptischen Integralen auftauchen, z. B. welche, die Sie erhalten, wenn Sie z. B. die Bogenlänge einer Ellipse berechnen möchten. Eine kurze Diashow über die Herkunft des Namens.
Was haben sie mit Kryptographie zu tun?
Es gibt Möglichkeiten, nP = P+P+...+P
sehr effizient zu rechnen . Dies kann beispielsweise im Diffie Hellman-Schlüsselaustausch verwendet werden . Die modulare Arithmetik kann durch das Hinzufügen von Torsionsuntergruppen ersetzt werden. Dies sind nur die Punkte auf der Kurve, die eine endliche Ordnung haben. (Das bedeutet, dass mP = 0
für einige m
, die im Grunde nur rechnen mod m
).
quelle
y^2 = x^3 + x
eine gültige elliptische Kurve und(0,0) ≠ 0
ein Punkt auf der Kurve ist!)B = 0
und mich gefragt habe, wie0
es funktionieren würde ... und dann habe ich es vergessen. Ich glaube, ich nahm an, dass ichB
letzte Nacht irgendwann nicht mehr 0 sein konnte. Haben Sie Vorschläge, wie der Input dafür aussehen soll? Vielleicht wennB = 0
, dann definieren0 = (-1, -1)
? Ich bin froh, meinen Code anzupassen, um damit[0]
(nur eine Koordinate) der Unendlichkeitspunkt ist oder etwas Ähnliches!nP
? Könnten Sie mich auf Ressourcen zu diesem Thema hinweisen, um die Gedanken zum Fließen zu bringen? Es fällt mir schwer, etwas zum googeln zu finden. Vielen Dank!Python 3,
193 -191 BytesEine Lösung, die auf der Pyth-Antwort von Rhyzomatic und ihrer Python-Logik basiert. Bestimmtes. Ich mochte, wie sie die dritte Wurzel eines monischen kubischen Polynoms fanden,
x^3 + bx^2 + cx + d
wenn Sie zwei Wurzeln habenx_1
und dasx_2
notierteb == x_1 + x_2 + x_3
und dementsprechend subtrahierte. Ich habe vor, eine Erklärung hinzuzufügen, diese Golf zu spielen und sie vielleicht in Ruby umzuwandeln, falls sich herausstellt, dass Ruby kürzer ist.Ungolfing:
quelle