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

Question

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.

Answer 1

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:

• Textbook ElGamal and RSA Encryption are Insecure, Dan Boneh, Antoine Joux, Phong Q. Nguyen, ASIACRYPT 2000.

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

• Twenty years of attacks on the RSA cryptosystem, Dan Boneh, Notices of the AMS, vol 46 no 2, pp.203-213, 1999.