10 of 19
replaced http://crypto.stackexchange.com/ with https://crypto.stackexchange.com/

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.
1. 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 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.
fgrieu
• 141.5k
• 12
• 310
• 593