Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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 security.stackexchange.com 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
2  
add comment

3 Answers

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
add comment

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
add comment

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
add comment

Your Answer

 
discard

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.