# How does the cyclic attack on RSA work?

I am trying to get the idea of cyclic attacks againts assymetric RSA encryption. Taken from Handbook of applied cryptography .

Let $k$ be a positive integer such that $$c^{(e^{k})} = c\mod n \tag{1}.$$ There for $k-1$ it holds that $$c^{(e^{k-1})} = m \mod n \tag 2$$ where $m$ is the message for encryption $n$ is the modulus and $c$ is the ciphertext.

I can't understand why equation (2) must hold?

-
It is important to note that such attacks are not a practical threat, for they are demonstrably less likely to succeed than some extremely inefficient factorization methods. –  fgrieu Jun 27 '12 at 10:14

Let us remind that, by definition of the RSA encryption, we have $c = m^e \bmod{n}$ (where $n=pq$ and $\mathrm{gcd}(e, (p-1)(q-1)) = 1$, but it's not important here). Let's take the equation $$c^{e^{k-1}} \equiv m \bmod{n}$$ and let's raise both sides to the power $e$: $$\left(c^{e^{k-1}}\right)^e \equiv m^e \bmod{n}\,,$$ so $$c^{e^k} \equiv c \bmod{n}\,.$$

-
Ok i got it. As $c^{e^{k}} = c\space mod (n)$ (1) and $c=m^{e}\space mod(n)$ (2) then $c^{e^{k}} = m^{e}\space mod(n)$ (3). Then dividing each member in (3) by $e$ we get $c^{ e^{k-1}}=m\space mod(n)$ –  curious Jun 26 '12 at 14:02

We start with the definition of textbook RSA encryption: $c = m^e \bmod n$. From your first equation

$$c^{e^k} = c \pmod{n},$$ we have that if $c^{e^k} = c \pmod{n}$, then $e^k = 1 \pmod{\phi(n)}$ (Euler's theorem). Dividing both sides by $e$, we get

$$e^{k-1} = e^{-1} \pmod{\phi(n)}.$$

By definition, $d = e^{-1} \pmod{\phi(n)}$. Thus, $$c^{e^{k-1}} = c^d = m \pmod{n}.$$

-
why $c^{e^{k}} = c$ ? $c^{e^{k}} = c mod (n)$ right? –  curious Jun 26 '12 at 13:48
Right, just changed the answer to make the modulo explicit. –  Samuel Neves Jun 26 '12 at 14:09