Let $p$ and $q$ be large primes, $n=pq$ and $e : 0<e<\phi(n), \space gcd(e, \phi(n))=1$ the public encyption exponent, $d : ed \equiv 1 \space (mod \space \phi(n)) $ the private decription exponent, and $m \in \mathbb{Z_n}$ the plaintext, in an $RSA$ cryptosystem. Suppose Eve wants to read the ciphertext $\mu= m^e$ (suppose she can tell when an element of $\mathbb{Z_n}$ is the plaintext), she comes up with the following attack:
compute $m^{e} \left(\mod n \right)$, $m^{e^2} (\mod\space n)…$ and so on untill, for some $k: \space$ $m^{e^k} = m$
Notice that such $k$ exists, as $e$ can be considered an element of the multiplicative group $\mathbb{Z_{\phi(n)}}^\times$ and therefore $e^{-1}\in<e>\leq\mathbb{Z_{\phi(n)}}^\times$. I found this attack to be called the cycle attack but it isn't mentioned in any cryptography textbooks I know of, and therefore I'm guessing it isn't much of a a threat to $RSA$. Having said this, my questions are:
- How can we justify that the attack is computationally infeasible, even when $e$ is chosen at random? We know $k=|e|$ , and that $|e|$ divides $ |\mathbb{Z_{\phi(n)}}^{\times}|=$$\phi(\phi(n))=\phi((p-1)(q-1))$ , but do we know anything about the expected value for $|e|$ (for example, by deducing it from the structure, and in particular from the distribution of orders of elements of $\mathbb{Z_{\phi(n)}}^{\times}$)?
- Is there an efficient algorithm to chose $e$ such that its order in $\mathbb{Z_{\phi(n)}}^{\times}$ is sufficiently large (although this doesn't seem to be necessary)?
I also posted this thread in the cryptography section, you can view it here
Best Answer
The question has been answered here. However if anyone can provide any further results regarding orders of elements in multiplicative groups of integers modulo $n$, I would much appreciate.