しょうがくせい向けDiffie-Hellman(ディフィー・ヘルマン/DH)共通鍵交換方式のしくみ
DH共通鍵交換の仕組みを小学生にでもわかりやすいように、なるべく簡単な用語で解説しています。
秘密の数・秘密じゃない数とダイヤル
登場人物と環境
- ポチさん:A国のスパイです。日本の重要機密書類Aをタマさんに渡し、タマさんから重要機密書類Bを受け取る必要があります。情報通信は監視されており一切使えません。
- タマさん:ポチさんの仲間。重要機密書類Aをポチさんから受け取り、ポチさんに重要機密書類Bを渡すのが任務です。
- 配達屋さん:B国政府系配達屋さん。ポチさんタマさんの重要機密書類をいずれか盗み見るのが任務です。
- ロッカー:0から36までの番号がついたロッカー。37個の内、1人につき1つしか開けることが出来ません。
ダイヤル
ダイヤルがあります。特別なもので0−36までのメモリがついています。ボタンがあり好きな数だけ押すことが出来ます。すると針は一旦0にもどり「先ほどさしていた数」を「今押した数」だけ「かけ合わせた数ぶん」針が回ります。例えば3をさしているときにボタンを2回おすと3x3で0から9メモリ針が進みます。2をさしているときに3回おしたら2x2x2で0から8メモリ針が進みます。
問題点
ポチさんは重要機密書類を格納するロッカーの番号(0-36のどれか)を知っています。ポチさんはダイヤルを重要機密書類を格納したロッカーの番号、例えば3にセットし配達屋さん経由でタマさんに渡します。タマさんは3番ロッカーに重要機密情報がある事を知りますが、悪意のある配達屋さんはロッカー番号を盗み見ることで、その数3のロッカーを開き、タマさんより先に重要機密書類を盗み見る事が出来ます。
DH鍵交換方式によるうけわたし
そこでタマさんポチさんは工夫します。ダイヤルの横には「公開番号は5」と書いてあります。そしてあらかじめタマさんとポチさんは自分で好きな秘密番号、例えばタマさんは3、ポチさんは2と決めておきます。これらの3と2は配達屋さんは知りません。
ポチさんは公開番号（この場合だと5）の通り、ダイヤルを5にまわしボタンを自分の秘密番号の数、2回押します。針は一旦0に戻り5を2回かけたメモリ分、つまり5x5で25メモリ自動的に進みます。針は25を示しています。これを配達屋さん経由でタマさんに渡します。
タマさんはメモリの25を確認した後、ダイヤルを公開番号の5に戻し、今度は自分の秘密番号の数、3回押します。針は一旦0に戻り5を3回かけたメモリ分、つまり5x5x5で125メモリ自動的に進みます。メモリはグルグル回って14を示します。これを配達屋さん経由でポチさんに渡します。
ポチさんは14を指し示したダイヤルを受け取り、今度はそのまま自分の秘密の数、2回、ボタンを押します。針は一旦0に戻り14x14=196メモリぐるぐる回ります。針はぐるぐるまわって11で止まります。ポチさんはこの番号のロッカー、11番に重要機密書類Aを入れて針をリセットしたダイヤルを配達屋さん経由でタマさんに渡します。
タマさんも同様にダイヤルを最初に受け取った数、25に戻してからボタンを自分の秘密の数、3回押します。針は一旦0に戻り、25x25x25＝15625メモリ進みます。針はぐるぐるまわって11で止まります。タマさんがこの番号のロッカーを開けると、、重要機密書類Aがありました。タマさんは書類を取り出し自分の重要機密書類Bを格納します。以後はポチさんとタマさんはこのロッカー11でやり取りできます。
悪意のある配達屋さんが見た数値は公開番号の5とダイヤルの25と14の数値だけ。やり取りしているロッカー番号11を知るすべはありません。
疑問点
疑問がいくつかわきます。
- 公開番号が5じゃなくて他の数の場合でもちゃんとポチさんタマさん同じロッカー番号になるのか？
- ポチさんとタマさんが決めた番号、2と3は他の数字でもいいのか？
- ダイヤルは37メモリじゃないといけないのか？
- 配達屋さんは途中の25と14のダイヤルと公開番号の5からロッカー番号11がわかるのでは？
一つ一つ答えていきます。
公開番号が5じゃなくて他の数の場合でもちゃんと太郎さんはダイヤルを戻せるのか？ポチさんとタマさんが決めた番号、2と3は他の数字でもいいのか？
例えば次のミッションの公開番号が4だったとします。ポチさんが決めた数値は5、タマさんが決めた数値は6だったとします。
ポチさんが公開番号4にして5回ボタンを押すと4x4x4x4x4で1024メモリ、0からぐるぐる回って指し示すのは25。 タマさんが公開番号4にして6回ボタンを押すと4x4x4x4x4x4で4096メモリ、0からぐるぐる回って指し示すのは26。
それぞれその状態でダイヤルをそのまま配達屋さん経由で交換して
ポチさんが26のダイヤルに5回ボタンを押すと26x26x26x26x26で11881376メモリ、0からぐるぐる回って指し示すのは10。 タマさんが25のダイヤルに6回ボタンを押すと25x25x25x25x25x25で244140625メモリ、0からぐるぐるぐるぐる回って指し示すのは、、、10。
どうやら違う公開数値とお互い決めた数でも無事同じロッカーを使えるようです。
ダイヤルは37メモリじゃないといけないのか？
これは「ある程度」決まっています。きまりは、1以外のかけ算で表せない数値であること。例えば37は○x□x△・・・では表せませんよね。2つ下がって35は7x5で表せますからこれはダメです。このように1以外のかけ算で表せない数値を「素数（そすう）」といいます。
ダイヤルの数はこの素数である必要があります。どうしてかは後で説明しますね。
配達屋さんは途中の25と14のダイヤルと公開番号の5からロッカー番号11がわかるのでは？
これは、実はかんたんにできます（！）。配達屋さんは5を何度もかけ合わせてダイヤル数37で割ったあまりを試します。5は2回かけると余り25に、また3回かけると余りは14になり、秘密の数が2と3であることがわかってしまいます。あとは5を2回かけてさらにそれを3回かけ合わせると(5x5)x(5x5)x(5x5)=15625。それを37で割った余りは、、11。なんとロッカー番号がばれてしまいました！
どうしてこんなに簡単に解けるDH法が世界的に標準で使われているSSL/TLSにも採用されているのでしょうか。
そのポイントは配達屋さんが公開数値5をかけ合わせてやり取りした数値25と14を探していたところにあります。例えばダイヤルが11003、公開数値が53、決めた数が524と237だったらどうでしょうか。配達屋さんが見える数値は7423と5888です。配達屋さんは公開数値53を掛けあわせながら11003で割ったあまりがそれぞれになる数を探さなければいけません。これは骨が折れる作業です。配達屋さんは苦労の末、524と237という数値を算出しました。これでロッカー番号9490番を推測できますが、ずいぶん時間がかかりました。
もっと大きい数値だったらどうでしょう？ダイヤル数が8002793 で公開数値が2221、決めた数値が931420と748343だったら。6997694だという事を配達屋さんが知るには膨大な計算量が必要な事が容易にわかります。Core2Duoのコンピューターでは大体2時間程度。
それではもっともっと大きい数値だったらどうでしょう。コンピューターを利用しても計算に何年何十年もかかる数値だったら。これがDH鍵交換が世界で利用されている土台です。
DH鍵交換の原理
さらに疑問が残る人もいるでしょう。
- そもそもなぜダイヤルを使うのか
- なぜ、公開数をお互いが決めた数、それぞれ掛けると順番によらず1つの数になるのか。
簡単に解説します。
ダイヤルの意味
例えばまっすぐのものさしはメモリ4cmの所から5cm延ばしたら9cmの所になります。当たり前ですね。ところが一周7のダイヤルの場合はメモリ4から5メモリ回したら、、9ではなくダイヤルは一周して2になります。これを9を7でわった剰余（じょうよ）といいます。
剰余のメリットは一方向性にあります。簡単に言うと、わり算をした余りを出すのはすぐに出来ますが、逆に余りから、どんなわり算をしたのかを推測するのは試してみるしかなく、時間がかかります。DH鍵交換はこの一方向性を利用しています。
なぜ、公開数をお互いが決めた数、それぞれ掛けると順番によらず1つの数になるのか。
簡単に考えるため、上の7のダイヤルで考えます。例えば公開数が3だとして、ダイヤルを3に合わせます。ボタンを2回押すと針は3x3＝9で一周+2のところで止まります。もとの3に戻して今度はボタンを3回押すと3x3x3=27で三周＋6。また3に戻して今度はボタンを四回押すと3x3x3x3で11周＋4。周回数を無視して続けると、+5、+1、そしてボタン7回の時、再び3になります。
今度は最初の3からボタンを2回押した値、2を起点にやってみます。ボタンを2回押すと2x2で4。また2に戻して今度は3回、2x2x2で一周+1。また2に戻して今度は4回。2x2x2x2でもとの2の位置に戻りました。
ここで気づく事があります。3の時ボタンを4回押すと4になり、2の時はボタンを2回で同じく4になりました。3の時はボタンを6回で1になり、2のときはボタンを3回で同じく1になりました。つまり、もとが3の時のボタンを押した値は2の時はそのちょうど半分のボタン数で同じ値になりそうです。そして3を2にするには2回ボタンを押しました。
このことから次の様な事が考えられます。
「ある数値の時ボタンをA回押した値は、同じ数値の時、ボタンをB回押して出た値に対して（AわるB）回押して出る値と等しい」
そして実際、そうなります。証明は省きますが、興味のある方は「合同式の累乗」で検索してみてください。
今、ポチさんが決めた数が上のB。タマさんの決めた数が上の（AわるB）だとします。（Aはタマさんが決めた値とポチさんの決めたBから自動的に決まります）
ある数値にポチさんがB回ボタンを押した値をタマさんが（AわるB）回押すわけですから、出る値は「ある数値をA回押した値」。 逆にタマさんがある数値を（AわるB）回押した値を「ある数値をA回押した値」にするには、、そう、「Aわる（AわるB)」、つまりポチさんのBです。
だからポチさんが先にボタンを押してもタマさんが先にボタンを押しても、最終的な値は1つの数になるのです。
そして、この法則はダイヤルが素数の場合だけ成り立ちます。素数じゃない数、例えば8がダイヤル数だとすると公開数2を3回ボタンを押すと0になってしまい、そこから何回ボタンを押しても0のままです。これでは使えません。ダイヤル数が素数であれば公開数が何であろうが絶対に0になることはありません。仮にそんな公開数があったとして、「公開数x公開数x公開数・・・・＝素数x○」なんてことはありえませんからね。1以外のかけ算では表せないのが素数の定義ですから、仮に公開数が○のかけ算で表せたとしても「（公開数わる○）x公開数x公開数x・・・＝素数」となり、素数の定義に反します。
実際のDiffie-Hellman鍵交換方式
ここまでは例え話でした。実際にはポチさんとタマさん配達屋さんには知られずに共有しあったロッカー番号11の部分が、DH鍵交換で交換する「共通鍵」に該当します。そして公開数3とダイヤルの37は公開されている数p、q。ポチさんとタマさんが各自決めた数が秘密値a、bとなります。
お互いの通信元は公開値p、qとそれぞれの秘密値aまたはbを使って通信を傍受されても共通鍵を解読されない様に交換することができます。
Logjam攻撃
ちなみにコンピューターの演算能力は日々高まっていきます。過去には安全と思われていた強度でも技術の発達により安全では無くなることもあります。
2015年にTLSの脆弱性として話題になったLogjam攻撃は1990年代の米国の輸出規制に対応した比較的弱めのDHをサポートするソフトウェアに対して中間者攻撃でそれにダウングレードさせ暗号を解読するというものです。多くの実装が素数を固定で使っていることも要因の一つですが、90年代の輸出レベルのDHが数時間で解読出来る様になったというのが大きな原因です。過去、脆弱性ではなかったものが脆弱性になってしまうというのが今日の暗号化技術の普遍的な課題なのかもしれません。
TLSの中間者攻撃についてはこちらの記事も参照ください。
おわりに
DH鍵交換は1976年にスタンフォード大学の2名の研究員ホイットフィールド・ディフィーとマーティン・ヘルマンが開発した方式で現在は特許が切れて誰でも自由に使えます。
上述の様な偽装中継に弱かったりRSAの様に認証や署名には向きませんが、共通鍵を交換するだけであれば実装がシンプルですむのが特徴です。
簡単に説明する為、一部証明をとばした箇所もありますが公開鍵暗号の原点ともいえるDiffie-Hellman方式の雰囲気を感じて頂ければと思います。
