楕円曲線ディフィー・ヘルマン

楕円曲線ディフィー・ヘルマン（ECDH）は、楕円曲線公開鍵と秘密鍵のペアを持つ2者が安全でないチャネルを介して共有秘密を確立できるようにする鍵合意プロトコルです。^{[1] [2] [3]}この共有秘密は、鍵として直接使用することも、別の鍵を導出するために使用することもできます。その後、その鍵または導出された鍵を使用して、対称鍵暗号を使用して後続の通信を暗号化できます。これは、楕円曲線暗号を使用するディフィー・ヘルマンプロトコルのバリエーションです。

次の例は、共有鍵がどのように確立されるかを示しています。アリスがボブと共有鍵を確立したいが、2 人が利用できる唯一のチャネルが第三者に盗聴される可能性があるとします。最初に、ドメイン パラメータ(つまり、素数の場合は 、バイナリの場合は ) について合意する必要があります。また、各当事者は、楕円曲線暗号に適した鍵ペアを持っている必要があります。この鍵ペアは、秘密鍵(区間 内のランダムに選択された整数) と点(ここで、つまり をそれ自体に回加算した結果)で表される公開鍵で構成されます。アリスの鍵ペアを、ボブの鍵ペアを とします。各当事者は、プロトコルの実行前に、相手の公開鍵を知っておく必要があります。 ${\displaystyle (p,a,b,G,n,h)}$${\displaystyle (m,f(x),a,b,G,n,h)}$${\displaystyle d}$${\displaystyle [1,n-1]}$${\displaystyle Q}$${\displaystyle Q=d\cdot G}$ ${\displaystyle G}$${\displaystyle d}$${\displaystyle (d_{\text{A}},Q_{\text{A}})}$${\displaystyle (d_{\text{B}},Q_{\text{B}})}$

アリスは点 を計算します。ボブは点 を計算します。共有秘密は(点のx座標) です。ECDH に基づくほとんどの標準化されたプロトコルは、ハッシュベースのキー導出関数を使用して 対称キーを導出します。${\displaystyle (x_{k},y_{k})=d_{\text{A}}\cdot Q_{\text{B}}}$${\displaystyle (x_{k},y_{k})=d_{\text{B}}\cdot Q_{\text{A}}}$${\displaystyle x_{k}}$${\displaystyle x_{k}}$

両者によって計算された共有秘密は等しい、なぜなら。 ${\displaystyle d_{\text{A}}\cdot Q_{\text{B}}=d_{\text{A}}\cdot d_{\text{B}}\cdot G=d_{\text{B}}\cdot d_{\text{A}}\cdot G=d_{\text{B}}\cdot Q_{\text{A}}}$

アリスが最初に公開する鍵に関する情報は、公開鍵のみです。したがって、楕円曲線の離散対数問題を解決できない限り、アリス以外の誰もアリスの秘密鍵を特定できません (もちろんアリスはそれを選択したため、それを知っています)。ボブの秘密鍵も同様に安全です。楕円曲線のディフィー・ヘルマン問題を解決できない限り、アリスまたはボブ以外の誰も共有秘密を計算できません。

公開鍵は、静的（証明書などによって信頼されている）か、一時的（ECDHEとも呼ばれ、最後の「E」は「一時的」を意味する）のいずれかです。 一時的鍵は一時的なもので、必ずしも認証されているわけではありません。そのため、認証が必要な場合は、他の手段で真正性の保証を得る必要があります。認証は、中間者攻撃を回避するために必要です。アリスまたはボブの公開鍵の 1 つが静的である場合、中間者攻撃は阻止されます。静的公開鍵は、高度なセキュリティ特性の中でも、前方秘匿性や鍵侵害のなりすまし耐性を提供しません。静的秘密鍵の保持者は、他の公開鍵を検証し、静的秘密鍵に関する情報の漏洩を防ぐために、生の Diffie-Hellman 共有秘密に安全な鍵導出関数を適用する必要があります。他のセキュリティ特性を持つスキームについては、 MQV を参照してください。

アリスが悪意を持って自分の鍵に無効な曲線点を選択し、ボブがアリスの点が選択されたグループの一部であることを検証しない場合、アリスはボブの鍵の十分な残基を集めて彼の秘密鍵を導出することができます。いくつかのTLSライブラリがこの攻撃に対して脆弱であることが判明しました。^[4]

共有秘密は、サイズ ののサブセットに均一に分散されます。このため、秘密は対称鍵として直接使用すべきではありませんが、鍵導出関数のエントロピーとして使用できます。 ${\displaystyle [0,p)}$${\displaystyle (n+1)/2}$

となるとします。モンゴメリ形式の楕円曲線は、と表記される無限遠点とともに方程式を満たすすべてのものの集合です。これは曲線のアフィン形式と呼ばれます。 と表記されるのすべての有理点の集合は、 とともに方程式を満たすすべてのものの集合です。適切に定義された加算演算のもとで、は を単位元とする群です。この群の位数は 4 の倍数であることが知られています。実際、 の位数が素数 に対してとなるようなおよびを得ることは通常可能です。モンゴメリ曲線とその算術に関するより広範な議論については、以下を参照してください。^{[5] [6] [7]}${\displaystyle A,B\in F_{p}}$${\displaystyle B(A^{2}-4)\neq 0}$${\displaystyle E_{M,A,B}}$${\displaystyle (x,y)\in F_{p}\times F_{p}}$${\displaystyle By^{2}=x(x^{2}+Ax+1)}$${\displaystyle \infty}$${\displaystyle F_{p}}$${\displaystyle E_{M,A,B}}$${\displaystyle E_{M,A,B}(F_{p})}$${\displaystyle (x,y)\in F_{p}\times F_{p}}$${\displaystyle By^{2}=x(x^{2}+Ax+1)}$${\displaystyle \infty}$${\displaystyle E_{M,A,B}(F_{p})}$${\displaystyle \infty}$${\displaystyle A}$${\displaystyle B}$${\displaystyle E_{M,A,B}}$${\displaystyle 4q}$${\displaystyle q}$

計算効率を上げるには、射影座標を使用するのが望ましい。モンゴメリ曲線の射影形式は である。上の点に対して、-座標マップは次のようになる: ^[7]かつの場合。Bernstein ^{[8] [9]}は、次のようにマップを導入した: これはおよびにおけるすべての値に対して定義される。Miller ^[10] 、 Montgomery ^[5]、および Bernstein ^[9]に従って、Diffie-Hellman 鍵共有はモンゴメリ曲線上で次のように実行できる。を の素数位数サブグループの生成元と する。Alice は秘密鍵を選択し、公開鍵 を持つ。Bob は秘密鍵を選択し、公開鍵 を持つ。Alice と Bob の共有秘密鍵は である。従来のコンピュータを使用して、 とを取得する最もよく知られた方法は、Pollards rho アルゴリズム を使用した約時間を要する。^[11]${\displaystyle E_{M,A,B}}$${\displaystyle BY^{2}Z=X(X^{2}+AXZ+Z^{2})}$${\displaystyle P=[X:Y:Z]}$${\displaystyle E_{M,A,B}}$${\displaystyle x}$${\displaystyle x}$ ${\displaystyle x(P)=[X:Z]}$${\displaystyle Z\neq 0}$${\displaystyle x(P)=[1:0]}$${\displaystyle P=[0:1:0]}$${\displaystyle x_{0}}$${\displaystyle x_{0}(X:Z)=XZ^{p-2}}$${\displaystyle X}$${\displaystyle Z}$${\displaystyle F_{p}}$${\displaystyle Q}$${\displaystyle E_{M,A,B}(F_{p})}$${\displaystyle s}$${\displaystyle x_{0}(sQ)}$${\displaystyle t}$${\displaystyle x_{0}(tQ)}$${\displaystyle x_{0}(stQ)}$${\displaystyle x_{0}(stQ)}$${\displaystyle Q,x_{0}(sQ)}$${\displaystyle x_{0}(tQ)}$${\displaystyle O(p^{1/2})}$

モンゴメリ曲線の最も有名な例は、Bernstein によって導入されたCurve25519です。 ^[9] Curve25519 の場合、および。TLS 1.3 の一部であるもう 1 つのモンゴメリ曲線は、Hamburg によって導入されたCurve448です。 ^[12] Curve448 の場合、および。Curve25519およびCurve448と競合する M[4698] および M[4058] という名前のモンゴメリ曲線が2003 年に提案されました。^{[13] M[4698] の}場合、および M[4058] の場合、。 256ビットのセキュリティレベルでは、M[996558]、M[952902]、M[1504058]という3つのモンゴメリ曲線が提案されています。 ^[14] M[996558]については、、M[952902]については、、M[1504058]については、それぞれです。これら2つ以外にも、モンゴメリ曲線の提案は、で見つけることができます。^[15]${\displaystyle p=2^{255}-19,A=486662}$${\displaystyle B=1}$${\displaystyle p=2^{448}-2^{224}-1,A=156326}$${\displaystyle B=1}$${\displaystyle p=2^{251}-9,A=4698,B=1}$${\displaystyle p=2^{444}-17,A=4058,B=1}$${\displaystyle p=2^{506}-45,A=996558,B=1}$${\displaystyle p=2^{510}-75,A=952902,B=1}$${\displaystyle p=2^{521}-1,A=1504058,B=1}$

• Curve25519 は、C言語のDaniel J. Bernsteinによる楕円曲線パラメータおよびリファレンス実装の一般的なセットです。バインディングおよび代替実装も利用できます。
• Curve448 は、 Rambus Cryptography Researchの Mike Hamburg 氏が開発した、潜在的に 224 ビットのセキュリティを提供する楕円曲線です。
• LINEメッセンジャーアプリは、2015年10月から、同アプリを通じて送信されるすべてのメッセージのエンドツーエンド暗号化「Letter Sealing」にECDHプロトコルを使用しています。^[16]
• Signal プロトコルは、 ECDH を使用して侵害後のセキュリティを確保します。このプロトコルの実装は、Signal、WhatsApp、Facebook Messenger、Skypeで見つかります。

• 楕円曲線暗号
• ディフィー・ヘルマン鍵交換
• 前方秘匿性