# RSA encryption why does ed=1?

So I fully understand the how the RSA algorithm works, but now I am trying to reason with the formula. I want to know:

why the public key e and the private key d in the RSA encryption have to satisfy the equation ed = 1 mod (p − 1)(q − 1)?

Is it because of the standard modular arithmetic rule where 1 mod anything is 1, or is there a more to this answer?

• What research have you done? This is answered in standard textbook explanations of RSA, which are numerous. There is no value to the world in having us re-type out what is already found in standard textbooks and in many online resources. – D.W. May 23 '14 at 21:59
• That quote is incorrect; the congruence only needs to hold mod $\:\operatorname{L}\hspace{-0.03 in}\operatorname{cm}\hspace{.02 in}(\hspace{.04 in}p\hspace{-0.04 in}-\hspace{-0.05 in}1,q\hspace{-0.04 in}-\hspace{-0.05 in}1)\;$. $\hspace{1.34 in}$ – user12859 May 24 '14 at 9:26
• hey @D.W. if you don't have an answer, don't comment. Ive tried many web resources and found nothing. If its all there why not link them. – joker May 24 '14 at 11:01
• @joker For example: en.wikipedia.org/wiki/RSA_(cryptosystem)#Proofs_of_correctness. – Yuval Filmus May 24 '14 at 14:08

## 1 Answer

The relation of $e$ and $d$ is set so that encryption and decryption are inverses of each other, that is, if you encrypt a message then the ciphertext decrypts to the original message. Encryption and decryption are $$c = m^e \pmod{n}, \quad p = c^d \pmod{n},$$ where $n = pq$ is part of the public key, $m$ is the message, $c$ the ciphertext, and $p$ the decrypted plaintext. We want $p = m$, i.e., $$m = m^{ed} \pmod{n}.$$ This equation holds for all $m$ iff $ed \equiv 1 \pmod{\lambda(n)}$, where $\lambda(n)$ is Carmichael's function. For $n = pq$, $\lambda(n) = \mathrm{lcm}(p-1,q-1)$. In practice, $\lambda(n)$ is replaced by Euler's function $\varphi(n) = (p-1)(q-1)$.