# RSA finding the inverse of the public exponent

I have a very basic doubt in RSA key generation and its usage.

In RSA key generation you choose two large prime numbers of a very large order. Then you multiply them.(eq $p \cdot q = N$) Now, $\phi(N)=(p-1)(q-1)$. Now you find a number $0 < e < \phi(N)$ such that $e$ and $\phi(N)$ are coprime. {$e,N$} becomes your public key. Now you compute $d$(private key) such that $ed \equiv 1 \bmod{\phi(N)}$.

Now suppose you encrypt something (say $m$) with your the public key: $c=m^e\bmod{N}$. To decrypt with the private key, you do $c^d\bmod{N}$.

Now my doubt is that you found out the inverse of $e$ modulo $\phi(N)$, but when you are decrypting you are doing it in modulo $N$. How is this possible?

-

## migrated from security.stackexchange.comApr 6 '12 at 13:48

This question came from our site for information security professionals.

I fixed the public key you had noted. It should be {$e,N$} not {$e,\phi(N)$} –  mikeazo Apr 6 '12 at 14:23

The answer comes from Euler's Theorem. Note: math below is done modulo $N$ unless otherwise specified and draws heavily from group theory.

That theorem says that any element of a group (say $m$) raised to the order of the group, in this case $\phi(N)$ is congruent to $1$ (i.e., $m^{\phi(N)}\equiv 1\bmod{N}$). Furthermore, this holds for multiples of $\phi(N)$ (i.e., $c\cdot\phi(N)$ where c is an integer).

In the case of RSA, you find $e,d$ such that $ed\equiv 1\bmod{\phi(N)}$. Note then that $ed=c\cdot\phi(N)+1$, where $c$ is some integer.

Thus $c^{d}=m^{ed}=m^{c\cdot\phi(N) + 1}=m^{c\cdot\phi(N)}\cdot m^1$. From the Euler's Theorem, $m^{c\cdot\phi(N)}=1$, so that term goes away and you are left with the original message.

-
You can say that Euler's theorem forms the basis for PKI. –  Ashwin Nov 21 '12 at 15:32

I'm not sure that I understand your question, so I might give you an answer that is not accurate.

Anyways, this happens because you encrypt your message using N (N is one of the two parts of the public key, not $\phi(N)$), this way: $c = m^e mod N$, like you said. So, as you can see, it's N that you are using to encrypt your message, and so you need N to decrypt it.

If this is not the answer you were looking for, just ignore it :D

-

Another way to look at it is that you are working in the ring ZmodN, but the multiplicative group of units, U(N) has (p-1)(q-1) elements. You still do the math mod N, but e and d are inverses in U(N) x^(ed) = 1 mod N for any unit x in U(N).

-