# Why does decryption in RSA not fail with 2 different moduli?

In RSA, we choose $p,q$ and calculate $\phi(n)=(p-1)(q-1)$. We then choose a public key $e$, and calculate its inverse modulo $\phi(n)$: $d\cdot e=1 \mod(\phi(n))$.

But then, when we decrypt a ciphertext $y=x^e \mod(n)$, we use the different modulus $n$ rather than $\phi(n)$: $x=y^d \mod(n)$. This is equal to $x^{e\cdot d \mod(n)}$, which supposedly equals $x^1$. But I don’t understand this last step, because we chose $d$ such that $e\cdot d=1 \mod (\phi(n))$, not such that $e\cdot d=1 \mod(n)$

• The question's notation $y=x^e\mod(n)$ and $x=y^d\mod(n)$ is not standard. RSA actually uses $y=x^e\bmod n$ and $x=y^d\bmod n$, with less space on the left of $\bmod$ and customarily no parenthesis around the single variable $n$. In this, $\bmod$ is an operator returning the remainder of the Euclidean division of its left operand by its right operand (like % does in C, Java, Go, at least for non-negative left argument and positive right argument). Also, it is unclear what "is equal to $x^{e\cdot d \mod(n)}$ " and what the later is. – fgrieu Sep 13 '18 at 8:19
• @fgrieu, With "is equal to ..." I meant to say that $y^d \bmod n = (x^e)^d \bmod n = x^{e\cdot d} \bmod n$. – user56834 Sep 13 '18 at 10:02

The question assumes, wrongly, that $a^b\bmod n$ is the same as $a^{b\bmod n}$ or $a^{b\bmod n}\bmod n$. In general these are three different quantities, as demonstrated with $a=5$, $b=5$, $n=3$: $$\begin{array}{} a^b\bmod n&=&\left(5^5\right)\bmod 3&=&3125\bmod 3&=&2\\ a^{b\bmod n}&=&5^{(5\bmod 3)}&=&5^2&=&25\\ a^{b\bmod n}\bmod n&=&\left(5^{(5\bmod 3)}\right)\bmod 3&=&25\bmod3&=&1 \end{array}$$ Note: going from the second to third expression of the last line uses the result obtained above.

• I still don't understand why $(x^e \bmod n )^d \bmod n = x \bmod n$ – user56834 Sep 13 '18 at 10:04
• @Programmer2134: That's asking why textbook RSA works, rather than why an RSA variant does not. We have multiple answers for that, including this which gives a simple proof valid for all messages. If we restrict to $x$ coprime with $n$ (that's most $x$), there's a simpler proof: $\left(x^e\bmod n\right)^d\bmod n$ is $x^{e\,d}\bmod n$, thus (by construction of $d$) is $x^{\phi(n)\,k+1}\bmod n$ for some $k$, thus $\left(x^{\phi(n)}\right)^kx\bmod n$, thus (since $x^{\phi(n)}\bmod n=1$ for any $x$ coprime to $n$) is $1^kx\bmod n$, thus is $x\bmod n$. – fgrieu Sep 13 '18 at 12:53
• More to the point, $x\equiv y \pmod n$ does not imply $a^x\equiv a^y \pmod n$; this is why we don't take $ed \equiv 1 \pmod n$. – fkraiem Sep 13 '18 at 12:59

You are correct, $ed=1 \bmod \phi(n)$.

• Actually, we have $ed \equiv 1 \pmod {\text{lcm}(p-1, q-1)}$ as being the necessary and sufficient condition on $e, d$ – poncho Sep 13 '18 at 14:44

I think you want to know why we use $\phi(n)$ as a modulus when calculating the keys and $n$ as a modulus when calculating the message/chiphertext. I was wondering the same when studying the RSA cryptosystem for the first time. The following is taken from the book Understanding Cryptography by Chrisoph Paar on page 178.

We have the definition of the RSA keys. $$de \equiv 1 \pmod {\phi(n)}$$

Per definition of the $\phi$ function this means the following: $$de = 1 + t*\phi(n)$$ for any integer $t$.

Edit: We assume that $gcd(x,n)=1$. Now we take a look at the decryption process. $$d(y) \equiv y^d \equiv (x^e)^d \equiv x^{de} \pmod n$$

It follows: $$x^{de} \equiv x^{1+t*\phi(n)} \equiv x^1*x^{t*\phi(n)} \equiv x*(x^{\phi(n)})^t \pmod n$$

Now take a look at Euler's theorem (a generalization of Fermat's little theorem). $$x^{\phi(n)} \equiv 1 \pmod n$$

Now we can substitute and get $$x^{de} \equiv x*1^t \equiv x \pmod n$$

• This proof is partial, silently assuming that $\gcd(x,n)=1$. For other $x$, the equality $x^{\phi(n)}\bmod n=1$ does not hold. Example: $x=6$, $n=15=3\cdot5$ with $\phi(n)=2\cdot4=8$, thus $x^{\phi(n)}=1679616$, thus $x^{\phi(n)}\bmod n=1679616\bmod 15=6\ne1$. Yet, such $x$ with $0\le x<n$ and $\gcd(x,n)\ne1$ still meet $x^{e\,d}\bmod n=x$. – fgrieu Sep 13 '18 at 14:37