Punct greșit pe curbă: împărțire cu / în loc de inversul modular
Pe o curbă eliptică modulo p, panta nu se calculează cu /, care dă un număr zecimal, ci înmulțind cu inversul modular al numitorului: s = (y2 - y1) * pow(x2 - x1, -1, p) % p. Cu /, coordonatele ies float și punctul nu mai e pe curbă.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Nu primești nicio eroare, sau primești una mai târziu (un TypeError la pow cu float, un hash diferit): punctul calculat are coordonate zecimale ca 14.5 și nu se află pe curbă. Formula adunării punctelor e aceeași ca în geometria de liceu, dar toate calculele se fac într-un corp finit, modulo p, unde nu există fracții.
În aritmetica modulară, „a împărți la d” înseamnă „a înmulți cu inversul lui d”, adică numărul d⁻¹ pentru care d * d⁻¹ % p == 1. În Python, pow(d, -1, p) îl calculează (din 3.8). (y2 - y1) / (x2 - x1) % p aplică modulo unui float, ceea ce nu are sens criptografic: rezultatul nu e nici măcar întreg, iar pentru numere de 256 de biți se pierde și precizia. Același lucru se aplică la dublarea punctului (3x² / 2y) și la semnăturile ECDSA (s = k⁻¹(z + r·d)).
De ce apare: cauzele frecvente
1Panta la adunarea a două puncte
s = (y2 - y1) / (x2 - x1) % ps = (y2 - y1) * pow(x2 - x1, -1, p) % pInversul modular înlocuiește împărțirea, iar rezultatul rămâne un întreg între 0 și p - 1.
2Panta la dublarea unui punct
s = 3 * x * x / (2 * y) % ps = 3 * x * x * pow(2 * y, -1, p) % pAceeași regulă: numitorul 2y se inversează modulo p.
3Semnătura ECDSA
s = (z + r * d) / k % ns = (z + r * d) * pow(k, -1, n) % nÎn ECDSA calculele se fac modulo ordinul n al curbei, tot cu invers modular.
Repară eroarea, direct în pagină
Funcția aduna de mai jos adună două puncte pe curba de jucărie y² = x³ + 7 modulo 17, dar calculează panta cu /, așa că rezultatul are coordonate zecimale și nu e pe curbă. Repară calculul pantei ca programul să afișeze punctul P + Q și Pe curbă: True.
p = 17
def pe_curba(P):
x, y = P
return (y * y - x ** 3 - 7) % p == 0
def aduna(P, Q):
(x1, y1), (x2, y2) = P, Q
s = (y2 - y1) / (x2 - x1) % p
x3 = (s * s - x1 - x2) % p
y3 = (s * (x1 - x3) - y1) % p
return (x3, y3)
P, Q = (1, 5), (3, 0)
print("P și Q pe curbă:", pe_curba(P), pe_curba(Q))
R = aduna(P, Q)
print("P + Q =", R)
print("Pe curbă:", pe_curba(R))P și Q pe curbă: True True P + Q = (15, 13) Pe curbă: True
Indiciu
Împărțirea modulo p înseamnă înmulțirea cu inversul modular.
Reparația
p = 17
def pe_curba(P):
x, y = P
return (y * y - x ** 3 - 7) % p == 0
def aduna(P, Q):
(x1, y1), (x2, y2) = P, Q
s = (y2 - y1) * pow(x2 - x1, -1, p) % p
x3 = (s * s - x1 - x2) % p
y3 = (s * (x1 - x3) - y1) % p
return (x3, y3)
P, Q = (1, 5), (3, 0)
print("P și Q pe curbă:", pe_curba(P), pe_curba(Q))
R = aduna(P, Q)
print("P + Q =", R)
print("Pe curbă:", pe_curba(R))De ce merge
Cu /, panta era -2.5, iar coordonatele rezultatului ieșeau numere zecimale care nu verifică ecuația curbei. pow(x2 - x1, -1, p) este inversul lui 2 modulo 17, adică 9, pentru că 2 * 9 = 18, care dă 1 modulo 17. Panta devine (-5) * 9 mod 17 = 6, iar punctul rezultat, (15, 13), este pe curbă.
Cum o eviți pe viitor
În tot codul de curbe eliptice, / nu are ce căuta: scrie o funcție inv(a, m) care întoarce pow(a, -1, m) și folosește-o la fiecare numitor. După fiecare operație cu puncte, verifică cu o funcție pe_curba(P) că rezultatul respectă ecuația modulo p. Exersează pe o curbă mică (de exemplu modulo 17), unde poți verifica rezultatele de mână.
Întrebări frecvente
De ce uneori rezultatul cu / iese corect?
Când numitorul divide exact numărătorul, împărțirea obișnuită dă un întreg care coincide cu cel modular. E o coincidență; în general rezultatele diferă.
Ce fac dacă x2 - x1 este 0?
Atunci punctele au același x: fie sunt egale (folosești formula de dublare), fie unul e opusul celuilalt, iar suma lor este punctul la infinit. pow(0, -1, p) aruncă base is not invertible.
Erori înrudite
ValueError: base is not invertible for the given modulus pow(x, -1, m) caută inversul modular al lui x, dar acesta nu există: x e 0 modulo m sau are un divizor comun cu m. În codul de curbe eliptice apare de obicei la dublarea unui punct (P + P) tratată ca adunare obișnuită, cu x2 - x1 = 0. Punct valid respins: verificarea curbei fără modulo p Ai verificat ecuația curbei cu y**2 == x**3 + 7, fără modulo p, așa că puncte valide par să nu fie pe curbă. Curbele din criptografie sunt definite peste numere modulo p: verifică (y*y - x**3 - 7) % p == 0. TypeError: pow() 3rd argument not allowed unless all arguments are integers Ai apelat pow(baza, exponent, modul) cu un float, de obicei o cheie sau un exponent calculat cu /. Puterea modulară merge doar cu întregi: folosește // sau calculează inversul cu pow(e, -1, phi). Învață Blockchain de la zero, cu exerciții la fiecare lecție
Curs Blockchain și criptomonede: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 15 lecții sunt gratuite.
