I'm fairly new to this stuff so be forgiving. I'm trying to learn how RSA works, My resources for the manner of sake:

This is what I got so far:


$m^{phi(n)} \equiv 1 \bmod n$

as long as $m$ coprimes to $n$.

So eventually:

$m^{k * phi(n)+1} \equiv m \bmod n$

Now we construct $e$ and $d$:

$k*phi(n) +1 = e * d$

$e$ is selected so that it coprimes with $phi(n)$

I have 2 questions:

  1. Since $m$ can be anything (this is the encrypted content right?), how do you verify that $m$ and $n$ coprimes, as needed for the Euler's theorom to work?

  2. Why do $e$ needs to comprime to $phi(n)$ ?


  • 1
    $\begingroup$ 1, RSA can encrypt any messages $m < n$. there are at least two good answers to this. 1 2. How do you find the inverse of $e$? Please search this site before asking? If something is not clear on the answers you can ask. $\endgroup$
    – kelalaka
    Jan 27 at 17:06
  • $\begingroup$ As you will see the problem here How to compute m value from RSA if phi(n) is not relative prime with the e? and remember the correctness requirement $\endgroup$
    – kelalaka
    Jan 27 at 18:59
  • $\begingroup$ Even the 'simple' version of wikipedia correctly notes you can, and we generally do, use Carmichael's $lambda(pq)=lcm(p-1,q-1)$ instead of Euler's $phi$, but real wikipedia is more detailed. $\endgroup$ Jan 28 at 0:47

Your Answer

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

Browse other questions tagged or ask your own question.