Digital Signatures

Cryptography

#The problem hashing doesn’t solve

I’ve already gone through hash functions, and how they can be used to prove that a piece of data hasn’t been tampered with. However, on their own, hash functions tell you nothing about who sent the data, or whether they can be trusted.

Say you want to spend some bitcoin. You need to produce a message that says “move these coins that I own” in a way that anyone can check is legitimate, but that only you could have produced. Hashing the message alone doesn’t do this, since anyone can hash a message. What you need is a way to tie the message to a private key that only you hold, i.e., a digital signature.

#Digital signatures

We are already familiar with Asymmetric Encryption: two keys, one public and one private, where anything encrypted with the public key can only be decrypted with the private key. Digital signatures use the same public/private key setup, so it’s tempting to assume they are just encryption flipped around: decrypt with the private key to sign, encrypt with the public key to verify. This is a common misconception for people first learning about digital signatures [1]. It doesn’t hold in general, and most signature schemes (including the ones Bitcoin uses) don’t have a decryption step to flip in the first place. In other words, signing needs its own definition, separate from encryption. Signing has to guarantee that anyone can verify the signature, but only you could have produced it.

Following Katz and Lindell again [1], let’s define a digital signature formally.

To use a signature scheme, the sender runs $\texttt{Gen}(1^\kappa)$ to obtain the public and private keys $(pk, sk)$. The sender is then free to publish $pk$ anywhere they wish. When the sender wants to authenticate a message $m$, they compute

and then send $(m, \sigma)$ to the recipient.

The recipient who knows $pk$ can then check whether

This way, the receiver can verify that the sender sent $m$, and that $m$ has not been modified in transit.

#What does “secure” mean for signatures?

Up to this point we have (hopefully) gotten a good idea of what it means for something to be secure in the cryptographic sense. The Integer Factorization Problem, the Discrete Logarithm Problem (DLP), and the Elliptic Curve Discrete Logarithm Problem (ECDLP) underlie asymmetric encryption, and preimage and collision resistance (Cryptographic hash function) underlie hash functions. However, signatures are a little different. A secure signature scheme needs more than an attacker being unable to compute $sk$ from $pk$.

Consider an adversary who has seen you sign a bunch of other messages, and now tries to forge your signature on a message you have never signed. The formal name for security against this attack is existential unforgeability under an adaptive chosen-message attack (EUF-CMA) [1].

Put simply, a digital signature scheme is EUF-CMA secure if no efficient attacker can produce a valid $(m, \sigma)$ pair on a message $m$ it was never given a signature for, even if it first gets to request signatures on any other messages of its choosing. Without this property, a digital signature doesn’t prove authenticity, since someone could forge your signature on a message you never touched.

#Textbook RSA signatures

So what does it look like when a scheme isn’t EUF-CMA secure? RSA is a good example, and it actually got attacked recently. Remember the misconception from earlier, that signing is just encryption flipped around? For RSA in its most bare-bones form, usually called textbook RSA, that’s actually how it works. This is probably where the misconception came from [1]. It’s also insecure, which we’ll see in a second. You sign a message by raising it to your private exponent,

and anyone with $pk = (N, e)$ can verify it by checking whether

The problem is that this plays way too nicely with multiplication. Say you get the owner to sign two messages, $m_1$ and $m_2$. Multiplying the two signatures together gives

which is a valid signature on $m_1 m_2$, a message they never signed. That alone already breaks EUF-CMA [1]. It’s a pretty limited forgery though, since you only get signatures on products of things you’ve already had signed. What if you want a signature on one specific message?

That’s what Joux, Naccache, and Thomé worked out back in 2007 [2]. The idea is to get signatures on a huge pile of numbers you pick (all of a specific form), then find a way to build your target message out of them by multiplying. Once you have that, you multiply the matching signatures together just like above. Finding that combination is the hard part, and they did it with the same kind of math the best factoring algorithms use. It still takes a long time, but it’s faster than the best known way to factor $N$, so forging a signature ends up easier than breaking the key outright.

Nobody actually pulled this off for almost 20 years, until September 2026, when a team at UC San Diego and INRIA (including Thomé from the original paper) did it [3]. They took a device that signs with a 1024-bit RSA key, had it sign about $2^{32}$ (around 4 billion) numbers of their choosing, then ran the math on a ton of computers for about five months. On a single processor core it would’ve taken 1380 years. At the end they had a forged signature on a message the device never signed, without ever getting $sk$ or factoring $N$.

To be fair, nobody actually signs with textbook RSA. Real RSA runs the message through a hash function first and signs $\operatorname{hash}(m)$ instead of $m$. Now, to pull off the multiplying trick, you’d need to find some message $m$ with

and with a good hash (one whose output is about as big as $N$), nobody knows how to find one [1]. You no longer get to choose the numbers that actually get signed, which also kills the 2007 attack. The researchers had to switch the hashing off on the device to make it work. Still, they estimate that if an attacker can get raw RSA signatures on numbers they pick, forging one is somewhere between 30 thousand and a billion times easier than we thought from factoring alone [3].

NIST already plans to phase RSA out because of quantum computers (which we’ll get to later in the series), and under its current draft, RSA won’t be allowed at all after 2035 [4]. The same plan covers the elliptic curve signatures Bitcoin uses too. The researchers argue their result is one more reason to drop RSA entirely while we’re making that switch anyway, this time from a regular, non-quantum attack [3].

#ECDSA

Since the specific signature schemes that Bitcoin employs will be a key point in discussing how exactly quantum computers threaten Bitcoin’s security, I think it’s worth going into how these schemes work in some depth. Luckily, there are only two of interest, and the first that I will discuss is the Elliptic Curve Digital Signature Algorithm (ECDSA).

Bitcoin uses ECDSA over the secp256k1 curve. ECDSA is a general-use digital signature scheme standardized by the National Institute of Standards and Technology (NIST) [5], though the curve itself comes from a separate standard called SEC 2.

As a reminder of my earlier notation, recall that $\mathbb{E}(\mathbb{Z}_p)$ is the elliptic curve group, where $p$ is the 256-bit prime defining secp256k1’s underlying field (with $\mathbb{Z}_p = \{0, 1, 2, \dots, p - 1\}$, and $\mathbb{Z}_p^*$ being the same set excluding 0), $G$ is the generator point, and $n$ is the order of $G$ (the size of the group $G$ generates).

Since ECDSA is a digital signature scheme, it fits into the $\texttt{Gen}$/$\texttt{Sign}$/$\texttt{Vrfy}$ template from Digital signature. Here’s what those three algorithms look like for ECDSA specifically:

ECDSA over secp256k1 is parameterized by the fixed curve $\mathbb{E}(\mathbb{Z}_p)$, generator $G$, order $n$, hash function

and

These are fixed once for the whole scheme, not generated or received per key pair.

Notice that $\texttt{Sign}$ never touches $m$ directly, only $\operatorname{hash}(m)$. This is where hash functions come back in. If an attacker could find two messages with $\operatorname{hash}(m_1) = \operatorname{hash}(m_2)$, a signature on $m_1$ would also be a valid signature on $m_2$. This is why the hash has to be collision resistant (Cryptographic hash function), and why MD5 signatures had to be phased out once MD5 collisions were found.

Why does this actually work? Let’s start with answering: why does the signature verify? Let’s substitute $P = dG$ into the reconstruction step in $\texttt{Vrfy}$.

But, from the $\texttt{Sign}$ algorithm,

Substituting this in, we get

The mod $n$ can be dropped here because $G$ has order $n$, so $nG = \mathcal{O}$ and multiplying $G$ by any number only depends on that number mod $n$. Applying $F$ to both sides then gives $r' = F(kG) = r$, which is exactly the check in $\texttt{Vrfy}$.

We have reconstructed $kG$, the same point $r$ was computed from in the first place. Why can’t this be forged? To produce a signature that passes this check without knowing $d$, the obvious route is to recover $d$ directly from $P = dG$. In other words, given $G$ and $P = dG$, determine $d$. Does this look familiar? This is exactly the Elliptic Curve Discrete Logarithm Problem (ECDLP) that I described earlier. This is an informal argument though, not a proof, and I’ll come back to why later.

I’ll note that this only demonstrates security against an attacker who has just your public key, but EUF-CMA is stronger, and has to hold even if an attacker has seen any number of your real signatures. The intuition still holds here, because each signature uses a fresh value of $k$, so the attacker can’t extract anything useful from your past signatures unless they get lucky enough to guess $k$ outright.

This is also why $k$ can never be reused. If you sign two different messages $m_1$ and $m_2$ with the same $k$, both signatures have the same $r$, and subtracting the two signing equations gives

Anyone can solve this for $k$, and then for $d$. Sony, for example, signed PlayStation 3 software using the same $k$ every time, and in 2010 their private key was recovered this way [6]. In 2013, a bug in Android’s random number generator caused some Bitcoin wallets to reuse $k$, and coins were stolen [7].

#Schnorr Signatures

The second signature scheme of interest that Bitcoin employs is Schnorr signatures. The security of Schnorr signatures rests on the same ECDLP, but it gets there with a different construction. Once again, since Schnorr is a valid signature scheme it fits into the same $\texttt{Gen}$/$\texttt{Sign}$/$\texttt{Vrfy}$ template. However, since $\texttt{Gen}$ here is identical to the ECDSA case, I will focus only on $\texttt{Sign}$ and $\texttt{Vrfy}$, since this is where Schnorr diverges.

Similar to ECDSA, Schnorr has the same idea with $\texttt{Vrfy}$: reconstruct something from the signature and public key, then check it matches. For example, substituting $P = dG$:

Thus $I^\prime$ reconstructs to the same point you started with, and therefore $\operatorname{hash}(I', m) = r$ and the verification passes. To fake this without knowing $d$, you would again either have to guess $k$ in advance or recover $d$ directly from $P = dG$, which is the same ECDLP problem as ECDSA.

What’s the point of having two different signature schemes? Isn’t one sufficient? Both schemes reduce to the same hard problem: recovering $d$ from $P = dG$ is ECDLP either way.

However, there’s one small step in the middle where they diverge, and it ends up mattering a lot. ECDSA sets $r \gets F(kG)$, which is just the x-coordinate. On the other hand, Schnorr sets $r \gets \operatorname{hash}(I, m)$. It runs $I$ through a hash first, and that’s why one scheme can be provably secure while the other cannot.

A proof of security basically works by imagining an attacker who could forge a signature, then showing that attacker could be turned into a machine that solves ECDLP, which is supposed to be impossible. The trick used to build that machine needs to catch the forger reusing the same $kG$ but ending up with two different values of $r$. If that ever happens, you can subtract the two signing equations, the nonce $k$ cancels out, and you’re left holding $d$.

For Schnorr, a proof can actually force this to happen, because $r$ comes from a hash, and a hash is exactly the kind of thing a proof is allowed to just reassign (the proof treats the hash as a perfectly random function that it controls). The proof can run the forger twice with the same $I = kG$ and hand back a different $r$ the second time. So an attacker who could reliably forge signatures could be forced into producing exactly this situation, two valid responses to the same $kG$, which is enough to extract $d$ directly. That contradicts ECDLP being hard, so no such attacker can exist. Forging a Schnorr signature is provably as hard as solving ECDLP (as long as the hash behaves like that perfectly random function) [8].

ECDSA can’t use this same argument. $r$ is just the $x$-coordinate of $kG$, which is fixed the moment $kG$ exists, so there’s no way to force a second value of $r$ out of it. This doesn’t mean ECDSA is unprovable in principle, just that this specific method doesn’t work, and decades later, nobody’s found a different one that works from ECDLP alone either.

So from a pure security standpoint, Schnorr wins, and it’s older (1989 vs 1992 for ECDSA [5]). Given that, you’d expect Bitcoin to have used Schnorr from day one. It didn’t, and the reason is historical. Schnorr patented his scheme [9] shortly after it was published in 1989 [10]. Around that time, NIST needed a standard digital signature algorithm but didn’t want to license someone else’s patent. So they went with DSA, which is widely seen as designed to get around Schnorr’s patent (though Schnorr argued it didn’t). ECDSA is DSA carried over to elliptic curves. The key change was swapping Schnorr’s hashed $r$ for just the $x$-coordinate of $kG$, which also meant the proof technique above no longer works. The patent expired in 2008, shortly before Bitcoin launched, but by then ECDSA was already the standard, so that’s what Bitcoin used. Schnorr signatures were not introduced into Bitcoin until 2021 [11].

The security proof was one reason Bitcoin eventually added Schnorr, but the bigger reason was a practical one. Schnorr’s signing equation

is linear in $d$ and $k$, meaning that different people’s signing equations can be added together. For example, three people can work together to produce a single $(r, s)$ pair that looks exactly like a one-person signature (this takes a special protocol, not just adding three finished signatures). The analogous step for ECDSA has a $k^{-1}$ sitting in front of it, which breaks this property.

That was all of the cryptography I had planned to cover, and I hope it was useful. Both signature schemes Bitcoin uses come down to the Elliptic Curve Discrete Logarithm Problem (ECDLP): recovering $d$ from $P = dG$. Next I’m going into Bitcoin itself and how it works.