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.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Nu primești nicio eroare, doar un rezultat greșit: cheia publică sau punctul G al curbei sunt declarate „nu sunt pe curbă”. Cauza este că în criptografie curba y² = x³ + 7 (secp256k1, și curba de jucărie din curs) nu e cea din geometria de liceu. Coordonatele sunt numere modulo p, iar ecuația trebuie să fie adevărată tot modulo p. De exemplu, pe curba mod 17, punctul (15, 13) e valid: 13² = 169, 15³ + 7 = 3382, iar amândouă dau restul 16 la împărțirea cu 17. Fără % p, compari 169 cu 3382 și obții False.
Verificarea punctelor e importantă: cine acceptă de la alții puncte nevalidate poate fi atacat (invalid curve attack). Deci verificarea trebuie să existe, dar să fie corectă.
De ce apare: cauzele frecvente
1Ecuația fără modulo
def pe_curba(x, y):
return y ** 2 == x ** 3 + 7def pe_curba(x, y, p=17):
return (y * y - x ** 3 - 7) % p == 0Ambele părți trebuie comparate modulo p, adică restul diferenței trebuie să fie 0.
2Modulo aplicat doar pe o parte
def pe_curba(x, y, p=17):
return y ** 2 == (x ** 3 + 7) % pdef pe_curba(x, y, p=17):
return y ** 2 % p == (x ** 3 + 7) % py ** 2 poate fi mai mare decât p, deci trebuie redus și el.
Repară eroarea, direct în pagină
Funcția pe_curba de mai jos verifică dacă un punct e pe curba y² = x³ + 7 mod 17, dar respinge și punctele valide, inclusiv G = (15, 13). Repară-o ca programul să afișeze True pentru primele trei puncte și False pentru (3, 5), apoi Puncte valide: 3.
p = 17
def pe_curba(x, y):
return y ** 2 == x ** 3 + 7
puncte = [(15, 13), (2, 10), (8, 3), (3, 5)]
valide = 0
for x, y in puncte:
ok = pe_curba(x, y)
valide += ok
print((x, y), ok)
print("Puncte valide:", valide)(15, 13) True (2, 10) True (8, 3) True (3, 5) False Puncte valide: 3
Indiciu
Ecuația trebuie să fie adevărată modulo p.
Reparația
p = 17
def pe_curba(x, y):
return (y * y - x ** 3 - 7) % p == 0
puncte = [(15, 13), (2, 10), (8, 3), (3, 5)]
valide = 0
for x, y in puncte:
ok = pe_curba(x, y)
valide += ok
print((x, y), ok)
print("Puncte valide:", valide)De ce merge
Pe curba mod 17, punctul (15, 13) e valid pentru că 169 și 3382 dau același rest la împărțirea cu 17. Comparația fără modulo vedea doar că 169 e diferit de 3382. Cu (y * y - x ** 3 - 7) % p == 0 verifici că diferența e multiplu de 17, adică ecuația e adevărată modulo p.
Cum o eviți pe viitor
În orice cod de curbe eliptice, fiecare rezultat intermediar se reduce modulo p. Scrie o funcție pe_curba și testeaz-o pe punctul generator cunoscut (G al curbei): dacă G nu trece, verificarea e greșită. Pentru exponenți mari folosește pow(x, 3, p), care reduce la fiecare pas.
Întrebări frecvente
De ce curba e definită modulo p?
Ca să lucrăm doar cu numere întregi, într-o mulțime finită. Așa calculele sunt exacte, fără zecimale, iar problema logaritmului discret devine grea.
La secp256k1 merge la fel?
Da, doar că p este 2256 - 232 - 977. Formula e aceeași: (y*y - x**3 - 7) % p == 0.
Erori înrudite
TypeError: cannot unpack non-iterable NoneType object Ai despachetat x, y = ... dintr-o valoare None. Pe curbele eliptice, de obicei funcția de adunare a întors None pentru punctul de la infinit (P + (-P)). Verifică if R is None înainte să despachetezi, sau adaugă return în funcție. 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. cryptography.exceptions.InvalidSignature Verificarea semnăturii a eșuat: mesajul verificat nu e exact același cu cel semnat (alt text, altă ordine a câmpurilor, alte spații) sau folosești altă cheie publică. Serializează mesajul identic la semnare și la verificare. Î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.
