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

Tech

本記事は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

【選択肢の吟味】

選択肢 判定 解説
ア 正解 Diffie-Hellman鍵交換の安全性の根拠は、大きな素数位数を持つ有限群上の離散対数問題の計算困難性に基づきます。
イ 不正解 素因数分解問題の困難さは、公開鍵暗号方式であるRSA暗号の安全性の根拠です。
ウ 不正解 楕円曲線暗号（ECDH等）で用いられるのは「楕円曲線上の離散対数問題」であり、単純な「加算の困難さ」ではありません（加算自体は容易に計算可能です）。
エ 不正解 ナップサック問題の困難さは、歴史的なパブリックキー暗号（Merkle-Hellmanナップサック暗号など）の根拠ですが、解読法が発見されたため現在は主流ではありません。

【ポイント】

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

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

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

ライセンス：本記事のテキスト/コードは特記なき限り CC BY 4.0 です。引用の際は出典URL（本ページ）を明記してください。
利用ポリシー もご参照ください。

コメント

タイトルとURLをコピーしました