ITパスポート 2010年春期問70

問題文

共通鍵暗号方式では通信の組合せごとに鍵が1個必要となる。例えばA〜Dの4人が相互に通信を行う場合は、AB, AC, AD, BC, BD, CDの組合せの6個の鍵が必要である。10人が相互に通信を行うためには何個の鍵が必要か。

🖊️ 解答を隠して解いてみる

ア：15

イ：20

ウ：45（正解）

エ：50

🔒 解説は解答すると表示されます

共通鍵暗号方式（共通鍵：通信双方が同じ鍵を使う暗号方式）では、2人が通信する組合せごとに1つの鍵を用意します。順序（A→B と B→A）は区別せず、自分自身との通信は考えないため、10人間の異なる2人組みの数は組合せの公式で求められます。式で表すと

(2 10) = \frac{10 \times 9}{2} = 45

となり、したがって正しい選択肢はウです。

「誰と誰」の組合せは順序を区別しないことを確認する（AとB は BとA と同じ組合せ）。
順序を区別すると、10人それぞれが残り9人と通信できるので一時的に $10 \times 9 = 90$ 通りと数える。
しかし A–B と B–A は同じなので二重に数えているため $2$ で割る。結果 $90/2 = 45$ 。
あるいは直接組合せの公式 $(2 n) = \frac{n ( n - 1 )}{2}$ に $n = 10$ を代入しても同じ。

ア: 15
15 は 6 人間の組合せ数 $(2 6) = 15$ に相当します。人数を誤って 6 人と見なしたり、公式を間違って適用した場合に出る数です。問題の人数が10人である点を見落としているミスです。
イ: 20
20 は「1人あたり必要な鍵を少数で固定してしまう」ような誤りの結果として出ることがあります。例えば「各人が2人としか通信しない」と誤解して $10 \times 2 = 20$ としてしまうパターンです。問題文は「相互に通信を行う（全員が互いに）」なので、この仮定は誤りです。
ウ:（正解）
上記の通り $(2 10) = \frac{10 \times 9}{2} = 45$ で正しい組合せ数になります。ウが正答です。
エ: 50
50 は「各人が5人分の鍵を持つ」として $10 \times 5 = 50$ としたような計算から生じる誤答です。各人が必要な鍵の数は9ですが、そこから半分にして扱う際の端数処理や二重計算の取り扱いを誤るとこのような値になります。正しい処理では 9 を 2 で割ると4.5になり、そのまま切り上げて整数の 5 を使うのは誤りです（切り上げ/切り捨ては適用しない）。

この種の問題は「握手（ハンドシェイク）問題」としても知られます。一般に n 人で全員が互いに1回ずつ挨拶（または通信）する組合せ数は

(2 n) = \frac{n ( n - 1 )}{2}

です。
鍵の数は人数の二乗に比例して急増するため、人数が多いと鍵管理が大変になります。例えば 100 人だと

(2 100) = 4950

個の鍵が必要です。実運用では、全員と個別に鍵を共有する方式（ペアワイズ鍵）は管理負担が大きいため、鍵配布サーバ（KDC：Key Distribution Center）や PKI（Public Key Infrastructure：公開鍵基盤）など、鍵管理を効率化する仕組みが使われます。

Q1: 両方向通信なら鍵を2つ用意する必要がありますか？
A1: いいえ。共通鍵暗号方式では通信双方が同じ鍵を共有し、暗号化と復号に同じ鍵を使います。したがってA—Bの通信に1つの鍵で十分です。

Q2: 自分自身との通信も鍵が要りますか？
A2: 通常は不要です。自分と自分の通信（自己ループ）は鍵管理の対象ではありません。

Q3: もっと簡単に鍵の数を減らす方法はありますか？
A3: グループ鍵（複数人が同じ鍵を使う）や公開鍵方式（PKI）を使うと、ペアごとの鍵数を減らせます。ただしセキュリティの性質や運用ルールが変わる点に注意が必要です。

関連キーワード: 共通鍵暗号、組合せ、組合せ数、n(n-1)/2、鍵管理、公開鍵(PKI)

\ せっかくなら /

ITパスポートを
クイズ形式で学習しませんか？

すぐに利用可能！