Programmierung und die ECDSA-Gleichung

Ich habe Punktaddition in ein C++-Programm implementiert, das ich geschrieben habe, aber ich sehe nicht, wie das richtig gemacht werden kann. Wenn ich das tue slope = (y1 - y2)/(x1 - x2), bekomme ich eine verdammte Dezimalzahl, die nicht die richtigen Punkte erzeugt, wenn sie auf die anderen Teile der Gleichung angewendet wird, da sie ihre Bruchqualitäten nicht beibehält. Hat jemand eine Idee, wie man das überwindet?

Point Addition wird durch die folgende Gleichung definiert:

slope = (y1 - y2) / (x1 - x2)

xsum = slope ^ 2 - (x1 + x2)

ysum = slope * (x1 - xsum) - y1

Wobei Privatadresse x02 jeweils mit x,y Koordinaten:

89565891926547004231252920425935692360644145829622209833684329913297188986597
12158399299693830322967808612713398636155367887041628176798871954788371653930

mit dem Punkt Zusatz der Privatadresse x01 mit x,y-Koordinaten jeweils:

55066263022277343669578718895168534326250603453777594175500187360389116729240
32670510020758816978083085130507043184471273380659243275938904335757337482424

Angewandt auf die obige Gleichung ergibt sich das Ergebnis der Privatadresse x03 mit den entsprechenden x-, y-Koordinaten:

112711660439710606056748659173929673102114977341539408544630613555209775888121
25583027980570883691656905877401976406448868254816295069919888960541586679410

http://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication

BEARBEITEN:

Ich habe dieses C++-Programm zusammengestellt und auf jede erdenkliche Weise modifiziert (%p herumbewegen, zu oft wiederholen, Gleichungen auflösen und dergleichen). Ich kann es nicht dazu bringen, die richtigen Ergebnisse zu erzielen. Hat jemand Lust, es auszuprobieren und zu sehen, was Sie finden können, bitte?

http://coliru.stacked-crooked.com/a/26f9ed24ed5a86ed

Sie sollten wahrscheinlich einen Hinweis auf die Beschreibung geben, die Sie gerade lesen, da die, die ich gesehen habe, nichts namens Steigung haben. Aber vielleicht soll die Division mit modularer Arithmetik erfolgen?
Wow, erste Antwort und es hat mein begrenztes Verständnis von C++ bereits herausgefordert. Wie würde ich es zu einem ... "Zeiger" machen?
Entschuldigung, ich meine nur eine URL zur Beschreibung des Algorithmus.
Sie verwenden ph1^2, was XOR in C++ ist, Sie sollten ph1*ph1 schreiben,
und Sie verwenden viel zu viele Klammern. und %p gilt nur für (gx1 + gx2), nicht für den gesamten Ausdruck
und Sie verwenden vorzeichenlose Ganzzahlen, ich denke, Sie brauchen vorzeichenbehaftete Ganzzahlen.
und das while (a>1) in deiner mul_inv sollte sein: while (b!=0)
In der unteren rechten Ecke der Website gibt es einen "Bearbeiten"-Button, den jeder benutzen kann, um es auszuprobieren (dann kompilieren und teilen Sie es, die Freigabe erzeugt eine neue URL, die Sie teilen können). coliru.stacked-crooked.com/a/7368ec065cd78b8c ist die neueste. Ich habe alle Ihre Vorschläge (viele Variationen davon) ohne Erfolg ausprobiert.
Wilem, tyvm, ich kann nicht einmal verstehen, warum eine meiner Variationen nicht funktioniert hat (da ich "weiß", dass ich das versucht habe). Vielleicht mache ich einen Fehler, wo meine Programme nicht in einer aktualisierten Form kompiliert werden oder so ... Würden Sie mir zufällig zeigen, wie Sie auch in diesem Programm die richtige y-Koordinate erhalten? ich verstehe es wirklich nicht; aber meins funktioniert nicht für den y-Wert.
Okay, ich habe es verstanden ... Ich verstehe nicht, warum ich y2 = (ph1 * gx1) - (ph1 * x2) - gy1 mit %p jeder Klammer anstelle von y2 = ph1 * (gx1 - x2) machen musste ) - y1 und dann y2 %= p.
Ihr ph1-Ergebnis hat irgendwie das falsche Vorzeichen, wenn Sie es durch 'p-ph1' ersetzen, kommen Sie zum richtigen Ergebnis. vielleicht stimmt mit deiner mul_inv noch was nicht?
Das scheint plötzlich möglich, ich habe gerade einige meiner Ergebnisse überprüft, das Programm spuckt die richtigen x,y-Koordinaten nur für ein paar Adressen aus. Es bekommt plötzlich die falsche y-Koordinate, was dann alle nachfolgenden Werte verzerrt. Ich werte es weiter aus
coliru.stacked-crooked.com/a/74648b16c2692525 Ergebniswerte von x sind bis 0x05 gültig, bei 0x06 sind sie falsch. Werte von y sind nur für 0x03 gültig und für keine anderen.

Antworten (1)

Die magische Phrase auf dieser Seite befindet sich in einem endlichen Feld . Hier ist der endliche Körper die ganzen Zahlen mod p, wobei p die Zahl 2 256 - 2 32 - 2 9 - 2 8 - 2 7 - 2 6 - 2 4 - 1 ist (siehe hier ). Die gesamte Arithmetik in Ihren Gleichungen ist also keine gewöhnliche Arithmetik mit ganzen Zahlen oder reellen Zahlen; es muss mod p getan werden. Siehe http://en.wikipedia.org/wiki/Modular_arithmetic . Für Addition, Subtraktion und Multiplikation können Sie ganz normale Ganzzahlarithmetik verwenden und am Ende den Rest mod p berechnen. Für die Division benötigen Sie so etwas wie den erweiterten euklidischen Algorithmus. Natürlich müssen Sie auch Arithmetik mit beliebiger Genauigkeit verwenden , wenn Sie dies nicht bereits tun, da Zahlen dieser Größe viel zu groß für Standard-C++-Typen wie long intund sind double.

Also gibt es im Grunde keine einzige kurze einfache Methode, um dies zu erreichen?
Nein, ich glaube nicht, dass es Abkürzungen gibt, die es wesentlich mehr vereinfachen als das, was Sie bereits gelesen haben. Insbesondere kommt man um den Einsatz der modularen Arithmetik nicht herum.
Programmierung und die ECDSA-Gleichung
AntwortenHierDatenschutz-Bestimmungen1y, 0v