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$
  • $\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 '14 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 '14 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 '14 at 11:01
  • 1
    $\begingroup$ @joker For example: en.wikipedia.org/wiki/RSA_(cryptosystem)#Proofs_of_correctness. $\endgroup$ – Yuval Filmus May 24 '14 at 14:08
4
$\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$
  • $\begingroup$ $\langle n\hspace{.02 in},\hspace{-0.03 in}e,\hspace{-0.03 in}d\hspace{.03 in}\rangle = \langle 143,\hspace{-0.04 in}7\hspace{-0.02 in},\hspace{-0.03 in}43\rangle \;$ is a counter-example to your iff sentence. $\;\;\;\;$ $\endgroup$ – user12859 May 24 '14 at 9:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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