問76
頻出度★★☆
共通鍵暗号方式では通信の組合せごとに鍵が1個必要となる。例えばA～Dの4人が相互に通信を行う場合は，AB，AC，AD，BC，BD，CDの組合せの6個の鍵が必要である。8人が相互に通信を行うためには何個の鍵が必要か。
平成25年度 春期 ITパスポート試験 問76
テクノロジ系基礎理論 › 応用数学
This question's explanation and your answers so far.
解説
問 76
Incorrectア
12 comes from taking the 6 keys needed for 4 people and doubling them as 6×2, on the idea that doubling the number of people doubles the number of keys. The number of keys is not proportional to the number of people; it grows at a roughly squared pace, as n(n−1)÷2, so this is wrong. In fact, going from 4 people to 8 people increases the keys from 6 to 28, about 4.7 times rather than 2 times.
Incorrectイ
16 corresponds to values such as 8×2 or 4×4, and it appears at no stage of the combination calculation n×(n−1)÷2. Putting 16 back into the formula, there is no integer n that satisfies n(n−1)÷2 = 16, so it cannot be the number of keys for 8 people communicating with one another.
- ウ
正解 In symmetric-key cryptography, one key is needed for each pair of people who communicate. The total number of keys therefore equals the number of ways to choose 2 people out of n, that is nC2 = n×(n−1)÷2. Checking with the example of the 4 people A through D given in the question, 4×(4−1)÷2 = 6, which matches the 6 keys AB, AC, AD, BC, BD, and CD, so the formula is confirmed to be correct. Applying the same formula with n=8 gives 8×(8−1)÷2 = 8×7÷2 = 28. Another way of counting gives the same result: each of the 8 people shares a key with the other 7, making 8×7 = 56 in total, but AB and BA are one and the same key, so dividing by 2 gives 28. The correct answer is therefore ウ, 28.
Incorrectエ
32 is the value obtained by calculating 8×8÷2, which mistakenly counts even pairs of a person with themselves, such as AA and BB. The other party is one of the other 7 people, so the number to multiply by is not 8 but 8−1 = 7, and the correct calculation is 8×7÷2 = 28 keys.
ここがポイント
- In symmetric-key cryptography, the number of keys needed for n people to communicate with one another is the number of 2-person combinations, nC2 = n×(n−1)÷2. It is easy to derive by thinking: each person holds a key with each of the other n−1 people → n(n−1) in total → AB and BA are the same key, so divide by 2.
- The number of keys growing roughly with the square of the number of people is the weakness of symmetric-key cryptography (the burden of key management is heavy). By contrast, in public-key cryptography each person only needs to hold one pair of a public key and a private key, so the total number of keys is just 2n, and the growth stays proportional to the number of people.
用語