This is a simplified version of a question I made long ago, that never got an accepted answer.

It's given $N$ of $n=2048$ bit, assumed hard to factor, which two prime factors each are $\equiv2\pmod3$, so that the public exponent $e=3$ is usable. It's also given $C\in[0,N)$, known to have been obtained as $C=M^3\bmod N$ for random $M$ of exactly $m$ bits, that is $M\in[2^{m-1},2^m)$, for some public parameter $m$.

Up to what $m$ can we realistically find $M$, in say a day on a standard PC?

Here are the attacks I see so far:

  1. If $m<\lfloor n/3\rfloor$ that is $m<682$, it holds $M^3<N$ thus $M=\sqrt[3]C$, which can be readily computed.
  2. For very slightly larger $m$, it holds $M=\sqrt[3]{x\,N+C}$ for small $x\in\mathbb N$ and we can enumerate $x$ and test $x\,N+C$ until one is a cube. For $m=n/3+k$ the effort grows as $\mathcal O(8^k)$, thus this can't extend the range for $m$ much.
  3. As an improvement of 2, it's possible to skip many $x$ in the search by observing that when $u\equiv1\pmod 6$ is prime, then $x\,N+C\bmod u$ is among a set of only $(u+2)/3$ values: $\{0,1,6\}$ for $u=7\,$, $\,\{0,1,5,8,12\}$ for $u=13\,$, $\,\{0,1,7,8,11,12,18\}$ for $u=19\,$, $\,\{0,1,2,4,8,15,16,23,27,29,30\}$ for $u=31$. Doing this for $u\le61$ reduces by a factor over $1099$ the number of candidates $x$, and we can make a "wheel" of $4729725$ increments of $x$ to quickly go from one $x$ to the next. Larger primes $u$ can be used to quickly weed out most of the remaining candidates $x$, and I think a standard PC can eliminate like $2^{48}$ candidates $x$ per day; thus we can tackle like $m\approx n/3+16$.
  4. On top of improvements 2 and 3, we can hope that $M$ is divisible by a small integer $v>1$: there's probability >73% that holds for at least one $v\in\{2,3,5\}$. If so $\hat M=M/v$ is an integer, and $\hat C=v^{-3}C\bmod N$ that we can compute is such that $\hat C={\hat M}^3\bmod N$. We can thus carry the attack of 1/2/3 on $\hat C$, and if we find $\hat M$ go back to $M$.

I don't see that 3 and 4 combined can work with sizable probability for $m>n/3+20$ or so. But perhaps there is a smarter attack, e.g. with the LLL?



Your Answer

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

Browse other questions tagged or ask your own question.