問70
頻出度★★★
共通鍵暗号方式では通信の組合せごとに鍵が 1 個必要となる。例えば A～D の 4 人が相互に通信を行う場合は, AB, AC, AD, BC, BD, CD の組合せの 6 個の鍵が必要である。10 人が相互に通信を行うためには何個の鍵が必要か。
平成22年度 春期 ITパスポート試験 問70
この問題の解説と、これまでの解答の記録です。
解説
問 70
不正解ア
15 は、例示の「4 人で 6 個」を人数に単純比例させて 6×(10÷4) = 15 と計算したときや、6 人の場合の組合せ数 6×5÷2 = 15 と人数を取り違えたときに出る値。鍵の数は人数に比例せず、n(n-1)÷2 とおよそ人数の 2 乗に比例して増えるので誤り。10 人では 45 個が正しい。
不正解イ
20 は、1 人あたり鍵を 2 個持てばよいと考えて 10×2 = 20 と数えるなど、組の数え方を過小に見積もったときに出る値。実際には 1 人が残り 9 人それぞれと別々の共通鍵を持つ必要があり、全体では 10×9÷2 = 45 個になるので誤り。
- ウ
正解 共通鍵暗号方式では、通信する 2 人の組（ペア）ごとに専用の共通鍵を 1 個用意する必要がある。したがって必要な鍵の数は「n 人から 2 人を選ぶ組合せの数」に等しく、公式は nC2 = n×(n-1)÷2 となる。図の 4 人の例で検算すると 4×3÷2 = 6 個となり、図に描かれた線（AB, AC, AD, BC, BD, CD）の 6 本と一致する。同じ考え方を 10 人に当てはめると、1 人が自分以外の 9 人それぞれと鍵を持つので延べ 10×9 = 90 通りだが、AB と BA は同じ鍵を 2 回数えているので 2 で割り、10×9÷2 = 45 個。よって ウ の 45 が正しい。
不正解エ
50 は、10×10÷2 = 50 のように「自分自身との組合せ」を除かずに計算したときに出る値。組合せは異なる 2 人の組なので、掛ける相手は自分を除いた (10-1) = 9 人であり、10×9÷2 = 45 個が正しい。同じ計算法を 4 人の例に当てはめると 4×4÷2 = 8 となり、図の 6 本と合わないことからも誤りと分かる。
ここがポイント
- 共通鍵暗号方式は通信相手の組ごとに固有の鍵が必要なため、n 人が相互に通信する場合の鍵数は組合せの数 nC2 = n(n-1)÷2 個になる。延べ n(n-1) 通りを、AB と BA が同一の鍵であることから 2 で割るのがポイント。
- 鍵数は人数の約 2 乗で増えるため、利用者が増えると鍵の作成・配布・保管という鍵管理の負担が急激に大きくなる。これが公開鍵暗号方式（1 人が公開鍵と秘密鍵の対を持てばよく、鍵数は 2n で済む）と対比される共通鍵暗号方式の短所である。
用語