Digital signatures: Schnorr, ECDSA and how PS3 was hacked

In the previous post, we built up to the key equation: Public Key = x * G. A private key x, a generator point G, and a public key P that anyone can see but nobody can reverse. This post picks up exactly where that left off.

What is a digital signature?

You know how a handwritten signature works. You scribble something on a document and everyone agrees it proves you authorized it. Digital signatures do the same thing, except they're actually secure.

A digital signature has three properties:

Authentication - it proves the signer has the private key
Integrity - it proves the message hasn't been tampered with
Non-repudiation - the signer can't later deny signing it

In blockchain, every transaction you send is signed with your private key. The network verifies that signature using your public key - without ever learning the key itself. No trust needed. Just math.

There are two signature schemes that matter here: Schnorr and ECDSA. Schnorr is more "classic" math and easier to understand, so we'll start with it. ECDSA is the one everyone actually uses - for historical reasons we'll get into.

Bear with me.

1. Schnorr signatures: the ingredients

Quick refresher from the previous post. We have:

G - the generator point (public, same for everyone)
x - the private key (secret, a scalar)
P = xG - the public key (public, a point on the curve)

A Schnorr signature introduces one new ingredient: a nonce. This is a random number k, freshly generated for every single signature. Think of it as a one-time secret that makes each signature unique. Only the signer knows k — it is never revealed to the verifier, because anyone who learns k can trivially extract the private key from s = k + ex.

From k, we compute the nonce commitment:

R = kG

Just like the public key is k times G, the nonce commitment is k times G. Same operation, different secret. R is a point on the curve.

Signing

To sign a message m (in practice, m is the hash of the original message - a function like SHA-256 turns "hello world" into a fixed-size 256-bit number, so it can be used in math):

Step 1. Pick a random nonce k, compute R = kG

Step 2. Compute the challenge:

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

where H is a hash function (like SHA-256) and || means concatenation. The challenge e is a scalar - just a regular number, living in the same modular arithmetic space as the private key.

Step 3. Compute the signature scalar:

s = k + ex  (mod n)

where n is the order of the curve (the number of points in the group generated by G).

The signature is the pair (R, s).

Click "Next step" to walk through Schnorr signing

Why does e include P and R? (the chicken-and-egg thing)

You might wonder: if the challenge e depends on R (which the signer computes), can't the signer cheat by picking e first and then engineering R to match?

That's exactly why e is computed as a hash of R, P, and m together. The hash function makes it computationally impossible to pick R such that H(R || P || m) gives you a convenient e. You'd need to break the hash function to do it.

This also means there's a chicken-and-egg: you need R to compute e, and you need e to compute s. But you don't need e to compute R - R = kG is independent. So the order is: pick k, compute R, then compute e, then compute s. No contradiction.

One consequence: because e includes P, you can't recover the public key from a Schnorr signature alone. You need to already know P to verify. This is different from ECDSA, where public key recovery is possible - more on that later.

2. Schnorr verification: why it works

The verifier has: the message m, the public key P, and the signature (R, s).

Step 1. Recompute the challenge:

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

Step 2. Check whether:

sG = R + eP

If both sides are equal, the signature is valid.

That's the entire verification. Compute both sides of the equation, check if they match. Let's walk through why this works.

Click "Next step" to walk through Schnorr verification: sG = R + eP

P (public key) R (from signature) eP Result

Remember: on actual blockchains this math happens over finite fields, so the curve looks like scattered dots - not a smooth snake. This smooth curve is just to make the geometry easier to follow.

Algebraic proof (expand if you want to see the substitution)

We know that s = k + ex (mod n).

Multiply both sides by G:

sG = (k + ex)G
sG = kG + exG
sG = kG + e(xG)

But kG = R (nonce commitment) and xG = P (public key), so:

sG = R + eP

That's it. The equation checks out because of how s was constructed. The private key x is hidden inside s, combined with the nonce k in a way that the verifier can confirm without ever extracting either secret.

Why can't you fake it?

Three attack scenarios and why they all fail:

Attack 1: Forge without knowing x. You'd need to produce s such that sG = R + eP. Since e depends on R (through the hash), you can't choose R and e independently. You'd have to solve the discrete logarithm problem, which is computationally infeasible.

Attack 2: Reuse someone else's signature. The challenge e includes the message m. A different message produces a different e, which requires a different s. Old signatures don't work on new messages.

Attack 3: Modify the message after signing. Changing even one bit of m changes e (because hash functions), which breaks the equation sG = R + eP. Tampering is immediately detectable.

3. ECDSA: the one everyone uses

Schnorr signatures were invented in 1989 by Claus-Peter Schnorr. They're clean, efficient, and mathematically elegant. So naturally, the world didn't use them - because Schnorr patented the algorithm.

The patent expired in 2008, but by then ECDSA (Elliptic Curve Digital Signature Algorithm) was already the standard. ECDSA was designed as a patent-free alternative, and it's what Bitcoin, Ethereum, and most of the blockchain world run on. Bitcoin finally adopted Schnorr in the 2021 Taproot upgrade (BIP340), but ECDSA remains dominant.

ECDSA signing

Same ingredients: private key x, nonce k, message m. But the math is different.

Step 1. Pick random nonce k, compute R = kG. Let r be the x-coordinate of R.

Step 2. Compute:

s = k⁻¹(m + rx)  (mod n)

where k⁻¹ is the inverse of k (the number that satisfies k * k⁻¹ = 1 mod n - think of it as division in modular arithmetic).

The signature is (r, s).

Notice the difference: Schnorr uses s = k + ex, which is linear. ECDSA uses s = k⁻¹(m + rx), which involves a modular inverse. That k⁻¹ makes ECDSA fundamentally non-linear, and that non-linearity has consequences.

The r, s, and v of Ethereum

If you've looked at Ethereum transactions, you've seen three values: v, r, s.

r - the x-coordinate of the nonce point R = kG
s - the signature scalar from the formula above
v - the recovery ID (27 or 28, or 0/1 in EIP-155)

An ECDSA signature is 65 bytes: 32 bytes for r, 32 bytes for s, and 1 byte for v.

ecrecover: public key recovery

Here's something ECDSA can do that Schnorr can't: recover the public key from the signature alone.

Given (r, s, v) and the message hash m, the ecrecover function reconstructs the signer's public key P. This is possible because the ECDSA equation links r, s, m, and P in a way that lets you solve for P if you know the other three. The v byte disambiguates which of two possible points R was (since an x-coordinate on the curve maps to two y-values).

Ethereum uses ecrecover heavily. Instead of storing the sender's public key in every transaction, the network recovers it from the signature. This saves space and is why Ethereum addresses are derived from public keys rather than included explicitly.

Schnorr can't do this because the challenge e = H(R || P || m) includes P. You'd need to know P to compute e, which you need to verify the signature. Chicken and egg - but in Schnorr's case, it's a feature, not a bug.

4. Schnorr vs ECDSA

Property	Schnorr	ECDSA
Signature size	64 bytes (R, s)	65 bytes (r, s, v)
Equation	`s = k + ex`	`s = k⁻¹(m + rx)`
Linear	Yes	No
Batch verification	Native (via linearity)	Not natively
Malleable	No	Yes (needs low-s rule)
Key recovery	Not possible	Yes (ecrecover)
Signature aggregation	Yes (MuSig)	No

Why Schnorr's linearity matters

The Schnorr equation s = k + ex is linear in both k and x. This has a powerful consequence: signatures can be aggregated.

If Alice signs with s₁ = k₁ + ex₁ and Bob signs with s₂ = k₂ + ex₂, you can combine them:

s = s₁ + s₂ = (k₁ + k₂) + e(x₁ + x₂)

The result is a valid Schnorr signature for the combined public key P₁ + P₂. One signature, one verification, multiple signers. This is the foundation of multisig schemes like MuSig, and it's why Taproot transactions on Bitcoin are cheaper - an n-of-n multisig looks identical to a single-signer transaction on chain.

ECDSA can't do this. The k⁻¹ term makes the equation non-linear, so adding two ECDSA signatures together produces garbage.

Caveat: Naive Schnorr aggregation (just adding keys and nonces) is vulnerable to rogue-key attacks. Production schemes like MuSig and MuSig2 add a commitment round to prevent this. The linearity enables aggregation, but safe aggregation requires a protocol on top.

ECDSA malleability

ECDSA has a quirk: for any valid signature (r, s), the pair (r, n - s) is also a valid signature for the same message. This is called signature malleability - a third party can "flip" your signature without knowing your private key.

This caused real problems. On early Bitcoin, malleability allowed transaction IDs to be changed after broadcast (since the txid included the signature), which broke systems that tracked transactions by ID.

The fix: the low-s rule (BIP 62, and later EIP-2 for Ethereum). Valid signatures must have s in the lower half of the range (s <= n/2). If s is in the upper half, the signer must replace it with n - s. This makes each signature unique and eliminates malleability.

Schnorr doesn't have this problem. The signature includes the full point R (not just an x-coordinate), so there's no ambiguity to exploit.

5. The nonce catastrophe

Everything above assumes one thing: the nonce k is unique and secret for every signature. If it's not, you're gonna have a bad time.

Nonce reuse in Schnorr

If you sign two different messages m₁ and m₂ with the same nonce k:

s₁ = k + e₁x
s₂ = k + e₂x

Subtract:

s₁ - s₂ = (e₁ - e₂)x

Solve for the private key:

x = (s₁ - s₂) / (e₁ - e₂)

Two signatures, same nonce, your private key is gone. Simple division.

Nonce reuse in ECDSA

Same disaster, slightly different algebra:

s₁ = k⁻¹(m₁ + rx)
s₂ = k⁻¹(m₂ + rx)

Since k and r are the same (same nonce means same R, same r):

s₁ - s₂ = k⁻¹(m₁ - m₂)
k = (m₁ - m₂) / (s₁ - s₂)

Once you have k, extract x:

x = (s₁k - m₁) / r

Game over.

The PS3 hack: a real-world catastrophe

This isn't theoretical. In 2010, fail0verflow demonstrated this exact attack against Sony's PlayStation 3.

Sony used ECDSA to sign all PS3 software updates and games. The private signing key was the ultimate safeguard - without it, nobody could produce valid signed code for the console. The entire security model depended on that key staying secret.

The problem: Sony's implementation used a static nonce. Not a weak random number generator, not a biased nonce - a constant. Every single signature Sony produced used the same value of k. That means anyone with two signed firmware updates could apply the algebra above and extract Sony's private signing key. And that's exactly what happened.

With the key, anyone could sign arbitrary code and run it on any PS3. The console's entire code-signing security model was broken - permanently and irreversibly. Sony couldn't fix it with a software update because the compromised key was the root signing key. Every PS3 ever manufactured trusted that key. The hardware couldn't be patched.

The fix: deterministic nonces (RFC 6979)

The root cause of these catastrophes is relying on a random number generator to produce k. If the RNG is broken, biased, or reused, the private key leaks.

RFC 6979 eliminates this by making the nonce deterministic: k = HMAC(x, m) - derived from the private key and the message using HMAC. The same message and key always produce the same k (so signing is reproducible), but different messages produce different k values (so there's no reuse). No randomness needed, no RNG to fail.

Most modern ECDSA implementations use RFC 6979 or something equivalent. Schnorr (BIP340) similarly recommends deterministic nonce generation.

Wrapping up

So that's digital signatures. A private key, a nonce, a hash, and some elliptic curve arithmetic - and you get a proof that someone authorized something without ever revealing their secret. Schnorr does it with a clean linear equation, ECDSA does it with a modular inverse and a patent-free workaround that became the global standard. Both break catastrophically if you reuse a nonce, and both work beautifully if you don't.

If you made it through this and the previous post, you now understand the core cryptography underneath every blockchain transaction. Not bad for someone who doesn't like math.