What use is the signature without the message under RSA?

Using RSA for signing & verification, is there a way to take a valid signature for an unknown message, and for someone else to generate a valid signature using a different key against the valid signature, given knowledge of the original public key?

First, let me describe how I understand signing/verification with RSA:

You start with a keypair with modulous $N$ that is the product of two large primes, along with integers $e$ and $d$ such that $e d ≡ 1 \pmod {\varphi(N)}$, where $\varphi$ is the Euler phi-function. The signer's public key consists of $N$ and $e$, and the signer's secret key contains $d$.

To sign something, the signer computes $\sigma ≡ m^d \pmod {N}$. To verify, the receiver checks that $\sigma^e ≡ m \pmod N$.

What are the risks to making $\sigma$ public, if $m$ is kept secret, along with the signers private key, $d$?

The public key, $N$ and $e$, is public, as is $\sigma$, the signature.

$\sigma^e$ is easily calculatable, which gets us $m \pmod N$, but not $m$ itself.

Given $m \pmod N$ but an unknown $m$, what can we do with it?

Can a second signer, with public key $N^{\prime}$ and $e^{\prime}$, and private key $d^{\prime}$ be used to generate $\sigma^{\prime} = m^{d^{\prime}} \pmod {N^{\prime}}$?

How resistant to brute forcing is that? How about if some sort of verification oracle is available?

Since $m \pmod N$ is lossy, without $m$ (or more likely $\text{pad}(\text{hash}(m))$ in practice), is anything about $m$ recoverable?

Is there another system for signing whose signatures are of less use without the message?

• You'll be wanting to look into padding schemes and the difference between PKCS#1 v1.5 and PSS padding. – Maarten - reinstate Monica Apr 7 '15 at 2:29

If we signed a secret message $m$ by publishing its signature $σ$ computed as $m^d\bmod N$, at least two very bad things would happen:

1. The message would not be so secret anymore
That's because anyone knows the public key $(N,e)$, and thus from $σ$ can compute $σ^e\bmod N$, which is $m\bmod N$. This reveals a lot of information about $m$, which goes straight against the requirement to keep $m$ secret. In modern cryptography, the adversary succeeds if she learns anything about a secret message (except its length), and $m\bmod N$ qualifies. For example:
• $m\bmod N$ allows (with overwhelming odds) to recognize $m$ among a moderate list of arbitrary messages.
• If $m$ is shorter than $N$ then $m\bmod N$ is $m$ and thus $m$ is no longer secret at all (this occurs when $m$ is less than $256$ bytes for $2048$-bit $N$, a common size).
• If (as in the question) it is computed and published the signature $σ'$ of the same $m$ according to a different RSA key $(N',e')$, then this reveals $m\bmod N'$. By the Chineese Remainder Theorem we can efficiently compute $m\bmod(N\;N')$, and this reveals $m$ if it's size is less than the sum of the size of $N$ and $N'$, extending the above to longer messages than was possible with a single signature.
• If $m$ is known except for a segment shorter than $N$ (that is $m=m_0\|m_1\|m_2$ with $m_0$ and $m_2$ known, and $m_1$ shorter than $N$), from $m\bmod N$ it is easy to find $m_1$, thus $m$, as follows: if $|m_i|$ is the number of bits in each segment of $m$, we have $m\bmod N=\big((m_0 2^{|m_1|}+m_1)2^{|m_2|}+m_2\big)\bmod N$ thus $m_1=\big((m\bmod N)-m_0 2^{|m_1|+|m_2|}-m_2\big)2^{-|m_1|}\bmod N$ where $2^{-|m_1|}$ is the multiplicative inverse of $2^{|m_1|}$ modulo $N$, which is easily computed using the Extended Euclidian algorithm.
2. It would be easy to make forgeries
In particular, for small to moderate $e$ (including $e=3$ and $e=2^{16}+1$, often used in practice), it would be possible to forge a large class of messages, including C strings showing as anything desired. For any $m_0$, it is easy to exhibit $m_1$ such that $m=m_0||m_1$ is the (non-modular) $e$-th power of a known integer $σ$ (compute $σ=\Big\lceil\sqrt[e]{m_0 2^{2e|N|}}\Big\rceil$ and $m_1=σ^e-m_0 2^{2e|n|}$ of size $2e|N|$ bit); this $σ$ verifies as the signature for $m$; and $m$ prints the same as $m_0$ if $m_0$ is a zero-terminated C-string.

Rather, good and common practice in order to RSA-sign a confidential message is to:

1. Encrypt and sign (or sign and encrypt)
Encipher the message (typically using a symmetric algorithm such as AES in CTR mode with random IV), then RSA-sign the cryptogram (ciphertext, rather than the plaintext), e.g. as in 2 below; or transform the message into a signed message (again e.g. as in 2 below), then encipher that whole signed message.
Note: if possible, use encrypt-then-sign. If for some reason sign-then-encrypt must be used, make sure to encrypt the signature even if it is randomized; pay care that deciphering of any invalid ciphertext can not trigger undesirable behavior on the receiver side; and pay care that signature verification of partially invalid messages does not leak information about the message.
2. (and) Use a signature scheme with hash-based padding
In order to RSA-sign a message $m$ (confidential or not), signature must NOT be computed as $σ=m^d\bmod N$, which would be an unsafe use of textbook RSA. Rather, one might (there are other secure ways)

• compute $h=H(m)$ for some hash function $H$ like SHA-256, with $h$ what will actually be signed (albeit still not using textbook RSA, as it could be vulnerable to forgery if the adversary could obtain the signature of chosen messages)
• appropriately pad $h$ into a so-called message-representative $r$ with $0<r<N$ by some method (possibly involving adding randomness), the most common such methods being RSASSA-PSS and RSASSA-PKCS1-v1_5 in PKCS#1;
• compute the signature as $σ=r^d\bmod N$
• build the signed message as $m\|σ$ (that is, append the signature); the verifier will extract $m$ and $σ$ from $m\|σ$, compute $h=H(m)$, compute $r=σ^e\bmod N$, and check $r$ against $h$ according to the padding method.