What is the difference between a signature scheme "with message recovery" and one "without message recovery," and why does it matter?

With message recovery (RSA) the message can be reconstructed from the signature alone; without it (DSA, Schnorr, ElGamal signatures) the message must be sent alongside the signature and verification only returns yes/no.

* Recovering m from s is what existential forgery exploits; discrete-log schemes send (m, s) and leak no message from s, blocking it by construction. *

In RSA, verifying $m = s^e \bmod N$ literally recomputes the message out of the signature — the message "falls out" of the check, so it need not be sent separately. That convenience is exactly what enables existential forgery: since any $s$ yields some $m = s^e \bmod N$, an attacker can fabricate a valid $(m, s)$ pair without ever signing. Schemes without message recovery (DSA, Schnorr, ElGamal Sig) instead compute a verification value from the message and signature together and compare it; you must already hold $m$ to verify, and the signature reveals no message on its own. Removing message recovery removes the very thing the forgery exploited, which is why these discrete-log schemes were designed that way.

RSA need not abandon message recovery to be safe, though: adding padding (PKCS#1-v1.5 or PKCS#1-v2.1) before signing imposes a fixed structure on the signed value, so a random $s^e \bmod N$ almost never decodes to a properly formatted message and the forgery fails. The trade-off is that with-recovery schemes can be more compact (no separate message to transmit), while without-recovery schemes resist this attack by construction.

Go deeper:

• Digital signature forgery — why message recovery is the property that hands an attacker existential forgery, and how padding closes it.