ねじれたエドワーズ曲線

代数幾何学において、ツイスト・エドワーズ曲線は楕円曲線の平面モデルであり、2008年にBernstein、Birkner、Joye、Lange 、Petersによって導入されたエドワーズ曲線の一般化である。 ^{[1]この曲線セットは数学者}Harold M. Edwardsにちなんで名付けられている。楕円曲線は公開鍵暗号において重要であり、ツイスト・エドワーズ曲線はEdDSAと呼ばれる電子署名方式の中核をなすものであり、この方式は高いパフォーマンスを提供しながら、他のデジタル署名方式で表面化したセキュリティ問題を回避している。

特性が2 でない体上のねじれたエドワーズ曲線(つまり、どの要素もそれ自身の加法逆ではない) は、次の式で定義されるアフィン平面曲線です。 ${\displaystyle E_{E,a,d}}$ ${\displaystyle \mathbb {K} }$

${\displaystyle E_{E,a,d}:ax^{2}+y^{2}=1+dx^{2}y^{2}}$

ここで、 はの異なる非ゼロ要素です。 ${\displaystyle a,d}$${\displaystyle \mathbb {K} }$

ねじれたエドワーズ曲線はそれぞれ、エドワーズ曲線のねじれです。特殊なケースはねじれがなく、曲線は通常のエドワーズ曲線に縮小されます。 ${\displaystyle a=1}$

ねじれたエドワーズ曲線はすべてモンゴメリ形式の楕円曲線と双有理的に同値であり、その逆もまた同様である。^[2]

すべての楕円曲線と同様に、ねじれたエドワーズ曲線でも、2 つの点を加算したり、1 つの点を 2 倍 (または 3 倍) にするなど、その点の間でいくつかの操作を行うことができます。これらの操作の結果は常に、曲線自体に属する点です。次のセクションでは、他の 2 つの点を加算 (加算) した結果の点の座標、または曲線上の 1 つの点を 2 倍にした結果の点の座標を取得するためのいくつかの式を示します。

を2 とは異なる特性を持つ体とします。および をねじれたエドワーズ曲線上の点 とします。 ねじれたエドワーズ曲線の方程式は次のように表されます。${\displaystyle \mathbb {K} }$${\displaystyle (x_{1},y_{1})}$${\displaystyle (x_{2},y_{2})}$

${\displaystyle E_{E,a,d}}$: .${\displaystyle ax^{2}+y^{2}=1+dx^{2}y^{2}}$

これらの点の合計は次のようになります。 ${\displaystyle (x_{1},y_{1}),(x_{2},y_{2})}$${\displaystyle E_{E,a,d}}$

${\displaystyle (x_{1},y_{1})+(x_{2},y_{2})=\left({\frac {x_{1}y_{2}+y_{1}x_{2}}{1+dx_{1}x_{2}y_{1}y_{2}}},{\frac {y_{1}y_{2}-ax_{1}x_{2}}{1-dx_{1}x_{2}y_{1}y_{2}}}\right)}$

中立要素は（0,1）であり、負の要素は${\displaystyle (x_{1},y_{1})}$${\displaystyle (-x_{1},y_{1})}$

これらの公式は倍数計算にも適用できます。aがの正方形で、dがの非正方形の場合、これらの公式は完全です。つまり、例外なくすべての点のペアに使用できます。したがって、倍数計算にも適用でき、中立要素と負の要素も入力として受け入れられます。^{[3] [検証失敗]}${\displaystyle \mathbb {K} }$${\displaystyle \mathbb {K} }$

追加の例

a = 3、d = 2の次のねじれたエドワーズ曲線があるとします。

${\displaystyle 3x^{2}+y^{2}=1+2x^{2}y^{2}}$

上記の式を使用して点を加算することができます。結果は座標を持つ点 P ₃になります。 ${\displaystyle P_{1}=(1,{\sqrt {2}})}$${\displaystyle P_{2}=(1,-{\sqrt {2}})}$

${\displaystyle x_{3}={\frac {x_{1}y_{2}+y_{1}x_{2}}{1+dx_{1}x_{2}y_{1}y_{2}}}=0,}$

${\displaystyle y_{3}={\frac {y_{1}y_{2}-ax_{1}x_{2}}{1-dx_{1}x_{2}y_{1}y_{2}}}=-1.}$

倍増は加算とまったく同じ式で実行できます。曲線上の点の倍増は次のようになります。 ${\displaystyle (x_{1},y_{1})}$${\displaystyle E_{E,a,d}}$

${\displaystyle 2(x_{1},y_{1})=(x_{3},y_{3})}$

どこ

${\displaystyle {\begin{aligned}x_{3}&={\frac {x_{1}y_{1}+y_{1}x_{1}}{1+dx_{1}x_{1}y_{1}y_{1}}}={\frac {2x_{1}y_{1}}{ax_{1}^{2}+y_{1}^{2}}}\\[6pt]y_{3}&={\frac {y_{1}y_{1}-ax_{1}x_{1}}{1-dx_{1}x_{1}y_{1}y_{1}}}={\frac {y_{1}^{2}-ax_{1}^{2}}{2-ax_{1}^{2}-y_{1}^{2}}}.\end{aligned}}}$

2 倍算の分母は曲線方程式を使用して簡略化されます。これにより、累乗が 4 から 2 に削減され、より効率的な計算が可能になります。 ${\displaystyle dx^{2}y^{2}=ax^{2}+by^{2}-1}$

倍増の例

前の例で示した同じねじれたエドワーズ曲線（a=3、d=2）を考えると、点を2倍にすることができます。上記の式を使用して得られた点2P _1の座標は次のようになります。 ${\displaystyle P_{1}=(1,{\sqrt {2}})}$

${\displaystyle x_{3}={\frac {2x_{1}y_{1}}{ax_{1}^{2}+y_{1}^{2}}}={\frac {2{\sqrt {2}}}{5}},}$

${\displaystyle y_{3}={\frac {y_{1}^{2}-ax_{1}^{2}}{2-ax_{1}^{2}-y_{1}^{2}}}={\frac {1}{3}}.}$

少し計算するだけで、点が曲線に属していることが簡単にわかります。 ${\displaystyle P_{3}=\left({\frac {2{\sqrt {2}}}{5}},{\frac {1}{3}}\right)}$${\displaystyle 3x^{2}+y^{2}=1+2x^{2}y^{2}}$

ねじれたエドワーズ曲線上の点を表すことができる別の種類の座標系があります。上の点は、次の式x  =  X / Z、y  =  Y / Z、xy  =  T / Zを満たすX、Y、Z、Tとして表されます。 ${\displaystyle (x,y,z)}$${\displaystyle ax^{2}+y^{2}=1+dx^{2}y^{2}}$

点の座標 ( X : Y : Z : T ) は拡張ツイストエドワーズ座標と呼ばれます。単位元は (0:1:1:0) で表されます。点の負の値は (− X : Y : Z :− T ) です。

点の座標は、曲線 上の 反転ツイスト エドワーズ座標と 呼ばれます。この点は、上のアフィン エドワーズ座標に相当します。Bernstein と Lange は、a=1 の場合にこれらの反転座標を導入し、さらに座標によって時間が節約されることを観察しました。 ${\displaystyle (X_{1}:Y_{1}:Z_{1})}$${\textstyle (X^{2}+aY^{2})Z^{2}=X^{2}Y^{2}+dZ^{4}}$${\textstyle X_{1}Y_{1}Z_{1}\neq 0}$${\displaystyle (Z_{1}/X_{1},Z_{1}/Y_{1})}$${\displaystyle E_{E,a,d}}$

射影ツイストエドワーズ曲線の方程式は次のように与えられます: Z ₁ ≠ 0の場合、 点 (X ₁ :Y ₁ :Z ₁ ) はE _E、a、d上のアフィン点( x ₁ =  X ₁ / Z ₁、y ₁ = Y ₁ / Z ₁ )を表します。 ${\displaystyle (aX^{2}+Y^{2})Z^{2}=Z^{4}+dX^{2}Y^{2}}$

楕円曲線をツイスト エドワーズ形式で表現すると、同じ曲線をエドワーズ形式で表現できる場合でも、計算時間が節約されます。

射影ツイストエドワーズ曲線上の加法は次のように表される。

(X ₃ :Y ₃ :Z ₃ ) = (X ₁ :Y ₁ :Z ₁ ) + (X ₂ :Y ₂ :Z ₂ )

これには 10回の乗算 + 1 回の 2乗+ 2 D + 7 回の加算が必要です。ここで、 2 D はaによる乗算 1 回とdによる乗算 1 回です。

アルゴリズム

A = Z ₁ · Z ₂、

B = A ²

C = X ₁ · X ₂

Ｄ＝_Ｙ１・_Ｙ２

E = dC · D

F = B − E

G = B + E

X ₃ = A · F((X ₁ + Y ₁ ) · (X ₂ + Y ₂ ) − C − D)

Y ₃ = A · G · (D − aC)

Z ₃ = F · G

射影ねじれ曲線上の倍加は次のように与えられる。

(X ₃ :Y ₃ :Z ₃ ) = 2(X ₁ :Y ₁ :Z ₁ ) です。

これには 3回の乗算 + 4 回の二乗 + 1 回のD + 7 回の加算が必要です。ここで、1 回のDはaによる乗算です。

アルゴリズム

B = (X ₁ + Y ₁ ) ²

C = X ₁ ²

^Ｄ＝_Ｙ１２

E = αC

F = E + D

H = Z ₁ ²

J = F − 2H

X ₃ = (B − C − D).J

Y ₃ = F · (E − D)

Z ₃ = F · J ^[1]

• エドDSA
• 特定のケースで必要な実行時間の詳細については、「楕円曲線での演算コストの表」を参照してください。

• ダニエル・J・バーンスタイン。マーク・ジョイ。タンジャ・ランゲ。ピーター・バークナー。クリスティアン・ピーターズ、Twisted Edwards Curves (PDF)

• Huseyin Hisil、Kenneth Wong、Gary Carter、Ed Dawson。(2008)「ツイスト エドワーズ曲線の再考」、Cryptology ePrint Archive{{citation}}: CS1 maint: multiple names: authors list (link)

• ダニエル・J・バーンスタイン。タンジャ・ランゲ。ピーター・バークナー。 Christiane Peters、エドワーズ曲線を使用した ECM (PDF)

• http://hyperelliptic.org/EFD/g1p/index.html
• http://hyperelliptic.org/EFD/g1p/auto-twisted.html
• Ed25519 アルゴリズム: http://ed25519.cr.yp.to/