ディフィーヘルマン共通鍵の仕組みに感動したことを伝えてみる

(サーバサイドよりの)WebエンジニアやっているとOpenSSHなるものが存在していて、そこの鍵交換の仕組みにDH(ディフィーヘルマン)鍵交換アルゴリズムなるものがあることをなんとなく知っていたりすると思います。

それが何なのか知らないでもぶっちゃけなんとなく回ってしまう世の中ですが、何かの機会にこの仕組を知って感動をした記憶があるので、その感動をShareしたく、記事にしました。この感動が伝えられるようにがんばります。

ずっと思っていた疑問

エンジニアやっていると

「この通信は鍵を最初に共有して、その後はその鍵で暗号化するから安全ですよ」

みたいな文言を耳にしたことがある、かと思います。

一見、問題なさそうに聞こえるんですが、よくよく考えると以下のことが疑問でした。

「最初の鍵共有する通信のときに鍵盗まれたらだめなんじゃない？」と。

最初の鍵を共有するところを暗号化するための鍵を事前に共有しておかないとだめなんじゃないだろうか、と思ったりして、でもそれすると鍵のための鍵のための鍵が...と無限ループする気がしていました。

それを解決するのがディフィー・ヘルマンさんです。

で、どういう仕組なのか？

具体的な例で見ていきましょう。登場人物はAliceとBobです(なんかこういう例の説明のときは、こういう感じの名前を使うとかどこかできいたことがあります)。若干数学、が出てきます。

前提

以下の数字pとgが世界に公開されているとします。

素数：p (できるだけ大きい数字で)
任意の数字：g

それとは別にAliceとBobはそれぞれ心のなかに

Aliceはaという秘密の数字
Bobはbという秘密の数字

と決めておきます。この2つは互いにも、世界にも教えず、自分のみに留めておきます。

公開されているのに秘密に鍵を共有する仕組み

最初に合同式、の概念を簡単に説明します。というか簡単です。

合同式とは

x ≡ y (mod z)

のような書き方をしたときに、【xとyはzで割ったときのあまりが共に等しい】ことを表します。
具体例をあげると

6 ≡ 10 (mod 4)

となります。

では実際の流れを見てみましょう。

1. Aliceが g ** a ≡ A (mod p)を計算し、Aをbobに伝える。(Aは盗み見されても良い)
2. Bobも同じくg ** b ≡ B (mod p)を計算し、BをAliceに伝える。(Bは盗み見されても良い)
3. Aliceは a ** B ≡ K(mod p) を計算する。
4. Bobも同様に b ** A ≡ K(mod p)が計算できる(<- !?)。

はい、これで二人は通信を盗み見されまくっているのですが3, 4で二人は他の人に知られることなく共通の秘密の数字(共通鍵)Kを手に入れることができました。

まず3.と4の部分なのですが二人が同じ値を計算できるのはわかるかと思います。

B ** a ≡ (g ** b) ** a ≡ g ** a ** b ≡ A ** b

じゃあ次にこのKという値が外部の覗き見してる人にも簡単に計算できるんじゃないか？と思われるかもしれないのですが、それができない(わかるのにかかる時間がとても掛かる)ことがわかっています。

gもpもAもBもバレているのに、aとbがわかってないことでKがばれないのです。pが十分に大きいと、AやBからいい感じのaとbの組み合わせを現実的な時間で求めるのは時間が足らないのです(離散対数問題と言うそうです)。
(最近はこれより更に計算しづらいディフィーヘルマンの楕円曲線による鍵方式が使われることもありますが、考え方のベースは同じです。)

これを最初知ったとき将棋の詰みそうでなかなか詰まなさそうな盤面みたいなしぶとさに、感動を覚えました。

最後に

ディフィー・ヘルマンの鍵共有について解説している記事は正直たくさんありますが、この仕組の感動を伝えている記事はあまり見かけなかったと思うので書いてみました。

正直こういう仕組みを知らずに使っているものがエンジニアでもたくさんあると思いますが、何かをきっかけに仕組みを知っておくことで応用がきくことは結構あったりすると思います。

例えば今回のような仕組みを知っておけば、暗号化も計算頑張りまくられたら突破されるんだな、というのが実感を持って結構わかると思います。こういう自分なりの感覚を持っておくことは大事だなと思っていますので、これからも気になったことを調べたりして感動したら共有していきたいなと思います。

以上です。