An existential forgery attack creates at least one message–signature pair that verifies without possessing the private signing key. The attacker does not choose the message beforehand; any valid pair is sufficient. section 9.3
Schoolbook RSA makes the failure concrete. A signer computes s = m^d mod n, and verification checks s^e mod n = m. An attacker can instead choose a random signature s, calculate m = s^e mod n, and submit the resulting pair. Verification reproduces the same m, so the pair appears authentic. section 9.4
The attack and its defenses follow a short sequence:
- Choose a candidate signature value without first selecting a message. section 9.4
- Compute the corresponding message with the public operation m = s^e mod n. section 9.4
- Submit the calculated message and signature as a valid-looking pair. section 9.3
- Enforce padding and formatting rules so randomly inverted messages almost never have an acceptable encoding. section 9.4
Equation 9.3
\[\begin{aligned} \begin{aligned} s\prime &= \text{Verify}(m, s, \text{PubKey}_{\text{Alice}}) \\ s\prime &= s^e \bmod n \\ s\prime &= (m^d)^e \bmod n \\ s\prime &= m \bmod n \end{aligned} \label{equation:alice-rsa-verify} \end{aligned}\]Follow the RSA verification equation to see why applying the public exponent to the attacker’s chosen signature reconstructs the calculated message. section 9.4
