# Why is RSA encryption performed in mod n, but computation of inverse in $\bmod \varphi(n)$

I am studying the principles of RSA and have come across some unintuitive statements. Lets revisit the RSA algorithm:

RSA Key Generation

Output: public key: $$k_{pub} = (n,e)$$ and private key: $$k_{pr} = (d)$$

1. Choose two large primes $$p$$ and $$q$$.
2. Compute $$n$$ = $$pq$$.
3. Compute $$\varphi(n) = (p−1)(q−1)$$.
4. Select the public exponent $$e \in \{1,2,\ldots,\varphi(n)−1\}$$ such that $$\gcd(e,\varphi(n)) = 1.$$
5. Compute the private key $$d$$ such that $$d\cdot e \equiv 1 \bmod \varphi(n)$$

Decryption: $$x=d_{kpr}(y)\equiv y^{d} \bmod n$$

Encryption: $$y=e_{kpub}(x)\equiv x^{e} \bmod n$$

I don't find intuitive on why we perform encryption and decryption in modulus $$n$$, but compute the inverse of $$e$$ in modulus $$\varphi(n)$$. Any help is appreciated.

• Hint: did you see Euler and Fermat's theorems? – kelalaka Sep 29 '19 at 8:28
• I've seen some theorems I did not fully grasp on intuitive level. When they were used to proof that xˆ(de) = x mod n, that was not intuitive as well. – sanjihan Sep 29 '19 at 8:33

What's relevant here is that the Carmichael totient $$\lambda(n) = \operatorname{lcm}(p-1, q-1)$$ is the exponent of the multiplicative group of integers modulo $$n$$, i.e. the smallest positive integer such that $$x^{\lambda(n)} \equiv 1 \pmod n$$ for all $$x$$.*

This means that if $$ed$$ is one more than an integer multiple of $$\lambda(n)$$, i.e. if $$ed \equiv 1 \pmod{\lambda(n)}$$ or, equivalently, if $$ed = k\lambda(n)+1$$ for some integer $$k$$, then $$x^{ed} = x^{k\lambda(n)+1} = (x^{\lambda(n)})^k x \equiv 1^kx = x \pmod n.$$

(Of course, the Euler totient $$\varphi(n) = (p-1)(q-1)$$ is itself an integer multiple of $$\lambda(n)$$, so $$ed \equiv 1 \pmod{\varphi(n)}$$ implies $$ed \equiv 1 \pmod{\lambda(n)}$$.)

*) To be precise, $$x^{\lambda(n)} \equiv 1 \pmod n$$ only holds for $$x$$ coprime with $$n$$, since if $$x$$ shares a prime factor with $$n$$, it won't be invertible modulo $$n$$ and no power of it can be congruent to $$1$$ modulo $$n$$. That's why the definition of the modular multiplicative group requires the elements to be coprime to the modulus. However, the slightly weaker congruence $$x^{\lambda(n)+1} \equiv x \pmod n$$ does hold for all $$x$$ as long as $$n$$ is squarefree, and that's all we really need for RSA. Not to mention that finding a positive $$x < n$$ that's not coprime to the modulus $$n$$ is literally equivalent to factoring $$n$$.

To get the decrypted value $$x^e \pmod n$$ of the meesage $$x$$ you need the Euler's theorem : $$a^{\varphi (n)} \equiv 1 \pmod{n}$$

Replace $$a$$ with $$x$$; $$x^{\varphi (n)} \equiv 1 \pmod{n}$$

Now, take any value as the decryption exponent $$d'$$ to figure out

$$x^{e\cdot d'} \equiv \;? \pmod{n}$$

Now, consider $$e\cdot d' \bmod \varphi (n)$$ that is equal to $$e\cdot d' = k \varphi (n) +t.$$

Pun back into the equation.

$$x^{e\cdot d'} \equiv x^{k \varphi (n) +t} \equiv x^{k \varphi (n)} x^t \equiv 1^{k} x^t \equiv x^t \pmod{n}$$

For decryption, you want the $$d'$$ so that $$x^{e\cdot d'} \equiv x \pmod{n}$$

For this we need $$t=1$$ this means that

$$e\cdot d' \equiv 1 \bmod{\varphi (n)}.$$ i.e. word the inverse.

Note 1: RSA is actually defined with Carmichael lambda $$\lambda(n)$$ See $$\lambda$$ versus $$\varphi$$ in RSA

Note 2: The only cases in which a message $$(m,n)\not\equiv 1$$ is when $$m$$ is $$p$$ and $$q$$. RSA works with that, too. One can see this with CRT. See Does RSA work for any message M? for details.

• 𝑎 and 𝑛 should be coprime. How can one know that the input to be encrypted x, is also coprime with n? I believe n is a product of 2 primes, so it isn't prime. – sanjihan Sep 29 '19 at 9:21
• The only cases are $p$ and $q$ and RSA works with that, too. See Does RSA work for any message M? – kelalaka Sep 29 '19 at 9:27