1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    May 23, 2014 at 21:59
  • $\begingroup$ 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}$ $\endgroup$
    – user12859
    May 24, 2014 at 9:26
  • $\begingroup$ 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. $\endgroup$
    – joker
    May 24, 2014 at 11:01
  • 1
    $\begingroup$ @joker For example: en.wikipedia.org/wiki/RSA_(cryptosystem)#Proofs_of_correctness. $\endgroup$ May 24, 2014 at 14:08

1 Answer 1

5
$\begingroup$

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

$\endgroup$
0

Your Answer

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

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