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

ValueError: base is not invertible for the given modulus

Pe scurt

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.

Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la

Ce înseamnă

pow(x, -1, m) calculează inversul modular: numărul y pentru care x * y % m == 1. El există doar dacă x și m nu au divizori comuni (în special, x nu e multiplu de m). Mesajul spune că pentru valorile tale inversul nu există.

În codul unei curbe eliptice, panta dreptei dintre două puncte este (y2 - y1) / (x2 - x1), calculată cu inversul lui x2 - x1. Când aduni un punct cu el însuși (dublare, la 2 · G), x2 - x1 = 0, iar 0 nu are invers: ai nevoie de formula tangentei, cu 2 * y1 la numitor. Același lucru la P + (-P), unde rezultatul e punctul la infinit. La ECDSA, eroarea apare și când s sau k e 0 modulo n, sau când folosești din greșeală un modul care nu e prim.

De ce apare: cauzele frecvente

1Dublarea punctului tratată ca adunare

Greșit
PYTHON
def aduna(P, Q):
    x1, y1 = P
    x2, y2 = Q
    m = (y2 - y1) * pow(x2 - x1, -1, p) % p
    ...
Corect
PYTHON
def aduna(P, Q):
    x1, y1 = P
    x2, y2 = Q
    if P == Q:
        m = 3 * x1 * x1 * pow(2 * y1, -1, p) % p
    else:
        m = (y2 - y1) * pow(x2 - x1, -1, p) % p
    ...

La P == Q dreapta devine tangenta, cu altă formulă pentru pantă.

2Inversul calculat cu modulul greșit

Greșit
PYTHON
w = pow(s, -1, p)   # p = modulul curbei
Corect
PYTHON
w = pow(s, -1, n)   # n = ordinul lui G

În ECDSA, s, k și r se lucrează modulo n, ordinul grupului, nu modulo p.

3Exponentul RSA nu e prim cu phi

Greșit
PYTHON
phi = 3120
e = 15
d = pow(e, -1, phi)
Corect
PYTHON
phi = 3120
e = 17
d = pow(e, -1, phi)

15 are divizori comuni cu 3120 (3 și 5), deci nu are invers; 17 nu are.

Repară tu

Repară eroarea, direct în pagină

Codul de mai jos calculează multiplii punctului G pe curba mică a cursului, y² = x³ + 7 (mod 43), dar dă ValueError: base is not invertible for the given modulus chiar la 2 · G. Repară funcția aduna ca să trateze dublarea cu formula tangentei și afișează punctele 1·G până la 4·G.

Codul care dă eroarea
PYTHON
p = 43
G = (2, 12)

def aduna(P, Q):
    if P is None:
        return Q
    if Q is None:
        return P
    x1, y1 = P
    x2, y2 = Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return None
    m = (y2 - y1) * pow(x2 - x1, -1, p) % p
    x3 = (m * m - x1 - x2) % p
    y3 = (m * (x1 - x3) - y1) % p
    return (x3, y3)

P = G
print("1·G =", P)
for k in range(2, 5):
    P = aduna(P, G)
    print(f"{k}·G =", P)
După reparație, programul afișează
1·G = (2, 12)
2·G = (7, 7)
3·G = (35, 21)
4·G = (21, 18)
Indiciu

Când P == Q, panta este 3·x1² / (2·y1) modulo p.

Cum o eviți pe viitor

În funcția de adunare pe curbă tratează explicit cele trei cazuri: unul dintre puncte e la infinit (None), P + (-P) (rezultatul e infinitul) și P == Q (tangenta). Ține separat p (modulul coordonatelor) și n (ordinul lui G), cu nume clare. Testează cu inmulteste(2, G) și inmulteste(n, G), care trebuie să dea un punct valid și, respectiv, infinitul.

Întrebări frecvente

De ce pow(x, -1, m) și nu 1 / x?

Pentru că pe curbă lucrezi cu numere întregi modulo p, nu cu fracții. 1 / x dă un float, iar inversul modular e întregul y cu x * y % p == 1. pow cu exponent -1 îl calculează direct (din Python 3.8).

De ce ECDSA cere un nonce k nenul și secret?

Dacă k e 0, semnătura nu se poate calcula. Dacă k e cunoscut sau refolosit, cheia privată se poate afla din semnături. De aceea k se derivă determinist cu RFC 6979.

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.