What use is the signature without the message under RSA? Using RSA for signing &amp; 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$.

( http://en.wikipedia.org/wiki/Digital_signature#How_they_work )

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?
Caution: the question assumes that the message $m$ can be larger than the public modulus $N$ and sent separately from the signature (perhaps, encrypted), contrary to textbook RSA as in the original article. The answer makes that assumption unless otherwise specified.

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:

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\mathbin\|m_1\mathbin\|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.


It would be easy to make forgeries
In particular, it would be possible to forge a large class of messages, including C strings showing as anything desired. For any $m_0$, $N$ and $e$, it is easy to exhibit $m_1$ such that $m=m_0\mathbin\|m_1$ verifies $\sigma^e \equiv m \pmod N$. Just choose $m_0$ ending with a terminating 0x00 bytes, decide a size $b$ of $m_1$ with $b$ multiple of 8 and $2^b&gt;N$, pick any $\sigma$, compute $m\gets m_0\,2^b+((\sigma^e-m_0\,2^b)\bmod N)$ ).

Note: in common textbook RSA, $m$ is not sent separately and is recovered as $m\gets\sigma^e\bmod N$, hence $0\le m&lt;N$. This makes the attack more difficult. However for small $e$, and when $|m_0|$ is small enough (roughly up to $\log_2(N/e)/e$ bit including terminating 0x00), we find $b\gets8\,\lfloor \log_2(N/(m_0+1))/8\rfloor$, compute $σ\gets\left\lceil\sqrt[e]{m_0\,2^b}\right\rceil$ and $m\gets σ^e$. This $σ$ verifies as the signature for this $m$, and prints the same as $m_0$.

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

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.

(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&lt;r&lt;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.