2
$\begingroup$

The question: "10 friends wish to establish secure communications between themselves using asymmetric-key cryptography. How many keys need to be known by each user?" was posed by my teacher. He says 10 keys are needed. I say only 2 keys are needed. As long as they have copies of the same keypair (keypair=2 keys, a public and a private), they don't need more than two. Why in the WORLD would you need more than a public key and a private key?

Edit:

I have already seen a few questions of this type by googling. Turns out this kind of question never specifies that the people of the group must be able to talk individually to each other. Nevertheless, the student must always assume they want to talk individually and secretly. That makes no sense to me, but that's reality. Ie: In public key cryptography, how many keys are required for secure communication between n parties?

In other words, in criptography, when they say communication between N entities, it is not actually communication between N entities, it's more like N private communications between each of the N entities.

$\endgroup$
  • 4
    $\begingroup$ If you only know your own key, how would you encrypt messages for your friends? $\endgroup$ – SEJPM Nov 20 at 10:43
  • $\begingroup$ Each person needs the public key of everyone else to encrypt to them, so 10 key pairs are created, 1 per person. Everyone needs a different key pair so that noone can read info that's not for them. $\endgroup$ – SamG101 Nov 20 at 11:09
  • $\begingroup$ Ten persons may keep a private key secret, but only if nine did not get it in the first place. And then that's not even easy. $\endgroup$ – fgrieu Nov 20 at 11:55
  • $\begingroup$ @SEJPM We would all use the same two keys. Copy and paste the keys. There would be no "my own key", but rather "our own key". If the purpose is to communicate between us, why use more? $\endgroup$ – Student123843 Nov 20 at 12:21
  • 1
    $\begingroup$ I'm not sure what other way you could interpret "communication between N users". If I wanted to describe the meaning you got, I would say "communication from 1 user to N users". $\endgroup$ – Josh Eller Nov 20 at 19:08
2
$\begingroup$

Depends if "between themselves" means that they are sort of in a simple group-chat scenario. Then one private-public-key pair (i.e. RSA) would theoretically suffice (not factoring in the security), because they can all encrypt messages with the public key and decrypt messages with the private key that they all have an identical pair of it. In actual group-chat messaging applictions that's not the case due to security. You can look at this answer for more information how it actually works in group-chats.

If they all want to send / receive messages between them individually then they would have to know 10 keys in total. Their own private key (and their public key for other people to use) and 9 public keys from each other member. Alice would i.e. send a message to Bob using Bob's public key and (only) Bob can then decrypt it because he's the only one that has the corresponding private key to his public key.

$\endgroup$
  • 2
    $\begingroup$ Would you agree with the following?: Asymmetric needs 2n keys in total, and n keys known by each user. Symmetric needs n(n-1)/2 keys in total, and n(n-1)/2 keys known by each user. $\endgroup$ – Student123843 Nov 21 at 15:10
  • $\begingroup$ Yes, that's correct. Asymmetric cryptography has less keys because you just distribute your own public key for everyone to send messages to you that can all be decrypted with your single private key. For symmetric cryptography you need to establish with each person a key for secure communication. $\endgroup$ – AleksanderRas Nov 21 at 15:26
3
$\begingroup$

Actually you are both wrong, assuming that each user wants to authenticate themselves individually and / or establish private conversations between pairs. Unfortunately this is assumption is missing from the question. If everybody is using (EC)DH then they need a key pair each to setup communication by establishing a session key. That means 10 times 2 keys = 20 keys. However, quite often key and key pair are confused, so the professor is really talking about the latter, only counting the private keys / key pairs, making 10 the correct answer.

If you establish a "master" user that you trust, and no entity authentication is required then you are correct. You need just one private key pair known to all, initially distributed by the master setting up the group. Then you can e.g. encrypt a session key with the public key and only those that have the private key can decrypt. Arguably this is not a good example of asymmetric cryptography though: the private key is now a shared secret, something that is common for symmetric cryptography rather than asymmetric cryptography. The sharing of the private key is required in this scheme, otherwise an adversary can join by identifying as one of your friends.

Note that just having 10 key pairs is not enough to authenticate all the users and setup 1:1 communication. It is also required to trust the public keys. Authentication is about proving you have (access to) a private key that belongs to a public key known to belong to you by the other user.


Note that I've talked about (EC)DH rather than RSA in the first section. It is common to setup (multiple) session keys in transport protocols rather than encrypting directly with the public key and decrypt with the private key. Of course, this requires a set of temporary keys in addition to the asymmetric keys.

It is possible to perform encryption / signature generation with just 10 key pairs, so session keys are not necessary. However, that's really not following good cryptographic practice. So I decided simply not to count the symmetric session keys.

$\endgroup$
  • $\begingroup$ So some people (type A people) say "key" (1 key) when they mean "keypair" (2 keys), but not all people, right? Some people (type B people) would still count two keys. If that is so, what am I supposed to do the day of my test? How am I gonna be able to guess if the guy who made the question and the answer is a type A or a type B? $\endgroup$ – Student123843 Nov 20 at 12:37
  • $\begingroup$ Explain your doubts to your professor and ask him to clarify. If it isn't computer based and you can leave comments, choose 20 and explain that you are talking about 10 key pairs. In the unlikely event that neither is possible, follow what they are saying just for the sake of getting a good grade. $\endgroup$ – Maarten - reinstate Monica Nov 20 at 12:41
  • $\begingroup$ Warning: above answer is about the total number of keys, and that's not correct as How many keys need to be known by each user? is in the question. The minimum number of keys per user is indeed 10 as explained in the answer of Alexander . Or 11 if you assume that you also hold on to your own public key, but that's not required. Otherwise the answers are compatible with each other. $\endgroup$ – Maarten - reinstate Monica Nov 21 at 19:32
1
$\begingroup$

Let's take a look at this from a higher level of view.

In asymmetric cryptography, private keys provide some form of authentication. Let $(e, d)$ be a public/private key pair respectively of a secure asymmetric encryption scheme $E$, and let $c = E_e(m)$ be the ciphertext corresponding to the plaintext $m$. If one is able to recover $m$ from $c$, then it's assured by the hardness of the underlying cryptographic scheme that $c$ is uniquely addressed to the holder(s) of $d$. Ignoring the issues arising by using an insecure medium for communication (e.g. the internet), if someone comes up to you with $m$, you have strong assurance that holder of $m$ is actually who you want it to be decrypted by, thus authentication.

In your case, if you want 10 parties in the network to be distinguishable, you would need 10 distinct key pairs because you would need to authenticate each of them separately. Otherwise, if you only want to address the group of users and you want to distribute the message to every member, you don't need separate authentication for each user, hence a single key pair held by all members is sufficient to distinguish the members of this group from the rest of the network.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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