Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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)$.
