楕円曲線暗号のための数学4（ウィンドウ法）

初めに

楕円曲線暗号のための数学2（バイナリ法によるスカラー倍算）では楕円曲線の点のスカラー倍算をバイナリ法を用いた方法を紹介しました。今回はより高速に計算できるウィンドウ法を紹介します。

記号の復習

楕円曲線の点からなる素数位数 $r$ の加法群を $G$ とします。
点 $P \in G$ の2倍算を $\text{dbl}(P)$, $P, Q \in G$ の和を $\text{add}(P, Q)$ とします。

バイナリ法の復習

$n>0$ を整数として、Ec を楕円曲線の点を表すクラスとして Python で記述すると次のようになりました。

def mul(P : Ec, n : int):
  bs = bin(n)[2:] # nを2進数展開
  Q = Ec() # zero
  for b in bs: # 上位ビットから順次計算
    Q = dbl(Q)
    if b == '1':
      Q = add(Q, P)
  return Q

$n$ を2進数展開して、その上位ビットから $Q$ を2倍しながら 1 が立っているときに $P$ を足していくのでした。

ウィンドウ法

ウィンドウ法は $n$ を1ビットずつ見ていくのではなく、$w$ ビットずつ区切って見ていくやり方です。
たとえば $w=3$ のとき、$n$ を2進数展開して $w$ ビットずつ区切ると0以上7以下の値になります。
$0, P, 2 P, \dots, 7 P$ を事前に計算しておき、$Q$ を2倍しながら途中でその値を足せばよいのです。

ウィンドウ法

def mulWin(P : Ec, n : int, w : int):
  l = n.bit_length()
  mask = (1<<w) - 1
  Q = Ec() # zero
  T = [Q]
  # T = [0, P, 2 P, 3 P, ..., (2^w-1) P]
  for i in range(1, 2**w):
    T.append(add(T[i-1], P))
  for i in reversed(range(0, l, w)):
    for i in range(w):
      Q = dbl(Q)
    t = (l >> w) & mask
    Q = add(Q, T[t])
  return Q

$n$ が $l$ ビット整数のとき、バイナリ法のコストは $l(D+A/2)$ でした（$D$ が dbl の回数で $A$ が add の回数）。
ウィンドウ法は $w$ ビットのテーブルを作るのに $2^w-1$ 回の add, ループ内は dbl の回数は変わらず、add の回数は $1/w$ になります。
したがって、全体では$(2^w-1)A+l(D+A/w)=l D + (2^w+l/w-1)A$.
$w$ を大きくするとテーブルを作成するコストが指数的に大きくなります。$w$ を大きくしすぎると、テーブル作成コストがループ内の add のコスト削減を上回ってしまいます。
そこで、$l=128, 256, 384$ のとき add の回数が最小になる $w$ を調べると、表のようになりました。

コストが最小となる $w$ とそのときの $A$ のコスト

l	128	256	384
w	4	4	5
ウィンドウ法	47	79	108
バイナリ法	64	128	192

$w$ をうまく取ると、ウィンドウの方がバイナリ法よりも効率がよいことが分かります。

テーブル作成コストの半減

前節のように $w$ をあまり大きくできません。そこで少しでもテーブル作成のコストを下げたいものです。

ループ内の操作を再確認しましょう。

    for i in range(w):
      Q = dbl(Q)
    t = (l >> w) & mask
    Q = add(Q, T[t])

$Q$ を $w$ 回 dbl してから $Q$ に $T[t]=t P$ を足しています。

$$Q' ← 2^w Q + t P$$

もし $t$ が偶数なら

$$Q' ← 2(2^{w-1} Q + (t/2) P)$$

と変形できます。「$w$ 回 dbl してから $t P$ を足す」操作は、「$w-1$ 回 dbl してから $(t/2) P$ を足し、そして dbl する」操作と同じです。
$t/2$ が偶数なら更に2で括れます。つまり、$t = 2^a b$（$b$ は奇数）の形に書けば $Q' ←2^a(2^{w-a} Q + b P)$ です。
このように dbl の操作と add の操作の順序を交換することで $t$ は奇数として処理できます。
この変換をしてもループ内の dbl と add の回数は変わりません。ただ、テーブルのインデックスが奇数のみでよくなったので、テーブル作成のコストが $2^w$ から $2^{w-1}$ と半減します。

演算コスト : $l D + (2^{w-1}+l/w-1)A$.

奇数インデックスのみのテーブル作成

T = [P]
P2 = dbl(P)
# T = [P, 3 P, 5 P, ..., (2^w-1) P]
for i in range(1, 2**(w-1)):
  T.append(add(T[i-1], P2))

コストが最小となる $w$ とそのときの $A$ のコスト
ウィンドウ法の括弧内は最小となる $w$ の値を示す

l	128	256	384
バイナリ法	64	128	192
ウィンドウ法	47 (4)	79 (4)	108 (5)
修正ウィンドウ法	39 (4)	67 (5)	92 (5)

バイナリ法に比べて $A$ のコストが50~60%まで下がりました。