楕円曲線の点乗算

楕円曲線スカラー乗算は、楕円曲線上の点をそれ自体に繰り返し加算する演算です。楕円曲線暗号(ECC) で使用されます。文献では、この演算は楕円曲線のヘッセ形式で記述されるスカラー乗算として示されています。この演算は楕円曲線点乗算とも呼ばれますが、これは 2 点間の乗算であるという誤った印象を与える可能性があります。

有限体における何らかの方程式によって定義された曲線E （ E : y ² = x ³ + ax + bなど）が与えられた場合、点乗算はその曲線に沿った点の繰り返し加算として定義されます。あるスカラー（整数）nと曲線E上にある点P = ( x , y )に対して、 nP = P + P + P + … + Pと表します。このタイプの曲線はワイエルシュトラス曲線として知られています。

現代の ECC のセキュリティは、nが大きい場合にQとPの既知の値からQ = nPからn を決定することの難しさ (他の暗号化システムとの類似性から楕円曲線の離散対数問題として知られています) に依存しています。これは、楕円曲線上の 2 つの点を追加すると (または 1 つの点をその点自体に追加すると)、楕円曲線上の 3 番目の点が生成され、その位置は最初の 2 つの位置とはすぐには明らかな関係がなく、これを何度も繰り返すと、基本的にどこにでもある可能性のある点nPが生成されるためです。直感的には、これは、円上に点P がある場合、その角度に 42.57 度を追加してもPから「それほど遠くない」点になる可能性がありますが、42.57 度を 1000 倍または 1001 倍追加すると、元の角度を見つけるためにもう少し複雑な計算が必要な点が生成されることと似ています。このプロセスを逆にして、つまりQ=nPおよびP が与えられ、n を決定するには、すべての可能なnを試してみるしかありませんが、 nが大きい場合、この作業は計算上不可能です。

楕円曲線の点に対して一般的に定義されている演算は、加算、倍増、否定の 3 つです。

無限大点⁠ ⁠は、楕円曲線演算の${\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)をとって、上記のように計算されます。^[2]

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

ここで、a は上記の曲線Eの定義方程式から得られます。

ポイント乗算を計算する最も簡単な方法は、加算を繰り返すことです。ただし、乗算を計算するより効率的な方法があります。

最も単純な方法は、倍数化して加算する方法^{[3]で、モジュラー指数の}平方乗算に似ています。アルゴリズムは次のように機能します。

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 まで)
   res = # 無限大を指す${\displaystyle {\begin{aligned}{\mathcal {O}}\end{aligned}}}$
   let temp = P # 2倍になったP値を追跡する
   ビット単位のビットの場合:
       ビット == 1 の場合:            
           res = res + temp # ポイント追加
       temp = temp + temp # 倍
   戻り値

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

   let bits = bit_representation(s) # s を表すビットのベクトル (LSB から MSB まで)
   i = 長さ(ビット) - 2 とします。
   res = Pとする
   while (i >= 0): # 2番目のMSBからLSBまで移動
       res = res + res # 倍精度
       ビット[i] == 1の場合:            
           res = res + P # 追加
       私 = 私 - 1
   戻り値

上記の反復法は両方ともタイミング解析に対して脆弱であることに注意してください。代替アプローチについては、以下の Montgomery Ladder を参照してください。

• 再帰アルゴリズム:

  f(P, d)は
     d = 0 の場合
         0を返す # 計算完了
     そうでなければd = 1の場合
         Pを返す
     そうでなければ、d mod 2 = 1 ならば
         return point_add(P, f(P, d - 1)) # dが奇数の場合の加算
     それ以外
         return f(point_double(P), d / 2) # dが偶数の場合は2倍にする

ここで、fは乗算する関数、Pは乗算する座標、d は座標を自身に加算する回数です。例: 100P は2(2[P + 2(2[2(P + 2P)])])と表記され、6 回の点の倍精度演算と 2 回の点の加算演算が必要です。100Pはf(P, 100)に等しくなります。

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

このアルゴリズムのウィンドウバージョン^[3]では、ウィンドウサイズ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 ← ポイントダブルリピート(Q, w)
      d i > 0 ならば
          Q ← point_add(Q, d i P) # d i Pの事前計算された値を使用する
  Qを返す

このアルゴリズムは、倍増と加算のアプローチと同じ複雑さを持ちますが、ポイント加算 (実際には倍増よりも低速) が少なくなるという利点があります。通常、wの値は、事前計算段階がアルゴリズムの些細なコンポーネントになるように、かなり小さく選択されます。NIST 推奨曲線の場合、通常は が最適な選択です。nビット数の全体的な複雑さは、ポイント倍増とポイント加算 として測定されます。${\displaystyle w=4}$${\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
  i が m から 0 までの場合
      d i = 0の場合
          Q ← ポイントダブル(Q)
      それ以外t ← d（d iを含む）
          からj（w − 1まで）の追加ビットを抽出する
          私 ← 私 − j
          j < w ならば
              tを使用して倍増加算を実行する
              Qを返す
          それ以外
              Q ← ポイントダブルリピート(Q, w)
              Q ← ポイント追加(Q, tP)
  Qを返す

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

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

   私 ← 0
   (d > 0) の場合
       (d mod 2) = 1の場合
           d i ← d を 2 で割った値w 
           d ← d − d i
       それ以外
           d i = 0
       d ← d/2
       私 ← 私 + 1
   (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 ← ポイントダブル(Q)
       (d j  != 0)の場合
           Q ← point_add(Q, d j P)
   Qを返す

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

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

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

モンゴメリラダー^{[5]アプローチは、}固定された回数の演算で点乗算を計算します。これは、タイミング、消費電力、または分岐測定がサイドチャネル攻撃を実行する攻撃者にさらされている場合に役立ちます。アルゴリズムは、倍精度加算と同じ表現を使用します。

  R 0 ← 0
  R 1 ← P
  i が m から 0 までの場合
      d i = 0の場合
          R 1 ← point_add(R 0 , R 1 )
          R 0 ← ポイントダブル(R 0 )
      それ以外
          R 0 ← point_add(R 0 , R 1 )
          R 1 ← ポイントダブル(R 1 )

      // 正確性を維持するための不変プロパティ
      R 1 == point_add(R 0 , P)をアサートする
  R 0を返す

このアルゴリズムは、被乗数dの値に関係なく、同じ数のポイント加算と倍増を計算する点を除けば、実質的に倍増と加算のアプローチと同じ速度です。つまり、このレベルでは、アルゴリズムは分岐や電力消費を通じて情報を漏らしません。

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

モンゴメリーラダーのRustコード: ^[7]

/// 定数演算ポイントの乗算。
/// 注: メモリセーフではありません。
/// * `s`: 乗算するスカラー値
/// * 乗算は P₀ + P₁ + ... Pₛ と定義されます
fn  sec_mul ( & mut self , s : big ) -> E521 { let mut r0 = get_e521_id_point (); let mut r1 = self . clone (); for i in ( 0 ..= s . validity_bits ()). rev () { if s . get_bit ( i ) { r0 = r0 . add ( & r1 ); r1 = r1 . add ( & r1 . clone ()); } else { r1 = r0 . add ( & r1 ); r0 = r0 . add ( & r0 . clone ()); } } r0 // r0 = P * s }   
        
        
         
          
              
              
          
              
              
        
    
     

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

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

  アルゴリズムMontgomery-Ladder(x P ,n)
  入力:ビットのスカラーと点の座標。
  出力:の座標、のスカラー倍数。X     
  1 ← x P ; X 2 ← 1; Z 2 ← 0; X 3 ← x P ; Z 3 ← 1${\displaystyle l}$${\displaystyle n}$${\displaystyle x}$${\displaystyle x_{P}}$${\displaystyle P}$${\displaystyle x}$${\displaystyle nP}$${\displaystyle n}$${\displaystyle P}$

  前へ ← 0
  から0まで${\displaystyle i}$${\displaystyle l-1}$bit ← インデックスの
      ビット値
      b ← ビット前ビット${\displaystyle i}$${\displaystyle n}$${\displaystyle \oplus }$
      前ビット ← ビット
      ( X 2、Z 2、X 3、Z 3 ) ← CSwap( X 2、Z 2、X 3、Z 3、b)${\displaystyle \langle }$${\displaystyle \rangle }$${\displaystyle \langle }$${\displaystyle \rangle }$${\displaystyle \langle }$${\displaystyle \rangle }$${\displaystyle \langle }$${\displaystyle \rangle }$
      ( X 2 ,Z 2 , X 3 ,Z 3 ) ← ラダーステップ( X 2 ,Z 2 , X 3 ,Z 3 ,X 1 )戻り値X 2 Z 2 p-2${\displaystyle \langle }$${\displaystyle \rangle }$${\displaystyle \langle }$${\displaystyle \rangle }$${\displaystyle \langle }$${\displaystyle \rangle }$${\displaystyle \langle }$${\displaystyle \rangle }$
       
  

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

  関数ラダーステップ( X 2 ,Z 2 , X 3 ,Z 3 ,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 ( X 2 ,Z 2 , X 3 ,Z 3）
${\displaystyle \langle }$${\displaystyle \rangle }$${\displaystyle \langle }$${\displaystyle \rangle }$


  ${\displaystyle \langle }$${\displaystyle \rangle }$${\displaystyle \langle }$${\displaystyle \rangle }$

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

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

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