Elliott (aka @robot__dreams) posted a Bitcoin-flavored cryptography challenge on Twitter. The goal is to extract the private key from two Schnorr signatures that reuse a nonce. I’ve recently reviewed and merged Kalle Rosenbaum’s cross-post of his Schnorr Basics post to bitcoin-dev.blog. His post shows, for example, why nonce reuse leaks the private key. The challenge was the perfect opportunity for me to apply the theory the blog post explains. This post is a write-up of how I solved the challenge.

Challenge

The challenge puts us into the role of an adversary. The goal is to extract the private key used in the creation of two Schnorr signatures. The nonce is reused in both signatures.

You're given Schnorr signatures on two different messages signed by the same private key. Fortunately for you (the adversary), the signer screwed up their implementation of BIP-340 and reused a nonce. Can you capitalize on this fatal error and extract the signer's private key?

Note: You may find it helpful to interpret some of the byte strings as ASCII, in order to check your work.

Public Key: 463F9E1F3808CEDF5BB282427ECD1BFE8FC759BC6F65A42C90AA197EFC6F9F26
Message 1: 6368616E63656C6C6F72206F6E20746865206272696E6B206F66207365636F6E
Signature 1: F3F148DBF94B1BCAEE1896306141F319729DCCA9451617D4B529EB22C2FB521A32A1DB8D2669A00AFE7BE97AF8C355CCF2B49B9938B9E451A5C231A45993D920
Message 2: 6974206D69676874206D616B652073656E7365206A75737420746F2067657420
Signature 2: F3F148DBF94B1BCAEE1896306141F319729DCCA9451617D4B529EB22C2FB521A974240A9A9403996CA01A06A3BC8F0D7B71D87FB510E897FF3EC5BF347E5C5C1

Theory

We use the same notation as laid out in Schnorr basics. The Schnorr signature scheme used in Bitcoin uses the secp256k1 curve. The generator point $G$ and the curve group order $n$ for the secp256k1 curve are listed, along with the other curve parameters, in Standards for Efficient Cryptography.

We are looking for the private key $p$. The public key $P$, two messages, $m_1$ and $m_2$, and two Signatures $(R, s_1)$ and $(R, s_2)$ are given. Both signatures share the nonce commitment $R$, as they reuse the nonce $r$. The responses $s_1$ and $s_2$ are different in both signatures as they belong to distinct messages.

$$ \begin{align} p & \quad \text{private key} \\ P = pG & \quad \text{public key} \\ m & \quad \text{message} \\ r & \quad \text{random nonce} \\ R = rG & \quad \text{nonce commitment} \end{align} $$

The signature signs a challenge hash $e$ which is the hash the concatenation of $R$, $P$, and $m$.

$$ e = H(R||P||m) \tag{1} $$

The response $s$ is the addition of the nonce $r$ and $ep$.

$$ s = r + ep $$

To extract the private key $p$, we can set up an equation system with two equations and two unknowns. This is adapted from the Schnorr basics post but shown in more detail.

$$ \begin{align} I & \quad s_1 = r + e_1 p \\ II & \quad s_2 = r + e_2 p \end{align} $$

We substract $II$ from $I$.

$$ \begin{align} s_1 - s_2 &= r + e_1 p - (r + e_2 p) & \tag*{ negating $(r + e_2 p)$} \\ s_1 - s_2 &= r + e_1 p - r - e_2 p & \tag*{ $+r$ and $-r$ cancel out} \\ s_1 - s_2 &= e_1 p - e_2 p & \tag*{ extracting $p$ } \\ s_1 - s_2 &= p(e_1 - e_2) \tag*{ dividing by ($e_1 - e_2)$ } \\ \frac{s_1 - s_2}{e_1 - e_2} &= p \tag{2} \end{align} $$

We can calculate $e_1$ and $e_2$ and know $s_1$ and $s_2$ from the provided signatures. The nonces $r$ and $-r$ only cancel out because the nonce is reused. With no nonce reuse, $r_1$ and $r_2$ wouldn’t cancel out, and we couldn’t solve for $p$.

Implementation

We’ve implemented a solution in Python. The curve group order, messages, signatures, and the public key are Python’s integer type. Python integers can hold arbitrarily large numbers (PEP 237). Arithmetic on integers is modulo $n$, the curve group order.

# curve group order
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

# public key
P = 0x463F9E1F3808CEDF5BB282427ECD1BFE8FC759BC6F65A42C90AA197EFC6F9F26

# first message and signature
m1 = 0x6368616E63656C6C6F72206F6E20746865206272696E6B206F66207365636F6E
sig1 = 0xF3F148DBF94B1BCAEE1896306141F319729DCCA9451617D4B529EB22C2FB521A32A1DB8D2669A00AFE7BE97AF8C355CCF2B49B9938B9E451A5C231A45993D920

# second message and signature
m2 = 0x6974206D69676874206D616B652073656E7365206A75737420746F2067657420
sig2 = 0xF3F148DBF94B1BCAEE1896306141F319729DCCA9451617D4B529EB22C2FB521A974240A9A9403996CA01A06A3BC8F0D7B71D87FB510E897FF3EC5BF347E5C5C1

Bitcoin ECDSA signatures are DER-encoded and have an encoding overhead. Bitcoin Schnorr signatures have no overhead as they are just the concatenation of 32 bytes of $R$ and 32 bytes of $s$. See Evolution of the signature size in Bitcoin for more details. As the nonce $r$ is reused, the signatures share the same $R$.

# the first 256 bits of the signatures are R
R = sig2 >> 256

# the last 256 bits of the signatures sig1 and sig2 are the reponses s1 and s2
s1 = sig1 - (R << 256)
s2 = sig2 - (R << 256)

The next step is to calculate $e_1$ and $e_2$ using formula $(1)$.

$$ e = H(R||P||m) $$

BIP 340 defines that the hashes are tagged with a context-specific tag. This makes sure hashes used in one context can’t be reinterpreted in another context. The tag for challenges is SHA256("BIP0340/challenge") || SHA256("BIP0340/challenge"). We use the hashlib module provided by Python to calculate SHA256 hashes.

import hashlib
challenge_tag = hashlib.sha256(b"BIP0340/challenge").digest() * 2

As the hashlib.sha256 function expects parameters of type bytes we need to convert our integers. We define the int_to_bytes(i) helper function and calculate the challenge hashes $e_1$ and $e_2$. We treat integers as big-endian when converting them to and from byte arrays.

byteorder = "big"

def int_to_bytes(i):
  return i.to_bytes(32, byteorder, signed=False)

def challenge_hash(tag, R, P, m):
  return hashlib.sha256(tag + R + P + m).digest()

e1_hash = challenge_hash(challenge_tag, int_to_bytes(R), int_to_bytes(P), int_to_bytes(m1))
e2_hash = challenge_hash(challenge_tag, int_to_bytes(R), int_to_bytes(P), int_to_bytes(m2))

The hashlib.sha256 function returns a bytes object. To convert the result back to integers, we define the helper function bytes_to_int(b).

def bytes_to_int(b):
  return int.from_bytes(b, byteorder, signed=False)

e1 = bytes_to_int(e1_hash) % n
e2 = bytes_to_int(e2_hash) % n

We now have the challenge hashes $e_1$ and $e_2$ and the responses $s_1$ and $s_2$. These can be used in formula $(2)$

$$ p = \frac{s_1 - s_2}{e_1 - e_2} = \frac{i}{j} $$

to calculate $p$. We first calculate the dividend $i$ and the divisor $j$.

i = (s1 - s2) % n
j = (e1 - e2) % n

However, implementing modular division isn’t as straightforward as dividing the dividend by the divisor.

# incorrect modular division!
p_ =  i / j

We need the modular multiplicative inverse $j^{-1} = x$ of the divisor for modular division. The modular inverse $x$ multiplied with the divisor $j$ is congruent to 1 modulo $n$.

$$ j \cdot x \equiv 1 \mod n $$

The modular inverse is defined if the $i$ and $n$ are co-prime. This is the case if the greatest common divisor ($\text{GCD}$) of $i$ and $n$ is $1$. Then, to perform modular division, we can multiply the divisor $i$ and $x$.

$$ \begin{align} \frac{i}{j} = i \cdot j^{-1} = i \cdot x \mod n \tag{3} \end{align} $$

This is implemented using the extended Euclidean algorithm ¹ to calculate the $\text{GCD}(j, n)$, and, if $j$ and $n$ are co-prime, also the modular multiplicative inverse $x$. We’ve adapted the recursive Python implementation of the extended Euclidean algorithm provided by wikibooks.org.

def eea(a, b):
    """return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
    if a == 0:
        return (b, 0, 1)
    else:
        b_div_a, b_mod_a = divmod(b, a)
        g, x, y = eea(b_mod_a, a)
        return (g, y - b_div_a * x, x)

(gcd, x, _) = eea(j, n)
if gcd != 1:
  raise Exception('GCD of divisor mod n is not 1. Modular inverse is not defined.')

We check that the $\text{GCD}$ of $i$ and $n$ is equal to $1$. If that’s the case, we can use formula $(3)$ to calculate $p$.

p = (i * (x % n)) % n

The variable p now holds the private key as an integer. The challenge mentioned checking our results by printing the ASCII encoded private key. We can convert the integer to bytes with the int_to_bytes(i) helper function we defined earlier. When printed, the bytes type automatically shows ASCII characters.

# The output is purposefully omitted here.
print(int_to_bytes(p))

Another way of checking if the extracted private key is correct is to calculate the corresponding public key and compare it to the provided public key. If the public keys match, the private key is correct. We use the fastecdsa Python module for elliptic curve scalar multiplication (a scalar multiplied with a point). The public key is $P = pG$.

from fastecdsa.curve import secp256k1

if (p * secp256k1.G).x == P:
  print("Congratulations, you found the private key")
else:
  print("Public keys don't match: the private key is incorrect!")

# prints: Congratulations, you found the private key

This solves the challenge. The complete Python code as a Jupyter Notebook can be found here and run online in Google Colab here.

Bonus

While not part of the original challenge, knowing the private key $p$ allows us to extract the nonce $r$. Solving formula $(1)$ for $r$.

$$ \begin{align} s = & \ r + ep \tag*{- ep} \\ s-ep = & \ r \end{align} $$

r1 = (((e1 * p) % n) - s1) % n
r2 = (((e2 * p) % n) - s2) % n
assert(r1 == r2)

To double-check, we can calculate the nonce commitment $R = rG$.

if (r2 * secp256k1.G).x == R:
  print("The provided and the calculated nonce commitment R match!")
else:
  print("Nonce commitments don't match!")

# prints: The provided and the calculated nonce commitment R match!

Thanks

I’ve enjoyed this challenge and wanted to thank Elliott for setting it up. For me, as someone who is far from being an expert in cryptography, it turned out to hit the sweet spot between challenging and still being solvable. Elliott already followed up with the second and harder challenge.

I wouldn’t have looked at this challenge if I hadn’t read Kalle Rosenbaum’s Schnorr basics post only a few days before. He mentions he attempts to explain Schnorr signatures at a level he appreciates and hopes the reader finds it valuable too. For me, this has been the case. I think it’s often worth it writing a deep-dive into topics that you spent a lot of time on.

I want to pay this forward with this post. There are likely some who can’t dedicate enough time to solve this challenge but who find my solution valuable.