What is the "existential forgery" attack on schoolbook RSA signatures, and why must the public key be authenticated?
Eve picks any random value $s$, computes $M = s^e \bmod N$ from Bob's public key, and the pair $(M, s)$ then passes RSA verification even though Bob never signed $M$ — a "signature first, message second" forgery.
* Signature first, message second: running verification backwards yields a valid pair for a junk message the signer never chose. *
Schoolbook RSA verification is symmetric to signing: Bob signs with $s = M^d \bmod N$, and a verifier checks by recomputing $M = s^e \bmod N$. Because the public exponent $e$ is known to everyone, an attacker can run that check backwards — choose the signature first and let a matching message fall out:
- Eve takes Bob's public key $(N, e)$.
- Eve picks a random $s$.
- Eve computes $M = s^e \bmod N$.
- Eve sends $(M, s)$ to Alice, who verifies $s^e \bmod N = M$ ✓.
The forgery succeeds because nothing ties the message to Bob's secret — any $s$ yields some valid-looking $(M, s)$. What saves naive RSA in practice is that Eve cannot choose $M$: it comes out as a random-looking number, so the chance of it being a meaningful, structured document (headers, encoding, language) is negligible. The real cure is to break the symmetry that makes the attack possible — hash-then-sign with padding (e.g. RSA-PSS / PKCS#1), so Bob signs $h(M)$ inside a fixed format. Forging then requires a preimage of $h$ that also satisfies the padding, which is computationally infeasible.
This is also why the public key itself must be authenticated via PKI/certificates: if Eve can pass off her own key as Bob's, she signs anything legitimately and the forgery math no longer matters. Authenticity of $(N, e)$ is the boundary this attack pushes on.
Go deeper:
Digital signature forgery — existential forgery — the formal attack hierarchy (existential, selective, universal) and where this one sits.