問76
頻出度★★☆
共通鍵暗号方式では通信の組合せごとに鍵が1個必要となる。例えばA～Dの4人が相互に通信を行う場合は，AB，AC，AD，BC，BD，CDの組合せの6個の鍵が必要である。8人が相互に通信を行うためには何個の鍵が必要か。
平成25年度 春期 ITパスポート試験 問76
テクノロジ系基礎理論 › 応用数学
この問題の解説と、これまでの解答の記録です。
解説
問 76
不正解ア
12 は、4 人のときの 6 個を「人数が 2 倍なら鍵も 2 倍」と考えて 6×2 とした値。鍵の数は人数に比例せず、n(n−1)÷2 という約 2 乗のペースで増えるので誤り。実際 4 人→8 人で鍵は 6 個→28 個と、2 倍ではなく約 4.7 倍に増える。
不正解イ
16 は 8×2 や 4×4 に相当する値で、組合せの計算 n×(n−1)÷2 のどの段階にも現れない。この 16 を式に戻すと n(n−1)÷2 = 16 を満たす整数 n は存在せず、8 人の相互通信の鍵数としては成立しない。
- ウ
正解 共通鍵暗号方式では、通信する 2 人の組ごとに 1 個の鍵が必要になる。したがって必要な鍵の総数は「n 人の中から 2 人を選ぶ組合せの数」に等しく、nC2 = n×(n−1)÷2 個で求められる。問題文が示す A～D の 4 人の例で確かめると 4×(4−1)÷2 = 6 となり、AB，AC，AD，BC，BD，CD の 6 個と一致するので、この式が正しいことが確認できる。同じ式に n=8 を当てはめると 8×(8−1)÷2 = 8×7÷2 = 28 となる。別の数え方でも同じで、8 人それぞれが自分以外の 7 人と鍵を共有するので延べ 8×7 = 56 通りだが、AB と BA は同じ 1 個の鍵なので 2 で割って 28 個となる。よって正解は ウ の 28。
不正解エ
32 は 8×8÷2 と計算した場合の値で、AA や BB のように「自分自身との組」まで数えてしまっている誤り。相手は自分以外の 7 人なので、掛けるのは 8 ではなく 8−1 = 7 であり、正しくは 8×7÷2 = 28 個となる。
ここがポイント
- 共通鍵暗号方式で n 人が相互に通信する場合に必要な鍵の数は、2 人の組合せの数 nC2 = n×(n−1)÷2 個。「各人が自分以外の n−1 人と鍵を持つ → 延べ n(n−1) → AB と BA は同じ鍵なので 2 で割る」と考えると導きやすい。
- 鍵の数が人数の約 2 乗で増えることが共通鍵暗号方式の弱点（鍵管理の負担が大きい）。一方、公開鍵暗号方式では 1 人が公開鍵と秘密鍵の対を持てばよいので鍵の総数は 2n 個で済み、人数に比例した増え方にとどまる。
用語