ディフィー・ヘルマン鍵交換

ディフィー・ヘルマン鍵交換は、2者間で共有される秘密鍵を確立し、公開ネットワーク上でデータを交換するための秘密通信に利用できます。公開鍵交換の概念を、非常に大きな数字の代わりに色を使って例えると分かりやすいでしょう。

このプロセスは、アリスとボブの2人が、秘密にする必要のない任意の開始色を公に合意することから始まります。この例では、色は黄色です。また、それぞれが秘密の色（この例では赤とシアン）を選び、それを他の人には教えません。このプロセスの重要な部分は、アリスとボブがそれぞれ自分の秘密の色とお互いに共有している色を混ぜ合わせ、それぞれオレンジベージュと水色の混合色を作り、それを公に交換することです。最後に、それぞれが相手から受け取った色と自分の秘密の色を混ぜ合わせます。その結果、最終的な色の混合色（この例では黄褐色）が、相手の最終的な色の混合色と全く同じになります。

第三者がやり取りを傍受した場合、共通の色（黄色）と最初の混合色（オレンジベージュと水色）しか分からず、最後の秘密の色（黄褐色）を突き止めるのは非常に困難です。この例えを、色ではなく大きな数値を用いた現実のやり取りに当てはめると、この判定は計算コストが高く、現代のスーパーコンピュータでも実用的な時間内に計算することは不可能です。

最も単純でオリジナルの実装^{[ 3 ]}は、後にRFC 7919 ^{[ 9 ]}で有限体ディフィー・ヘルマンとして形式化され、 pを法とする整数の乗法群を使用します。ここでpは素数、gはpを法とする原始根です。潜在的な脆弱性を防ぐため、少なくとも2048ビットの長さの素数を使用することが推奨されます。これにより、離散対数を計算して共有秘密を漏洩しようとする攻撃者の難易度が上がります。これらの2つの値は、結果として得られる共有秘密が1からp -1までの任意の値をとることができるように、このように選択されています。以下に、非秘密の値を青、秘密の値を赤で示したプロトコルの例を示します。

1. アリスとボブは、法p = 23、底g = 5（これは法23の原始根である）を使用することに公に合意した。
2. アリスは秘密の整数a = 4 を選び、ボブにA = g ^a mod pを送る
   • A = 5 ⁴ mod 23 = 4 (この例ではAとaはどちらも同じ値4ですが、通常はそうではありません)
3. ボブは秘密の整数b = 3 を選び、アリスにB = g ^b mod pを送る。
   • B = 5 ³ mod 23 = 10
4. アリスはs = B ^a mod pを計算する
   • s =10 ⁴ mod23= 18
5. ボブはs = A ^b mod pを計算する
   • s =4 ³ mod23= 18
6. アリスとボブは今、ある秘密（18という数字）を共有している。

アリスとボブはどちらも同じ値に到達しました。なぜなら、mod pの下では、

${\displaystyle {\color {Blue}A}^{\color {Red}{\boldsymbol {b}}}{\bmod {\color {Blue}p}}={\color {Blue}g}^{\color {Red}{\boldsymbol {ab}}}{\bmod {\color {Blue}p}}={\color {Blue}g}^{\color {Red}{\boldsymbol {ba}}}{\bmod {\color {Blue}p}}={\color {Blue}B}^{\color {Red}{\boldsymbol {a}}}{\bmod {\color {Blue}p}}}$

より具体的には、

${\displaystyle ({\color {Blue}g}^{\color {Red}{\boldsymbol {a}}}{\bmod {\color {Blue}p}})^{\color {Red}{\boldsymbol {b}}}{\bmod {\color {Blue}p}}=({\color {Blue}g}^{\color {Red}{\boldsymbol {b}}}{\bmod {\color {Blue}p}})^{\color {Red}{\boldsymbol {a}}}{\bmod {\color {Blue}p}}}$

aとbだけが秘密に保たれます。その他の値 ( p、g、g ^a mod p、g ^b mod p ) はすべて平文で送信されます。この方式の強みは、 p、g、 g a mod p、g ^b mod pの情報だけでは、既知の古典的なアルゴリズムではg ^ab mod p = g ^{ba mod} pを計算するのに非常に長い時間がかかるという事実にあります。このように計算は容易だが逆関数を求めるのが難しい関数は、一方向関数と呼ばれます。アリスとボブは共有秘密を計算したら、それを暗号鍵として使用し、同じオープンな通信チャネルを介してメッセージを送信できます。この鍵はアリスとボブだけが知っています。

もちろん、n mod 23の結果は 23 通りしかないため、この例を安全にするには、a、b、pの値をはるかに大きくする必要があります。ただし、 pが少なくとも 600 桁の素数である場合、最も速く既知のアルゴリズムを使用する最速の現代のコンピュータでも、g、p、g ^a mod pだけが与えられた場合、aを見つけることはできません。このような問題は、離散対数問題と呼ばれます。^{[ 2 ]} g ^a mod pの計算はモジュラーべき乗として知られており、大きな数でも効率的に実行できます。gは必ずしも大きくなくてもよく、実際には通常、小さな整数 (2、3、... など) であることに注意してください。

下の図は、誰が何を知っているかを示しています。ここでも、秘密でない値は青色、秘密の値は赤色で示されています。ここでは、イブは盗聴者です。彼女はアリスとボブの間で送受信される内容を監視しますが、通信内容を変更することはありません。

• g は、アリス、ボブ、イブに知られている公開（原始ルート）基底です。g = 5
• p は、アリス、ボブ、イブに知られている公開（素数）法です。p = 23
• a はアリスの秘密鍵であり、アリスのみが知っている。a = 6
• b は、ボブのみが知っているボブの秘密鍵です。b = 15
• Aはアリスの公開鍵であり、アリス、ボブ、イブに知られている。A= g ^a mod p = 8
• Bはボブの公開鍵であり、アリス、ボブ、イブに知られている。B = g ^b mod p = 19

ここで、sは共有秘密鍵であり、アリスとボブの両方に知られていますが、イブには知られていません。イブがABを計算することは役に立たないことに注意してください。AB はg ^{a + b} mod pに等しくなります。

注：アリスがボブの秘密鍵を解読するのは困難であるべきであり、ボブがアリスの秘密鍵を解読するのも困難であるべきである。アリスがボブの秘密鍵を解読するのが容易である場合（またはその逆の場合）、盗聴者であるイブは、自身の秘密鍵／公開鍵ペアを置き換え、ボブの公開鍵を自身の秘密鍵に代入し、偽の共有秘密鍵を生成してボブの秘密鍵を解読し（そしてそれを使って共有秘密鍵を解読する）、ボブの秘密鍵を解読することができる。イブは、ボブの秘密鍵を解読しやすくするような公開鍵／秘密鍵ペアを選択しようとするかもしれない。

プロトコルのより一般的な説明は次のとおりです。^{[ 10 ]}

1. アリスとボブは、位数nの有限巡回群Gの自然数nと生成元gについて合意する。（これは通常、プロトコルの残りの部分よりもずっと前に行われる。gとnはすべての攻撃者が知っていると想定される。）群Gは乗法的に記述される。
2. アリスは1 < a < nの範囲でランダムな自然数aを選び、 Gの要素g ^aをボブに送ります。
3. ボブは1 < b < nの範囲でランダムな自然数bを選び、 Gの要素g ^bをアリスに送信する。
4. アリスはGの要素( g ^b ) ^a = g ^{baを計算します。}
5. ボブはGの要素( g ^a ) ^b = g ^{abを計算します。}

アリスとボブはどちらも、共有秘密鍵として使用できる群要素g ^ab = g ^baを所有しています。群Gは、 g、g ^a、g ^bが与えられたときにg ^abを決定する効率的なアルゴリズムが存在しない限り、安全な通信に必要な条件を満たします。

例えば、楕円曲線ディフィー・ヘルマンプロトコルは、G の要素を n を法とする整数としてではなく、楕円曲線上の点として表現する変種です。超楕円曲線 を使用する変種も提案されています。超特異同種鍵交換は、量子コンピュータに対して安全になるように設計されたディフィー・ヘルマン変種ですが、2022 年 7 月に破られました。^{[ 11 ]}

1997年にサイモン・ブレイク＝ウィルソン、ドン・ジョンソン、アルフレッド・メネゼスによって一種のトリプルDHが提案され^{[ 13 ]} 、 2005年にC.クドラとKGパターソンによって改良され^{[ 14 ]}、安全であることが示されました。

アリスとボブの長期秘密鍵はそれぞれaとbで表され、公開鍵はAとB、さらに一時的な鍵ペアは ( x , X ) と ( y , Y ) である。プロトコルは次のようになる。

長期公開鍵は何らかの方法で転送する必要があります。これは、事前に別の信頼できるチャネルで行うか、匿名性を維持するために部分的な鍵合意を使用して公開鍵を暗号化することができます。このような詳細、およびサイドチャネル保護や明示的な鍵確認などのその他の改善、早期メッセージ、追加のパスワード認証については、たとえば米国特許「鍵合意とオプションの認証のための高度なモジュール式ハンドシェイク」を参照してください。^{[ 15 ]}

X3DHは、当初シグナルプロトコルで使用されるダブルラチェットアルゴリズムの一部として提案されました。このプロトコルは前方秘匿性と暗号否認性を提供します。楕円曲線上で動作します。^{[ 16 ]}

このプロトコルでは、5 つの公開鍵を使用します。アリスは、ID 鍵 IK _Aと一時鍵 EK _Aを持っています。ボブは、ID 鍵 IK _B、署名付き事前鍵 SPK _B、およびワンタイム事前鍵 OPK _Bを持っています。^{[ 16 ]}ボブはまず 3 つの鍵をサーバーに公開し、アリスはそれをダウンロードして署名を検証します。次にアリスはボブとの交換を開始します。^{[ 16 ]} OPK はオプションです。^{[ 16 ]}

2021 年に公開されたCVE ( CVE -2002-20001 ) では、一時的な鍵を使用するプロトコルのバリアントに対する D(HE)at 攻撃と呼ばれるサービス拒否攻撃(DoS) が明らかにされました。 ^{[ 19 ]}この攻撃は、Diffie–Hellman 鍵交換では、攻撃者が実際には公開鍵ではない任意の数値を送信できるため、被害者側でコストのかかるモジュラべき乗計算がトリガーされることを悪用します。別の CVE の公開では、Diffie–Hellman 鍵交換の実装では、モジュラべき乗計算を不必要にコストが高くする可能性のある長い秘密指数 ( CVE-2022-40735 )を使用する可能性があること、または長い指数を使用した鍵計算と同様のリソース要件を持つピアの公開鍵を不必要にチェックする可能性があること ( CVE-2024-41996 ) が明らかにされました。^{[21]攻撃者は}、両方の脆弱性を同時に悪用することができ^ます。

離散対数問題を解くのに一般的に最も効果的な数体篩アルゴリズムは、4つの計算ステップから構成されます。最初の 3 つのステップは、有限対数を求める特定の数ではなく、群 G の位数のみに依存します。^{[ 22 ]}インターネット トラフィックの多くは、位数が 1024ビット以下の少数の群のいずれかを使用していることが判明しています。 ^{[ 2 ]}最も一般的な群の数体篩の最初の 3 つのステップを事前に計算することで、攻撃者は、最初の 3 つのステップよりもはるかに計算コストの低い最後のステップを実行するだけで、特定の対数を取得できます。Logjam攻撃はこの脆弱性を利用して、位数が 512 ビットの素数である群の使用を許可しているさまざまなインターネット サービスを侵害しました。これは、いわゆるエクスポート グレードです。著者は、単一の 512 ビット素数のデータを事前に計算するために、1週間にわたって数千の CPU コアを必要としました。それが終わると、2つの18コアIntel Xeon CPUを使用して、個々の対数を約1分で解くことができた。^{[ 2 ]} 

Logjam攻撃の背後にいる著者らの推定によると、1024ビット素数の離散対数問題を解くために必要なはるかに困難な事前計算には、1億ドル程度の費用がかかり、これは米国国家安全保障局（NSA）のような大規模な国家情報機関の予算内に十分収まる。Logjamの著者らは、広く再利用されている1024ビットDH素数に対する事前計算が、NSAが現在の暗号の大部分を破ることができるという流出したNSA文書の主張の背後にあると推測している。 ^{[ 2 ]}

これらの脆弱性を回避するために、Logjamの著者らは、同様の攻撃が知られていない楕円曲線暗号の使用を推奨している。それができない場合は、Diffie–Hellman群の位数pを少なくとも2048 ビットにすることを推奨している。2048ビット素数に必要な事前計算は、1024ビット素数の場合よりも^{10⁹倍難しいと推定している。 [ 2 ]}

量子コンピュータは、素因数分解問題、離散対数問題、周期探索問題を解くためのショアのアルゴリズムを用いて、RSA、有限体DH、楕円曲線DH鍵交換プロトコルなどの公開鍵暗号方式を破ることができる。 2023年には、量子耐性のあるCRYSTALS-Kyberプロトコルと、従来の楕円曲線X25519プロトコルを組み合わせた、ポスト量子版のDiffie-Hellmanアルゴリズムが提案された。

ディフィー・ヘルマン鍵交換に基づく公開鍵暗号方式が提案されている。最初の方式はエルガマル暗号である。より現代的な方式としては、統合暗号方式（IES）がある。

前方秘匿性を実現するプロトコルは、セッションごとに新しい鍵ペアを生成し、セッション終了時にそれらを破棄します。ディフィー・ヘルマン鍵交換は、鍵生成が高速であるため、このようなプロトコルでよく用いられます。

アリスとボブがパスワードを共有する場合、中間者攻撃を防ぐために、パスワード認証鍵合意（PK）方式のディフィー・ヘルマン鍵交換方式を使用することがあります。シンプルな方式の一つは、 sのハッシュ値を連結し、チャネルの両端でそれぞれ独立して計算されたパスワードと比較することです。この方式の特徴は、攻撃者が各反復処理で相手側に対して特定のパスワードしかテストできないため、比較的弱いパスワードでも高いセキュリティが確保される点です。この方式は、ITU-T勧告X.1035に記載されており、 G.hnホームネットワーク規格で採用されています。

そのようなプロトコルの一例として、セキュアリモートパスワードプロトコルが挙げられる。

Diffie-Hellmanは公開鍵インフラストラクチャの一部としても使用でき、ボブがメッセージを暗号化してアリスだけが復号できるようにすることが可能です。この場合、ボブがアリスの公開鍵を信頼できる知識として持っていること以外に、両者の間に事前の通信は必要ありません。アリスの公開鍵は${\displaystyle (g^{a}{\bmod {p}},g,p)}$ボブはアリスにメッセージを送るために、ランダムにbを選び、アリスに送ります。${\displaystyle g^{b}{\bmod {p}}}$（暗号化されていない）メッセージと、共通鍵で暗号化されたメッセージ${\displaystyle (g^{a})^{b}{\bmod {p}}}$アリスだけが共通鍵を特定し、メッセージを復号できるのは、彼女だけが（秘密鍵を）持っているからである。また、事前に共有された公開鍵は中間者攻撃を防ぐ。

実際には、Diffie-Hellmanはこのように使用されることはなく、RSAが主流の公開鍵アルゴリズムとなっています。これは主に歴史的および商業的な理由によるもので、具体的には、RSA Securityが鍵署名のための認証局を設立し、それがVerisignとなったためです。前述のように、Diffie-Hellmanは証明書の署名に直接使用することはできません。しかし、ElGamalおよびDSA署名アルゴリズムは数学的にDiffie-Hellmanと関連しており、MQV、STS、およびインターネットプロトコル通信を保護するためのIPsecプロトコルスイートのIKEコンポーネントも同様です。

• ゴルマン、ディーター（2011）。コンピュータセキュリティ（第2 版）。ウェストサセックス、イングランド：ジョン・ワイリー・アンド・サンズ社。ISBN 978-0470741153。
• ウィリアムソン、マルコム J. (1974 年 1 月 21 日)。有限体を用いた非秘密暗号化(PDF) (技術報告書)。通信電子セキュリティ グループ。2017年 3 月 23 日にオリジナルからアーカイブ(PDF) 。2017年 3 月 22 日に取得。
• ウィリアムソン、マルコム・J.（1976年8月10日）。より安価な非秘密暗号化に関する考察（PDF）（技術報告書）。通信電子機器セキュリティグループ。2004年7月19日のオリジナルからアーカイブ（PDF） 。 2015年8月25日取得。
• 非秘密暗号化の歴史JH Ellis 1987 (28K PDFファイル) ( HTML版)
• 公開鍵暗号の最初の10年間 Whitfield Diffie著、IEEE論文集、第76巻、第5号、1988年5月、560～577ページ（1.9MBのPDFファイル）
• メネゼス、アルフレッド；ファン・オールショット、ポール；ヴァンストーン、スコット（1997）。応用暗号ハンドブック フロリダ州ボカラトン：CRC Press。ISBN 0-8493-8523-7（オンラインで入手可能）
• シン、サイモン（1999）『暗号書：メアリー・スチュアートから量子暗号までの秘密の進化』ニューヨーク：ダブルデイISBN 0-385-49531-5
• 公開鍵暗号の概要 マーティン・E・ヘルマン著、IEEE Communications Magazine、2002年5月号、42～49ページ 。（123kBのPDFファイル）