Take the 2-minute tour ×
Super User is a question and answer site for computer enthusiasts and power users. It's 100% free, no registration required.

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

1 Answer 1

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

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.