Super User is a question and answer site for computer enthusiasts and power users. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Got a homework question here that I have been staring at for a while. I am being asked how many keys will exist in a network of 'n' number of nodes with keys being distributed on a per-host-pair basis.
I understand that there will be a key shared for every network connection that exists between nodes on the network and I have come up with samples of smaller network sizes and their number of keys to try and generate an algorithm that will answer the question but I have been butting my head against the table just to try and figure out the pattern.

Sample(UPDATED...The sample data that I provide here is not correct and was only discovered after the accepted answer was posted): 2 computers on a network results in 1 key

3 computers on a network = 3 keys

4 computers on a network = 6 keys

5 computers = 8 keys

6 computers = 14 keys

7 computers = 20 keys

8 computers = 28 keys... etc..etc.

I know by attaching the 'homework' tag to the question I am understanding that I cannot be directly given the answer - so if someone could at least give me a push in the right direction it would be greatly appreciated.

share|improve this question
up vote 1 down vote accepted

This isn't so much about cryptography as it is about graph theory. When every computer is linked to all others, you have a complete graph, which has **(n(n-1))/2** edges.

For 6 computers, you would have (6*5)/2 = 15 keys.

share|improve this answer
That was it, I had to argue with myself for a while because I pictured I wasn't drawing the network diagrams correctly...therefore making the sample I listed in my original question incorrect. Thank you! – Stephen R May 9 '12 at 16:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .