I am just learning about RSA encrytion and I am somewhat confused.
First two prime numbers $p$ and $q$ must be chosen and multiplied to get $n$. Then we compute Euler function $\varphi (n) = (p-1)(q-1)$.
The public key $e$ is generated by choosing a random number that fulfills the condition $gcd(e, \varphi(n)) = 1$. And the private key $d$ is then computed $d * e \:\: mod\:\varphi(n) = 1$.
So if Alice wants to send a message to Bob, a pair of public and private key is generated. But if Bob wants to send something back to Alice, must another pair of public and private key be generated?
If this is the case, does it mean that for RSA between $x$ parties, there must be in total $x(x-1)$ keys (public and private) generated?
$\begingroup$
$\endgroup$
6
-
1$\begingroup$ Hint: the usual way things are described is that each of the $x$ participant draws a public/private key pair, then (by some way insuring integrity) makes their public key available to all participants. $\endgroup$– fgrieu ♦Nov 29, 2020 at 19:13
-
$\begingroup$ Ah okay, so this means that for $x$ participants there will still be $x(x-1)$ pairs of public and private keys generated? $\endgroup$– noobcoderNov 29, 2020 at 19:28
-
4$\begingroup$ Analogy: if each of $x$ persons has a public phone number and a private phone, how many phone numbers and phones are there? Note: we have a policy to only give hints on questions that seem to be homework. That makes sense because the point of such exercise is that you learn how to derive and check a result, not that you learn (much less, get) the result. $\endgroup$– fgrieu ♦Nov 29, 2020 at 20:38
-
$\begingroup$ any user can use the same public key (e.g. belonging to user_k) to encrypt a message to user_k $\endgroup$– kodluNov 29, 2020 at 21:09
-
$\begingroup$ Although the 1978 paper proposed choosing $e$ randomly, it doesn't need to be random, or large, and in practice is usually 65537. It does need to be coprime with $p-1, q-1$ but that can be achieved when choosing $p, q$. Also to be clear $p, q$ must be large enough and distinct -- some people consider this implicit in saying you choose 'two' primes but mathematicians like to be explicit -- and the inversion can be done using Carmichael's lambda instead of Euler's phi. All of this is explained in wikipedia, which you might look at, as well as many textbooks. $\endgroup$– dave_thompson_085Nov 30, 2020 at 3:05
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
So if Alice wants to send a message to Bob, a pair of public and private key is generated. But if Bob wants to send something back to Alice, must another pair of public and private key be generated?
Yes. Bob's public/private key pair, which protected the Alice-to-Bob transfer, is not usable to send data to Alice. However it's usable by anyone [assumed knowing Bob's public key $(n_b,e_b)$, trusting that to be matching Bob's private key $(n_b,d_b)$, and that Bob will not reveal that private key or use it unwisely] in order to send a confidential message to Bob.
Hence each user may need a single public/private key pair, yet the system allow anyone to send a confidential message to anyone.
If this is the case, does it mean that for RSA between $x$ parties, there must be in total $x(x-1)$ keys (public and private) generated?
No. As far as counting how many public/private key pairs there are, a good analogy is public phone number and private phone: we need as many phone numbers, and corresponding phones, as there are users.
