5
$\begingroup$

Quoting part of my homework/assignment:

How many keys are required for secure communication among 1000 person if:

  1. Symmetric key encryption algorithm is used?
  2. Asymmetric key encryption algorithm is used?

My guess:

For symmetric they each need to maintain and transfer their own key, so probably $1000 \times 1000$, and for asymmetric maybe just $2000$, each having one public one private.

Is that correct?

$\endgroup$
6
  • 4
    $\begingroup$ The answer depends on the security requirements, it could be just 1 symmetric key if everyone is supposed to read the messages of everyone else (group key) $\endgroup$ – Richie Frame May 8 '14 at 19:24
  • $\begingroup$ Its secure communication. $\endgroup$ – Prakash Wadhwani May 8 '14 at 19:31
  • 1
    $\begingroup$ Its secure communication. That was rather obvious. The question is: “What exactly are the security requirements which are expected in this secure communication?” Which somewhat asks for a protocol description… in case your homework/assignment provides that. $\endgroup$ – e-sushi May 8 '14 at 20:20
  • 2
    $\begingroup$ Do they really need a symmetric key to communicate with themselves? $\endgroup$ – mikeazo May 9 '14 at 12:25
  • 1
    $\begingroup$ I wouldn't count an asymmetric keypair as two keys. $\endgroup$ – CodesInChaos Jan 23 '15 at 17:01
4
$\begingroup$

For the symmetric key, you can approach this problem as a complete graph with order 1000. With the vertexes representing people and the edges representing the symmetric keys. Then each vertex would have degree 999 and, applying the Handshaking lemma, the number of edges would be:

$(1000 \times 999)/2 = 499500$

So they would need 499500 symmetric keys to have a secure communication between all of them.

For the asymmetric keys, each one would have 2 keys, so a total of 2000 keys.

$\endgroup$
2
$\begingroup$

Symmetric key encryption algorithm is used?

For symmetric, you need ${n \choose 2} = \frac{n \cdot (n-1)}{2}$ keys: Each pair of parties would need a single key that will be used to both encrypt and decrypt the message between the two parties. The number of pairs of parties is equal to the number of combinations to choose a pair of parties among $n$ parties: first you choose the first party - $n$ possibilities. Then, you are left with $n-1$ options to choose the next party. Once you've chosen the pair of parties, notice that you don't have any significance to the order of the parties in the pair, so you need to divide the number of possibilities by 2 to cancel out the order. Overall it's ${n \choose 2} = \frac{n \cdot (n-1)}{2}$.

Asymmetric key encryption algorithm is used?

For asymmetric, you need $2n$ keypairs, like you said - every party $A$ that wants to send a message $m$ to party $B$, encrypts $m$ using $PK_B$, the public key of party $B$, and then party $B$ decrypts the message using the private key corresponding to $PK_B$.

$\endgroup$
1
  • 3
    $\begingroup$ Welcome to Crypto.SE! Your answer while technically correct is bit short / doesn't really help the asker to see why these formulas hold. Would you please mind and edit your answer a bit? $\endgroup$ – SEJPM May 18 '18 at 18:34
1
$\begingroup$

For a homework question you are probably correct. If the keys are distributed in a secure way that should be the minimum amount of keys for persons to communicate without them being able to read each others messages, if those messages can be intercepted.

Practical protocols could use more or fewer static keys, it all depends on the requirements, attack vectors etc..

$\endgroup$

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