Diffie-Hellman鍵交換は、公開鍵暗号方式における最も重要な開発の1つであり、現在でもさまざまなセキュリティ プロトコルに頻繁に実装されています。
Diffie-Hellman鍵交換とは
Diffie-Hellman鍵交換は、安全ではないチャンネルで鍵を開発し交換する最初の方法として広く使われています。
上記の言葉では、それほどエキサイティングでも画期的でもないように思えるかもしれませんが、なぜDiffie-Hellman鍵交換が暗号の世界で重要なマイルストーンであり、現在でも頻繁に使用されているのか、例を挙げて説明してみましょう。
あなたが極秘のスパイで、重要な情報を本部に送る必要があるとします。
最も一般的な方法は、メッセージをコードで暗号化することです。
例えば、あなたが特に悪いスパイで、本部と一緒に弱いシフト暗号を使ってメッセージを暗号化することにしたとしましょう。
この暗号では、「a」が「b」になり、「b」が「c」になり、「c」が「d」になり、「z」が「a」になるという具合です。
しかし、もしあなたが事前に相手と暗号を取り決められなかったらどうなるでしょうか？
例えば、一度も会ったことのない同盟国のスパイと連絡を取りたいとします。 相手と話すための安全なチャンネルを持っていません。 メッセージを暗号化しなければ、敵に傍受されても内容を読むことができてしまいます。
この問題は、1970 年代までの暗号技術における最大の難問の 1 つでした。
事前に鍵を共有する機会がない場合、どのようにして誰かと安全に情報を交換することができるのでしょうか。
この問題を解決するために最初に公的に使用されたメカニズムが、Diffie-Hellman 鍵交換です。
Diffie-Hellman鍵交換の歴史
Diffie-Hellman鍵交換の起源は1970年代に遡ります。
公開鍵アルゴリズムが世間に登場したのは、1976年にウィットフィールド・ディフィーとマーティン・ヘルマンが論文「New Directions in Cryptography」を発表したときでした。
この論文は、ラルフ・マークルが開発した新しい鍵交換方式にヒントを得ています。 いわゆる「Merkle’s Puzzles」とは、一方の当事者がいくつかの暗号パズルを作成して相手に送信するというものです。
受信者は、解くべきパズルをランダムに1つ選び、必要な努力をして完成させます。
受信者は、解くべきパズルをランダムに1つ選び、必要な努力をして完成させる。
オリジナルの送信者がパズルを作成したので、識別子によって、受信者が発見したセッションキーを知ることができ、両者はこのキーを使ってより安全な通信を行うことができます。
識別子は、使用されているセッション キーを攻撃者に伝えないため、情報を復号化するための最良の方法は、すべてのパズルを解いて正しいセッション キーを明らかにすることです。 攻撃者は平均して半分のパズルを解かなければならないので、受信者よりも攻撃者の方が鍵を発見するのがはるかに難しいことになります。
このアプローチはより高いセキュリティを提供しますが、完全なソリューションではありません。
Diffie-Hellman 鍵交換として知られるようになりましたが、Martin Hellman はこのアルゴリズムを Diffie-Hellman-Merkle 鍵交換と呼ぶことを提案しました。これは、Ralph Merkle が公開鍵暗号方式に取り組んだことを反映したものです。
1997年に英国政府が、ジェームズ・エリス、クリフォード・コックス、マルコム・ウィリアムソンの3人が1970年代初頭に行った研究を機密解除するまでは、メルクル、ヘルマン、ディフィーの3人が公開鍵暗号方式を初めて開発したと一般に考えられていました。
彼らの発見は、実際にはRSAアルゴリズムだったので、Diffie、Hellman、Merkleの3人は、Diffie-Hellman鍵交換を最初に開発した人物ではありますが、公開鍵暗号の最初の発明者ではなくなりました。
Diffie-Hellman 鍵交換はどこで使用されるのか
Diffie-Hellman 鍵交換の主な目的は、鍵を導き出すために使用できる共有秘密を安全に開発することです。 この鍵は、対称鍵アルゴリズムを使用して、保護された方法で情報を送信することができます。
技術的には、Diffie-Hellman鍵交換は、公開鍵と秘密鍵を確立するために使用することができます。 しかし、実際には、代わりにRSAが使用される傾向にあります。
PGP で多用されている ElGamal アルゴリズムは、Diffie-Hellman 鍵交換に基づいているため、これを使用するプロトコルは、事実上、一種の Diffie-Hellman を実装していることになります。
Diffie-Hellman 鍵交換は、鍵を安全に配布するための最も一般的な方法の 1 つであり、TLS、IPsec、SSH、PGP などのセキュリティ プロトコルに頻繁に実装されています。
これらのプロトコルの一部として、Diffie-Hellman鍵交換は、ウェブサイトへの接続を保護したり、別のコンピュータにリモートでアクセスしたり、暗号化された電子メールを送信したりするためによく使用されます
Diffie-Hellman鍵交換の仕組み
Diffie-Hellman鍵交換は複雑で、その仕組みを理解するのは難しいかもしれません。
少しでも理解しやすくするために、Diffie-Hellman鍵交換を例え話で説明することから始めます。
Diffie-Hellman方式の最も良い例えは、2人の人間が絵の具を混ぜていると考えることです。 暗号技術の標準を使って、二人の名前をアリスとボブとしましょう。 二人は最初にランダムな色を決めることに同意します。
二人は自分の色を設定します。 相手には自分の選択を伝えません。
次のステップでは、アリスとボブの両方が、自分の秘密の色 (アリスは赤、ボブは緑がかった青) を、お互いに合意した黄色と混ぜ合わせます。
混合が終わると、二人はその結果を相手に送ります。
相手から混ぜた結果を受け取った後、二人はそこに自分の秘密の色を加えます。
相手から混ざった結果を受け取った後、二人は自分の秘密の色を加えます。アリスは濃い青に秘密の赤を加え、ボブはオレンジ色の混ざった結果に秘密の緑青を加えます。 二人とも同じ色になりましたが、この場合は嫌な茶色です。 リビングルームに塗りたくなるような色ではないかもしれませんが、それでも共有された色なのです。
Diffie-Hellman 鍵交換の重要な点は、共通の秘密の全体を通信チャネルで送信することなく、両当事者が同じ結果を得ることです。
もし攻撃者が交換を聞いていたら、アクセスできるのは、AliceとBobが最初に持っていた共通の黄色と、交換された混合色だけです。
Diffie-Hellman 鍵交換のこのような構造が、Diffie-Hellman 鍵交換を非常に便利なものにしています。
このDiffie-Hellman鍵交換の構造が、非常に便利な点です。2つの当事者が、潜在的に危険な接続を介して通信しても、共有の秘密を得ることができます。
Diffie-Hellman 鍵交換の技術的詳細
数学の時間です…
心配しないでください。 上の例え話と同じような前提に立っていますが、Diffie-Hellman スキームでは、色を混ぜて送る代わりに、特別に大きな素数に基づいて実際に計算を行い、それを全体に送ります。
安全性を確保するために、素数 (p) の長さは少なくとも 2048 ビットであることが推奨されています。これは、10 進数のこれくらいの大きさの 2 進数に相当します。
415368757628736598425938247569843765827634879128375827365928736 84273684728938572983759283475934875938475928475928739587249587 29873958729835792875982795837529876348273685729843579348795827 93857928739548772397592837592478593867045986792384737826735267 3547623568734869386945673456827659498063849024875809603947902 7945982730187439759284620950293759287049502938058920983945872 0948602984912837502948019371092480193581037995810937501938507913 95710937597019385089103951073058710393701934701938091803984091804 98109380198501398401983509183501983091079180395810395190395180935 8109385019840193580193840198340918093851098309180019
誰かの頭が爆発するのを防ぐために。 ここでは、もっと小さな数字を使って説明します。 Diffie-Hellman鍵交換は、この例のような小さな数字を使うと安全ではないことに注意してください。
Diffie-Hellman 鍵交換の最も基本的な形式では、アリスとボブは、上の例での単一の共通ペイントとは対照的に、開始する 2 つの数字を相互に決定することから始めます。
実用的には、モジュラス(p)は非常に大きな素数で、ベース(g)は計算を簡単にするために比較的小さな値にします。
実用的には、モジュラス(p)は非常に大きな素数で、ベース(g)は計算を簡単にするために比較的小さいものです。
お互いにこれらの数字を決めたら、アリスは自分のための秘密の数字(a)を決め、ボブは自分の秘密の数字(b)を選びます。
a = 3 b = 6
アリスは次のような計算をして、ボブに送る数字を決めます。
A = ga mod p
上記の計算において、modはmodulo演算を意味しています。 これは本来、左辺を右辺で割った後の余りを求める計算です。 例：
15 mod 4 = 3
モジュロ演算の仕組みを理解していれば、以下の計算で自分で行うことができますし、そうでなければオンラインの計算機を使うこともできます。
では、私たちの数字を式に入れてみましょう：
A = 43 mod 17 A = 64 mod 17 A = 13
ボブについても同じようにすると、次のようになります。
B = 46 mod 17 B = 4096 mod 17 B = 16
その後、アリスは自分の結果(A)をボブに送り、ボブは自分の数字(B)をアリスに送ります。 そしてアリスは、ボブから受け取った数字（B）と自分の秘密の数字（a）を使って、次の式で共有秘密（s）を計算します。
s = Ba mod p s = 163 mod 17 s = 4,096 mod 17 s = 16
次にボブは、基本的には同じ計算を行いますが、アリスが送ってきた番号（A）と自分の秘密の番号（B）を使って計算します。
s = Ab mod p s = 136 mod 17 s = 4,826,809 mod 17 s = 16
お分かりのように、両者はsについて同じ結果である16を得ました。 これが、アリスとボブだけが知っている共有秘密です。
上の例では、B と s が同じになっていますが、これは例示のために選んだ小さな数字に基づく偶然の一致です。
上記のデータの多くは平文でチャネルを介して送信され (p、g、A、B)、潜在的な攻撃者が読むことができるにもかかわらず、共有秘密 (s) は決して送信されません。
もちろん、これは、Diffie-Hellman鍵交換が適切に実装され、十分に大きな数字が使用されていることを前提としています。
これは、Diffie-Hellman 鍵交換が適切に実装され、十分な数が使用されていることを前提としています。
複数の当事者間で共有鍵を確立する
Diffie-Hellman 鍵交換は、より多くの参加者で共有鍵を設定するためにも使用できます。
2 パーティ バージョンの Diffie-Hellman 鍵交換と同様に、情報の一部は安全でないチャネルを介して送信されますが、攻撃者が共有鍵を計算できるほどではありません。
Diffie-Hellman の鍵交換はなぜ安全なのか
数学的なレベルでは、Diffie-Hellman の鍵交換は、安全性の基礎として一方向性関数に依存しています。
より具体的には、Diffie-Hellman 問題に依存しています。これは、適切なパラメータの下では、g、ga、gb の個別の値から gab を計算することは不可能であると仮定するものです。 現在のところ、他の値から gab を簡単に見つける方法は公表されておらず、攻撃者が p、g、A、B の値を傍受できるにもかかわらず、Diffie-Hellman 鍵交換が安全であると考えられている理由です。
これらの攻撃は、Diffie-Hellman 鍵交換が単独で実装されている場合に発生します。なぜなら、接続中の相手が本当に自分が言っていることを検証する手段がないからです。
このような理由から、Diffie-Hellman 鍵交換は一般的に、何らかの認証手段と一緒に実装されています。
Variations of the Diffie-Hellman key exchange
Diffie-Hellman 鍵交換はさまざまな方法で実装することができ、いくつかの他のアルゴリズムの基礎にもなっています。
楕円曲線 Diffie-Hellman
楕円曲線 Diffie-Hellman は、楕円曲線の代数的な構造を利用して、より小さな鍵サイズで同程度のセキュリティを実現しています。 224ビットの楕円曲線キーは、2048ビットのRSAキーと同レベルのセキュリティを提供します。
キーの長さが小さいことと、楕円曲線の特性に依存していることを除けば、楕円曲線 Diffie-Hellman は標準の Diffie-Hellman 鍵交換と同様に動作します。
TLS
インターネットの多くの部分を保護するために使用されているプロトコルである TLS は、Diffie-Hellman 交換を、匿名、静的、および ephemeral の 3 つの方法で使用できます。
- Anonymous Diffie-Hellman – このバージョンの Diffie-Hellman 鍵交換は、認証を使用しないため、中間者攻撃に対して脆弱です。
- Static Diffie-Hellman – Static Diffie-Hellman は証明書を使用してサーバーを認証します。
- Ephemeral Diffie-Hellman (エフェメラル Diffie-Hellman) – 完全な前方機密を提供するため、最も安全な実装と考えられています。 一般的には、DSA や RSA などのアルゴリズムと組み合わせて、接続している当事者の一方または両方を認証します。 エフェメラルDiffie-Hellmanは、プロトコルを実行するたびに異なる鍵ペアを使用します。
ElGamal
ElGamalは、Diffie-Hellman鍵交換の上に構築された公開鍵アルゴリズムです。
ElGamal は、Diffie-Hellman 鍵交換の上に構築された公開鍵アルゴリズムで、Diffie-Hellman と同様に、それ自体には認証のための規定がなく、一般的には認証のために他のメカニズムと組み合わせて使用されます。 RSAの特許は2000年に切れたので、それ以降は自由に実装できるようになりました。
STS
Station-to-Station(STS)プロトコルもDiffie-Hellman鍵交換をベースにしています。
このプロトコルでは、接続する両方の当事者がすでに鍵ペアを持っていることが必要で、これは各当事者の認証に使用されます。
Diffie-Hellman 鍵交換 & RSA
先ほど説明したように、Diffie-Hellman 鍵交換は、接続の認証を提供するために、RSA または他のアルゴリズムと一緒に実装されることがよくあります。 RSA をご存知の方は、なぜわざわざ Diffie-Hellman 鍵交換も使用するのかと思われるかもしれません。RSA は、初対面の相手と安全に通信することができるからです。
RSAは、相手の公開鍵でメッセージを暗号化し、一致する秘密鍵がなければ解読できないようにすることができますが、実際には、通信全体を暗号化するためにRSAを使用することはありません。 これには、各当事者のデジタル証明書が使用されます。このデジタル証明書は、証明機関によって検証され、証明書の所有者が自分の言うとおりの人物であり、証明書の公開鍵が実際に自分のものであることを証明します。 各受信者は、署名されたメッセージを通信相手のデジタル証明書の公開鍵と照合することで、相手の身元を確認することができます（この仕組みの詳細については、前述のRSAに関する記事、特に「メッセージの署名」のセクションを参照してください）。
双方の当事者が認証されたので、技術的には、RSA を使用して自分たちの間で暗号化されたメッセージを安全に送信し続けることは可能ですが、結局は非効率的です。
この非効率性を回避するために、多くのセキュリティ プロトコルは、Diffie-Hellman 鍵交換などのアルゴリズムを使用して、共有対称鍵を確立するために使用できる共通の秘密を導き出します。
これは複雑なプロセスのように見えるかもしれませんが、交換全体に公開鍵アルゴリズムを使用する場合と比較して、結果的にはるかに迅速で、リソースの需要が少ないものとなります。
先ほど述べた非効率性に加え、RSAのみを使用した場合のデメリットもいくつかあります。
RSA は完全な前方秘匿性を提供しないため、一時的な Diffie-Hellman 鍵交換と比較した場合のもう一つの欠点でもあります。
代わりに、Diffie-Hellman 鍵交換を Digital Signature Standard (DSS) のようなアルゴリズムと組み合わせて、認証、鍵交換、秘密保持、データの完全性のチェックを行うことができます。
Diffie-Hellman鍵交換のセキュリティ問題
Diffie-Hellman鍵交換のセキュリティは、その実装方法や選択された数字に依存します。
数字の選択に関するパラメーター
Diffie-Hellman 鍵交換の実際の実装が、私たちの例のように小さな数字を使用した場合、攻撃者にとって交換プロセスをクラックするのは簡単なことでしょう。 しかし、重要なのは数字の大きさだけではありません。数字は十分にランダムである必要があります。 乱数生成器が予測可能な出力を生成した場合、Diffie-Hellman 鍵交換のセキュリティが完全に損なわれてしまいます。
数pは、安全性を確保するために、2048ビットの長さにする必要があります。基数gは、2のような比較的小さな数でも構いませんが、大きな素因数を持つGの次数から来ている必要があります
Logjam攻撃
Diffie-Hellman鍵交換は、離散対数問題の解決が難しいことを前提に設計されました。
このアルゴリズムの性能は、Diffie-Hellman 鍵交換の設計時に考慮されていましたが、解を見つけるための最も効果的な公知のメカニズムは、数場のふるいアルゴリズムです。
このアルゴリズムは、Diffie-Hellman 鍵交換の設計時にその機能が考慮されていました。1992 年までに、あるグループ G に対して、アルゴリズムに含まれる 4 つのステップのうち 3 つを事前に計算できる可能性があることがわかっていました。
これは、インターネットトラフィックのかなりの部分が、1024ビット以下の同じグループを使用していることに気づくまでは、あまり気になりませんでした。
2015年、ある学術チームは、TLSのDiffie-Hellman鍵交換で使用される最も一般的な512ビットの素数について計算を行いました。
また、DHE-EXPORTをサポートするTLSサーバーの80%をダウングレードし、512ビットの輸出グレードのDiffie-Hellman鍵交換による接続を受け入れるようにすることができました。
研究者はさらに、この結果を外挿して、国家が 1024 ビットのプライムを破ることができると推定しています。
さらに、2番目の素数を使えば、VPNサーバーの66％、SSHサーバーの26％の接続を解読することができるとしています。
報告書の後半では、NSAがすでにこのような能力を持っている可能性を示唆しています。
公開されているNSAのリーク情報を詳細に読むと、NSAのVPNに対する攻撃は、このようなブレークを達成したことと一致していることがわかります。 2048ビットの鍵を使用している限り、Logjam攻撃は機能しません。
Is the Diffie-Hellman key exchange safe?
Diffie-Hellman key exchangeは複雑に見えるかもしれませんが、オンラインで安全にデータを交換するための基本的な部分です。
Diffie-Hellman 鍵交換は、1970 年代に開発された、未知の 2 者が安全に通信するための革新的な方法でした。
1970年代に開発されたDiffie-Hellman鍵交換は、未知の2つの当事者が安全に通信するための革新的な方法でした。現在では、現代の技術から保護するために、より大きな鍵を持つ新しいバージョンを実装していますが、プロトコル自体は、量子コンピューティングとそれに伴う高度な攻撃が登場するまでは、引き続き安全であると考えられます。
量子コンピューティングは、ブレークスルーを続けている新しいコンピューティングの分野です。
簡単に説明すると、量子コンピューターは、古典的なコンピューターでは現在実現不可能な特定の問題を解決できると期待されています。 これにより、多くの扉が開かれ、新しい可能性が生まれます。
これは素晴らしいことですが、現在の多くの暗号メカニズムの安全性は、これらの問題を解決するのが難しいことに依存しています。
これは素晴らしいことですが、現在の暗号メカニズムの安全性は、これらの問題が解決困難であることに依存しています。これらの数学的問題が計算しやすくなれば、これらの暗号メカニズムを破ることも容易になります。 量子コンピュータが十分に強力になれば、AESなどの共通鍵暗号に対する攻撃が高速化されます。 しかし、鍵のサイズを2倍にすることで簡単に緩和することができます。
最大の懸念は、ショーのアルゴリズムが公開鍵暗号にどのような影響を与えるかということです。
- 離散対数問題
- 整数分解問題
- 楕円曲線離散対数問題
それぞれの具体的な内容はあまり重要ではありませんが、追加情報が必要な場合はリンク先を参照してください。 重要なのは、十分に強力な量子コンピュータが登場すれば、これらの問題をショアーのアルゴリズムで解くことがより現実的になるということです。
公開鍵暗号は、私たちの通信を保護する上で基本的な役割を果たしています。そのため、量子コンピューティングは暗号学者にとって大きな課題となっています。
Diffie-Hellman鍵交換の場合、その安全性は、現在の技術とリソースで離散対数問題を解くことができないという非現実性に依存しています。
量子コンピューティングがいつDiffie-Hellman鍵交換を脅かすかについては、楽観的な研究者とそうでない研究者がいるため、大まかな時期を決めることはできません。
Potential replacements for the Diffie-Hellman key exchange
量子コンピューターの脅威はすぐには起こらないので、暗号コミュニティはまだDiffie-Hellman key exchangeの具体的な代替案を決定していません。 しかし、さまざまな方法が追求されています。
- 格子ベースの暗号
- 多変数暗号
- 楕円曲線等式暗号
量子化後の世界が暗号にとってどのようなものになるかはまだ正確にはわかりませんが、セキュリティ コミュニティは積極的に問題に取り組み、量子コンピューティングの世界の進歩に追随しています。 将来的には大きな変化があるでしょうが、一般の人が恐れる必要はなく、変化があっても気づかないかもしれません。