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.


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$$


$$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!

  • $\begingroup$ 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? $\endgroup$
    – kelalaka
    May 27, 2022 at 22:29
  • $\begingroup$ @kelalaka im afraid i dont understand how is that possible ? $\endgroup$
    – ezio
    May 28, 2022 at 3:16
  • $\begingroup$ crypto.stackexchange.com/a/2894/18298 $\endgroup$
    – kelalaka
    May 28, 2022 at 19:18

1 Answer 1


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<f$, 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<t$ and $s-r$ a multiple of $t$
  • $s\bmod t$ is the uniquely defined integer $r$ with $0\le r<t$ 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.

  • $\begingroup$ 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 $\endgroup$
    – ezio
    May 28, 2022 at 9:59
  • $\begingroup$ @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)$. $\endgroup$
    – fgrieu
    May 28, 2022 at 14:27
  • $\begingroup$ 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. $\endgroup$
    – ezio
    May 28, 2022 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.