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

させて${\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 }$単位元として。この群の位数は4の倍数であることが知られています。実際、通常は${\displaystyle A}$そして${\displaystyle B}$順序が${\displaystyle E_{M,A,B}}$は${\displaystyle 4q}$プライム${\displaystyle q}$モンゴメリー曲線とその算術に関するより詳細な議論については、以下を参照してください。^{[ 5 ] [ 6 ] [ 7 ]}

計算効率の観点から、射影座標を用いる方が望ましい。モンゴメリー曲線の射影形式${\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}$以下の通りです。^{[ 7 ]}${\displaystyle x(P)=[X:Z]}$もし${\displaystyle Z\neq 0}$そして${\displaystyle x(P)=[1:0]}$もし${\displaystyle P=[0:1:0]}$バーンスタイン^{[ 8 ] [ 9 ]}は地図を導入した${\displaystyle x_{0}}$次のように：${\displaystyle x_{0}(X:Z)=XZ^{p-2}}$これは、すべての値に対して定義されます。${\displaystyle X}$そして${\displaystyle Z}$で${\displaystyle F_{p}}$ミラー^{[ 10 ]} 、モンゴメリー^{[ 5 ]}、バーンスタイン^{[ 9 ]}に従って、ディフィー・ヘルマン鍵合意はモンゴメリー曲線上で次のように実行できる。${\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})}$ポラードのローアルゴリズムを使用して時間を計算します。^{[ 11 ]}

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