ディフィー・ヘルマン：公の場で共有する秘密

アリスは gᵃ mod p を、ボブは gᵇ mod p を送信します。すると、どちらも直接送っていないはずの gᵃᵇ mod p を、二人とも共有できるのです。通信路上を流れた数値は、すべて盗聴者イヴの目に入っています。鍵共有とイヴの攻撃を順を追って進め、p や g を変えながら、どのような条件が彼女の手間を劇的に減らすのかを探ってみましょう。

計算例 — ディフィー・ヘルマン：公の場で共有する秘密

アリスの公開値	8
ボブの公開値	19
共有秘密	2
共有秘密が取りうる値の個数	22 のうち 22
この A に対する全探索の試行回数	7（最悪時は 22）
この A に対するポーリグ・ヘルマン法の試行回数	8（最悪時は 13）
イヴが x から復元した秘密	2

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

レッスン

理論 — ディフィー・ヘルマン：公の場で共有する秘密

ディフィー・ヘルマン鍵共有では、誰でも盗聴できる通信路を使いながら、二者が安全に秘密の数を共有します。まず、素数 p と底 g を公に定めます。双方が秘密の指数を選び、g をその指数で累乗した mod p の値を公開し合います。そして、相手から送られてきた公開値を自分の秘密の指数で累乗します：(gᵇ)ᵃ = (gᵃ)ᵇ = gᵃᵇ mod p。これを第三者が破るには、離散対数問題を解く必要があります。すなわち、公開された A = gᵃ mod p から gˣ ≡ A (mod p) を満たす x を見つけ出すことです。1976年、ディフィーとヘルマンは、離散対数を解くことなしに公開値から共有秘密を導く方法は見当たらないとし、同時にそうした方法が存在しないという証明もないことを記しました。g の位数とは、gⁿ ≡ 1 (mod p) を満たす最小の整数 n ≥ 1 のことです。位数が p − 1 に等しいとき、g を生成元と呼びます。

各記号の意味

p: 法となる素数（公開）
g: 底（公開）
a, b: アリスとボブの秘密の指数
A, B: それぞれの公開値（gᵃ mod p と gᵇ mod p）
x: イヴが特定する指数。gˣ ≡ A を満たす x であれば何でもよいため、実質的に g の位数を法とする a を求めます
ord(g): g の位数：共有秘密が取りうる値の総数

前提: p は 5 から 1,999 までの素数、g は 2 から p − 2 までの任意の底であり、a と b は 1 から p − 2 の範囲をとります。試行回数は、計算された累乗と標的の値を 1 回比較することを指し、成功した最後の比較も含みます。ポーリグ・ヘルマン法の各桁は、候補を順に試すことで求めています。これは原論文で小さな素因数向けに示された手法です。大きな素因数に対してはメモリと時間のトレードオフを用いた探索法も提案されていますが、本ページでは実行していません。ディフィーとヘルマン自身が論文で挙げた例は 200 ビット程度の素数であり、その離散対数の計算にはおよそ 2¹⁰⁰ 回の計算が必要と見積もられていました。

257 において、底 2 が残す秘密はわずか 16 通り 🖖

周期 16 のループ を押してみてください。257 は素数ですから、A も B も 256 通りのどの値にもなり得るように見えます。ところが 2⁸ = 256 ≡ −1 (mod 257) なので、2¹⁶ = 1 となり、2 の累乗は 16 個の数（1, 2, 4, 8, 16, 32, 64, 128, 256, 255, 253, 249, 241, 225, 193, 129）をループするにすぎません。マス目に色が塗られているのがそれらの数です。a と b が何であれ、共有秘密 gᵃᵇ はこの 16 個の中に限られ、ここでは 129 になります。イヴの全探索は 14 回の試行で止まり、最悪でも 16 回を超えません。ここで見つかる x = 13 はアリスの秘密 77 そのものではありませんが、指数が持ちうる周期である mod 16 の世界で合同です。法が素数だからといって安全とは限りません。2 から 255 までにある 254 個の底のうち、実に 126 個は生成元ではなく、そのうち二つの底（16 と 241）では秘密の候補がわずか 4 通りまで狭まります。対照的に、p − 1 = 2 × 131 である 263 では、2 から 261 までのすべての底の位数が 131 か 262 のどちらかになります。

双子素数：811 回対 21 回の試行 🖖

細かく分解できる p − 1 を押してみてください。1621 は素数ですが、1620 = 2² · 3⁴ · 5 と分解できるため、ポーリグ・ヘルマン法が g の 1,620 個の累乗をすべて探す必要はありません。a mod 4 を二つずつの候補から、a mod 81 を三つずつの候補から、a mod 5 を五つの候補から絞り込み、中国剰余定理で統合します。試行回数は最悪でも 2·2 + 4·3 + 5 = 21 回。この例では 15 回で解けてしまいます。全探索が 1,235 回を要するのとは対照的です。今度は近傍の素数表から 1619 を選んでみましょう。値としては二つ小さいだけですが、1618 = 2 × 809 です。809 個もの候補を持つ断片のせいで、最悪試行回数は 811 回に跳ね上がり、同じ a に対しても 427 回かかります。イヴの計算量を決めるのは p ではなく、p − 1 の最大素因数なのです。このツールが扱う 301 個の素数において、ポーリグ・ヘルマン法の最悪計算量がこの最大素因数を 25 以上上回ることはありません。172 個の素数で全探索の 10 分の 1 未満の手間で済み、素数を昇順に辿る 300 回のステップ中、146 回で計算量が減少します。1978年にポーリグとヘルマンが明言したように、p − 1 が小さな素因数ばかりであるとき、mod p の冪乗算は「優れた一方向性関数とは言えない」のです。

より安全な底は、生成元ではない 🖖

位数が素数の底 を押してみてください。263 において、底 2 は生成元ではありません。累乗が 131 回で一巡するため、共有秘密としてあり得る数は 131 通りだけです。生成元である g = 5 に変えると、候補の数は二倍になります。そのときのポーリグ・ヘルマン法の最悪試行回数を見てみましょう。133 回のうち 2 回は、a の最下位ビットの判定に費やされます。a が偶数なら A¹³¹ は 1 となり、奇数なら 262（すなわち −1）になるからです。奇素数では p − 1 が必ず偶数になるため、生成元を使うとこの 1 ビットがいつでも漏洩してしまいます。g = 2 に戻してみると、位数 131 は素数なのでポーリグ・ヘルマン法には分解の余地がなく、最悪試行回数は全探索と同じ 131 回です。生成元は秘密の候補数を二倍に増やした反面、イヴに秘密の 1 ビットを無償で手渡しました。彼女は公開値 A と B だけから、それが mod 263 の平方剰余かどうかを判別できてしまうのです。g = 2 の累乗はすべて平方数ですから、そこから読み取れる隙はありません。

全プロセスの詳細解説

p = 101 におけるアリスの秘密の復元 5 ステップ
アリスとボブが p = 101、g = 2 を使っており、イヴは A = 12 と B = 53 を傍受しました。ポーリグ・ヘルマン法を用いて 2ˣ ≡ 12 (mod 101) を満たす x を求め、その試行回数を数え、x から共有秘密を特定してください。さらに、同じ攻撃を p = 65,537 で行った場合にどれほどの試行回数が必要になるかを答えてください。

この問題をツールで開く
1. 100 = 2² · 5² ですから、x は x mod 4 と x mod 25 によって一意に定まります。2 の位数は 100 の約数ですが、2⁵⁰ = 100、2²⁰ = 95 はどちらも 1 ではないため、位数は 100 そのものです。つまり 2 は生成元です。
  
  $100 = 2^{2} \cdot 5^{2}, 2^{50} \equiv 100, 2^{20} \equiv 95 (both \neq = 1) \Rightarrow ord (2) = 100$
2. mod 4 において、γ = 2⁵⁰ = 100 ≡ −1 です。2 進法の 1 桁目：12⁵⁰ = 100 となるため、2 回目の試行で d = 1 と決まります。この影響を取り除きます：12 · 2⁻¹ = 12 · 51 = 612 ≡ 6。そして 6²⁵ = 100 なので、次の桁も同様に 2 回目の試行で 1 と求まります。したがって x ≡ 1 + 1 · 2 = 3 (mod 4) です。
  
  $1 2^{50} \equiv 100 \Rightarrow d_{0} = 1; 12 \cdot 2^{- 1} = 12 \cdot 51 \equiv 6, 6^{25} \equiv 100 \Rightarrow d_{1} = 1; x \equiv 3 (mod 4)$
3. mod 25 において、γ = 2²⁰ = 95 であり、その累乗は 1, 95, 36, 87, 84 となります。5 進法の 1 桁目：12²⁰ = 95 より、2 回目の試行で d = 1 です。これを取り除きます：6⁴ = 1,296 ≡ 84 となるため、次の桁は 5 回目の試行で 4 と決まります。よって x ≡ 1 + 4 · 5 = 21 (mod 25) です。
  
  $9 5^{0..4} = 1, 95, 36, 87, 84; 1 2^{20} \equiv 95 \Rightarrow d_{0} = 1; 6^{4} = 1296 \equiv 84 \Rightarrow d_{1} = 4; x \equiv 21 (mod 25)$
4. 100 未満で mod 25 において 21 となる数は 21, 46, 71, 96 の四つで、このうち mod 4 で 3 となるのは 71 だけです。したがって試行回数は 2 + 2 + 2 + 5 = 11 回（最悪時は 2·2 + 2·5 = 14 回）で x = 71 と求まります。全探索なら 0 から 71 まで 72 回の試行が必要でした。共有秘密は 53⁷¹ mod 101 = 35 です。
  
  $x \in {21, 46, 71, 96}, x \equiv 3 (mod 4) \Rightarrow x = 71; 2 + 2 + 2 + 5 = 11 tries, at worst 2 \cdot 2 + 2 \cdot 5 = 14$
5. 65,537 = 2¹⁶ + 1 は素数であり、p − 1 = 2¹⁶ です。ポーリグ・ヘルマン法なら 16 桁の 2 進数を一桁ずつ、それぞれ二つの候補から求めていきます。最悪でも 32 回の試行で済み、全探索の 65,536 回とは対照的です。ポーリグとヘルマンは一般の場合を論じる前に、まさにこの p = 2ⁿ + 1 というケースを解いてみせました。
  
  $s = B^{x} = 5 3^{71} mod 101 = 35; 65537 = 2^{16} + 1 : at worst 16 \cdot 2 = 32 tries$
解答

試行回数 11 回（最悪でも 14 回）で x = 71 が得られ、共有秘密は 35 です。p = 65,537 の場合、攻撃に必要な試行回数は高々 32 回です。このページの上限は 1,999 なので、この数値は実際のシミュレーションではなく計算上の値です。

$x = 71, 11 tries, s = 35$

学習の道すじ

暗号はいかにして破られるか

参考文献 (2)

The exchange itself, the definition's sentence that its authors could see no way round a logarithm and had no proof, and the 200-bit example in `assumes`: Whitfield Diffie and Martin E. Hellman, "New Directions in Cryptography," IEEE Transactions on Information Theory 22(6), 644–654, November 1976. §III, p. 649.
The second insight's quotation, the digit-by-digit search the page runs, and the worked problem's p = 2ⁿ + 1: Stephen C. Pohlig and Martin E. Hellman, "An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance," IEEE Transactions on Information Theory 24(1), 106–110, January 1978. §III–IV, pp. 107–110.

42Math チーム · 公表された資料と照合しています。訂正のご指摘を歓迎します。