How does recovering a message from a signature, as described by RSA, prove that the message was signed with a private key?

Question

In the original RSA paper, in the section that describes digital signatures, the authors write, “He [Bob] need not send M as well; it can be computed from S.” Then, a few sentences later, “Bob cannot later deny having sent Alice this message, since no one else could have created S = D_B(M).”

But Bob’s encryption procedure E_B can be applied to any S to produce some M. That is, S could be manufactured from whole cloth, and you’d still get an M from E_B(S), albeit gibberish.

How then does merely recovering M from S, as described by the authors, prove that D_B was applied to M to produce S? Is legibility alone a strong enough proof of M having been signed by D_B?

If M (or a hash of M if you want to nitpick) were included in the message alongside S, then you'd have something to compare the result of E_B(S) to. But if only S is given, I don’t understand where the proof comes from.

This question is purely academic. I have no intention of using digital signature as conceived in the original paper in a practical implementation.

Answer 1

How then does merely recovering $M$ from $S$, as described by the authors, prove that $D_B$ was applied to $M$ to produce $S$?

It does not¹. As pointed in the question, $M$ could have been produced from a random $S$.

Is legibility alone a strong enough proof of $M$ having been signed by $D_B$?

No. It's easy to build counterexamples, for various plausible definitions of legibility. My favorite is that it can efficiently be built four pronounceable ASCII² byte strings $M_i$ of same sizable length with $M_0\,M_1=M_2\,M_3$, and then it is trivial to find $S_0$ from $S_1,S_2,S_3$. Thus the private key holder having signed $M_1,M_2,M_3$ can be wrongly accused of having signed $M_0$.

If $M$ (or a hash of $M$ if you want to nitpick) were included in the message alongside $S$, then you'd have something to compare the result of $E(S)$ to.

No. Sending $(M,S)$ and/or $(H(M),S)$ with $S$ computed as $S\gets M^d\bmod N$ does not help at all improve security: again, just pick a random $S$, compute $M\gets S^e\bmod N$, send $(M,S)$ or $(H(M),S)$. The verifier will accept it.

What does help is sending $(M,S')$ with $S'$ computed as $S'\gets H(M)^d\bmod N$, when $H$ is a wide hash. Verifier checks $S'\bmod N=H(M)$. That's the principle of Full Domain Hash, aka RSA-FDH. It's secure; but because an earlier (quantitatively weaker) security proof of RSA-FDH was deemed not strong enough, it was devised RSA-PSS, and its derivative RSASSA-PSS is used in practice.

---

¹ Academic cryptography was in its infancy, and back then it was considered acceptable to present as fact some bold, unproven, and occasionally wrong statement. Another claim in the paper was later disproved by ElGamal and Schnorr signature:

To implement signatures the public-key cryptosystem must be implemented with trap-door one-way permutations (…)

---

² That could perhaps even be made borderline meaningful. It would actually make a nice CTF, that I have not seen implemented: server textbook-RSA-signs (with 2048-bit and $e=2^{16}+1$ ) any ASCII/UTF8 byte string that some criteria (or "AI") deems acceptable, but not if it's on the tune of IOU$ followed by digits; the winner is who get the highest amount signed.