問70
頻出度★★★
共通鍵暗号方式では通信の組合せごとに鍵が 1 個必要となる。例えば A～D の 4 人が相互に通信を行う場合は, AB, AC, AD, BC, BD, CD の組合せの 6 個の鍵が必要である。10 人が相互に通信を行うためには何個の鍵が必要か。
平成22年度 春期 ITパスポート試験 問70
This question's explanation and your answers so far.
解説
問 70
Incorrectア
15 is the value you get when you scale the example (6 keys for 4 people) in simple proportion to the number of people, 6×(10÷4) = 15, or when you mistake the number of people and compute the combinations for 6 people, 6×5÷2 = 15. The number of keys is not proportional to the number of people; it grows as n(n-1)÷2, roughly in proportion to the square of the number of people, so this is wrong. For 10 people, 45 keys is correct.
Incorrectイ
20 is the value you get when you undercount the pairs, for example by assuming each person only needs to hold 2 keys and computing 10×2 = 20. In reality each person must hold a separate shared key with each of the other 9 people, which comes to 10×9÷2 = 45 keys in total, so this is wrong.
- ウ
正解 In symmetric-key cryptography, one dedicated shared key must be prepared for each pair of people who communicate with each other. The number of keys required therefore equals the number of combinations of choosing 2 people out of n, given by the formula nC2 = n×(n-1)÷2. Checking this against the 4-person example in the figure gives 4×3÷2 = 6 keys, which matches the 6 lines drawn in the figure (AB, AC, AD, BC, BD, CD). Applying the same idea to 10 people: each person holds a key with each of the other 9 people, giving 10×9 = 90 in raw count, but AB and BA are the same key counted twice, so divide by 2, giving 10×9÷2 = 45 keys. Therefore ウ, 45, is correct.
Incorrectエ
50 is the value you get when you compute 10×10÷2 = 50 without excluding the combination of a person with themselves. A combination is a pair of two different people, so the number you multiply by is (10-1) = 9, the people other than yourself, and 10×9÷2 = 45 keys is correct. Applying the same method to the 4-person example gives 4×4÷2 = 8, which does not match the 6 lines in the figure, further showing that it is wrong.
ここがポイント
- Symmetric-key cryptography needs a unique key for each pair of communicating parties, so when n people all communicate with each other the number of keys is the number of combinations, nC2 = n(n-1)÷2. The key point is to divide the raw count of n(n-1) by 2, because AB and BA are the same key.
- Because the number of keys grows roughly with the square of the number of people, key management, that is creating, distributing, and storing keys, becomes dramatically heavier as the number of users increases. This is the drawback of symmetric-key cryptography when contrasted with public-key cryptography, where each person only needs one pair of a public key and a private key, so 2n keys are enough.
用語