Cryptography – RSA Encryption Iterated 10 Times Does Not Encrypt $x$

cryptographymodular arithmetic

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…

Best Answer

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

Related Question