Același nonce k la două semnături ECDSA (r identic)
Dacă semnezi două mesaje diferite cu același k, ambele semnături au același r, iar oricine le vede poate calcula cheia ta privată. k trebuie să fie diferit și secret la fiecare semnătură: în practică se derivă din cheie și mesaj (RFC 6979).
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
O semnătură ECDSA are două numere, r și s. r vine din punctul k·G, unde k e un număr ales la fiecare semnătură (nonce-ul semnăturii). Dacă același k e folosit de două ori, r iese identic, iar din cele două ecuații pentru s se pot scoate k și apoi cheia privată d, cu o simplă împărțire modulo n. Codul nu dă nicio eroare și semnăturile se verifică perfect: problema se vede doar dacă știi să cauți r repetat.
Cazuri reale: consola PlayStation 3 (cheia Sony recuperată în 2010) și portofele Bitcoin pe Android în 2013, din cauza unui generator aleator defect. Soluția modernă este RFC 6979: k se calculează determinist dintr-un HMAC al cheii private și al hash-ului mesajului, deci e diferit pentru fiecare mesaj și nu depinde de un generator aleator.
De ce apare: cauzele frecvente
1k fix în cod
def semneaza(d, z):
k = 12345
r = inmulteste(k, G)[0] % N
return r, pow(k, -1, N) * (z + r * d) % Ndef semneaza(d, z):
k = int(hashlib.sha256(d.to_bytes(32, "big") + z.to_bytes(32, "big")).hexdigest(), 16) % N
r = inmulteste(k, G)[0] % N
return r, pow(k, -1, N) * (z + r * d) % Nk depinde acum de cheie și de mesaj, deci e diferit pentru fiecare mesaj (o versiune simplificată a ideii din RFC 6979).
2Generator aleator cu seed fix
import random
random.seed(1)
k = random.randrange(1, N)import hmac, hashlib
k = int.from_bytes(hmac.new(d.to_bytes(32, "big"), z.to_bytes(32, "big"), hashlib.sha256).digest(), "big") % Nrandom cu seed dă aceeași valoare la fiecare rulare și nu e criptografic. Un k derivat cu HMAC din cheie și mesaj nu se repetă pentru mesaje diferite.
Repară eroarea, direct în pagină
Funcția semneaza de mai jos folosește mereu același k, așa că cele două semnături au același r și programul afișează r repetat: True. Repară-o ca k să fie derivat din cheia privată și din hash-ul mesajului: int(hashlib.sha256(d.to_bytes(32, "big") + z.to_bytes(32, "big")).hexdigest(), 16) % N. Programul trebuie să afișeze r repetat: False și Semnături valide: True.
import hashlib
P = 2**256 - 2**32 - 977
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)
def aduna(A, B):
if A is None:
return B
if B is None:
return A
if A[0] == B[0] and (A[1] + B[1]) % P == 0:
return None
if A == B:
m = 3 * A[0] * A[0] * pow(2 * A[1], -1, P) % P
else:
m = (B[1] - A[1]) * pow(B[0] - A[0], -1, P) % P
x = (m * m - A[0] - B[0]) % P
return (x, (m * (A[0] - x) - A[1]) % P)
def inmulteste(k, punct):
rezultat = None
while k:
if k & 1:
rezultat = aduna(rezultat, punct)
punct = aduna(punct, punct)
k >>= 1
return rezultat
def semneaza(d, mesaj):
z = int(hashlib.sha256(mesaj).hexdigest(), 16) % N
k = 12345
r = inmulteste(k, G)[0] % N
s = pow(k, -1, N) * (z + r * d) % N
return r, s
def verifica(Q, mesaj, r, s):
z = int(hashlib.sha256(mesaj).hexdigest(), 16) % N
w = pow(s, -1, N)
X = aduna(inmulteste(z * w % N, G), inmulteste(r * w % N, Q))
return X is not None and X[0] % N == r
d = 0x1E99423A4ED27608A15A2616A2B0E9E52CED330AC530EDCC32C8FFC6A526AEDD
Q = inmulteste(d, G)
r1, s1 = semneaza(d, b"Ana->Bogdan:5")
r2, s2 = semneaza(d, b"Ana->Carmen:7")
print("r1:", hex(r1)[:18])
print("r2:", hex(r2)[:18])
print("r repetat:", r1 == r2)
print("Semnături valide:", verifica(Q, b"Ana->Bogdan:5", r1, s1) and verifica(Q, b"Ana->Carmen:7", r2, s2))r1: 0x66bc33e657590cfa r2: 0x9fe5a78c67e3bfa7 r repetat: False Semnături valide: True
Indiciu
k trebuie să se schimbe când se schimbă mesajul.
Reparația
import hashlib
P = 2**256 - 2**32 - 977
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)
def aduna(A, B):
if A is None:
return B
if B is None:
return A
if A[0] == B[0] and (A[1] + B[1]) % P == 0:
return None
if A == B:
m = 3 * A[0] * A[0] * pow(2 * A[1], -1, P) % P
else:
m = (B[1] - A[1]) * pow(B[0] - A[0], -1, P) % P
x = (m * m - A[0] - B[0]) % P
return (x, (m * (A[0] - x) - A[1]) % P)
def inmulteste(k, punct):
rezultat = None
while k:
if k & 1:
rezultat = aduna(rezultat, punct)
punct = aduna(punct, punct)
k >>= 1
return rezultat
def semneaza(d, mesaj):
z = int(hashlib.sha256(mesaj).hexdigest(), 16) % N
k = int(hashlib.sha256(d.to_bytes(32, "big") + z.to_bytes(32, "big")).hexdigest(), 16) % N
r = inmulteste(k, G)[0] % N
s = pow(k, -1, N) * (z + r * d) % N
return r, s
def verifica(Q, mesaj, r, s):
z = int(hashlib.sha256(mesaj).hexdigest(), 16) % N
w = pow(s, -1, N)
X = aduna(inmulteste(z * w % N, G), inmulteste(r * w % N, Q))
return X is not None and X[0] % N == r
d = 0x1E99423A4ED27608A15A2616A2B0E9E52CED330AC530EDCC32C8FFC6A526AEDD
Q = inmulteste(d, G)
r1, s1 = semneaza(d, b"Ana->Bogdan:5")
r2, s2 = semneaza(d, b"Ana->Carmen:7")
print("r1:", hex(r1)[:18])
print("r2:", hex(r2)[:18])
print("r repetat:", r1 == r2)
print("Semnături valide:", verifica(Q, b"Ana->Bogdan:5", r1, s1) and verifica(Q, b"Ana->Carmen:7", r2, s2))De ce merge
r este coordonata x a punctului k·G, deci același k dă același r la orice mesaj, iar din două semnături cu același r cheia privată se poate calcula. Derivat din d și z, k e diferit pentru mesaje diferite, dar același pentru același mesaj, fără generator aleator. Semnăturile se verifică în continuare cu cheia publică Q.
Cum o eviți pe viitor
Nu scrie singur cod de semnare pentru bani reali: folosește biblioteci care implementează RFC 6979 (de exemplu cele din Bitcoin Core sau coincurve, eth-keys). În codul de învățare, derivă k din cheie și mesaj și verifică în teste că două mesaje diferite dau r diferit. Când analizezi semnături, un r repetat la aceeași adresă e semnal de alarmă.
Întrebări frecvente
De ce nu e suficient ca k să fie secret?
Trebuie să fie și unic. Chiar dacă nimeni nu știe k, două semnături cu același k dau două ecuații din care k se poate calcula, iar apoi cheia privată.
Cum arată calculul cheii din două semnături?
k = (z1 - z2) / (s1 - s2) mod n, apoi d = (s1·k - z1) / r mod n. Exercițiul 40 din setul de exerciții îl face pas cu pas pe numere mici.
Erori înrudite
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. 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. 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. Î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.
