Introduction
I’ve learned a lot from Ethernaut recently. Setting aside the more basic stuff, I want to document some ECDSA-related notes.
In the formulas below, lowercase letters represent scalar values, uppercase letters represent points, except N which is the curve order.
ECDSA relies on the discrete logarithm problem on elliptic curves. For a private key privkey, the public key PubKey is a point on the elliptic curve satisfying $\text{PubKey} = \text{privkey} \cdot G$, where G is the generator of the elliptic curve. Because the discrete logarithm problem on elliptic curves makes it computationally infeasible to derive privkey from PubKey and G, digital signatures become possible.
Sign
The signing formula:
$$ s = k^{-1} \cdot (h + r \cdot \text{privkey})\mod{N} $$k is a random nonce. RFC6979 provides a deterministic generation method — you shouldn’t truly randomize it, because reuse leads to private key leakage (more on that later).
h is the hash value being signed.
r is the x-coordinate of the point k * G.
After computing s, it forms the signature (r, s) together with r. However, during signature recovery there’s ambiguity with two possible results, so a value v is introduced to disambiguate — more on that later.
1import hashlib
2from eth_hash.auto import keccak
3from ecdsa import SECP256k1
4from ecdsa.rfc6979 import generate_k
5
6CURVE = SECP256k1
7N = CURVE.order
8G = CURVE.generator
9
10priv_key = 0xac0974bec39a17e36ba4a6b4d238ff944bacb478cbed5efcae784d7bf4f2ff80
11
12h = keccak(b'hello')
13print(f'hash: 0x{h.hex()}')
14
15h_int = int.from_bytes(h, 'big')
16
17# random k, important
18k = generate_k(
19 order=N,
20 secexp=priv_key,
21 hash_func=hashlib.sha256,
22 data=h,
23)
24
25R = k * G
26r = R.x() % N
27k_inv = pow(k, -1, N)
28
29# s = k^-1 * (h + r * pk)
30s = (k_inv * (h_int + r * priv_key)) % N
31
32print(f'sig : 0x{r.to_bytes(32, 'big').hex()}{s.to_bytes(32, 'big').hex()}')
33print(f'r : 0x{r.to_bytes(32, 'big').hex()}')
34print(f's : 0x{s.to_bytes(32, 'big').hex()}')
Recover
The signature recovery formula — recovering public key Pub from signature (r, s).
Starting from the signing formula, we can derive:
$$ \begin{aligned} s &= k^{-1} \cdot (h + r \cdot \text{privkey}) &\mod{N} \\ \text{privkey} &= (s \cdot k - h) \cdot r^{-1} &\mod{N} \\ \text{Pub} &= \text{privkey} \cdot G \\ &= (s \cdot k - h) \cdot r^{-1} \cdot G & \\ &= (s \cdot k \cdot G - h \cdot G) \cdot r^{-1} & \\ &= (s \cdot R - h \cdot G) \cdot r^{-1} & \\ \end{aligned} $$Where R is the point k * G, and r in the signature is the x-coordinate of R. Since R lies on the elliptic curve, we can compute the y-coordinate by substituting x into the curve equation, giving us R.
From the elliptic curve equation, we know each x-coordinate has two possible y values — one positive and one negative (though after mod p there are no negatives). These two values yield two different recoverable public keys. Which one to use depends on v provided during signing. The example below doesn’t use v and computes both candidates.
1# utils.py
2from ecdsa import SECP256k1
3from ecdsa.numbertheory import square_root_mod_prime
4
5# y^2 = x^3 + ax + b mod p
6def curve_x_to_y(x, CURVE = SECP256k1):
7 a = CURVE.curve.a()
8 b = CURVE.curve.b()
9 p = CURVE.curve.p()
10
11 try:
12 y = square_root_mod_prime((pow(x, 3, p) + a * x + b) % p, p)
13 except Exception as e:
14 raise ValueError(f'square_root_mod_prime() error: {e}')
15
16 return [y, p-y]
1import utils
2
3from eth_hash.auto import keccak
4from eth_utils import to_checksum_address
5from ecdsa import SECP256k1
6from ecdsa.ellipticcurve import Point
7
8CURVE = SECP256k1
9N = CURVE.order
10G = CURVE.generator
11
12h = keccak(b'hello')
13print(f'hash: 0x{h.hex()}')
14
15h_int = int.from_bytes(h, 'big')
16
17# R = k * G
18# r = x of R(x, y)
19# pub = pk * G
20
21# s = k^-1 * (h + r * pk)
22# r^-1 * (s * k - h) = pk
23# pub = r^-1 * (s * k - h) * G
24# pub = r^-1 * (s * k * G - h * G)
25# pub = r^-1 * (s * R - h * G)
26
27r = 0x73eebf81a611136662d65778960c853fdcaf6eca86793ed9cabc30f2195937af
28s = 0x78a07e601627da5b4cc80c0ab35f6894da19b4a01759d90c101d9c9dd1c6745d
29
30r_inv = pow(r, -1, N)
31r_y_candidates = utils.curve_x_to_y(r, CURVE=CURVE)
32
33for r_y in r_y_candidates:
34 try:
35 R = Point(curve=CURVE.curve, x=r, y=r_y, order=N)
36 except Exception as e:
37 raise ValueError(f'Point() error: {e}')
38
39 tmp = s * R + (-h_int % N) * G.to_affine() # to_affine: PointJacobi => Point
40 pub = r_inv * tmp
41 pub_bytes = pub.x().to_bytes(32, 'big') + pub.y().to_bytes(32, 'big')
42 print(f'pub : 0x{pub_bytes.hex()}')
43 pub_hash = keccak(pub_bytes)
44 print(f'addr: {to_checksum_address('0x' + pub_hash.hex()[-40:])}')
Nonce Reuse
The random number k used during signing, also called the nonce, must never be reused. If the same private key signs two different hashes with the same nonce, it leads to private key leakage — which is exactly why every signing operation should follow RFC6979 to generate a secure nonce.
Suppose a private key used the same k to sign two different hashes h1 and h2, producing two signatures s1 and s2.
Same k means R = k * G is the same, and r = R.x() mod N, so r in both signatures is identical.
From the signing formula we can derive:
$$ \begin{gathered} \begin{aligned} s1 &= k^{-1} \cdot (h1 + r \cdot \text{privkey}) &\mod{N} \\ s2 &= k^{-1} \cdot (h2 + r \cdot \text{privkey}) &\mod{N} \end{aligned} \\[2em] \begin{aligned} k \cdot s1 - h1 &= r \cdot \text{privkey} &\mod{N} \\ k \cdot s2 - h2 &= r \cdot \text{privkey} &\mod{N} \end{aligned} \\[2em] \begin{aligned} k \cdot s1 - h1 &= k \cdot s2 - h2 &\mod{N} \\ k &= (h1 - h2) \cdot (s1 - s2)^{-1} &\mod{N} \end{aligned} \\[2em] \begin{aligned} h1 + r \cdot \text{privkey} &= s1 \cdot (h1 - h2) \cdot (s1 - s2)^{-1} &\mod{N} \\ \text{privkey} &= (h1 \cdot s2 - s1 \cdot h2) \cdot (s1-s2)^{-1} \cdot r^{-1} &\mod{N} \end{aligned} \end{gathered} $$So the private key can be recovered from the known values s1, s2, h1, h2, and r.
1from ecdsa import SECP256k1
2
3CURVE = SECP256k1
4N = CURVE.order
5
6r = 0xe5648161e95dbf2bfc687b72b745269fa906031e2108118050aba59524a23c40
7
8s1 = 0x4c3ac03b268ae1d2aca1201e8a936adf578a8b95a49986d54de87cd0ccb68a79
9h1 = 0x6a0d6cd0c2ca5d901d94d52e8d9484e4452a3668ae20d63088909611a7dccc51
10
11s2 = 0x70026fc30e4e02a15468de57155b080f405bd5b88af05412a9c3217e028537e3
12h2 = 0x937fa99fb61f6cd81c00ddda80cc218c11c9a731d54ce8859cb2309c77b79bf3
13
14# s1 = k^-1 * (h1 + r * pk)
15# s2 = k^-1 * (h2 + r * pk)
16
17# k * s1 = h1 + r * pk
18# k * s2 = h2 + r * pk
19
20# k * s1 - h1 = k * s2 - h2
21# k * (s1 - s2) = h1 - h2
22# k = (h1 - h2) * (s1 - s2)^-1
23
24# s1 * (h1 - h2) / (s1 - s2) = h1 + r * pk
25# (s2h1 - s1h2) / (s1 - s2) = r * pk
26# pk = (r * (s1 - s2))^-1 * (s2h1 - s1h2)
27
28tmp = pow((r * (s1 - s2)) % N, -1, N)
29pk = tmp * (s2 * h1 - s1 * h2) % N
30
31print(f'priv: 0x{pk.to_bytes(32, 'big').hex()}')
Spoofing
During signature recovery, we can compute the PubKey corresponding to a signature from hash and (r, s).
A single private key can sign many different hashes, producing different (r, s) pairs, all of which recover to the same PubKey.
Conversely, for any given PubKey, there exist many different combinations of hash and (r, s) that recover to that PubKey.
We know that signing a specific hash to get the corresponding (r, s) requires the private key. Without the private key, you can only randomly pick from the vast space of valid combinations — this is Spoofing.
In other words, given a known PubKey, you can randomly generate a hash and (r, s) pair that recovers to that PubKey.
Deriving from the recovery formula:
$$ \begin{gathered} \begin{aligned} \text{Pub} &= (s \cdot R - h \cdot G) \cdot r^{-1} &\mod{N} \\ s \cdot R &= \text{Pub} \cdot r + h \cdot G &\mod{N} \\ R &= r \cdot s^{-1} \cdot \text{Pub} + h \cdot s^{-1} \cdot G &\mod{N} \end{aligned} \\[2em] \begin{aligned} u &= r \cdot s^{-1} &\mod{N} \\ v &= h \cdot s^{-1} &\mod{N} \end{aligned} \\[2em] \begin{aligned} R &= u \cdot \text{Pub} + v \cdot G &\mod{N} \\ s &= u \cdot r^{-1} &\mod{N} \\ h &= v \cdot s &\mod{N} \\ &= v \cdot u \cdot r^{-1} &\mod{N} \end{aligned} \end{gathered} $$We pick random values u and v (both less than N) as intermediates.
After computing point R, we get r (the x-coordinate of R). Then we compute the signature (r, s) and hash h from r, u, and v.
The takeaway: never blindly trust an externally provided hash. Always compute it yourself from known parameters, and never attach real-world meaning (like amounts) to a hash you don’t control.
1import secrets
2
3from ecdsa import SECP256k1
4from ecdsa.ellipticcurve import Point
5
6CURVE = SECP256k1
7N = CURVE.order
8G = CURVE.generator
9
10# pub = r^-1 * (s * R - h * G)
11
12# Pub * r = s * R - h * G
13# h * G = s * R - r * Pub
14
15# R = s^-1 * h * G + s^-1 * r * Pub
16
17# R = u1 * G + u2 * Pub
18# u1 = s^-1 * h
19# u2 = s ^ -1 * r
20# s = r * u2^-1
21# h = s * u1 = r * u2^-1 * u1
22
23alice_pub = 0x33da8e7fe906411e4fc12842632ec77c2aee6a4324a4a3ca554b56667e4ccf97eda346ace5f9dce2781697ad353350c7509e1ffb491fedf49e37d4504185c676
24alice_pub_x = 0x33da8e7fe906411e4fc12842632ec77c2aee6a4324a4a3ca554b56667e4ccf97
25alice_pub_y = 0xeda346ace5f9dce2781697ad353350c7509e1ffb491fedf49e37d4504185c676
26
27u1 = secrets.randbelow(N)
28u2 = secrets.randbelow(N)
29Pub = Point(curve=CURVE.curve, x=alice_pub_x, y=alice_pub_y, order=N)
30
31R = u1 * G.to_affine() + u2 * Pub
32r = R.x() % N
33s = r * pow(u2, -1, N) % N
34h = s * u1 % N
35
36print(f'hash: 0x{h.to_bytes(32, 'big').hex()}')
37print(f'sig : 0x{r.to_bytes(32, 'big').hex()}{s.to_bytes(32, 'big').hex()}')
38print(f'r : 0x{r.to_bytes(32, 'big').hex()}')
39print(f's : 0x{s.to_bytes(32, 'big').hex()}')