# What does Euler's theorem have to do with RSA?

In RSA we compute e (encryption key) and d (decryption key) $$\bmod phi(n)$$ and not $$\bmod n$$, so how come when we get the keys and encrypt and decrypt we use $$\bmod n$$ not $$\bmod phi(n)$$ using the following rules:

Encryption: $$C =(m^e) \bmod n$$

Decryption: $$m = C^d = (m^e)^d \bmod n = m^{e.d} \bmod n = m^1 \bmod n = m \bmod n$$

I don't understand how come $$e \cdot d=1$$ even if its $$\bmod n$$ not $$\bmod phi(n)$$? because in reality it doesn't equal to $$1$$. What I don't understand is how is it; if it doesn't equal to $$1$$ it will still decipher successfully.

Example:

Given $$p = 11$$, $$q = 3$$ and $$n = 33$$, $$phi(n) = (p-1)(q-1) = 20$$, $$e = 3$$ therefore $$d = 7$$ since $$e \cdot d = 1 \bmod phi(n)$$

lets encrypt the number $$15$$

$$C = 15^3 \bmod n= 9$$

$$m = 9^{7} \bmod n=15$$

but

$$9^7 = (15^{3})^7 = 15^{7 \cdot 3}=15^{21} =15 \mod n$$

How is it possible that we deciphered it successfully using only $$\bmod n$$ and not $$\bmod phi(n)$$? Therefore $$e \cdot d =21$$ and not $$1$$ and still got $$m$$? I have a feeling that Euler's theorem ($$m^{phi(n)}=1 \bmod n$$) have something to do with this but I don't know how!

• It is for proof of the correctness! You can live without it because $a^{b \bmod \phi(n)} \mod n = a^b \mod n$. Can you see why? May 27, 2022 at 22:29
• @kelalaka im afraid i dont understand how is that possible ?
– ezio
May 28, 2022 at 3:16
• crypto.stackexchange.com/a/2894/18298 May 28, 2022 at 19:18

For a given $$n>1$$, let integer $$f>0$$ be such that for all $$m$$ in $$[0,n)$$ with $$\gcd(m,n)\ne1$$ it hold $$m^f\bmod n=1$$. One such integer $$f$$ is the Euler totient of $$n$$, $$\operatorname{phi}(n)$$ aka $$\varphi(n)$$, $$\Phi(n)$$ or $$\phi(n)$$. Among so many Euler theorems, the one in the question likely is about that property of the Euler totient. The smallest such $$f$$ is $$\lambda(n)$$, where $$\lambda$$ is the Carmichael function.

Assume $$e$$ and $$d$$ have been chosen such that $$e\cdot d\bmod f=1$$. By definition¹ of what the operator$$\bmod$$ is when there is no opening parenthesis immediately on it's left, that means: exists integer $$k$$ such that $$e\cdot d=k\cdot f+1$$ (and $$0\le1, which stands).

Now, assuming $$\gcd(m,n)=1$$, \begin{align} \left(m^e\right)^d\bmod n&=m^{e\cdot d}&\bmod n\\ &=m^{k\cdot f+1}&\bmod n\\ &=m^{k\cdot f}\cdot m^1&\bmod n\\ &=m^{f\cdot k}\cdot m&\bmod n\\ &=\left(m^f\right)^k\cdot m&\bmod n\\ &=1^k\cdot m&\bmod n\\ &=1\cdot m&\bmod n\\ &=m&\bmod n\\ \end{align} We have proven this under the condition $$\gcd(m,n)=1$$, which is what the original RSA paper does, and many introductions to RSA do. But that happens to be true under a condition not involving $$m$$: that $$n$$ is square-free, see this.

This "square-free $$n$$" condition is much more satisfying than $$\gcd(m,n)=1$$ in the context of encryption of arbitrary message $$m$$, especially when we use artificially small $$n$$, since then we can't summarily rule out $$\gcd(m,n)\ne1$$ as unlikely. In the question $$n=33$$, thus $$\gcd(m,n)\ne1$$ occurs for $$m$$ one of $$0$$, $$3$$, $$6$$, $$9$$, $$11$$, $$12$$, $$15$$, $$18$$, $$21$$, $$22$$, $$24$$, $$27$$, $$30$$, thus including the $$m=15$$ considered!

¹ For integer $$s$$ and integer $$t>0$$, equivalent definitions of what the operator$$\bmod$$ is when there is no opening parenthesis immediately on it's left include

• $$s\bmod t$$ is the uniquely defined integer $$r$$ with $$0\le r and $$s-r$$ a multiple of $$t$$
• $$s\bmod t$$ is the uniquely defined integer $$r$$ with $$0\le r such that exists integer $$k$$ with $$s=k\cdot t+r$$
• depending on sign of $$s$$, $$s\bmod t$$ is
• if $$s\ge0$$, the remainder of the Euclidean division of $$s$$ by $$t$$
• if $$s<0$$, either
• $$t-((-s)\bmod t)$$ if that's not $$t$$
• $$0$$, otherwise

This is not to be confused with the notation² $$r\equiv s\pmod t$$ with opening parenthesis immediately on the left of$$\bmod$$, which equivalent definitions include:

• $$s-r$$ is a multiple of $$t$$
• exists integer $$k$$ with $$s=k\cdot t+r$$

² $$r\equiv s\pmod t$$ is preferably read with any of the possibly several $$\equiv$$ on the left of$$\pmod t$$ read as congruent or equivalent rather than equal, and with a pause where the opening parenthesis is. That pause is to mark that$$\pmod t$$ qualifies what's been said. It's common to use $$=$$ instead of $$\equiv$$, to omit$$\pmod t$$, or omit the opening parenthesis before$$\bmod$$. That's also a common cause of confusion when the difference between$$\bmod t$$ and$$\pmod t$$ matters, which includes computation of ciphertext in RSA.

• That means exists integer k such that e⋅d=k⋅f+1 i got confused here! and is it possible to work on two modulos in the same equation? e.d=1 is true only under modulo phi(n) not modulo n, sorry im new to cryptography
– ezio
May 28, 2022 at 9:59
• @ezio: For positive integers, $e⋅d=1$ is possible only for $e=1=d$. Please read the new notes 1 and 2 and be careful with notation, RSA is an area where that's critical. Also be aware that when we write $m^{e\cdot d}\bmod n$, the exponent $e\cdot d$ is not modulo $n$ or any other modulo, and can not in general be reduced modulo $n$. The exponent $e\cdot d$ can be reduced under any modulo $f$ that's a non-zero multiple of $\lambda(n)$, including $f=\varphi(n)$.
– fgrieu
May 28, 2022 at 14:27
• sir your first note clicked in my mind as if its the first time i understand something in mathematics objectively, it felt good, thanks sir may allah grant you everything you wish.
– ezio
May 28, 2022 at 21:18