Hatena::ブログ(Diary)

小人さんの妄想 このページをアンテナに追加 RSSフィード Twitter

2012-05-14

ディフィー・ヘルマン鍵共有の仕組み

2人の間で秘密の暗号通信を行うには、まず最初に2人だけが知っている共通のキーワード〜鍵を取り交わす必要がある。

しかし、2人が遠く離れていて、盗聴の危険性のあるインターネットでしか通信できないとしたら、

どうやって最初の鍵を取り交わすことができるか?

この難問を解決するアルゴリズムとして「ディフィー・ヘルマン鍵共有」が知られています。

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

あからさまに盗聴されている通信路だけを使って、2人だけの秘密を共有する・・・

そんな一見不可能に思える離れ業を、どのようにして実現するのでしょうか?


ディフィー・ヘルマン鍵共有(以下、DH法と略)の基本となる考え方は、以下の図から出発します。

いま、アリスとボブの2人が、2人だけの秘密の数字を共有したかったとしましょう。

f:id:rikunora:20120515020757p:image

まず、アリスが数字Aを、ボブが数字Bを決めて、お互いに交換します。

そして、お互いに交換し合った数字を掛け合わせて、共通の数字を保有するのです。

例えばアリスが3、ボブが4なら、共通の数字は3x4=12です。

ただ、このままでは何も暗号化されてはいません。

通信路上の数字が盗聴されてしまえば、秘密の数字もバレバレです。


何とかもう一工夫して、数字がバレないようにしたい。

そこで、「一方向性関数」という仕組みを導入します。

方向性関数とは、順方向の計算は簡単だけれど、逆方向の計算は難しい関数のことです。

方向性関数をうまく使えば、「暗号をかける人にとっては簡単だが、解く人にとっては難しい」状況が作れるわけです。

DH法で用いられている一方向性関数は、以下のものです。

f:id:rikunora:20120515020818p:image

式の上で「mod P」とあるのは、「P で割ったときの余り」という意味です。

ある整数Gをx乗して、それをPで割ったときの余りを求めるのはやさしい(計算手順が一本道)。

しかし、その逆に、余りがyだったとき、元のxを求めるには?

試しに数字を入れてやってみましょう。

f:id:rikunora:20120515020855p:image

 5^3 ÷ 7 = 125 ÷ 7 = 17 余り 6

これはやさしい。

では、逆に

 5^x ÷ 7 = ? 余り 3

だったとき、xは幾つになるか?

この答を得るには、xに1つ1つ順番に数字を代入して、確かめてみるしかありません。

つまりこの「G^x mod P」という計算は「行きはよいよい帰りは怖い」のです。


この「G^x mod P」という一方向性関数を使って、当初、アリスとボブが交換したかった2つの数、AとBを隠すことを考えます。

 ・Aを直接送る代わりに「G^A mod P」を、

 ・Bを直接送る代わりに「G^B mod P」を、

互いに交換すれば、たとえ途中の数字が盗聴されたとしても、そこから盗聴者がもとの数AとBを求めることは極めて難しい。

f:id:rikunora:20120515021000p:image

一方、お互いに数字を交換し合った、アリスとボブはどうするか。

例えばアリスは、もらってきた数字 (G^B mod P) を、自分の持っている数字Aでべき乗した後、Pで割った余りを求めます。

 (G^B mod P)^A mod P = (G ^ (BxA)) mod P

ボブも同じ計算を施します。

 (G^A mod P)^B mod P = (G ^ (AxB)) mod P

結果として、2人の手元には同じ数字が残るのです。

なぜ同じになるのか。

それは、2人の手元で行っている計算が、本質的には「Gの肩の上で行っている掛け算」だからです。

 (G ^ A) ^ B = (G ^ (AxB))

Gの指数が、AxBという掛け算になっていることに注目。

つまり、DH法とは、

「単純に数字を交換して掛け算する手順を、G^x mod P という一方向性関数によって隠したもの」

だったのです。


しかし、GとPは、どのようにして2人の間で交換すればよいのでしょうか?

もしGとPを秘密に送らなければならないとしたら、何の解決にもなっていないではありませんか。

実は、たとえGとPを盗聴者に盗まれたとしても、数字の秘密はちゃんと守られているのです。

方向性関数による困難な計算、例えば

 5^x ÷ 7 = ? 余り 3

で、5と、7と、3が知られたとしても、xを知ることは難しいでしょう。

なので、GとPは秘密にすることなく、堂々と交換しても大丈夫なのです。


こうして種明かしをすれば、DH法は、一見ささいなアイデアであるようにも思えます。

ところが、このDH法が世に出るまでは、鍵交換問題は解決不可能と信じられていた時代さえあったのです。

ネット上を検索すると、DH法のアルゴリズムを解説したページはたくさんヒットします。

しかし「なぜDH法で鍵交換ができるのか」という疑問に答えてくれるページは(私が探したところ)見当たりませんでした。

仕方なく自分の頭で考えて、上の説明にたどり着くまで、私は1週間くらいかかりました。

最初にDH法を編み出したヘルマンは、こう言ったそうです。

オリジナルな研究をやるということは、愚か者になることなのです。

諦めずにやり続けるのは愚か者だけですからね。

第一のアイディアが湧いて大喜びするが、そのアイディアはコケる。

第二のアイディアが湧いて大喜びするが、そのアイディアもコケる。

九十九番目のアイディアが湧いて大喜びするが、そのアイディアもコケる。

百番目のアイディアが湧いて大喜びするのは愚か者だけです。

しかし、実りを得るためには、百のアイディアが必要かもしれないでしょう?

コケてもコケても大喜びできるぐらい馬鹿でなければ、動機だってもてやしないし、やり遂げるエネルギーも湧きません。

神は愚か者に報いたまうのです。

    -- 暗号解読より

暗号解読―ロゼッタストーンから量子暗号まで

暗号解読―ロゼッタストーンから量子暗号まで

skyshipskyship 2012/05/17 04:10 こんばんは。DH鍵共有について初めて読み、面白く感じています。

実は以前に無理数範囲の既約剰余類を考察したことがありまして、
例えば、(1+√3)^x≡4+3√3 (mod 7) となるxを求めるのは(x=23)、
5^x≡3 (mod 7) となるxを求めるよりさらに大変となります。

無理数範囲の既約剰余類の話はなかなかネットでも見なくて、
ぜひ多くの人に知ってもらえたらいいなあと思っています。
そこから新しいアイデアが生まれたらもっといいなあと思います。


最後の引用を読んで、離散対数とか素因数分解の画期的なアルゴリズムが
もしかしたら今後編み出されるかもしれないと思えてきました。

rikunorarikunora 2012/05/18 10:10 なるほど、数の範囲を無理数に広げると、一段と難しさが増すわけですね。
ひょっとするとこれで、より強度の高い暗号を作ることができて、大喜びするアイディアなのかも!
デジタルなコンピュータだと√3といった無理数を直接(無限小数で)表現することはできないので、
無理数を有限個の数字で表す何らかの方法が必要になると思います。

離散対数を求める画期的なアルゴリズムが「ない」、ということが証明されたわけではありません。
ネットを検索すると、676-bitの世界記録というのがありました。
>> http://www.nict.go.jp/publication/shuppan/kihou-journal/kihou-vol57no3_4/kihou-vol57no3-4_0406.pdf

ぷかぷか 2012/05/30 02:15 今大学受験生です。だいたい週一更新ということで、少年ジャンプと同じように楽しんでます。笑 まあむずかしくて理解できない記事も多いのですが。。。
今回の記事がおもしろかった!ただそれだけです。他の人みたく数学的な感想を述べることはできないということです。応援してます。

rikunorarikunora 2012/05/31 13:12 応援ありがとうございます!
こちらからも、受験がんばってください!
このブログにあるくらいの内容は、きっとそのうち分かるようになります。
ちなみに、少年ジャンプは熱いです。私もいまだに読んでます。

hirotahirota 2012/06/01 11:35 4+3√3 みたいな数を計算機で扱った事はあります。
X+Y√3 としてX,Yだけを計算する方法ですから、√3 部分は有限個しか扱えませんが。
でも、数式処理で一般的な代数的数を厳密に扱うアルゴリズムがあると聞いた事もあります。

rikunorarikunora 2012/06/19 16:06 > 一般的な代数的数を厳密に扱うアルゴリズム
これは何とも気になりますね。Mathematicaみたいな数式処理ソフトが用いているのでしょうか。
実際の暗号には、なるべく計算量を抑えるようにシンプルな方法が望まれますが、
もし代数的数を自由に使って良いというのであれば、暗号の方法はもっと広がるものと思います。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

リンク元