# RSA encryption - confusion about the moduli

I read an article about the RSA cryptosystem and I find the way of encryption a bit confusing. This is the part that I do not understand:

Let's say that we choose these prime numbers: $p = 17$ and $q = 23$, hence $n = pq = 391$. Also, the totient function: $\varphi(17 \cdot 21) = 320$.

Now, we choose our public and private key integers - the first one, $e$, should be coprime with $320$, so let's pick $169$. which yields that $d = 89$.

Now, we know that $ed = 1 \mod 320$. However, in the algorithm itself, we perform operations $\mod 391$, and yet $(\mbox{message})^{ed}=\mbox{message} \mod 391$. How can we know that $ed = 1\mod 391$ given $md = 1 \mod 320$?

• The exponents operate in a different modulus than the base. This is responsible for the change. For the precise reason, see Euler's Theorem on congruences mod $n$. – Randall Apr 20 '18 at 17:22

Euler's Theorem asserts that when $x$ is relatively prime to $n$ then $x^{\varphi(n)} \equiv 1 \bmod n$. Note that it does not say that $x^n \equiv 1 \bmod n$: just because $n \equiv 0 \bmod n$ does NOT mean that you can replace the $n$ in the exponent this way. In fact, you definitely cannot/should not, and Euler's Theorem shows you the right path.

Now, if $x$ is relatively prime to $n$ then it is easy to show that RSA decryption always works. The whole point is that you've chosen $e$ and $d$ so that $ed \equiv 1 \bmod \varphi({n})$, hence $ed = 1 + k\varphi(n)$ for some integer $k$. After encrypting by $x \mapsto x^e \bmod n$ we decrypt by $x^e \mapsto (x^e)^d = x^{ed} \bmod n$. Why is this $x$ again? It's Euler's Theorem:

$$x^{ed} = x^{1+k\varphi(n)} = x \cdot (x^{\varphi(n)})^k = x \cdot 1^k =x$$ where all computations happened mod $n$.

The case when $x$ is not relatively prime to $n$ is proven by a slightly different argument, but in the same spirit. In all cases, $x^d$ always decrypts correctly.