Wie leiten Sie die Lambda- und Beta-Werte für den Endomorphismus auf der secp256k1-Kurve ab?

Einen kleinen Hintergrund dazu finden Sie in diesem Bitcointalk-Beitrag des verstorbenen Hal Finney.

Beta und Lambda sind die Werte auf der secp256k1-Kurve, wobei:

λ^3 (mod N) = 1

β^3 (mod P) = 1

Wie hier zu sehen , sind N und P in Hex:

N = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

P = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

Die tatsächlichen Werte von Lambda und Beta sind leicht nachprüfbar und lauten:

λ = 5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72

β = 7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee

Die Frage für mich ist, wie kommst du darauf? Kann mir jemand Schritt für Schritt zeigen, wie man diese Werte herausfinden kann?

Auch im Cryptography Stack Exchange gepostet

Möglicherweise erhalten Sie eine Antwort eher auf der Cryptography SE-Website.
Hal Finney sagt, er habe Hinweise zur Berechnung auf den Seiten 125-129 des Guide to Elliptic Curve Cryptography von Hankerson, Menezes und Vanstone gefunden. Er fand ein PDF auf einer russischen Website.
Ich habe dieses Buch und diese bestimmten Seiten tatsächlich mehrmals gelesen und konnte es nicht herausfinden.

Antworten (3)

Mit ein bisschen Reverse-Engineering konnte ich, glaube ich, sehen, wie Hal zu diesen Ergebnissen kam.

Erstens ist es ein ziemlich bekanntes Ergebnis von Fermats kleinem Satz, dass wenn peine Primzahl und gein Generator für das Feld Z/pZist, dann:

g ^ (p - 1) = 1

Beachten Sie, dass Sie diesen abstrakten Generator nicht gmit dem Generator für die Gruppe secp256k1 verwechseln G. Nun, angesichts der obigen Gleichung ist es kein großer Sprung, das zu sehen:

(g ^ ((p - 1)/3)^3 = g ^ (p - 1) = 1

So können wir λund finden, βindem wir zuerst Generatoren für Z/NZund finden Z/PZ( Nund Psind die in der ursprünglichen Frage angegebenen Parameter) und sie dann jeweils mit (N-1)/3und (P-1)/3potenzieren. Sie können überprüfen, ob sowohl N-1als P-1auch durch 3 teilbar sind.

Der Generator, für den Hal anscheinend verwendet hat, λist 3 und für β2. Ich bin mir nicht sicher, warum er diese ausgewählt hat, es gibt viele andere gute Generatoren zur Auswahl. Es war wahrscheinlich auf Trial-and-Error-Basis.

Mit dem Sage-Mathematik-Notebook konnte ich die gleichen Werte für λund erzeugen β.

Geben Sie hier die Bildbeschreibung ein

Lambda und Beta sind nicht-triviale Kubikwurzeln von 1 in den jeweiligen Feldern (mod n für Lambda, mod p für Beta). Es gibt nur zwei solcher Werte. Ausgehend von einem Generator g und potenziert (n-1)/3 bzw. (p-1)/3 sie zu finden, ist nur eine Möglichkeit, dies zu tun. Und egal mit welchem ​​g man beginnt, man findet immer eine der beiden gültigen Lösungen, oder 1 (wenn das g nicht ein Generator, sondern ein Würfel war).

Zitieren von cryptography.stackexchange.com :

Da N und P Primzahlen sind, besteht eine naheliegende Möglichkeit darin, einen zufälligen Wert g aus [1,N−1] auszuwählen und g^((N−1)/3) mod N zu berechnen; unter der Annahme, dass N≡1(mod 3), ist dieser resultierende Wert entweder 1, der angezeigte Wert von λ, oder N−λ−1 (mit jeweils gleichen Wahrscheinlichkeiten). Wenn N≢1(mod 3), dann ist die einzige modulare Kubikwurzel von 1 1.

Und um β zu berechnen, machen Sie dasselbe mit P.

Der Grund dafür ist der kleine Satz von Fermat, der besagt:

g^(N-1) ≡ 1 (mod N)

was impliziert

(g^((N-1)/3))^3 ≡ 1 (mod N)

was impliziert

g^((N-1)/3) ist unser Potential λ. Wenn es nicht 1 ist, funktioniert es für die Zwecke des Endomorphismus.

Ich bin dabei, im Grunde dasselbe aufzuschreiben, aber mit einigen konkreteren Zahlen. :/

Python-Code zum Abrufen von Beta- und Lambda-Werten für p und n der secp256k1-Kurve

Betaversion von p erhalten

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
print "beta of p = 0x%x" % pow(2, (p-1)/3, p)

Beta von p = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee

Lambda von n bekommen

n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
print "lambda of n = 0x%x" % pow(3, (n-1)/3 , n)

Lambda von n = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72

Mehr Info

Ich experimentierte weiter damit, indem ich Beta und Lambda für p und n erhielt und entdeckte, dass alle generierten Ergebnisse nützlich sind, um die identischen Werte für x oder y in der Gleichung y ^ 2 = x ^ 3 + 7 mod p zu finden

#beta and lambda for p
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
betaOfP = pow(2, (p-1)/3, p)
lambdaOfP = pow(3, (p-1)/3, p)
print "betaOfP \t= 0x%x " % betaOfP 
print "lambdaOfP\t= 0x%x " % lambdaOfP 
print

#beta and lambda for n
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
betaOfN = pow(2, (n-1)/3 , n)
lambdaOfN = pow(3, (n-1)/3 , n)
print "betaOfN \t= 0x%x" % betaOfN
print "lambdaOfN\t= 0x%x" % lambdaOfN

betaOfP = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee lambdaOfP = 0x851695d49a83f8ef919bb86153cbcb16630fb68aed0a766a3ec68

betaOfN = 0xac9c52b33fa3cf1f5ad9e3fd77ed9ba4a880b9fc8ec739c2e0cfc810b51283ce

Wie leiten Sie die Lambda- und Beta-Werte für den Endomorphismus auf der secp256k1-Kurve ab?
AntwortenHierDatenschutz-Bestimmungen1y, 1v