# Show that this RSA encryption iterated $10$ times does not encrypt $x$

Let's say we have an RSA key of modulus $$n = 383\cdot563 = 215629$$ and encryption exponent $$e = 49$$. Suppose our encryption $$E(x)=(x^{49})^{10}$$ where we are iterating $$x^{e}$$ ten times. I want to show that $$E(x)=x$$. It seems like I just need to show that the decryption key $$d=10$$. Usually, to find decryption keys, I've used the fact that

$$de\equiv 1 \mod (p-1)(q-1)$$

But since $$490\equiv 64\mod {(383-1)(563-1)}$$ It must not be true then, that for every RSA encryption and decryption exponents $$e$$ and $$d$$ that $$de\equiv 1 \mod (p-1)(q-1)$$, right? What's different about this case?

How do I prove that $$E(x)=x$$? That is, how do I show $$x^{490}\equiv x\mod 215629$$? What does this say about an eavesdropper that doesn't know the prime factors of $$n$$?

I'm told I can use the fact that

$$7^{20} \equiv 1 \mod 191$$ and $$7^{20} \mod 281$$ which does mean $$49^{10} \equiv 1$$ for those...

• I just realized $191$ and $281$ divide $(p-1)(q-1)$ as well Nov 10, 2023 at 4:54
• @kelalaka I thought it worked for $x=3,4,5...$ but I must've been looking at something else. Nov 13, 2023 at 0:08
• @kelalaka The actual problem states "Suppose we let $E$ denote encryption with this public key, so $E(x) = x^{49} (\mod 215629)$. Show that E^10(x) = x (where $E^k$ denotes $E$ iterated $k$ times)". Nov 13, 2023 at 0:19

Let we have RSA encrypt $$E(x) = x^{49} \bmod 215629$$ then the double RSA encrypt is \begin{align} E^2(x) &= (x^{49})^{49} \bmod 215629\\ &= \color{red}{x^{49\cdot49}} \bmod 215629\\ &= x^{49^2} \bmod 215629\\ &= x^{2401} \bmod 215629\\ \end{align}

Now, if you encrypt 10 times than

\begin{align} E^{10}(x) &= ((x^{49})^{{49}^{\cdots^{49}}} ) \bmod 215629\\ &= x^{49^{10}} \bmod 215629\\ &= x^{79792266297612001} \bmod 215629\\ \end{align}

From Euler's theorem we know that $$a^{\varphi(n)} \equiv 1 \pmod n$$

The $$\varphi(383\cdot 563) = (383-1)\cdot (563-1)= 214684$$

With a simple test $$79792266297612001 = 1 \bmod 214684$$

• Thank you, I think I misunderstood the iteration part Nov 14, 2023 at 2:51
• Serial exponentiation Nov 14, 2023 at 9:07