3
$\begingroup$

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?

Improve this question
$\endgroup$
2

3 Answers 3

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ You can say that Euler's theorem forms the basis for PKI. $\endgroup$
    – Ashwin
    Nov 21, 2012 at 15:32
  • $\begingroup$ That's not altogether accurate, since there are several different signature algorithms used in PKI. $\endgroup$
    – pg1989
    Nov 11, 2015 at 1:17
  • $\begingroup$ Euler's work formed the basis of most of modern group theory, though, so in that way it forms the basis for PKI. $\endgroup$
    – pg1989
    Nov 11, 2015 at 1:18
  • $\begingroup$ Can you perform general division as the owner of $d, p, q$ ? If I am trying to make more than one invertible inverse, can $c$ just be a random number (in practice)? ... the idea is this.... $(n,d,e)$ ... $d=s$ (sign), $e=v$ (verify). But I also want some extra identities: $w'w = s, t't = 1, f'f = 1$. $\endgroup$
    – Rob
    Dec 25, 2021 at 6:58
0
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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