Cycle attack on RSA

I originally posted this question in the mathematics section, you can see it here.

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} (mod\space n)$, $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)?
-

The cornerstone of the argument is the following:

1. If the cycle attack works, then you can factor $n$ (see details below).
2. The attacker can choose $e$. I.e., when trying to factor $n$, the attacker is not constrained to use the specific $e$ which you selected for your public key; he can invent his own $e$, since he will do all the computations himself.
3. Therefore, the "cycle attack" is a generic factorization algorithm, against which you cannot protect yourself by selecting a specific $e$; instead, you rely on the cycle attack being hard for any $e$ that the attacker may conceivably choose.

Fortunately, there are only very few values of $e$ with a short cycle length modulo $\phi(n)$. Indeed, $\phi(\phi(n)) = \phi((p-1)(q-1))$; on average, the biggest prime factor of $p-1$ (let's call it $r$) will have a size close to about 30% of the size of $p-1$, i.e. at least 150 bits for a 1024-bit RSA modulus. This implies that:

• If the attacker chooses a $e$ with an order multiple of $r$, then the cycle length $k$ will be at least as big as $r$, hence way too long for the attack to be feasible;
• The chances of a random $e$ having an order which is not a multiple of $r$, are at most $1/r$, i.e. way too small for the attacker hitting one out of pure luck.

There is no known way to efficiently find an $e$ such that the cycle attack is not intolerably expensive; as shown above, a random $e$ is not good enough. In other words, the "cycle attack" does not seem to be an efficient factorization algorithm.

About turning a cycle into a factorization

If you find $e$ and $k$ which yield a cycle, then you know that $x = e^k-1$ is a multiple of $\phi(n)$. Write $x = 2^f·y$ for an integer $f$ and an odd integer $y$ ($e$ is a potential RSA public exponent, hence odd; therefore, $x$ is even, which means that $f \geq 1$).

Now select a random $a$ modulo $n$ such that $\left(\frac{a}{n}\right) = -1$ (that's the Jacobi symbol and it can be efficiently computed for any $a$ and $n$); about half of the integers modulo $n$ have such a property, so you will not have to search long for that. Such an $a$ is then a square modulo $p$ but not modulo $q$, or vice versa. Now do the following:

• Compute $b = a^y \pmod n$. If $b = 1$ of $b = n-1$, try again with another $a$.
• Compute $c = b^2 \pmod n$. If $c = n-1$, then start again this algorithm with another $a$. If $c = 1$, then compute the GCD of $b-1$ and $n$: this will yield a non-trivial factor of $n$. Otherwise, set $b = c$, and start again this step.

The first step will succeed with probability at least $1/2$. The second step will loop at most $f$ times, and will yield a non-trivial factor of $n$ with probability at least $1/2$. Therefore, you will need, on average, no more than four values $a$ to factor $n$, given the cycle length $k$.

Note, though, that $k$ may be quite big. The conditions which we work with imply that it is computationally feasible for the attacker to raise an integer modulo $n$ to the power $e$, and do so $k$ times -- this does not formally imply that the attacker can store an integer of size $k$ times the size of $e$. Given $k$, finding $f$ is easy by dichotomy (compute $e^k$ modulo $2^f$ for various values of $f$ until you find the biggest for which the result is still $1$). Knowing $f$ and $k$, it should be possible to compute $a^{(e^k-1)/2^f} \pmod n$ with about the same cost than computing $m^{e^k} \pmod n$ took in the first place (it is a bit tricky because it involves using very big integers, and I am too lazy to work out the details this morning, but I instinctively find it plausible).

This leads to a factorization effort of roughly four times the work of the cycle-length-finding effort. That's close enough for my purposes: I want to show that the "cycle attack" cannot be efficient, because otherwise it could be turned into an almost as efficient factorization algorithm.

-
Thank you for your answer, this is what I was looking for. I still don't understand one thing though: why is the probability of $|e|$ not being a multiple of $r$ at most $1/r$? – Emilio Ferrucci Jan 5 '12 at 15:04
@EmilioFerrucci: for the general intuition, consider a prime $u$, and a prime $v$ which divides $u-1$. Write $w = (u-1)/v$. Values $x$ with an order which is not a multiple of $v$ are such that $x^w = 1 \pmod u$ (because $x^{u-1} = 1 \pmod u$). So these $x$ are solutions to a polynomial of degree $w$ in a field (integers modulo $u$); thus, there can be no more than $w$ of them, and $w/u \approx 1/v$. Here, we work modulo $p-1$ which is not prime, but the same general principle applies. – Thomas Pornin Jan 5 '12 at 15:16

One of the biggest problems you'll have is to ascertain that $m^{e^k} = m$ for some $k$. You need to have a way of knowing that particular value is genuine. Given the typical use-case of RSA applies padding and is used for small data sizes for things such as keys to symmetric algorithms, it isn't always likely that this check will be easy to compute.

The other side of the coin is that $m^{e^k} = m^{ed} = m$; that is, $m^{e^k} = ( m^e )^d$. In other words, I am pretty certain what you're looking at amounts or is no better than a brute force search.

Is there an efficient algorithm to chose $e$ such that its order in $\mathbb{Z}_{\phi(n)}^{\times}$ is sufficiently large?

$e$ is an element of that group in itself; specifically $d$ is computed to be its inverse under that group. $e$ does not, however, affect the size of that group - it is simply chosen to be in it.

The requirements for a group with regards to multiplication stipulate that each element must have a unique inverse. This only holds true for positive $\mathbb{Z}$ without 0 modulo a prime; for it to hold above that you must include from $\mathbb{Z}$ only those elements that are coprime to the modulo. However, holding only $n$ and $e$ you do not have the ability to compute $(p-1)(q-1)$ i.e. $\phi(n)$ so the size of the group is irrelevant - you can only factorise $n$ (hard) and must therefore search everything. If you did know $\phi(n)$ you would simply find $d$ in $de \equiv 1 \mod \phi(n)$.

So that gives us our answer:

How can we justify that the attack is computationally infeasible, even when $e$ is chosen at random?

because aside from the verification problem which would apply to any type of brute force search, $\mathbb{Z}_{\phi(n)}^{\times}$ is as hard to find as factorising $n$.

-
Thank you for your answer. I was expecting th first objection you made: even if I came across $m$ I might not be able to tell it's the plaintext, and distinguish it from any other element in $\mathbb{Z_n}$. I don't know much about padding, and I can see how this is possible. – Emilio Ferrucci Jan 5 '12 at 2:47
Then regarding the first highlighted part you quoted: I am not wondering about the order of $\space$ $\mathbb{Z}_{\phi(n)}^{\times}$ (which of course is fixed), but about the order of $e$ in $\mathbb{Z}_{\phi(n)}^{\times}$, that is the order of the subgroup $<e>$ of $\mathbb{Z}_{\phi(n)}^{\times}$. This might not have much to do with the order of $\mathbb{Z}_{\phi(n)}^{\times}$ : for example the group $\mathbb{Z}_{8}^{\times}$ has order 4, but the only possible orders of elements are $1$ or $2$, since it is the klein group. – Emilio Ferrucci Jan 5 '12 at 2:48
@EmilioFerrucci well the order of $e$ will be $k$ since $e^k = 1$ is the solution you're trying to find. $e$ can't be a subgroup on its own as it doesn't have an identity element wrt multiplication. I think you might be thinking of the notes here - finding $k$ is at least as hard as factoring unless $ord(\mathbb{Z}_{\phi(n)}^{\times})$ is known. Of course, finding that order is going to be hard in and of itself - you don't know how the group is generated in the first place (remember $\phi(n)$ is (part of the) the private key). – user46 Jan 5 '12 at 14:33
By $<e>$ i mean the group generated by $e$, $<e>=\{1,e,e^2,...,e^{k-1} \}$ (yes, $|e|$=k). I don't see the connection with factoring or with evaluating $\phi(n)$ (which are computationally equivalent, up to polynomial transformations), since in theory $k$ could be much smaller than $|\mathbb{Z}_{\phi(n)}^{\times}|=\phi(\phi(n))$ (I'm guessing it probably isn't - this is the type of result I was looking for). – Emilio Ferrucci Jan 5 '12 at 14:53
@EmilioFerrucci, k is a factor of the order of the group by Lagrange's theorem. – Peter Taylor Jan 5 '12 at 15:59