In [35]:

from hashlib import sha1, sha256
from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse
from ecdsa import ellipticcurve
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key
from random import randint

Prerequisites¶

ecdsa

Theory¶

Task

Exploit the fact that 2 signatures corresponding to 2 different messages were crafted using the same nonce $k$

We know

the order of the subgroup generated by $G$: $q$
messages: $m_1, m_2$ and their hashes $h_1, h_2$
the signatures were generated using the same $k$
signatures: $(r, s_1), (r, s_2)$ <= $r$ is the same since we use the same $k$ => $Q_1 = Q_2 = kG$

$ \begin{equation} s_1 \equiv k^{-1}(h_1 + dr) \ mod \ q \\ s_2 \equiv k^{-1}(h_2 + dr) \ mod \ q \end{equation}$

Substract $s_2$ from $s_1$

$s_1 - s_2 \equiv k^{-1}(h_1 + dr) - k^{-1}(h_2 + dr) \equiv k^{-1}(h_1 - h_2) \ mod \ q => k \equiv (h_1 - h_2)(s_1 - s_2)^{-1} \ mod \ q$

Therefore we can calculate $d$

$d \equiv (sk - h)r^{-1} \ mod \ q$

Code¶

In [14]:

#generate the parameters
G = generator_256
q = G.order()
print(is_prime(q))

True
110293943109482154156062517946490981556599973730885811037950153262390807421596

In [19]:

#generate the public and private key
d = randint(1, q-1)
pubkey = Public_key(G, d*G)
privkey = Private_key(pubkey, d)

In [31]:

#hash the messages
m1 = b'secret_message'
m2 = b'another_one'
h1 = bytes_to_long(sha256(m1).digest())
h2 = bytes_to_long(sha256(m2).digest())

In [32]:

#random k
k = randint(1, q-1)

In [33]:

sign1 = privkey.sign(h1, k)
sign2 = privkey.sign(h2, k)

s1, r1 = sign1.s, sign1.r
s2, r2 = sign2.s, sign2.r
print(r1 == r2) #check if the r's are equal

r = r1

True

In [41]:

k_decr = ((h1 - h2) * inverse((s1 - s2), q)) % q
print(k_decr == k)

True

In [42]:

d_decr = ((s1 * k - h1) * inverse(r, q)) % q
print(d_decr == d)

True

Resources¶

In [ ]: