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?

$\endgroup$
  • 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 Jun 27 '12 at 10:14
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}\,.$$

$\endgroup$
  • $\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 Jun 26 '12 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}.$$

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

Choose two prime numbers, p=3; q=7.

  • n=p*q = 21
  • Phi(p, q) = (p-1)*(q-1) = 12
  • Choose number e, so that it could be prime && less than Phi(p,q), i.e.: 3, 5, 7, 11. (Example e=5)
  • Now {e, n} my public key
  • We need to calculate number d, so that (d*e) % Phi(p,q) = 1, i.e. (5*d) % 12 = 1, d might be 17 for example.
  • {d, n} = private key
  • Lets suppose friends message is number 19; P=19.
  • {e, n} = {5, 21} ==> 19^e%n => 10; E=10
  • Your friend sends E to you
  • You receive message E=10
  • {d, n} = {17, 21}
  • E^d%n = 19
$\endgroup$
  • $\begingroup$ This illustrates textbook RSA with an example, when the question is about the cyclic attack on RSA, which is not illustrated (in this artificailly small example, performing encryption again on the ciphertext $10$ will lead to the original plaintext $19$; try it, it works, and that also shows that $d=5$ is just as good as $d=17$ is). To properly format an answer, insert a blank line before the first bullet, and use * or - instead of the bullet sign . Also, consider using MathJax. $\endgroup$ – fgrieu Oct 22 '17 at 18:29
  • $\begingroup$ This does not adress the question at all. $\endgroup$ – tylo Oct 23 '17 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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