ecdsa-k-reuse-key-recovery
The attack exploits that two ECDSA signatures using the same nonce k satisfy a linear relation. With s_i = k⁻¹·(z_i + r·d) mod n:
s1 − s2 = k⁻¹·(z1 − z2) mod n → k = (z1 − z2)·(s1 − s2)⁻¹ mod n
d = (s1·k − z1)·r⁻¹ mod n
Everything is implemented with native BigInt plus the extended Euclidean algorithm for modular inverses — no bignum library. The solution lives in ~/ecdsa-k-reuse-recovery.js (secp256k1 point math for verification, hex parsing, all exports) with tests in ~/ecdsa-k-reuse-recovery.test.js.
Key pieces:
// --- modular inverse (extended Euclid) ---
function modInverse(a, m) {
let t = 0n, newT = 1n, r = m, newR = mod(a, m);
while (newR !== 0n) {
const q = r / newR;
[t, newT] = [newT, t - q * newT];
[r, newR] = [newR, r - q * newR];
}
if (r !== 1n) throw new Error('not invertible');
return mod(t, m);
}
// --- core recovery: k = (z1-z2)/(s1-s2), d = (s1*k - z1)/r (all mod n) ---
function recoverPrivateKeyFromPair(sig1, sig2, n = SECP256K1.n) {
const a = normalizeSig(sig1, n), b = normalizeSig(sig2, n);
if (a.r !== b.r) throw new Error('different r — nonces differ');
const k = recoverK(a, b, n); // throws if s1≡s2
const d = mod((a.s * k - a.z) * modInverse(a.r, n), n);
return { k, d };
}
// --- set-level API with degenerate-pair fallback + pubkey verification ---
function recoverPrivateKey(sigs, { curve = SECP256K1, expectedPub = null } = {}) {
// ...validate same r for all, then:
for (let i = 0; i < list.length; i++)
for (let j = i + 1; j < list.length; j++) {
const denom = mod(list[i].s - list[j].s, n);
if (denom === 0n) continue; // EDGE CASE: fall back to next pair
const k = mod((list[i].z - list[j].z) * modInverse(denom, n), n);
const d = mod((list[i].s * k - list[i].z) * modInverse(r0, n), n);
if (expectedPub && pointEquals(pointMul(d, curve.G, curve), expected)) return { k, d, usedIndices: [i, j] };
if (!expectedPub && firstCandidate === null) firstCandidate = { k, d, usedIndices: [i, j] };
}
// throw if nothing matched / all pairs degenerate
}
Usage:
const { recoverPrivateKey, pointMul, SECP256K1 } = require('./ecdsa-k-reuse-recovery.js');
const d = recoverPrivateKey([sig1, sig2], { expectedPub: pubKeyPoint }).d;
// or with 3+ signatures sharing the same r to survive a degenerate pair:
const res = recoverPrivateKey([sig0, sig1, sig2], { expectedPub: pubHex });
Edge-case handling: when (s1−s2) mod n ≡ 0, the pair is degenerate (it forces z1 ≡ z2, i.e., identical signatures) and k cannot be recovered from it. recoverPrivateKey takes a set of ≥2 same-r signatures, tries every pair, skips degenerate ones, and falls back to the next pair; the winner is optionally verified by recomputing d·G with double-and-add point multiplication and comparing to the supplied public key (object, [x,y], compressed 02/03||x, or uncompressed 04||x||y hex).
Ran `node ecdsa-k-reuse-recovery.test.js` on Node v22.22.3 (code is Node-20-compatible: only BigInt + `node:crypto`, syntax-checked with `node --check`): ``` passed: 25 failed: 0 ``` Coverage (25 tests, grouped): - **Modular primitives:** `modInverse` known vectors (`3⁻¹ mod 11 = 4`), random `a·a⁻¹ ≡ 1`, zero→throws; `modPow` sanity. - **EC math:** `1·G = G`, `2·G` matches the published secp256k1 doubling vector, `(a+b)·G = a·G + b·G`, `n·G = ∞`, `(n−1)·G = −G`. - **Happy path:** random `d, k, z1, z2` — recovered `k` and `d` exactly equal the originals (asserted via the exact formulas `k=(z1−z2)/(s1−s2)`, `d=(s1·k−z1)/r`), and re-signing `z1` with the recovered key reproduces `s1`. - **Edge cases:** first pair degenerate (`z1==z2 ⇒ s1==s2`) → fallback uses pair `(0,2)`/`(1,2)` and still returns the true key (with and without `expectedPub`); all-degenerate → clear error; single signature → error; `r≡0` rejected; mismatched-`r` pairs rejected. - **Verification:** wrong `expectedPub` → throws "no recovered candidate key matches"; correct `expectedPub` (array, object, compressed, and uncompressed hex) → returns verified key. - **Input flexibility:** hex strings for `z/r/s`, bare hex (no `0x`), BigInt mixes. - **Fuzz:** 200 random 2-sig recoveries + 100 random 3-sig sets with random degenerate pairs — every one recovered `d` and `k` exactly. A standalone demo confirmed a live random key/nonce recovery with pubkey verification (`match: true`).
{"model": "deepseek-v4-flash", "problem_class": "ecdsa-k-reuse-key-recovery", "result": "passed", "tests": 25}The attack exploits that two ECDSA signatures using the same nonce k satisfy a linear relation. With s_i = k⁻¹·(z_i + r·d) mod n:
s1 − s2 = k⁻¹·(z1 − z2) mod n → k = (z1 − z2)·(s1 − s2)⁻¹ mod n
d = (s1·k − z1)·r⁻¹ mod n
Everything is implemented with native BigInt plus the extended Euclidean algorithm for modular inverses — no bignum library. The solution lives in ~/ecdsa-k-reuse-recovery.js (secp256k1 point math for verification, hex parsing, all exports) with tests in ~/ecdsa-k-reuse-recovery.test.js.
Key pieces:
// --- modular inverse (extended Euclid) ---
function modInverse(a, m) {
let t = 0n, newT = 1n, r = m, newR = mod(a, m);
while (newR !== 0n) {
const q = r / newR;
[t, newT] = [newT, t - q * newT];
[r, newR] = [newR, r - q * newR];
}
if (r !== 1n) throw new Error('not invertible');
return mod(t, m);
}
// --- core recovery: k = (z1-z2)/(s1-s2), d = (s1*k - z1)/r (all mod n) ---
function recoverPrivateKeyFromPair(sig1, sig2, n = SECP256K1.n) {
const a = normalizeSig(sig1, n), b = normalizeSig(sig2, n);
if (a.r !== b.r) throw new Error('different r — nonces differ');
const k = recoverK(a, b, n); // throws if s1≡s2
const d = mod((a.s * k - a.z) * modInverse(a.r, n), n);
return { k, d };
}
// --- set-level API with degenerate-pair fallback + pubkey verification ---
function recoverPrivateKey(sigs, { curve = SECP256K1, expectedPub = null } = {}) {
// ...validate same r for all, then:
for (let i = 0; i < list.length; i++)
for (let j = i + 1; j < list.length; j++) {
const denom = mod(list[i].s - list[j].s, n);
if (denom === 0n) continue; // EDGE CASE: fall back to next pair
const k = mod((list[i].z - list[j].z) * modInverse(denom, n), n);
const d = mod((list[i].s * k - list[i].z) * modInverse(r0, n), n);
if (expectedPub && pointEquals(pointMul(d, curve.G, curve), expected)) return { k, d, usedIndices: [i, j] };
if (!expectedPub && firstCandidate === null) firstCandidate = { k, d, usedIndices: [i, j] };
}
// throw if nothing matched / all pairs degenerate
}
Usage:
const { recoverPrivateKey, pointMul, SECP256K1 } = require('./ecdsa-k-reuse-recovery.js');
const d = recoverPrivateKey([sig1, sig2], { expectedPub: pubKeyPoint }).d;
// or with 3+ signatures sharing the same r to survive a degenerate pair:
const res = recoverPrivateKey([sig0, sig1, sig2], { expectedPub: pubHex });
Edge-case handling: when (s1−s2) mod n ≡ 0, the pair is degenerate (it forces z1 ≡ z2, i.e., identical signatures) and k cannot be recovered from it. recoverPrivateKey takes a set of ≥2 same-r signatures, tries every pair, skips degenerate ones, and falls back to the next pair; the winner is optionally verified by recomputing d·G with double-and-add point multiplication and comparing to the supplied public key (object, [x,y], compressed 02/03||x, or uncompressed 04||x||y hex).
Ran `node ecdsa-k-reuse-recovery.test.js` on Node v22.22.3 (code is Node-20-compatible: only BigInt + `node:crypto`, syntax-checked with `node --check`): ``` passed: 25 failed: 0 ``` Coverage (25 tests, grouped): - **Modular primitives:** `modInverse` known vectors (`3⁻¹ mod 11 = 4`), random `a·a⁻¹ ≡ 1`, zero→throws; `modPow` sanity. - **EC math:** `1·G = G`, `2·G` matches the published secp256k1 doubling vector, `(a+b)·G = a·G + b·G`, `n·G = ∞`, `(n−1)·G = −G`. - **Happy path:** random `d, k, z1, z2` — recovered `k` and `d` exactly equal the originals (asserted via the exact formulas `k=(z1−z2)/(s1−s2)`, `d=(s1·k−z1)/r`), and re-signing `z1` with the recovered key reproduces `s1`. - **Edge cases:** first pair degenerate (`z1==z2 ⇒ s1==s2`) → fallback uses pair `(0,2)`/`(1,2)` and still returns the true key (with and without `expectedPub`); all-degenerate → clear error; single signature → error; `r≡0` rejected; mismatched-`r` pairs rejected. - **Verification:** wrong `expectedPub` → throws "no recovered candidate key matches"; correct `expectedPub` (array, object, compressed, and uncompressed hex) → returns verified key. - **Input flexibility:** hex strings for `z/r/s`, bare hex (no `0x`), BigInt mixes. - **Fuzz:** 200 random 2-sig recoveries + 100 random 3-sig sets with random degenerate pairs — every one recovered `d` and `k` exactly. A standalone demo confirmed a live random key/nonce recovery with pubkey verification (`match: true`).
{"model": "deepseek-v4-flash", "problem_class": "ecdsa-k-reuse-key-recovery", "result": "passed", "tests": 25}