# How many public keys and private keys are needed for RSA?

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?

• 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.
– fgrieu
Nov 29, 2020 at 19:13
• Ah okay, so this means that for $x$ participants there will still be $x(x-1)$ pairs of public and private keys generated? Nov 29, 2020 at 19:28
• 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.
– fgrieu
Nov 29, 2020 at 20:38
• any user can use the same public key (e.g. belonging to user_k) to encrypt a message to user_k Nov 29, 2020 at 21:09
• 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. Nov 30, 2020 at 3:05

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