ディフィー・ヘルマン鍵かぎ共有きょうゆう

Diffie–Hellman鍵かぎ交換こうかんのスキームでは、各かくパーティが公開こうかい鍵かぎと秘密ひみつ鍵かぎのペアを生成せいせいし、ペアのうち公開こうかい鍵かぎを配布はいふする。互たがいの公開こうかい鍵かぎの本物ほんものの（この点てんが非常ひじょうに重要じゅうようである）コピーを取得しゅとくすれば、AliceとBobはオフラインで共有きょうゆう鍵かぎを計算けいさんできる。共有きょうゆう鍵かぎは、たとえば、基本きほん的てきにすべての場合ばあいにはるかに高速こうそくな対称たいしょう暗号あんごうの鍵かぎとして利用りようできる。

ディフィー・ヘルマン鍵かぎ共有きょうゆう（ディフィー・ヘルマンかぎきょうゆう、Diffie–Hellman key exchange、DH）、あるいはディフィー・ヘルマン鍵かぎ交換こうかん（かぎこうかん）とは、事前じぜんの秘密ひみつの共有きょうゆう無なしに、盗聴とうちょうの可能かのう性せいのある通信つうしん路ろを使つかって、暗号あんごう鍵かぎの共有きょうゆうを可能かのうにする、公開こうかい鍵かぎ暗号あんごう方式ほうしきの暗号あんごうプロトコルである。この鍵かぎは、共通きょうつう鍵かぎ暗号あんごうの鍵かぎとして使用しよう可能かのうである。

概要がいよう

1976年ねんにスタンフォード大学だいがくの2名めいの研究けんきゅう員いんホイットフィールド・ディフィーとマーティン・ヘルマンは、公開こうかい鍵かぎ暗号あんごうの概念がいねんを提案ていあんし、その具体ぐたい的てきな方式ほうしきの一ひとつとして、ディフィー・ヘルマン鍵かぎ共有きょうゆう（DH鍵かぎ共有きょうゆう）プロトコルを提案ていあんした。この鍵かぎ共有きょうゆう方式ほうしきは共通きょうつう鍵かぎ暗号あんごう方式ほうしきにおける鍵かぎの受うけ渡わたしを安全あんぜんに行おこなうために提案ていあんされた方式ほうしきである。

このプロトコルは、通信つうしんを行おこないたい2者しゃが各々おのおの公開こうかい鍵かぎと秘密ひみつ鍵かぎ（私有しゆう鍵かぎともいう）を用意よういし、公開こうかい鍵かぎのみを相手あいてに送信そうしんし、各自かくじ、自分じぶんの秘密ひみつ鍵かぎと受信じゅしんした公開こうかい鍵かぎから共通きょうつう鍵かぎを作成さくせいできる方法ほうほうである。たとえ送受信そうじゅしんされるデータ（すなわち、二人ふたりの公開こうかい鍵かぎ）を第三者だいさんしゃがすべて盗聴とうちょうしていてもそれからでは（計算けいさん量的りょうてきに）私有しゆう鍵かぎも共通きょうつう鍵かぎも生成せいせいすることができない所ところに特徴とくちょうがある。

アメリカ合衆国あめりかがっしゅうこくとカナダで特許とっきょが取得しゅとくされた。両国りょうこくでのアルゴリズムの特許とっきょ期限きげんは既すでに1997年ねん4月がつ29日にちに切きれたので、現在げんざいでは誰だれでも自由じゆうに利用りようができる。

プロトコルの内容ないよう

この方式ほうしきは以下いかのように行おこなわれる。まず大おおきな素数そすう $p$ と、 $p-1$ を割わり切きる大おおきな素数そすう $q$ を用意よういする。また、 $g$ を $({\mathbb {Z} }/p{\mathbb {Z} })^{\ast }$ の元もとであり、位い数すうが $q$ である値ねとする。この $p,q,g$ の値ねは公開こうかいされているものとする。

いまアリスとボブが通信つうしんを行おこなうとする。このときアリスとボブはお互たがい自分じぶんだけの知しる秘密ひみつの値ね a, b を選択せんたくする、この値ねは 0 以上いじょう q−1 以下いかの中なかからランダムに選えらぶ。（ここで、ゼロや小ちいさな値ね（g^a < p となる a 等ひとし）を選択せんたくすると安全あんぜん性せいが損そこなわれるが、そのような確かく率りつは無視むしできるほど小ちいさい。）

アリスは以下いかの値ね A を計算けいさんしてそれをボブに送信そうしんする。

$A=g^{a}{\bmod {p}}$

ボブも同様どうように以下いかの値ね B を計算けいさんしてそれをアリスに送信そうしんする。

$B=g^{b}{\bmod {p}}$

アリスは自分じぶんだけの知しる秘密ひみつの値ね a とボブから送おくられてきて受信じゅしんした値ね B から以下いかの値ねを計算けいさんする。

$K_{A}=B^{a}{\bmod {p}}$

ボブも自分じぶんだけの知しる秘密ひみつの値ね b とアリスから送おくられてきて受信じゅしんした値ね A から以下いかの値ねを計算けいさんする。

$K_{B}=A^{b}{\bmod {p}}$

このときアリスとボブが計算けいさんした $K_{A}$と$K_{B}$は

$K_{A}=K_{B}=g^{ab}{\bmod {p}}$

となっていて一致いっちするので、以後いごこの値ねを共通きょうつう鍵かぎ暗号あんごう方式ほうしきの鍵かぎ$K$として使用しようする。

ここで第三者だいさんしゃイブがこの二人ふたりの通信つうしんを傍受ぼうじゅしていて A と B の値ねを入手にゅうしゅできたとしても、$A=g^{a}{\bmod {p}}$ と $B=g^{b}{\bmod {p}}$ から $K=g^{ab}{\bmod {p}}$ を多項式たこうしき時間じかんで計算けいさんできる方法ほうほうはいまのところ知しられていないので、第三者だいさんしゃイブが秘密ひみつの共通きょうつう鍵かぎ$K$を生成せいせいすることは困難こんなんである。このためアリスとボブが安全あんぜんに通信つうしんを行おこなうことが可能かのうになる。

しかしながらたとえば、イブがボブになりすましをしていて、そうとは知しらずに上記じょうきの手順てじゅんでアリスが（相手あいてがボブだと思おもってだまされて）相互そうごに通信つうしんをして共通きょうつう鍵かぎ$K$を作つくったとすると、それ以降いこうのアリスからボブを相手あいてとして想定そうていして送おくった$K$を共通きょうつう鍵かぎとして暗号あんごう化かされた通信つうしんの内容ないようすべては，イブによって容易よういに内容ないようが解読かいどくされてしまうことに注意ちゅういが必要ひつようである。

なお、ディフィーとヘルマンによる最初さいしょの論文ろんぶんにおいては、 $g$ として$({\mathbb {Z} }/p{\mathbb {Z} })^{\ast }$の生成せいせい元もとを用もちいることが提案ていあんされているが、この場合ばあい、アリスが送おくった $A$ のルジャンドル記号きごうを計算けいさんすることによって、アリスの秘密ひみつ情報じょうほう $a$ の最下位さいかいビットが漏洩ろうえいしてしまう。

中ちゅう間あいだ者しゃ攻撃こうげき

ディフィー・ヘルマン鍵かぎ共有きょうゆう自体じたいは認証にんしょう手段しゅだんを提供ていきょうするものではないため、単独たんどくでは中ちゅう間あいだ者しゃ攻撃こうげきに対たいして脆弱ぜいじゃくである。

ここではディフィー・ヘルマン鍵かぎ共有きょうゆうにおける中ちゅう間あいだ者しゃ攻撃こうげきの具体ぐたい的てきな手順てじゅんについて示しめす。

DNS偽装ぎそう・ARPスプーフィング・その他たの手段しゅだんにより攻撃こうげき者しゃイブがこの二人ふたりの通信つうしんを中継ちゅうけいして A と B の値ねを（本来ほんらいの宛先あてさきには送おくらずに）盗ぬすみ取とったとする。

このとき攻撃こうげき者しゃイブはそれらに対たいして秘密ひみつの値ね c と d を選択せんたくする。この値ねは a や b と同おなじ基準きじゅんで選択せんたくされる。

攻撃こうげき者しゃイブは c を用もちいて次つぎの値ねを計算けいさんして(アリスになりすまして)ボブに送信そうしんする。

$A_{E}=g^{c}{\bmod {p}}$

また d を用もちいて次つぎの値ねを計算けいさんして（ボブになりすまして）アリスに送信そうしんする。

$B_{E}=g^{d}{\bmod {p}}$

ボブは自身じしんの秘密ひみつの値ね b と（アリスからだと思おもって，実際じっさいには攻撃こうげき者しゃイブから）受信じゅしんした値ね$A_{E}$から以下いかの値ねを計算けいさんする。

$K_{BE}=A_{E}^{b}{\bmod {p}}$

アリスは自身じしんの秘密ひみつの値ね a と（ボブからだと思おもって，実際じっさいには攻撃こうげき者しゃイブから）受信じゅしんした値ね$B_{E}$から以下いかの値ねを計算けいさんする。

$K_{AE}=B_{E}^{a}{\bmod {p}}$

攻撃こうげき者しゃイブは自身じしんの秘密ひみつの値ね c と d と（中継ちゅうけいせずに抜ぬき取とった）アリスからの値ね A とボブからの値ね B の値ねから以下いかの値ねをそれぞれ計算けいさんする。

$K_{EAE}=A^{d}{\bmod {p}}$

$K_{EBE}=B^{c}{\bmod {p}}$

このときアリスと（ボブになりすました）攻撃こうげき者しゃイブの計算けいさんした$K_{AE}$と$K_{EAE}$の値ね，およびボブと（アリスになりすました）攻撃こうげき者しゃイブの計算けいさんした$K_{BE}$と$K_{EBE}$の値ねは

$K_{AE}=K_{EAE}=g^{ad}{\bmod {p}}$

$K_{BE}=K_{EBE}=g^{bc}{\bmod {p}}$

になってそれぞれが一致いっちする。

そうしてそれ以降いこうの通信つうしんにおいて攻撃こうげき者しゃイブは，これら2つの値ねをそれぞれアリスおよびボブに対たいする共通きょうつう鍵かぎ暗号あんごう方式ほうしきの鍵かぎとして使用しようしてアリスとボブの通信つうしんを中継ちゅうけいし続つづけて、盗聴とうちょうや改かいざんを行おこなうことができる。

公開こうかい鍵かぎの選択せんたく

公開こうかい鍵かぎは（何なにかしらの証明しょうめいを付つけた）静的せいてきなものであっても、一時いちじ的てきなもの（ephemeral、この場合ばあい特とくにDHEと略記りゃっきされる）であってもかまわない。一時いちじ的てきな鍵かぎを使用しようした場合ばあい、鍵かぎそのものには認証にんしょうがないため、別べつな方法ほうほうで認証にんしょうを行おこなうこととなる。もし認証にんしょうがなければ、上述じょうじゅつの通とおり中ちゅう間あいだ者しゃ攻撃こうげきに対たいして脆弱ぜいじゃくとなる。どちらか一方いっぽうの鍵かぎが静的せいてきなものであった場合ばあい、中間なかま者しゃ攻撃こうげきを受うけることはなくなるが、forward secrecyのような、その他たの高度こうどなセキュリティに与あずかることはできなくなる。静的せいてきな鍵かぎを持もつ側がわでは、自身じしんの秘密ひみつ鍵かぎ漏洩ろうえいを防ふせぐため、相手あいての公開こうかい鍵かぎを確認かくにんして、安全あんぜんな共通きょうつう鍵かぎ生成せいせい関数かんすうを利用りようする必要ひつようがある。

共有きょうゆうした秘密ひみつをそのまま鍵かぎとして使つかうこともできなくはないが、ディフィー・ヘルマン鍵かぎ共有きょうゆうで生成せいせいしたことによってできる弱よわいビットの影響えいきょうを除去じょきょするため、秘密ひみつをハッシュに通とおすことが推奨すいしょうされる。

問題もんだい点てん

処理しょり負荷ふか

ディフィー・ヘルマン鍵かぎ共有きょうゆうは負荷ふかのかかる処理しょりであり、SSL/TLSに適用てきようした場合ばあいでは、通常つうじょうのRSA暗号あんごうによる鍵かぎ交換こうかんの場合ばあいと比較ひかくして、サーバのスループットが6分ぶんの1程度ていどまで落おち込こむという実験じっけん結果けっかも存在そんざいする。

パラメータの設定せっていミス

これはディフィー・ヘルマン鍵かぎ共有きょうゆうのシステム自体じたいに存在そんざいする問題もんだいではないが、2013年ねんの調査ちょうさでは、SSL/TLSでディフィー・ヘルマン鍵かぎ共有きょうゆうを有効ゆうこうとしているサーバのうち、電子でんし署名しょめいのビット数すうよりDHのビット数すうのほうが小ちいさく、総そう当あたり攻撃こうげきに対たいして弱よわくなってしまっているサーバが、実じつに80%以上いじょうの割合わりあいで存在そんざいしていた。

弱じゃく鍵かぎの存在そんざいと Logjam 攻撃こうげき

原理げんり上じょうは解読かいどくがきわめて困難こんなんではあるが、実装じっそう上じょうの問題もんだいが存在そんざいする場合ばあいには解読かいどくが可能かのうとなる場合ばあいがある。

また原理げんり上じょう、使つかわれている素数そすうに対たいして十分じゅうぶんな量りょうの事前じぜん計算けいさんを行おこなえば、その素数そすうに対たいしては比較的ひかくてき短みじかい時間じかんで鍵かぎを解読かいどくすることができる (い換いかえれば、その素数そすうを弱じゃく鍵かぎにすることができる)。2015年ねん、このことを元もとにした論文ろんぶんが発表はっぴょうされた。

この論文ろんぶんにおいて、Alexaによるトップ100万まんHTTPSドメインの中なかで512ビット輸出ゆしゅつ版ばんDHEを許可きょかしている 8.4% のうち 82% が、1024ビット非ひ輸出ゆしゅつ版ばんDHEでもトップドメイン全体ぜんたいの 17.9% がそれぞれ単一たんいつの素数そすうを使つかい回まわしており、これらの素数そすうに対たいして事前じぜん計算けいさん (ある種しゅの線形せんけい代数だいすう計算けいさんを含ふくむ) を行おこなうことで多おおくのサーバーの通信つうしんに対たいして解読かいどくが行おこなえることを指摘してきした。特とくに512ビットの素数そすうに対たいして解読かいどくを実証じっしょうし、数すう千せんコアと約やく8日にちの事前じぜん計算けいさんにより、およそ70秒びょうで解読かいどくができることを示しめした。

さらに、サーバーが用もちいる素数そすうについての離散りさん対数たいすう問題もんだいをリアルタイムで解とける攻撃こうげき者しゃが存在そんざいした場合ばあいには、たとえクライアント側がわが弱よわいDHEを許可きょかしていなくても偽にせのサーバーに接続せつぞくさせる中ちゅう間あいだ者しゃ攻撃こうげきが成立せいりつし、例たとえばサーバー側がわが512ビットの輸出ゆしゅつ版ばんDHEを許ゆるしている場合ばあいには、輸出ゆしゅつ版ばんDHEを許可きょかしていない新あたらしいクライアントであっても通信つうしんをダウングレードさせることが可能かのうであることを示しめした (Logjam 攻撃こうげき)。

同どう論文ろんぶんは1024ビットの非ひ輸出ゆしゅつ版ばんDHEについても、数すう億おくドルのコストをかけて専用せんようハードウェアを構築こうちくした場合ばあいには、1つの素数そすうに対たいして十分じゅうぶんな線形せんけい代数だいすう計算けいさんを1年間ねんかんで実行じっこうできる可能かのう性せいがあることを示唆しさしている。

参考さんこう文献ぶんけん

• W. Diffie and M. E. Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory, vol.IT-22, No.6, pp.644-654, Nov, 1976.
• カナダの特許とっきょ1,121,480
• TLSにおけるForward Secrecyの利用りように関かんする実証じっしょう的てき研究けんきゅう調査ちょうさ (PDF) シマンテック、2013年ねん（2014年ねん6月がつ12日にち閲覧えつらん）。

関連かんれん項目こうもく

• 暗号あんごう理論りろん
• 楕円だえん曲線きょくせんディフィー・ヘルマン鍵かぎ共有きょうゆう

外部がいぶリンク

• RFC 2631: Diffie-Hellman Key Agreement Method
  • Diffie-Hellman 鍵かぎ共有きょうゆう法ほう（DH 法ほう）