# In textbook RSA with low public exponent, how big does a random message needs to be?

Assume RSA with a public modulus $N$ of $n$ bits, a small odd public exponent $e$, plaintext $M$ a random non-negative integer less than $2^m$ for some integer parameter $m$, with $M\mapsto C=M^e\bmod N$ (textbook RSA) used for encryption. Inasmuch as it matters, assume there are $2^r$ ciphertexts available to the attacker, and her goal is to recover one plaintext with odds better than $2^{-k}$. If necessary also assume $n\ge1024$, $e\le2^{16}+1$, $r\le30$, $k\ge40$, or/and $M$ is of exactly (rather than at least) $m$ bits.

If $M^e<N$, then $M^e\bmod N=M^e$ and thus $M=C^{1/e}$, making decryption trivial by $e$th root extraction. $m\ge n/e+k+r$ makes us safe from trying that for each available ciphertext; but not necessarily against improvements, or other attacks.

Up to what bound for $m$ do we know an attack better than factoring $N$ using GNFS?

As an aside: starting with what bound for $m$ (if any) is there a positive security argument?

Updates (main question, now highlighted, remains without an answer proposing a bound):

As rightly pointed by D.W.'s in this answer, regardless of $e$, we must also have $m$ big enough to resist being found by "square-root" attack, a "meet-in-the-middle" search using a space/time tradeoff. To be safe from that we can make $m\ge a+b+k$ where the adversary is powerful enough to make $a$ accesses to a memory system of $b$ bits, say $m\ge 90+70+k$.

There is a simple extension to the $e$th root attack: the adversary hopes that an $M$ is divisible by some small integer $s$ of her choice, computes $C'=C\cdot s^{-e}\bmod N=(M/s)^e\bmod N$, then applies the $e$th root attack to $C'$. Perhaps she chooses $s$ as the successive primes, or some better method. This considerably extends the range of vulnerable $m$ (to, uh..).

Note: I assume all plaintext is random and independent, and the adversary has no access to a decryption oracle (even limited to revealing messages other than the originals and with at most $m$ bits).

Another simple extension to the $e$th root attack: the adversary hopes that $k=\lfloor M^e/N\rfloor$ is small enough to be enumerable, and tests if $C+k\cdot N$ is an $e$th root for small $k$. That's independent, but only marginally extends the range of vulnerable $m$, as far as I can tell.

-
For a positive security argument, I would think that the best approach is not to pour lots of resources into analyzing textbook (unpadded) RSA, but rather to adopt a padding scheme for which we do have positive security arguments. –  D.W. Apr 17 '13 at 17:49
@D.W.: Very right. Of course I do not plan to use textbook RSA for unpadded (even random) messages, I'm asking this question as an extension of this homework. –  fgrieu Apr 17 '13 at 22:22

Related messages. If you have (the encryptions of) a pair of messages that differ by a known fixed difference, then the Franklin-Reiter related message attack can be used to recover both messages. The running time of the attack is something like $O(e^2 n^2)$. This does not apply if the messages are independent and there are no known relationships between them.

Coppersmith's theorem. Coppersmith's theorem might be relevant. Roughly speaking, it says that if you have a monic polynomial $f(x)$ of degree e, then you can find all solutions to $f(x)=0 \pmod N$ satisfying $0 \le x < X=N^{1/e}$ in polynomial time, using a lattice technique. By defining $f(x)=x^e-C$, this can be used to recover $M$ if it is known that $M<N^{1/e}$. Therefore, it looks like this does not improve upon the trivial $e^{\textrm{th}}$ root extraction root method. I don't know if the attack can be improved by continuing to use his lattice methods even for a larger value of $X$.

Square-root attack. There is also a meet-in-the-middle style attack whose running time is $O(2^{m/2})$. If $e=3$ it will be dominated by other attacks, but it may be more relevant for larger values of $e$. The meet-in-the-middle attack is described by Boneh et al. (see below); basically, we hope that $M$ can be written as $M=M_1 M_2$ where $M_1,M_2 \le 2^{m/2}$, and we try to find $M_1,M_2$. To find them, we build a table of $C/M_1^e \bmod N$ for all candidate $M_1$ values, then for each candidate at $M_2$, we look up $M_2^e$ to see if it is present in the table.

This is described in Section 5 of the following paper:

Published work. A good summary of the above attacks can be found in this paper:

-
The "Square-root" attack indeed sets another required minimum for $m$, independent of $e$, and higher than the $n/e+k+r$ minimum for all but very small $e$. I do not see that the other attacks are more effective than the $e^{\operatorname{th}}$-root attack. Note: in the "Coppersmith's theorem" section, was $e$ meant instead of $3$? –  fgrieu Apr 17 '13 at 22:05
Thanks, @fgrieu, you are completely correct. I was being a little bit sloppy and thinking primarily of $e=3$. I've edited my answer to apply to general $e$, based upon your comments. Thanks for the helpful comments! –  D.W. Apr 17 '13 at 23:01
And thank you @D.W. for pointing the fully relevant "Square-root" attack. –  fgrieu Apr 17 '13 at 23:05