素数 p
共有秘密
イブの推測回数
全指数を試すのにかかる時間
アリス
公開(イブにも見える)
ボブ

表示

ディフィー・ヘルマン鍵共有についてもっと見る

ディフィー・ヘルマン鍵共有

一度も会ったことのない2人が、誰かにすべての言葉を聞かれている中で、どうすれば秘密鍵を取り決められるでしょうか。1976年、ホイットフィールド・ディフィーとマーティン・ヘルマンがその答えを見つけ、それは今ではインターネット上のほぼすべての安全な通信を守っています。アリスとボブと一緒に5つのステップを、一度は絵の具の混合として、もう一度は実際の数値でたどり、それから盗聴者イブに攻撃させてみましょう。小さな数なら彼女は一瞬で勝ちますが、実際に使われる大きさでは宇宙の年齢よりも長い時間が必要になります。 「次のステップ」を押すと、アリスとボブが秘密を取り決める様子をたどれます。イブは2人が送るものをすべて読んでいます。「戻る」で1ステップ戻ります。各値は絵の具と数値の両方で表示されます。鍵のかかった値は持ち主の手元から決して出ません。右側でもっと大きな素数や別の秘密を選ぶか、「新しい秘密」を押してください。最後のステップで「イブに攻撃させる」を押すと、イブは当てはまる指数が見つかるまですべての指数を試します。小さな素数なら簡単ですが、実際に使われる素数では見込みがありません。

使い方

  1. 「次のステップ」を押して、公開の合意、秘密、メッセージ、共有された結果という交換の流れをたどります。
  2. 各値を絵の具と数値の両方で見て、どれが非公開のままで、どれをイブが読めるのかを確かめます。
  3. 最後のステップで「イブに攻撃させる」を押し、次にもっと大きな素数を選んで、彼女の勝ち目がどれほど早く消えるかを見ます。

交換の仕組み

アリスとボブはまず、素数 p と数 g を公開で取り決めます。次にそれぞれが秘密の数を選び、アリスは a、ボブは b を自分だけのものにします。アリスはボブに A = gᵃ mod p を送り、ボブはアリスに B = gᵇ mod p を送ります。最後にアリスは Bᵃ mod p を、ボブは Aᵇ mod p を計算します。どちらの結果も g の a·b 乗 mod p に等しいので、2人は回線を一度も通らなかった数を共有したことになります。p、g、A、B を見たイブには、そのような近道はありません。

イブが行き詰まる理由

gᵃ mod p の計算は、繰り返し二乗法のおかげで、数百桁の数でもすぐにできます。逆向きに、結果から指数 a を求めることは離散対数問題であり、うまく選ばれた素数に対しては速い方法が知られていません。このデモの小さな素数なら、イブはすべての指数を試すだけで済みます。アプリは彼女の推測回数を数え、全探索にどれだけかかるかを見積もります。素数が1ビット増えるごとに手間は2倍になるので、インターネットで使われる2048ビットの素数では総当たり探索にはとても手が届きません。絵の具版も同じ考え方を表しています。色を混ぜるのは簡単ですが、混合色を元の色に分け戻すのは事実上不可能です。

よくある質問

なぜ絵の具のたとえが成り立つのですか?

絵の具を混ぜるのは簡単で、元に戻せません。g をべき乗して mod p をとるのが、行うのは簡単で元に戻すのは難しいのと同じです。アリスとボブはそれぞれ共通の色に自分の秘密の色を加え、混合色を交換します。そしてそれぞれが受け取った混合色に自分の秘密の色を加えます。2人とも共通の色と両方の秘密の色を含む色にたどり着きますが、イブには2色の混合色が2つ見えるだけで、それらを分離することはできません。ここでは絵の具を等量ずつ混ぜるので、順序は関係ありません。(gᵃ)ᵇ = (gᵇ)ᵃ と同じです。

g とは何で、なぜ原始根でなければならないのですか?

g は生成元です。そのべき乗 g¹, g², …, g^(p−1) mod p は1から p − 1 までのすべての数を巡ります。そのため公開される値があらゆる可能性に散らばり、イブがそこから得る情報はできるだけ少なくなります。アプリは各素数に対して、そのような数のうち最小のものを選びます。たとえば p = 23 なら g = 5 です。

ディフィー・ヘルマンはメッセージを暗号化しますか?

いいえ。共有秘密を取り決めるだけです。その秘密は AES のような高速な共通鍵暗号の鍵として使われ、実際のデータはその暗号で暗号化されます。HTTPS の通信はすべてこの仕組みで動いています。鍵交換(通常は楕円曲線を使用)のあとに共通鍵暗号による暗号化が続きます。

イブはボブになりすませますか?

それ単体では、できます。中間者がアリスと1回、ボブと別に1回交換を行い、すべてを中継することができます。実際のプロトコルでは、サーバーがデジタル署名と証明書で身元を証明することでこれを防ぎ、交換が認証されるようにしています。

サーバーに何か送信されますか?

いいえ。すべての数値、絵の具の混合、イブの攻撃はお使いのブラウザ内で計算され、設定はこのブラウザのローカルストレージに保存されます。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

エディターへ