0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Because $d$ needs to be an inverse of $e$ modulo $\varphi(n)$. $\endgroup$
    – yyyyyyy
    Apr 24, 2015 at 19:40

1 Answer 1

Reset to default
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$

Improve this answer
$\endgroup$
0

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