Forgery attack against Textbook RSA with simple redundancy I know how to forge vanilla Textbook RSA message signatures (easy).

I've learnt that by adding a good redundancy to the message, it cannot be forged anymore.

How can one add redundancy so that the message could be recovered from the signature (RSA with message recovery), and cannot be forged (meaning the redundancy function is "good")?

For example, a redundancy function which adds a 00...0 sequence in the beginning

of the message is considered not secure because it's easy to forge. (How?)
The usual methods of RSA signature with message recovery (that is, embedding a part of the message in the signature, known as the revoverable message) are those in ISO/IEC 9796-2:2010 (partial preview). There are three:


Scheme 1; it is an ad-hoc scheme that essentially concatenates the recoverable message, the hash of the whole message, and a little fixed data (about two bytes when there's more to the message than the recoverable part), forming the padded message; to which the raw RSA private function is then applied. This scheme is insecure if the adversary can obtain the signature of many chosen messages, see Jean-Sebastien Coron, David Naccache, Mehdi Tibouchi and Ralf-Philipp Weinmann, Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures, in proceedings of Crypto 2009; or full PDF
Scheme 2; in addition to hashing, it uses salting and an unbalanced two-rounds Feistel construct using a Mask Generation Function, so that the input of the raw RSA private function is indistinguishable from random (except for about two bytes, and without knowledge of the salt assumed random). It aims at demonstrable security similar to (and by the same means as) the Probabilistic Signature Scheme introduced in version 2 of PKCS#1, and pioneered by Mihir Bellare and Phillip Rogaway: The exact security of digital signatures - how to sign with RSA and Rabin, in proceedings of Eurocrypt 1996; or better PDF.
Scheme 3; that's precisely scheme 2 with no salt. It is deterministic (when the size of the recoverable portion of the message is fixed), and has the same message embedding capacity as scheme 1. It has the demonstrable security of Full Domain Hash; see Jean-Sébastien Coron, On the Exact Security of Full Domain Hash, in proceedings of Crypto 2000, or better PDF.




Noticing that left-padding a message $M$ with zero bits leaves its value unchanged when bitstrings are assimilated to integers using big-endian conventions (as customary), the last paragraph of the question asks how to attack the trivial RSA signature scheme giving message recovery where


the signature of message $M$ is defined as $\mathcal S(M)=M^d\bmod N$ (just as in vanilla Textbook RSA message signature), restricted to $M$ of (perhaps: at most) $m$ bits with $m$ fixed, positive, and such that $m\ll \log_2N$;
the verification procedure recovers $M$ from $\mathcal S(M)$, as $M=\mathcal S(M)^e\bmod N$, then checks that $M&lt;2^m$ (that is, checks the padding consists of zero bits).


Another way to look at this is: vanilla Textbook RSA message signature, with the message omitted (as it can be recovered from the signature), and restricted to be exactly (or at most) $m$ bits.

Just as in vanilla Textbook RSA message signature, it is easy to make an existential forgery out of nothing, in the sense that the message consisting of $m$ bits at zero has signature $0$, and the message consisting of $m-1$ bits at zero followed by a single bit at one has signature $1$. Also, if the public exponent $e$ is small, for any positive integer $S$ less than $2^{m/e}$, $S$ is the signature of message $M=S^e$.

Just as in vanilla Textbook RSA message signature, it is easy to make a forgery for a large fraction of valid messages $M$ one wishes to obtain a signature for, when having access to a signing oracle (that is, mean to obtain signature of any desired valid message, except for the messages subject to forgery). One method is to try to factor $M$ into $M_0\cdot M_1$ for $1&lt;M_0\le M_1$, which is possible for a large fractions of messages $M$ (including all even $M\ge4$, and more generally all $M$ divisible by a small prime and larger than this prime). It holds that $\mathcal S(M_0)\cdot\mathcal S(M_1)\bmod N=\mathcal S(M)$, and that allows computing the signature of $M$ from that of $M_0$ and $M_1$.

Note: a former version of the present answer explained how to forge a slightly less vulnerable trivial RSA signature scheme giving message recovery, which (it turned out) did not match that intended in the question.