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.

In public key cryptography, how many keys are required for secure communication between n parties?

In my view the answer should be $n^2$.

Reason: There are ‘$n$’ Parties. Every Party has One (1) Public Key (for Encryption). Also, every party has $(n-1)$ private keys (paired) (for Decryption). So every party has $$ 1 + (n-1) = n\,keys,$$ and there are $n$ parties communicating. Number of Keys required is therefore equal to $$ n * n = n^2$$ Have a look at the Image also, which provides the analogy

Now, am I correct? (Please be specific & also show the full logic & give proper explanations).

share|improve this question
    
Why would every party have one public key and $n$ private keys? That would mean there are $n$ public keys and $n^2-n$ private keys in the total system. Usually there is one public key for every private key, so the answer you proposed in the question is wrong. It is correct, that each user will have a total of $n$ keys, but the distribution of public and private keys will be different, and there are duplicates over all users (the questions states how many keys are required, not how many keys are in the system). –  tylo Jun 23 at 11:58
    
@tylo SO Is it correct to say there are $n^2$ keys? Or In short, What are the no of keys (total)? –  DWITI K DAS Jun 23 at 12:08
3  
It feels like you are so convinced that the answer is $n^2$ that you won't believe anyone until they say you are right. If we were talking symmetric key crypto then the answer would be $n^2$. Since we are talking asymmetric key crypto, the answer is $2n$. That is one of the major benefits of asymmetric crypto. –  mikeazo Jun 23 at 12:10
1  
I have absolutely no clue what that diagram shows, but your thought process is totally wrong, yes. The assumption in your question is "there are public keys". and that means "they are secure". Questioning the assumption of the question is plain wrong. –  tylo Jun 23 at 12:22
1  
I'm voting for closing this thread now, because it started to become a discussion. Besides being pretty much "below homework level", this question isn't beneficial for anyone else, because the basic understanding of the question is just wrong. –  tylo Jun 23 at 12:30
show 5 more comments

2 Answers 2

up vote 2 down vote accepted

Asymmetric keys come in pairs. The public key of a pair can be used to encrypt data so that only the holder of the private key can decrypt it. If you had one private key, you'd also have exactly one public key that corresponds to it, so your answer of one public key and $n-1$ private keys per person cannot be entirely correct.

The question is somewhat ambiguous, but the answer that is probably expected is $n$ key-pairs, so $2n$ keys altogether. Each person has a single key-pair and knows all the public keys of others' key-pairs. They can encrypt data using any public key to be decrypted using that person's (single) private key.

The number of keys each person knows is about $n$ (one private key and $n-1$ public keys, plus their own public key if you want to count that). However, the total number is not $n*n$, because the public keys are all the same $n$ keys.


However, in the real world you would use hybrid encryption. In addition to the long term key-pairs there would also be a symmetric key for either every message sent or every session (in an interactive protocol like chat). Further, depending on the symmetric primitives used, you could need a second short term key for message authentication/integrity.

share|improve this answer
    
How is it 2n? I mean If there is a public private pairing then One doesn't need to Encrypt or decrypt his own message! So it must be 2n(n-1) then! There are not in pairs, as you said! –  DWITI K DAS Jun 23 at 10:39
    
Ya, But what about the Private keys (See my explanations also)? You are correct about the Public Keys, But Private keys have their own secrecy (& pairing)! –  DWITI K DAS Jun 23 at 10:48
    
Ya But to others, same Private key wont work then, there must be total of n^2 keys –  DWITI K DAS Jun 23 at 10:54
2  
@DWITIKDAS, I tweaked it some, but honestly I've gone as basic as it gets. "Paired" probably refers to fact that a private key is paired with a public key, not to any pairing of two parties. –  otus Jun 23 at 12:03
1  
Thanks Everyone! for their Contribution! –  DWITI K DAS Jun 23 at 12:28
show 8 more comments

This is how it works..

For every user, there is 1 Private key and 1 Public key.
The Private key is used to decrypt messages from other users.
The Public key is used by everyone else to encrypt messages for that user.
These keys are mathematically linked.

If you have 5 users, there are 5 Private keys and 5 Public keys.
Each user would have a copy of everyone else Public keys, which means $n*(n-1)$ copies of the $n$ public keys on various systems to ensure mutual communication between all users, plus the $n$ Private keys.

The unique key count is $2n$, with $n^2$ distributed keys both Private and Public on various systems (assuming a user does not keep a copy of their public key once it is distributed).

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.