3
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – fgrieu ♦
    Commented Jun 27, 2012 at 10:14

2 Answers 2

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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)$ $\endgroup$
    – curious
    Commented Jun 26, 2012 at 14:02
4
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ why $c^{e^{k}} = c$ ? $c^{e^{k}} = c mod (n)$ right? $\endgroup$
    – curious
    Commented Jun 26, 2012 at 13:48
  • 1
    $\begingroup$ Right, just changed the answer to make the modulo explicit. $\endgroup$
    – Samuel Neves
    Commented Jun 26, 2012 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.