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:
- 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.
- 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.
- 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$.
- 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?
