Partition attack on the possible values of RSA modulus

Question

This is a question that arises from an exercise you can see here on breaking a bad EKE construction with RSA. However, my question does not tackle that construction.

The problem is that we work with an RSA modulus $N$ and with $e=3$ for encryption. As usual, $gcd(3,\phi(N)) = 1$. Also $N$ is a 1024 bits number. I need to reduce the possible $N$ in order to do an exhaustive search attack. It is claimed that:

1.As $N$ is odd and between $2^{1023},2^{1024}$ then the first and last digits are ones.

2.$N \, mod \,3 = 1$

3.The set of valid $N$ is at least $\frac{1}{8}$ of the full space (I understand the 1024 bits)

The first is clear to me. But I don't see a good reason for the second. Even if I admit the second point then I would have removed about $\frac{2}{3}$ of the possibilities (something more because of the first point). Why is it claimed that $\frac{7}{8}$ of the possibilities are removed?

Answer 1

But I don't see a good reason for the second.

One requirement for RSA is that, if $p, q$ are the prime factors of $N$, then $p-1, q-1$ must be relatively prime to $e$ (if this is not true, then it becomes impossible to uniquely decrypt, as $gcd(e,\phi(N)) \ne 1$). Now, if $e=3$, that means that $p \not\equiv 1 \bmod 3$ (and $q \not\equiv 1 \bmod 3$). And, since $p, q$ are prime (and presumably greater than 3), we have $p \not\equiv 0 \bmod e$, $q \not\equiv 0 \bmod 3$. That leaves, as the only alternative, $p \equiv q \equiv 2 \bmod 3$.

And, multiplying two values which are both 2 (modulo 3) together gives a value which is 1 (modulo 3). That is, if $N \not\equiv 1 \bmod 3$, then $N$ cannot be a two factor modulus that works with $e=3$

Why is it claimed that $\frac{7}{8}$ of the possibilities are removed?

My guess would be that Serge miscalculated here (however, his main point holds). The first criteria (top and bottom bit must both be 1) eliminates $\frac{3}{4}$ of the possibilities. As for the second point (which is independent), I suspect that they assumed that eliminating the $N=2 \bmod 3$ possibilities removed another half (and they they forgot about the $N=0 \bmod 3$ possibility); that miscomputation would have them eliminating $1 - (1 - \frac{3}{4})(1 - \frac{1}{2}) = \frac{7}{8}$. However, if we recognize that $N=0 \bmod 3$ would be possible on an incorrect guess (and can also be eliminated), that means that step 2 eliminates $\frac{2}{3}$ of the possibilities (as you noted); that gives us an aggregate of $1 - (1 - \frac{3}{4})(1 - \frac{2}{3}) = \frac{11}{12}$ of the incorrect possibilities (and so the result is actually stronger than originally claimed).