3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ wouldn't that mean that $e^k \mod \phi(n) = d$ $\endgroup$ – ratchet freak Jan 4 '12 at 18:51
  • $\begingroup$ yes it would; I'm interested in knowing if there is a reason to believe k is sufficiently large $\endgroup$ – Emilio Ferrucci Jan 4 '12 at 19:01
  • 1
    $\begingroup$ (actually with the edits I just made, it would be $e^{k-1} \mod \phi(n) = d$ ) $\endgroup$ – Emilio Ferrucci Jan 4 '12 at 19:10
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Taylor Jan 5 '12 at 13:53
  • 1
    $\begingroup$ @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. $\endgroup$ – user641 Jan 5 '12 at 14:06
1
$\begingroup$

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.

$\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.