...
Eroare Blockchain · Chei, semnături și aritmetică modulară

Punct greșit pe curbă: împărțire cu / în loc de inversul modular

Pe scurt

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

Greșit
PYTHON
s = (y2 - y1) / (x2 - x1) % p
Corect
PYTHON
s = (y2 - y1) * pow(x2 - x1, -1, p) % p

Inversul modular înlocuiește împărțirea, iar rezultatul rămâne un întreg între 0 și p - 1.

2Panta la dublarea unui punct

Greșit
PYTHON
s = 3 * x * x / (2 * y) % p
Corect
PYTHON
s = 3 * x * x * pow(2 * y, -1, p) % p

Aceeași regulă: numitorul 2y se inversează modulo p.

3Semnătura ECDSA

Greșit
PYTHON
s = (z + r * d) / k % n
Corect
PYTHON
s = (z + r * d) * pow(k, -1, n) % n

În ECDSA calculele se fac modulo ordinul n al curbei, tot cu invers modular.

Repară tu

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.

Codul care dă eroarea
PYTHON
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))
După reparație, programul afișează
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.

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

← Toate erorile Blockchain

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Î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.