Puncte:1

Crypto

Cum se calculează ordinea secp256k1?

Andy

21.12.2022, 21:16

Curba eliptică secp256k1 este definit ca $y^2 = x^3 + 7$. Primul pentru câmp este setat la:

p = 115792089237316195423570985008687907853269984665640564039457584007908834671663

Deci, acum, ar trebui să fie capabil să calculeze ordinea utilizând algoritmul lui Schoof. Există o implementare Python furnizată aici: https://github.com/pdinges/python-schoof

Cu toate acestea, pare să consume prea mult timp pentru a calcula ordinea numerelor prime mari. În plus, implementarea pare să nu fie capabilă să o calculeze pentru un prim atât de mare.

root@78774381cc80:/home/python-schoof# python3 reduced_computation_schoof.py 17 0 7
Numărarea punctelor lui y^2 = x^3 + 0x + 7 peste GF<17>: 18
root@78774381cc80:/home/python-schoof# python3 reduced_computation_schoof.py 1157920892373161954235709850086879078532699846656404056704089237316195423570985008687907853269984665640405670404056704704670
Numărarea punctelor de y^2 = x^3 + 0x + 7 peste GF<11579208923731619542357098500868790785326998466564056403945758400790883467: ultimul apel: Traceback (cele mai recente)
  Fișierul „reduced_computation_schoof.py”, linia 268, în <modul>
    runner.run()
  Fișier „/home/python-schoof/support/running.py”, linia 498, în curs
    rezultat = self.__algorithm( *element, output=self.__output)
  Fișierul „reduced_computation_schoof.py”, linia 258, în algoritmul reduced_computation_schoof_algorithm
    ordine = p + 1 - frobenius_trace( Curba Eliptică( Câmp Finit(p), A, B ) )
  Fișier „reduced_computation_schoof.py”, rândul 55, în frobenius_trace
    len(interval_căutare),
OverflowError: Python int prea mare pentru a fi convertit în C ssiize_t

Știe cineva că a fost calculat și cum se reproduce? Există o implementare mai bună a algoritmului Schoof pentru numere atât de mari?

407

1 + 3

curbe-eliptice

câmp finit

secp256k1

fgrieu

22.12.2022, 10:31

Notă: Ordinea $n$ a lui `secp256k1` este binecunoscută și este ușor să o _verificați: alegeți orice punct $T$ (altul decât $\mathcal O$ neutru) și bifați $n\,T=\mathcal O$, care demonstrează ordinea lui $T$ împarte $n$. Acum verificați că $n$ este prim și aproape de $p$ (în termen de 30% va fi suficient; sau [Hasses' bound](https://en.wikipedia.org/wiki/Hasse%27s_theorem_on_elliptic_curves)). Independent: avem un motiv strâns pe melodia „Solicitările de literatură, software sau recomandări similare sunt off-topic”, așa că întrebarea este în apele fierbinți; vom vedea dacă interesul întrebării depășește acea interdicție generală.

Răspunde

Andy

22.12.2022, 14:43

@fgrieu care este $\mathcal{O}$ neutru al lui `secp256k1`?

Răspunde

fgrieu

23.12.2022, 06:33

Neutru $\mathcal O$ este elementul neutru al grupului de puncte ale curbei. În mod echivalent, pentru toate punctele $T$ ale curbei, $T+\mathcal O=T=\mathcal O+T$. Se mai numește și punctul de la infinit și se notează $\infty$. Nu are coordonatele $x$, $y$ care să satisfacă ecuația curbei $y^2\equiv x^3+7\pmod p$.

Răspunde

Puncte:2

Crypto

djao

22.12.2022, 05:02

PARI include (printre multe alte lucruri) o implementare a algoritmului lui Schoof (mai precis algoritmul Schoof-Elkies-Atkin).

? p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
%1 = 115792089237316195423570985008687907853269984665640564039457584007908834671663
? ellcard(ellinit([0,7], p))
%2 = 115792089237316195423570985008687907852837564279074904382605163141518161494337

Este open source, așa că puteți privi cu ușurință în interior.

Dacă nu doriți să instalați PARI, CoCalc vă permite să rulați PARI (sau Sage) într-un browser. Doar porniți un nou proiect și în interiorul acestuia un nou terminal Linux, introduceți „gp” și sunteți oprit și rulați în PARI.

Alternativ, puteți face calculul direct în Salvie (pe care îl puteți rula și prin CoCalc: New â Sage worksheet), dar acest lucru nu vă oferă nicio implementare nouă, deoarece Sage doar apelează PARI pentru această funcție:

salvie: p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
sage: EllipticCurve(GF(p), [0,7]).order()
115792089237316195423570985008687907852837564279074904382605163141518161494337

Pentru documentare în PARI:

? ?ellcard
ellcard(E,{p}): dată o curbă eliptică E definită pe un câmp finit Fq, 
returnează ordinea grupului E(Fq); pentru alte domenii de definiție K, p trebuie 
definiți un câmp finit de reziduuri, (p prim pentru K = Qp sau Q; p un ideal maxim pentru 
K un câmp numeric), returnează ordinea reducerii (nesingulare) a lui E.

Pentru documentare în Sage:

salvie: E = Curba eliptică(GF(p), [0,7])
sage: E.comanda?
sage: E.comanda??

0 + 0