# Cycle attack on RSA

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

• wouldn't that mean that $e^k \mod \phi(n) = d$ – ratchet freak Jan 4 '12 at 18:51
• yes it would; I'm interested in knowing if there is a reason to believe k is sufficiently large – Emilio Ferrucci Jan 4 '12 at 19:01
• (actually with the edits I just made, it would be $e^{k-1} \mod \phi(n) = d$ ) – Emilio Ferrucci Jan 4 '12 at 19:10
• If $p$ and $q$ are Sophie Germain safe primes, I think you can probably use Sylow's third theorem to prove that the probability of a random $e$ having order less than $\varphi(n)$ is $O(n^{-1/2})$. Proof left as an exercise for someone who knows more group theory than me. – Peter Taylor Jan 5 '12 at 13:53
• @EmilioFerrucci: $\mathbb{Z}_{\phi(n)}^\times$ is a product of cyclic groups, and the bigger the prime factors of $\phi(n)$ are, the bigger the possible orders of elements. As far as expected value of the order of a randomly chosen element, I don't know enough to say what the "best" type of primes to choose are. But certainly the highest expected value is when $\mathbb{Z}_{\phi(n)}^\times$ is cyclic, and decreases until it is elementary abelian. In other words, a few very large prime factors of $\phi(n)$ is definitely preferable to many small ones. – user641 Jan 5 '12 at 14:06

## 1 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.