# 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?

-

1
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

## 2 Answers

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

1
Right, just changed the answer to make the modulo explicit. – Samuel Neves Jun 26 '12 at 14:09
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 21, "mathjax_display_tex": 8, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9365018606185913, "perplexity_flag": "middle"}