Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
(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
1  
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
1  
@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
show 6 more comments

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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