1
$\begingroup$

Confused about RSA message cipher: $c = m^e (mod\ n)$

So if $m^e$ can be greater than n, then you can get duplicate ciphers for the same message. Most postings I've read say that $m^e$ must always be smaller than n to counteract.

But if $m^e$ is smaller than n, then $c = m^e$ and can just be decrypted by $\sqrt[e]{c}$. Most postings I've read said that $m^e$ should be greater than n to counteract.

So it seems like there are only 2, differently broken, options. How is this reconciled in practice? (My assumption is that "padding" reconciles this, but I'm not sure how.)

$\endgroup$
6
$\begingroup$

Due to poor use of notation, the question uses an incorrect (or at least incomplete) definition of textbook RSA encryption, which actually defines ciphertext $c$ for a given $m$ as:$$c=m^e\bmod n$$This can be read as: “ $c$ equals [pause] $m$ to the $e$th power reduced modulo $n$ ” where power or/and reduced can be left implied, and the pause emphasizes that $c$ is the result of the final modular reduction. It means that $c$ is the remainder of the Euclidean division of $m^e$ by $n$, which unambiguously defines $c$ for given $m\ge0$, $e>0$, and $n>0$. It equivalently means that $0\le c<n$ and $c\equiv m^e\pmod n$, as defined below.

The notation $c\equiv m^e\pmod n$ can be read as: “ $c$ is equivalent to $m$ to the $e$th power [pause] modulo $n$ ” where the pause emphasizes that modulo pairs with the earlier equivalent, rather than with an implied reduction. For non-zero $n$, it means that $m^e-c$ is a multiple of $n$. There are infinitely many $c$ matching this.

Notation rule: when $\mod\;$ is without an opening parenthesis immediately on its left, and without an $\;\equiv\;$ sign anywhere on its left, it means reduction modulo, or equivalently remainder. Otherwise, it tends to mean equivalence modulo. The later is unambiguous when $\mod\;$ is with an opening parenthesis immediately on its left, and with an $\;\equiv\;$ sign somewhere on its left.


Indeed, in order to avoid guess of $m$ as $\sqrt[e]c$, it is necessary that $m^e\ge n$ holds, at least with overwhelming odds. The recommendable method to ensure this is not to directly avoid small $m$; rather, it is to pick $m$ essentially as a random integer with $0\le m<n$. It is safer, and practiced, to choose $m$ in the later way, and then use $m$ as a key to a symmetric cipher protecting the confidentiality of the actual message. Other methods exist that allow conveying with $c$ a small message $M$ reversibly turned into an integer $m$ that is random enough, see PKCS#1 encryption schemes.

$\endgroup$
  • 1
    $\begingroup$ Sorry that I have difficulty to understand your sentences "... pick m ... as a random integer with 0 <=m<n..." and "... use m as a key to a symmetric cipher ...". If n, as commonly recommended today, is of the order of 2000 bits, that would imply using a really huge symmetric key in most cases, wouldn't it? (Common symmetric ciphers have on the other hand fairly small and rather fixed key sizes.) $\endgroup$ – Mok-Kong Shen Jul 7 '16 at 18:18
  • $\begingroup$ @Mok-KongShen: indeed, one can not directly use $m$ as a key to a standard symmetric cipher, like AES in some mode. First, $m$ would go thru a key derivation function. That could be: apply SHA-256 to a representation of $m$ as octet string of prescribed size, and use the hash as key for AES in some mode. In a hurry, keeping the low 256 bits of $m$ would do. $\endgroup$ – fgrieu Jul 7 '16 at 18:37
  • 1
    $\begingroup$ Using RSA not directly to encrypt plaintext but to transfer a secret key of a block cipher is certainly the "standard" and processing-efficient way. However (1) Not all encryption applications need very high processing efficiency, (2) The additional involvement of a block cipher and hashing IMHO complicates the entire matter both in coding and conceptually (for understanding of the users). Hence I have a code (destined for the common users who have only small volumes of plaintexts to encrypt) that involves basically nothing but RSA in Ex.3 and 3S of s13.zetaboards.com/Crypto/topic/7234475/1/ $\endgroup$ – Mok-Kong Shen Jul 8 '16 at 9:32
5
$\begingroup$

So if $m^e$ can be greater than n, then you can get duplicate ciphers for the same message.

I'm not exactly certain what you mean, but:

  • If you mean that one particular message $m$ might be encrypted in two different ways, no, that's not the case, at least, not in the way that you mean. If you have a specific value for $m$, $e$ and $n$, then $m^e \bmod n$ has a unique value between 0 and $n-1$. Now, this "one particular message may be encrypted in multiple ways" is a property we actually do want; in practice, we handle it in the padding (which maps the message we actually want to encrypt to the value we present to the RSA algorithms).

  • If you mean that there might be two distinct messages $m_1$ and $m_2$ that would encrypt to the same ciphertext, no, that's not the case (unless $e$ happens to not be relatively prime to $\phi(n)$; when we select $e$ and $n$, we are always take care to make sure that $e$ and $\phi(n)$ are relatively prime).

Most postings I've read said that $m^e$ should be greater than n to counteract.

That is indeed the case; in fact, deliberately selecting a small $m$ is a bad idea (because it may allow other attacks based on the homomorphic properties of RSA).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.