4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ "Why is it claimed that 7/8 of the possibilities are removed?" No such thing is claimed. $\endgroup$ – fkraiem Jan 16 '17 at 18:50
5
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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