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

何千年もの間、秘密のメッセージを送るには、まず秘密の鍵を直接会って、または使者を通じて共有する必要がありました。1976年、スタンフォード大学の2人の研究者が、誰の目にも見える形でメッセージを交換することで、2者が何もないところから共有鍵を作り出せることを示しました。このアイデアは公開鍵暗号の時代を切り開き、ブラウザに南京錠のマークが表示されるたびに今も働いています。

公開チャネルの両側にいるアリスとボブが、それぞれ共通の黄色の絵の具に秘密の色を混ぜ、イブが見守る中で2人とも同じ混合色にたどり着く様子
公開チャネルの両側にいるアリスとボブが、それぞれ共通の黄色の絵の具に秘密の色を混ぜ、イブが見守る中で2人とも同じ混合色にたどり着く様子

鍵配送問題

AES のような暗号の安全性は鍵次第であり、双方が同じ鍵を持っている必要があります。1976年以前は、鍵を秘密裏に届けなければなりませんでした。外交行嚢、信頼できる使者、あるいは事前に印刷された暗号書によってです。今すぐ安全に通信したい見知らぬ2人、たとえばインターネット上の店と客にとって、それは不可能です。ホイットフィールド・ディフィーとマーティン・ヘルマンの論文『暗号の新しい方向』(New Directions in Cryptography)は、事前の秘密をまったく必要としない方法でこの問題を解決しました。

時計の上の算術

この交換では剰余演算を使います。p 時間の時計の上で計算するもので、p は大きな素数です。この時計の上では、べき乗が驚くべき振る舞いをします。g が原始根なら、g, g², g³, … mod p という数はあちこちに飛び回り、繰り返す前に1から p − 1 までのすべての時刻を、でたらめに見える順序で訪れます。gᵃ mod p の計算は速く、a の2進数の桁数と同じくらいの回数の掛け算で済みます。それを元に戻すのはそうはいきません。

ステップごとの交換

アリスとボブは p と g を公開で取り決めます。アリスは秘密 a を選んで A = gᵃ mod p を送り、ボブは秘密 b を選んで B = gᵇ mod p を送ります。アリスは Bᵃ = (gᵇ)ᵃ を、ボブは Aᵇ = (gᵃ)ᵇ を、どちらも mod p で計算します。指数の順序は関係ないので、2人とも g^(ab) mod p を得ます。古典的な小さな例 p = 23、g = 5、a = 6、b = 15 では、アリスは8を、ボブは19を送り、2人とも共有秘密2にたどり着きます。

離散対数問題

イブには p、g、A、B が見えています。もし A = gᵃ mod p から a を求められれば、アリスと同じように秘密を計算できます。これが離散対数問題です。数体ふるい法など、知られている最良の古典的アルゴリズムは、すべての指数を試すよりはるかに速いものの、それでも桁数のどんなべき乗よりも速く増える時間を必要とします。2048ビットの素数では、この問題は現存するどのコンピューターにも手が届きません。もっと速い方法が可能かどうかはわかっておらず、この交換の安全性はその見込みに基づいています。

中間者

ディフィー・ヘルマンは盗聴者からは守ってくれますが、なりすましからは守ってくれません。アリスとボブの間に入り込んだマロリーは、それぞれと1回ずつ交換を行ってメッセージを受け渡し、すべてを読むことができます。対策は認証です。HTTPS では、サーバーが信頼できる認証局によって証明された鍵で交換の自分の部分に署名するので、ブラウザは本当に正しいサイトと通信していることがわかります。鍵交換と署名は常にセットです。

誰が発明したのか?

ディフィーとヘルマンは1976年に発表しましたが、それはラルフ・マークルのアイデアに基づくもので、ヘルマンはのちにマークルの功績も認めるよう求めました。1997年、英国の情報機関 GCHQ は、自らの数学者たちが先にたどり着いていたことを明らかにしました。ジェームズ・エリスは1970年に公開鍵暗号のアイデアを持ち、クリフォード・コックスは1973年に RSA に似た方式を見つけ、マルコム・ウィリアムソンは1974年に同じ鍵交換を発見していましたが、いずれも20年以上秘密にされていました。

マーティン・ヘルマン(左)とホイットフィールド・ディフィー(右)、1977年
マーティン・ヘルマン(左)とホイットフィールド・ディフィー(右)、1977年
2007年のシンギュラリティ・サミットでのラルフ・マークル。SHA-256 が用いる連鎖型の構成は、彼とイヴァン・ダムゴーにちなんで名づけられた。
2007年のシンギュラリティ・サミットでのラルフ・マークル。SHA-256 が用いる連鎖型の構成は、彼とイヴァン・ダムゴーにちなんで名づけられた。

現在のディフィー・ヘルマン

現代の通信では主に楕円曲線ディフィー・ヘルマンが使われています。これははるかに短い数で同じ安全性を実現するもので、たとえば TLS 1.3、Signal、WhatsApp で使われる曲線 X25519 があります。接続ごとに新しい秘密のペアを使うと前方秘匿性が得られます。たとえ後でサーバーの長期鍵が盗まれても、過去の会話は安全なままです。弱いパラメーターは依然として危険で、2015年の Logjam 攻撃が古い512ビットの素数でそれを示しました。また、ショアのアルゴリズムを実行する大規模な量子コンピューターは、古典的なディフィー・ヘルマンも楕円曲線ディフィー・ヘルマンも破ってしまうため、現在ではポスト量子鍵交換がそれらと併用される形で導入されつつあります。

試してみましょう

ディフィー・ヘルマン・ビジュアライザーを開き、アリス、公開チャネル、ボブが知っていることを示すボード上で、5つのステップを絵の具と数値でたどってみましょう。23から2,147,483,647までの素数を選び、秘密を自分で設定し、イブにすべての指数を試させて攻撃させてみてください。小さな素数では彼女が瞬時に成功する様子と、素数が長くなるにつれて推定探索時間がどう増えるかがわかります。

よくある質問

ディフィー・ヘルマンは RSA と同じですか?

いいえ。どちらも1970年代の公開鍵方式ですが、別物です。1977年に発表された RSA は公開鍵と秘密鍵で暗号化と署名ができ、大きな数の素因数分解の難しさに基づいています。ディフィー・ヘルマンは共有秘密を取り決めるだけで、離散対数問題に基づいています。

実際にはどのくらい大きな数が使われますか?

古典的なディフィー・ヘルマンでは少なくとも2048ビット、10進数で約617桁の素数が使われ、3072ビットや4096ビットもよく使われます。楕円曲線版では、256ビット程度の鍵で同等の安全性が得られます。

なぜ1ビット増えるごとにイブの手間が2倍になるのですか?

1ビット多い素数はおよそ2倍の大きさなので、試すべき指数もおよそ2倍になります。実際の攻撃はすべての指数を試すよりも巧妙ですが、そのコストはやはり素数の大きさとともに非常に速く増えます。

なぜアリスとボブには素数が必要なのですか?

法が素数なら、1から p − 1 までのすべての数に逆元があり、原始根が存在するので、g のべき乗がすべての可能性を網羅します。p − 1 の小さな因数を利用する近道を排除するため、(p − 1)/2 も素数であるような安全素数がよく選ばれます。

試してみますか?

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

ディフィー・ヘルマン・ビジュアライザーを開く