# RSA: How Euler's Theorem is used?

I'm trying to understand the working of RSA algorithm. I am getting confused in the decryption part. I'm assuming

$$n = pq$$ $$m = \phi(n) = (p - 1)(q - 1)$$

E is the encryption key $\gcd(n, E) = 1$

D is the decryption key, and $DE = 1 \mod \phi(n)$

$x$ is the plain text

Encryption works as ($y = x^E \mod n$) and decryption works as ($x = y^D \mod n$)

The explanation for why the decryption works is that since $DE = 1 + k\phi(n)$,

$$y^D = x^{ED} = x^{1 + k \phi(n)} = x(x^{\phi(n)})^k = x \mod n$$

The reason why last expression works is $x^{\phi(n)} = 1 \mod n$ ? According to Eulers theorem this is true only if $x \text{ and }\phi(n)$ are coprimes. But $x$ is only restricted to be $0 < x < n$ and $\phi(n) < n$. So $x$ should be chosen to be coprime with $\phi(n)$?

Help me clear out the confusion!

-
It is frustrating that many references (not just the OP's question) claim that RSA uses Euler's theorem and the possibility that x and n have a common factor is treated as a separate case. As user996522 shows in an answer below (not the accepted answer, unfortunately), it is irrelevant that x could have a factor in common with n, and in fact RSA goes through with n being any squarefree number with no exceptions on x whatsoever. That RSA works depends on Fermat's little theorem, not Euler's theorem. Look at the original RSA paper: they use Fermat's little theorem, not Euler's theorem. –  KCd Dec 27 '11 at 16:50
@KCd I went through the original paper on RSA and indeed the explanation for decryption is based on Fermats Little theorem ( special case of Euler's theorem ) and the Chinese remainder theorem. –  sauravrt Dec 27 '11 at 21:11
I see you changed the accepted answer to user996522. Good move. –  KCd Dec 28 '11 at 1:34
Can you tell me how you arrived at the answer: \begin{align*} &\equiv x^1 \cdot x^{\phi(q) \phi(p) z} \\ &\equiv x \pmod q \end{align*} –  RVM Dec 29 '11 at 0:54
The above relation works out because $\phi(q) = q - 1$ and from Fermat's Little Theorem, $x^{q-1} \equiv 1 (\text{mod q})$ –  sauravrt Dec 29 '11 at 2:40

Even if the plaintext $x$ is not pairwise coprime with $p$ or $q$, RSA still works as advertised. Here is why:

$p$ and $q$ are prime, so $x$ is a multiple of either $p$ or $q$, given the restriction that $x < pq$.

Assume that $x \equiv 0 \pmod p$. If it is congruent to $0$ mod $q$ the below still applies, just switch the name assigned to the two primes.

$x^k \equiv 0 \pmod p$ for all $k > 0$, i.e $x^k \equiv x \pmod p$.

\begin{align*} x^{1+ z \phi(n)} & \equiv x^{1+ z \phi(p) \phi(q) } \\ &\equiv x^1 \cdot x^{\phi(q) \phi(p) z} \\ &\equiv x \pmod q \end{align*}

Combining both equations with the Chinese Remainder Theorem yields $x$, the plaintext.

-

First, the statement should read $x^{\phi(n)}\equiv1\pmod{n}$, not modulo $\phi(n)$. You are right that this assumes that $x$ and $n$ are coprime. Given that $p,q$ are very large primes, the fraction of possible $x$ that is not coprime with $n$ is exceedingly small: $\frac1p+\frac1q-\frac1n$. In fact the security of the method is based on the smallness of this number: if there were any reasonable chance of finding a number $m$ not coprime with $n$ by picking a random number between $0$ and $n$, then one could compute $\gcd(m,n)\in\{p,q\}$ using it, and factor $n$. But formally, the test of coprimality of the plain text $x$ with $n$ should be done by the encoder, just like the test you already assumed that $x\neq0$. In the very unlikely event that coprimality fails, one must add some noise to the plain text.

-
Thank. That clears the doubt that I had. And yes you are right about the modulo being mod n, I'll edit the question. –  sauravrt Dec 2 '11 at 13:20

Aside from it being unlikely that $\gcd(x,n) \neq 1$, note that the only possibilities are $\gcd(x,n) \in \{1,p,q,n\}$. Therefore, if $x$ and $n$ are not coprime, the one can decipher the text anyways (since one then knows either $p$ or $q$ and can easily find the other factor, and hence $n$).

In other words, if $x \in \mathbb{Z}/ n \mathbb{Z}$ is not a unit, we know that $$x^{ED} \equiv x \pmod{n} \Longleftrightarrow \left\{\begin{array}{ccc} x^{ED} \equiv x \pmod{p} \\ x^{ED} \equiv x \pmod{q} \end{array} \right\}.$$

Hope this helps.

-