Let $p$ and $q$ be large primes, $n=pq$ and $e : 0 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 I also posted this thread in the cryptography section, you can view it here
Cycle attack on RSA
3
$\begingroup$
group-theory
cryptography
-
0wouldn't that mean that $e^k \mod \phi(n) = d$ – 2012-01-04
-
0yes it would; I'm interested in knowing if there is a reason to believe k is sufficiently large – 2012-01-04
-
1(actually with the edits I just made, it would be $e^{k-1} \mod \phi(n) = d$ ) – 2012-01-04
-
0Does 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
-
0The 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
-
0I 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
-
1If $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
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.