Skip to main content
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<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.
fgrieu
  • 141.5k
  • 12
  • 310
  • 593