0
$\begingroup$

This question already has an answer here:

I've got a question concerning fields used in RSA.

Let's use the following symbols for my example:

{p,q} = primes
{e,n} = public key
{d,n] = private key

I learnt that an inverse element exists if a is coprime to m.

Applied to RSA I would have guessed that e needs to be coprime to n in order to find it's inverse element, because n is used as mod. But according to the rules of RSA it has to be coprime to ϕ(n) (gcd(ϕ(n),e)=1). Why?

$\endgroup$

marked as duplicate by poncho, yyyyyyy, fgrieu, woliveirajr, DrLecter Apr 24 '15 at 20:56

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Because $d$ needs to be an inverse of $e$ modulo $\varphi(n)$. $\endgroup$ – yyyyyyy Apr 24 '15 at 19:40
4
$\begingroup$

Because RSA takes advantage of the fact that:

$a^{\phi(n)} \equiv 1 \mod n$

Which means:

$a^{\phi(n)+1} \equiv a \mod n$

So, in order to encrypt and decrypt using $e$ and $d$, we need:

$ed \equiv 1 \mod \phi(n)$

Which can only be true if $gcd(e,\phi(n)) = gcd(d,\phi(n)) = 1$

$\endgroup$

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