3
$\begingroup$

Let $p$ and $q$ be large primes, $n=pq$ and $e : 0 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\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

  • 0
    wouldn't that mean that $e^k \mod \phi(n) = d$2012-01-04
  • 0
    yes it would; I'm interested in knowing if there is a reason to believe k is sufficiently large2012-01-04
  • 1
    (actually with the edits I just made, it would be $e^{k-1} \mod \phi(n) = d$ )2012-01-04
  • 0
    Does the accepted answer to http://crypto.stackexchange.com/questions/1151/is-it-reasonable-to-assure-that-p-1-and-q-1-arent-smooth answer the question?2012-01-04
  • 0
    @Peter Thanks for pointing this out; however I still don't see a clear connection with my question. Does the Pollard $p-1$ algorithm have anything to do with it?2012-01-04
  • 0
    @ratchetfreak No, it would mean that $e^k = 1 \bmod \phi(n)$ and $d = e^{k-1} \bmod \phi(n)$.2012-01-04
  • 0
    The connection I was seeing is that in the smooth prime attack it describes a more sophisticated cycle attack and gives hints which allow you to estimate the probability of vulnerability.2012-01-05
  • 0
    I don't know much about this, but in any implementation I've seen of RSA (even basic "toy" models), the primes $p$ and $q$ are chosen so that $\phi((p-1)(q-1))$ is large.2012-01-05
  • 0
    @SteveD Thanks, I didn't know this, and it makes sense. However is there some (maybe probabilistic) result that ensures $\mathbb{Z_{\phi(n)}}^\times$ isn't a group in which possible orders of elements are all quite small (even though it may be quite large)? In general such groups exist: take for example the additive product group $\mathbb{Z_2}^{2012}$; it's a pretty big group, but any $1 \neq a \in \mathbb{Z_2}^{2012}$ has order 2.2012-01-05
  • 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.2012-01-05
  • 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.2012-01-05

1 Answers 1

1

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.