本記事はGeminiの出力をプロンプト工学で整理した業務ドラフト（未検証）です。

令和5年度 秋期 情報処理安全確保支援士試験 午前Ⅱ 問12 Diffie-Hellman鍵交換の安全性根拠

Diffie-Hellman鍵交換の仕組みと、その安全性を支える数学的な計算困難性の根拠を正しく理解しているかが問われています。

【問題】

Diffie-Hellman鍵交換において、盗聴がある通信路上で安全に共有鍵を生成できる根拠となっている数学的困難さはどれか。

ア 離散対数問題を解くことの困難さ イ 素因数分解問題を解くことの困難さ ウ 楕円曲線上の加算の困難さ エ ナップサック問題を解くことの困難さ

【解説】

Diffie-Hellman（DH）鍵交換は、事前の鍵共有なしに不特定の通信相手と公開された通信路上で安全に共通鍵（暗号鍵）を生成・共有するアルゴリズムです。

大きめの素数 $p$ とその原始根 $g$ を公開パラメータとし、送信者Aと受信者Bは各自の秘密の値（私有鍵）$a, b$ を生成します。それぞれの公開値 $A, B$ は次のように計算されます。

$$A = g^a \bmod p$$ $$B = g^b \bmod p$$

両者は公開値 $A, B$ を交換し、次の計算によって同一の共有鍵 $K$ を得ます。

$$K = B^a \bmod p = (g^b)^a \bmod p = g^{ab} \bmod p$$

盗聴者は公開された $p, g, A, B$ を入手できますが、$A = g^a \bmod p$ から秘密の値 $a$ を求めるには「余り（剰余）を求める指数計算の逆演算」が必要です。この逆演算を求める問題を離散対数問題（Discrete Logarithm Problem: DLP）と呼び、十分大きな素数 $p$ を用いた場合、現代の計算機能力では現実的な時間内に解くことができません。これがDH鍵交換の安全性の根拠です。

sequenceDiagram
    autonumber
    participant Alice
    participant "Public Channel"
    participant Bob
    Note over Alice,Bob: 公開パラメータ: 素数 p, 原始根 g
    Alice ->> Alice: 秘密鍵 a を生成
    Bob ->> Bob: 秘密鍵 b を生成
    Alice ->> "Public Channel": 公開値 A = g^a mod p
    Bob ->> "Public Channel": 公開値 B = g^b mod p
    "Public Channel" ->> Bob: A を送信
    "Public Channel" ->> Alice: B を送信
    Alice ->> Alice: 共有鍵 K = B^a mod p
    Bob ->> Bob: 共有鍵 K = A^b mod p

【選択肢の吟味】

【ポイント】

• DH鍵交換：事前の鍵共有なしで安全に共通鍵を合意する方式。

• 離散対数問題（DLP）：$g^a \bmod p = A$ から $a$ を求める計算が極めて困難である性質。

• RSA暗号との対比：DH・エルガマル暗号＝離散対数問題／RSA暗号＝素因数分解問題。