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

Același nonce k la două semnături ECDSA (r identic)

Pe scurt

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

Greșit
PYTHON
def semneaza(d, z):
    k = 12345
    r = inmulteste(k, G)[0] % N
    return r, pow(k, -1, N) * (z + r * d) % N
Corect
PYTHON
def 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) % N

k 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

Greșit
PYTHON
import random
random.seed(1)
k = random.randrange(1, N)
Corect
PYTHON
import hmac, hashlib
k = int.from_bytes(hmac.new(d.to_bytes(32, "big"), z.to_bytes(32, "big"), hashlib.sha256).digest(), "big") % N

random 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ă tu

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.

Codul care dă eroarea
PYTHON
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))
După reparație, programul afișează
r1: 0x66bc33e657590cfa
r2: 0x9fe5a78c67e3bfa7
r repetat: False
Semnături valide: True
Indiciu

k trebuie să se schimbe când se schimbă mesajul.

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

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