2019 (R1) 年 国税専門官 情報工学 No.67 解説

　問 題　　　　　

k 人が相互に暗号を使って通信する場合を考える。共通鍵暗号方式を用いた場合に必要な異なる鍵の総数を M、公開鍵暗号方式を用いた場合に必要な異なる鍵の総数を N とする。M/N が 6 以上となるような最小の k はいくらか。ただし、公開鍵暗号方式では、公開鍵と秘密鍵をそれぞれ一つと数えるものとする。

1． 20
2． 25
3． 30
4． 35
5． 40

 

 

 

 

 

　解 説　　　　　

小さな人数で具体的に考えるとよいです。共通鍵暗号方式では、通信する 2 者間ごとに 1 つ共通鍵が必要になります。公開鍵暗号方式では、各通信者ごとに公開鍵と秘密鍵が 1 つずつ必要です。

【k = 2 の場合：Alice と Bob】
共通鍵暗号方式の場合
Alice と Bob の間に 1 つの共通鍵があれば、それで暗号化と復号化をすることで通信できます。

公開鍵暗号方式の場合
Alice の公開鍵と秘密鍵、Bob の公開鍵と秘密鍵 が必要です。つまり、全部で 4 つ必要です。

【k = 3 の場合：Alice と Bob と Carol】
共通鍵暗号方式の場合
Alice と Bob、Alice と Carol、Bob とCarol の間にそれぞれ共通鍵が必要です。つまり、全部で 3 つ必要です。

公開鍵暗号方式の場合
Alice の公開鍵と秘密鍵、Bob の公開鍵と秘密鍵、Carol の公開鍵と秘密鍵が必要です。つまり、全部で 6 つ必要です。

一般的に考えると k 人に対し
共通鍵暗号方式では _kC₂ = k(k-1)/2 個
公開鍵暗号方式では 2k 個の鍵が必要です。

従って
M/N = {k(k-1)/2}/2k = (k-1)/4 です。

(k-1)/4 ≧ 6 となるのは、k ≧ 25 です。
最小の k は 25 とわかります。

以上より、正解は 2 です。