Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

migrated from Apr 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
up vote 4 down vote accepted

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.

share|improve this answer
You can say that Euler's theorem forms the basis for PKI. – Ashwin Nov 21 '12 at 15:32
That's not altogether accurate, since there are several different signature algorithms used in PKI. – pg1989 Nov 11 '15 at 1:17
Euler's work formed the basis of most of modern group theory, though, so in that way it forms the basis for PKI. – pg1989 Nov 11 '15 at 1:18

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

share|improve this answer

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).

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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