2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I just realized $191$ and $281$ divide $(p-1)(q-1)$ as well $\endgroup$ Nov 10, 2023 at 4:54
  • $\begingroup$ @kelalaka I thought it worked for $x=3,4,5...$ but I must've been looking at something else. $\endgroup$ Nov 13, 2023 at 0:08
  • $\begingroup$ @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)". $\endgroup$ Nov 13, 2023 at 0:19

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .