楕円曲線点の乗算

無限遠を指す${\displaystyle {\mathcal {O}}}$は楕円曲線演算の単位元です。任意の点にこれを加えると、その点自体が得られます。無限遠点をそれ自身に加えることも可能です。つまり、次のようになります。

${\displaystyle {\begin{aligned}{\mathcal {O}}+{\mathcal {O}}={\mathcal {O}}\\{\mathcal {O}}+P=P\end{aligned}}}$

無限遠点は0と表記されることもあります。

点の否定とは、それ自身に加えると無限遠点になるような点を見つけることである（${\displaystyle {\mathcal {O}}}$⁠ )

${\displaystyle {\begin{aligned}P+(-P)={\mathcal {O}}\end{aligned}}}$

E : y ² = x ³ + ax + bの形の楕円曲線の場合、否定とは、 x座標は同じだがy座標が否定された点のことである。

${\displaystyle {\begin{aligned}(x,y)+(-(x,y))&={\mathcal {O}}\\(x,y)+(x,-y)&={\mathcal {O}}\\(x,-y)&=-(x,y)\end{aligned}}}$

2つの異なる点PとQにおいて、加算は曲線Eと点PとQによって定義される直線との交点から得られる点Rの否定として定義される。^{[ 1 ]}

${\displaystyle {\begin{aligned}P+Q&=R\\(x_{p},y_{p})+(x_{q},y_{q})&=(x_{r},y_{r})\end{aligned}}}$

楕円曲線Eがy ² = x ³ + ax + bで与えられると仮定すると、これは次のように計算できます。

${\displaystyle {\begin{aligned}\lambda &={\frac {y_{q}-y_{p}}{x_{q}-x_{p}}}\\x_{r}&=\lambda ^{2}-x_{p}-x_{q}\\y_{r}&=\lambda (x_{p}-x_{r})-y_{p}\\\end{aligned}}}$

これらの式は、どちらの点も無限遠点ではない場合に正しい。${\displaystyle {\mathcal {O}}}$また、点の x 座標が異なる場合 (互いに逆元でない場合) は、ハッシュ値がゼロになる可能性があるECDSA 検証アルゴリズムにとって重要です。

点Pと点 Qが一致している場合 (同じ座標にある場合)、加算は同様ですが、点Pを通る明確な直線がないため、極限の場合として、点Pにおける曲線Eの接線を使用して演算を閉じます。

これは、上記のように微分（dE/dx）/（dE/dy）を取って計算されます。^{[ 1 ]}

${\displaystyle \lambda ={\frac {3x_{p}^{2}+a}{2y_{p}}}}$

ここで、aは上記の曲線Eの定義式から得られる値である。

最も単純な方法は、モジュラーべき乗における二乗乗法に似た、倍加算法です^{[ 2 ]}。アルゴリズムは次のように動作します。

sPを計算するには、まずsの二進数表現から始めます。${\displaystyle s=s_{0}+2s_{1}+2^{2}s_{2}+\cdots +2^{n-1}s_{n-1}}$⁠、そこで⁠${\displaystyle s_{0}~..~s_{n-1}\in \{0,1\},n=\lceil \log _{2}{s}\rceil }$⁠ .

• 反復アルゴリズム、インデックス増加：

let bits = bit_representation(s) # s を表すビットのベクトル (LSB から MSB まで) let res =${\displaystyle {\begin{aligned}{\mathcal {O}}\end{aligned}}}$# 無限遠を指す let temp = P # 2倍の P 値を追跡 for bit in bits: if bit == 1: res = res + temp # ポイント加算 temp = temp + temp # double resを返す

• 反復アルゴリズム、インデックス減少：

let bits = bit_representation(s) # s を表すビットのベクトル (LSB から MSB まで) let i = length(bits) - 2 let res = P while (i >= 0): # 2 番目の MSB から LSB までを走査 res = res + res # double bits[i] == 1 の場合: res = res + P # 追加 i = i - 1 resを返す

上記の反復法はいずれもタイミング解析に対して脆弱であることに注意してください。代替手法については、下記のモンゴメリーラダーを参照してください。

• 再帰アルゴリズム：

アルゴリズムf(P, d)は 、 d = 0の場合は0を返す（計算完了） 、 d = 1 の場合は P を返す、 d mod 2 = 1の場合は point_add(P, f(P, d - 1)) を 返す（d が奇数の場合は加算）、d が偶数の 場合は f(point_double(P), d / 2)を返す（2倍）

ここで、 fは乗算関数、Pは乗算する座標、dは座標を自身に加算する回数です。例: 100P は2(2[P + 2(2[2(P + 2P)])])と書くことができ、したがって 6 回のポイント 2 倍演算と 2 回のポイント 加算演算が必要です。100Pはf(P, 100)と等しくなります。

このアルゴリズムでは、完全な点乗算を計算するために、log ₂ ( d ) 回点の倍増と加算を繰り返す必要があります。このアルゴリズムには、ウィンドウ、スライディングウィンドウ、NAF、NAF-w、ベクトルチェーン、モンゴメリーラダーなど、多くのバリエーションがあります。

このアルゴリズムのウィンドウ版では、^{[ 2 ]}ウィンドウサイズwを選択し、すべての${\displaystyle 2^{w}}$値${\displaystyle dP}$のために${\displaystyle d=0,1,2,\dots ,2^{w}-1}$アルゴリズムは現在、表現を使用しています。${\displaystyle d=d_{0}+2^{w}d_{1}+2^{2w}d_{2}+\cdots +2^{mw}d_{m}}$そして

Q ← 0 iをm から 0 まで繰り返す Q ← point_double_repeat(Q, w) if d i > 0 then Q ← point_add(Q, d i P) # 事前に計算された d i P の値を使用return Q

このアルゴリズムは、倍増加算方式と同じ複雑さを持ちながら、点加算の回数が少ないという利点があります（実際には、倍増よりも時間がかかります）。通常、wの値はかなり小さく選択されるため、事前計算段階はアルゴリズムのごく簡単な部分となります。NIST 推奨曲線の場合、${\displaystyle w=4}$が通常は最良の選択肢です。n ビット数の全体の複雑さは次のように測定されます。${\displaystyle n+1}$ポイントダブルと${\displaystyle 2^{w}-2+{\tfrac {n}{w}}}$ポイント加算。

スライディングウィンドウ版では、ポイントの追加とポイントの重複のトレードオフを検討します。ウィンドウ版と同様のテーブルを計算しますが、ポイントのみを計算します。${\displaystyle dP}$のために${\displaystyle d=2^{w-1},2^{w-1}+1,\dots ,2^{w}-1}$実際には、ウィンドウの最上位ビットがセットされている値のみを計算しています。アルゴリズムは、元の倍加算表現を使用します。${\displaystyle d=d_{0}+2d_{1}+2^{2}d_{2}+\cdots +2^{m}d_{m}}$。

Q ← 0 を m から 0まで繰り返す。もしd i = 0ならば Q ← point_double(Q) それ以外の場合は、t ← d (d iを含む) から j (最大 w − 1) ビットを追加で抽出する i ← i − j j < wの場合 t を使用して倍加算を実行します Q を返す Q ← point_double_repeat(Q, w) Q ← point_add(Q, tP) Qを返す

このアルゴリズムの利点は、事前計算段階の複雑さが通常のウィンドウ法の約半分である一方で、点の追加速度が遅くなる代わりに点の倍増が行われる点数が増えることです。事実上、このアプローチよりもウィンドウ法を使用する理由はほとんどありませんが、前者は定数時間で実装できます。このアルゴリズムは、${\displaystyle w-1+n}$ポイントダブルと最大${\displaystyle 2^{w-1}-1+{\tfrac {n}{w}}}$ポイント加算。

非隣接形式では、点の減算が点の加算と同じくらい簡単であるという事実を利用して、スライディングウィンドウ方式と比較して（どちらの場合も）実行回数を減らすことを目指します。被乗数のNAF${\displaystyle d}$まず、以下のアルゴリズムで計算する必要があります。

i ← 0 while (d > 0) do if (d mod 2) = 1 then d i ← d mod 2 w d ← d − d i else d i = 0 d ← d/2 i ← i + 1 return (d i−1 , d i-2 , ..., d 0 )

ここで、符号付き剰余関数modsは次のように定義されます。

(d mod 2 w ) > = 2 w−1ならば(d mod 2 w ) − 2 wを返す。そうでなければd mod 2 wを返す。

これにより、乗算を実行するために必要なNAFが生成されます。このアルゴリズムでは、ポイントの事前計算が必要です。${\displaystyle \lbrace 1,3,5,\dots ,2^{w-1}-1\rbrace P}$そしてそのネガティブな面では、${\displaystyle P}$は乗算される点です。典型的なワイエルシュトラス曲線では、${\displaystyle P=\lbrace x,y\rbrace }$それから${\displaystyle -P=\lbrace x,-y\rbrace }$つまり、本質的に負の値は計算コストが低いということです。次に、次のアルゴリズムで乗算を計算します。${\displaystyle dP}$:

Q ← 0 j ← i − 1 から 0 まで繰り返す Q ← point_double(Q) if (d j != 0) Q ← point_add(Q, d j P) return Q

wNAFは平均して密度が${\displaystyle {\tfrac {1}{w+1}}}$ポイントの追加（符号なしウィンドウよりわずかに優れている）。1 ポイントの倍増が必要で、${\displaystyle 2^{w-2}-1}$事前計算のためのポイント追加。次にアルゴリズムは${\displaystyle n}$ポイントの倍増と${\displaystyle {\tfrac {n}{w+1}}}$残りの乗算については、ポイントを加算します。

NAF の特性の 1 つは、すべての非ゼロ要素が保証されることです。${\displaystyle d_{i}}$少なくとも${\displaystyle w-1}$追加のゼロ。これは、アルゴリズムが下位のゼロをクリアするためです。${\displaystyle w}$断片${\displaystyle d}$mods関数の出力から減算するたびに、この観察はいくつかの目的に使用できます。すべての非ゼロ要素の後には、追加のゼロが暗黙的に存在するとみなすことができ、保存する必要はありません。次に、2による複数の連続除算は、1回の除算に置き換えることができます。${\displaystyle 2^{w}}$ゼロ以外のすべての後に${\displaystyle d_{i}}$要素をゼロごとに2で割る。

OpenSSLに対するFLUSH+RELOADサイドチャネル攻撃を適用することで、わずか200回の署名に対してキャッシュタイミングを実行するだけで、完全な秘密鍵が明らかになることが示されています。^{[ 3 ]}

モンゴメリーラダー^{[ 4 ]}方式では、ポイント乗算を固定回数の演算で計算します。これは、タイミング、消費電力、または分岐の測定値がサイドチャネル攻撃を行う攻撃者に晒される場合に有効です。このアルゴリズムは、倍加算と同じ表現を使用します。

R 0 ← 0 R 1 ← P for i from m downto 0 do if d i = 0 then R 1 ← point_add(R 0 , R 1 ) R 0 ← point_double(R 0 ) それ以外の場合は R 0 ← point_add(R 0 , R 1 ) R 1 ← point_double(R 1 ) // 正しさを維持するための不変プロパティ assert R 1 == point_add(R 0 , P) return R 0

このアルゴリズムは、乗数dの値に関係なく、同じ数の点加算と倍算を計算する点加算方式と実質的に同じ速度です。つまり、このレベルでは、アルゴリズムは分岐や電力消費を通じて情報を漏洩することはありません。

しかし、OpenSSLに対するFLUSH+RELOADサイドチャネル攻撃を適用することで、非常に低いコストで1つの署名に対してキャッシュタイミングを実行するだけで完全な秘密鍵が明らかになることが示されています。^{[ 5 ]}

ルーカス連鎖を用いると、モンゴメリーラダーに比べて倍加と加算のシーケンスが最適化され、より大きな倍数（より長い連鎖）で高速化されます。この方法は「PRAC」と呼ばれています。PRACはモンゴメリーによっても公開されており、「参照実装」はGMP-ECMです。^{[ 6 ]} DJ バーンスタインは2017年にこのようなスキームをいくつか挙げています。^{[ 7 ] : § 4.8.2}

暗号化実装のセキュリティは、実装のデータ依存タイミング特性を利用するいわゆるタイミング攻撃の脅威に直面する可能性が 高い。暗号化実装を実行するマシンは、異なる入力を処理するのに可変の時間を消費するため、タイミングは暗号化キーに基づいて変化する。この問題を解決するために、暗号化アルゴリズムは、実装からデータ依存の可変タイミング特性を取り除く方法で実装され、いわゆる定数時間実装となる。ソフトウェア実装は、^{[ 8 ]}で述べられているように、次の意味で定数時間であると考えられる。 「すべての入力依存分岐、すべての入力依存配列インデックス、および入力依存タイミングを持つその他の命令を回避する。」GitHub ページ^{[ 9 ]}には、暗号化操作の実装、より一般的には秘密値または機密値を含む操作のコーディング規則がリストされている。

モンゴメリーラダーは${\displaystyle x}$楕円曲線点の乗算のための座標のみのアルゴリズムであり、モンゴメリー曲線として知られる特定の曲線セット上の倍加ルールと加算ルールに基づいています。このアルゴリズムには条件分岐があり、その条件は秘密ビットに依存します。そのため、ラダーの単純な実装は定数時間ではなく、秘密ビットが漏洩する可能性があります。この問題は文献^{[ 10 ] [ 11 ]}で取り上げられており 、いくつかの定数時間実装が知られています。定数時間のモンゴメリーラダーアルゴリズムは、CSwapとLadder-Stepの2つの関数を使用する以下のとおりです。アルゴリズムの戻り値Z ₂ ^p-2は、フェルマーの小定理を使用して計算されたZ ₂ ⁻¹の値です。

アルゴリズムMontgomery-Ladder(x P , n)の入力: An${\displaystyle l}$-ビットスカラー${\displaystyle n}$そして${\displaystyle x}$-座標${\displaystyle x_{P}}$ある点の${\displaystyle P}$. 出力:${\displaystyle x}$-座標${\displaystyle nP}$、${\displaystyle n}$-倍のスカラー倍${\displaystyle P}$。 X 1 ← x P ; X 2 ← 1; Z 2 ← 0; X 3 ← x P ; Z 3 ← 1 前のビット ← 0 のために${\displaystyle i}$から${\displaystyle l-1}$downto 0 do bit ← インデックスのビット値${\displaystyle i}$の${\displaystyle n}$ b ← ビット${\displaystyle \oplus }$前のビット 前のビット ← ビット （${\displaystyle \langle }$X 2、Z 2${\displaystyle \rangle }$、${\displaystyle \langle }$X 3、Z 3${\displaystyle \rangle }$) ← CSwap(${\displaystyle \langle }$X 2、Z 2${\displaystyle \rangle }$、${\displaystyle \langle }$X 3、Z 3${\displaystyle \rangle }$、b) （${\displaystyle \langle }$X 2、Z 2${\displaystyle \rangle }$、${\displaystyle \langle }$X 3、Z 3${\displaystyle \rangle }$) ← はしごステップ(${\displaystyle \langle }$X 2、Z 2${\displaystyle \rangle }$、${\displaystyle \langle }$X 3、Z 3${\displaystyle \rangle }$,X 1 )はX 2 Z 2 p-2を返します

ラダー内で使用されるラダーステップ関数（下記参照）はアルゴリズムの中核であり、差分加算と倍算演算を組み合わせた形式です。フィールド定数 a _{24は、a 24} =と定義されます。${\displaystyle (A+2)/4}$、 どこ${\displaystyle A}$これは、基礎となるモンゴメリー曲線のパラメータです。

関数ラダーステップ(${\displaystyle \langle }$X 2、Z 2${\displaystyle \rangle }$、${\displaystyle \langle }$X 3、Z 3${\displaystyle \rangle }$、X 1 ) T 1 ← X 2 + Z 2 T 2 ← X 2 - Z 2 T 3 ← X 3 + Z 3 T 4 ← X 3 - Z 3 T 5 ← T 1 2 T 6 ← T 2 2 T 2 ← T 2 · T 3 T 1 ← T 1 · T 4 T 1 ← T 1 + T 2 T 2 ← T 1 - T 2 X 3 ← T 1 2 T 2 ← T 2 2 Z 3 ← T 2 · X 1 X 2 ← T 5 · T 6 T 5 ← T 5 - T 6 T 1 ← a 24 · T 5 T 6 ← T 6 + T 1 Z 2 ← T 5 · T 6 return (${\displaystyle \langle }$X 2、Z 2${\displaystyle \rangle }$、${\displaystyle \langle }$X 3、Z 3${\displaystyle \rangle }$）

CSwap関数は条件分岐を管理し、定数時間実装の要件に従ってラダーを実行するのに役立ちます。この関数はフィールド要素のペアを交換します。${\displaystyle \langle }$X ₂、Z ₂${\displaystyle \rangle }$そして${\displaystyle \langle }$X ₃、Z ₃${\displaystyle \rangle }$のみ${\displaystyle b}$= 1 であり、これは秘密ビットに関する情報を漏らすことなく行われます。CSwap を実装するためのさまざまな方法が文献で提案されています。^{[ 10 ] [ 11 ]}モンゴメリーラダーの定数時間要件を管理するためのより低コストなオプションは、関数 CSelect によって形式化された条件付き選択です。この関数はさまざまな最適化で使用されており、^{[ 12 ]で正式に議論されています。}

128 ビット セキュリティ レベルの標準 Montgomery 曲線Curve25519 の登場以来、さまざまなアーキテクチャで ECDH を計算するためのさまざまなソフトウェア実装があり、可能な限り最高のパフォーマンスを実現するために、暗号開発者は基盤となるアーキテクチャのアセンブリ言語を使用して実装を記述するようになりました。 ^{[ 13 ]}の研究では、AMD64 アーキテクチャを対象とした 64 ビット アセンブリ実装がいくつか提供されました。実装は、高速アセンブリ言語暗号プログラムを生成できるqhasm ^{[ 14 ]}と呼ばれるツールを使用して開発されました。これらのラダーの実装では、関数 CSwap が使用されました。その後、手書きのアセンブリ プログラムを使用してラダー実装を最適化する試みがいくつか行われ、その中で CSelect の概念が最初に^{[ 15 ]}で使用され、次に^{[ 16 ]}で使用されました。シーケンシャル命令の使用に加えて、さまざまな研究でベクトル命令もラダー計算の最適化に使用されています。^{[ 17 ] [ 18 ] [ 19 ] [ 20 ]} AMD64 に加えて、ARM などの他のアーキテクチャでも効率的な実装を実現しようとする試みが行われてきました。^{[ 21 ]}および^{[ 22 ]}の研究では、 ARM アーキテクチャを対象とした効率的な実装が提供されています。ライブラリ lib25519 ^{[ 23 ]}および^{[ 24 ]}は、 Curve25519用のモンゴメリーラダーの効率的な実装を含む最先端のライブラリです。ただし、これらのライブラリには他の暗号プリミティブの実装も含まれています。

Curve25519以外にも、さまざまなセキュリティ レベルで他の曲線上でラダーを計算する試みがいくつか行われてきました。224 ビット セキュリティ レベルで標準曲線Curve448上でのラダーの効率的な実装も文献で研究されています。^{[ 15 ] [ 18 ] [ 20 ]} 200 ビット強のセキュリティを提供する Curve41417 という曲線が提案されました^{[ 25 ]。}この曲線では、関連する ECC ソフトウェアに必要なフィールド乗算を実装するために、カラツバ戦略の変種が使用されています。Curve25519とCurve448に匹敵する Montgomery 曲線を探すために研究が行われ、対応するラダーの効率的な逐次実装^{[ 16 ]}とベクトル化実装[ ^{20 ]とともに}、いくつかの曲線が提案されました。256 ビット セキュリティ レベルでは、3 つの異なる Montgomery 曲線を通じてラダーの効率的な実装も検討されています。^{[ 26 ]}