11
$\begingroup$

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^\text{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^\text{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^\text{th}$ root attack to $C'$. Perhaps they choose $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 (and inefficient) extension to the $e^\text{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^\text{th}$ root for small $k$. That's independent, but only marginally extends the range of vulnerable $m$, as far as I can tell.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Apr 17, 2013 at 17:49
  • $\begingroup$ @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 (update: which now is deleted). $\endgroup$
    – fgrieu
    Apr 17, 2013 at 22:22

2 Answers 2

1
+100
$\begingroup$

For $e$ of moderate size (say $e=17$), Coppersmith's theorem makes it possible to go significantly beyond message size $n/e$.

Take for example a message $M$ of size $m=160$ bits and a modulus of $n=2048$ bits with exponent $e=17$. I can guess the top 40 bits $\textrm{MSB}_{40}(M)$ of $M$, and solve for the remaining 120 bits using Coppersmith applied to the polynomial $f(x) = (A+x)^e - C$ modulo $N$, with $A=2^{120}\cdot \textrm{MSB}_{40}(M)$. $2^{40}$ executions of Coppersmith's algorithm are surely much cheaper than GNFS for 2048 bits, and since this uses little memory, this is also most likely much better than the meet-in-the-middle attack. (I often give this as an exercise to students in the case $m=128$).

Note that this is the correct way of guessing bits in that setting, as opposed to enumerating $\lfloor M^e/N\rfloor$ which is much larger.

This line of attack doesn't help much for larger exponents like $e=65537$, however, and even for $e=17$, I don't know how to push things to message size $m=256$.

$\endgroup$
3
  • $\begingroup$ Right and nice. This seems to combine with a technique I suggest (hoping that $M$ is divisible by some small integer $s$ and apply the attack to $C'=C\cdot s^{-e}\bmod N=(M/s)^e\bmod N$ instead of $C$, for various small $s$). I wonder what the best balance is between trying more $s$ and guessing more bits of $M'=M/s$, and how large that makes a recommendable $m$ for say $e=3$. $\endgroup$
    – fgrieu
    Sep 27, 2023 at 10:38
  • $\begingroup$ It seems to me that hoping $M$ is divisible by some small integer of say $\ell$ bits is essentially equivalent entropy-wise to hoping that the top $\ell$ bits of $M$ are zero, so it basically enters as an additive term in the log-success probability $k$. $\endgroup$ Sep 28, 2023 at 0:54
  • 1
    $\begingroup$ To protect against the approach above, the bound on $m$ should be something like $m\geq n/e+\lambda(n)+k$ where $\lambda(n)$ is the bit complexity of GNFS for bit size $n$ (one could subtract the bit complexity of Coppersmith from that, but I wouldn't: attacking many similar polynomials is actually faster than trivial repetition thanks to tricks like LLL chaining). There is no term for $r$, because it is equivalent (actually a bit faster) to recover more bits of a single message vs. fewer bits of one of several messages. For $e=3$, $n=2048$ and $k=40$, this gives $m\gtrsim 835$. $\endgroup$ Sep 28, 2023 at 0:59
6
$\begingroup$

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:

$\endgroup$
3
  • $\begingroup$ 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$? $\endgroup$
    – fgrieu
    Apr 17, 2013 at 22:05
  • $\begingroup$ 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! $\endgroup$
    – D.W.
    Apr 17, 2013 at 23:01
  • $\begingroup$ And thank you @D.W. for pointing the fully relevant "Square-root" attack. $\endgroup$
    – fgrieu
    Apr 17, 2013 at 23:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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