SafegcdによるECDSA署名検証の高速化

2019年に発表された拡張ユークリッド互除法の新しいアルゴリズムを使った、ECDSA署名の生成/検証の高速化について↓

medium.com

libsecp256k1にもマージされたので、どういった内容か見てみる。

ユークリッド互除法

まず基本的なユークリッド互除法について。ユークリッド互除法は、２つの自然数a, bについて、その最大公約数を求める方法の１つ*1。これは、aをbで割った商を ${q_1}$ 、余りを ${r_1}$ とした場合、

${a ÷ b = q_1 ... r_1}$

さらに、

${b ÷ r_1 = q_2 ... r_2}$

とし、これを余り ${r_n}$ が0になるまで続けた場合、 ${r_{n-1}}$ が最大公約数になるというアルゴリズム。よくgcd(a, b)と表記される。

拡張ユークリッド互除法

そして、拡張ユークリッド互除法は、２つの自然数a, bについて、ベズーの等式とも呼ばれる ${ax + by = gcd(a, b)}$ を満たす整数解(x, y)を求める際に使われるアルゴリズム。

この一次不定方程式は、↑のユークリッド互除法から、a ÷ bの商を ${q}$ 、余りを ${r}$ とすると、 ${a = qb + r}$ となるため、

${(qb + r)x + by = gcd(a, b)}$

とすることができ、さらに

${b(q + y) + r x = gcd(a, b)}$

に変形できる。これはgcd(a, b)をより小さい値のgcd(b, r)にしている。そしてこれを再帰的に繰り返す↓

${x_1 = q + y, y_1 = y }$ として、 ${bx_1 + ry_1 = gcd(a, b)}$ に対して、 ${b = q_1r + r_1}$ から

${(q_1r + r_1)x_1 + ry_1 = r(q_1x_1 + y_1) + r_1x = gcd(a, b)}$

と、計算の過程で余りの値 ${r_n}$ が0になるまで繰り返す。すると、最後の式には ${x_n = 0, y_n = 1}$ が成立する。この2つの値が分かると、再起を逆に辿っていくと、 ${x_{n - 1}, y_{n - 1}}$ が順次計算でき、最終的に(x, y)の解を求めることができる。

楕円曲線暗号と拡張ユークリッド互除法

BitcoinやEthereumなどの暗号通貨で使用されている楕円曲線暗号において、鍵の導出やデジタル署名の生成でコアとなる計算が、逆元（モジュラ逆数）の計算になる。逆元は、整数aと法をnとした場合に

${ax ≡ 1(\mod n)}$

を満たすようなxを指す。つまり、 ${x(\mod n) ≡ a ^{-1}}$ となる値。

↑の式は、変形すると

${ ax - 1 = qn}$

とすることができ（qは適当な整数）、結果

${ax - qn = 1}$

と変形でき、↑の拡張ユークリッド互除法の不定方程式に似ているのがわかる。また、計算にあたって実際にaとnは既知の値である。つまり拡張ユークリッド互除法を使えば逆元の計算が可能で、それも高速に。

libsecp256k1の実装

楕円曲線ライブラリlibsecp256k1では、タイミング攻撃により秘密情報のヒントが漏れないよう定数時間の計算アルゴリズムを採用している（タイミング攻撃というのは計算の処理時間の差を分析することで、鍵の情報などを推測するサイドチャネル攻撃の一種）。このような攻撃により、秘密鍵に関する情報が漏れないように、入力されたデータに関係なく一定の時間で処理を行うアルゴリズムを定数時間アルゴリズムと言う。

拡張ユークリッド互除法を使った逆元の計算は高速だが、↑のように値によって計算回数が変わるため定数時間アルゴリズムにするのが難しいという課題があり、libsecp256k1ではBitcoinで使用する際は、それよりも遅いexponentiation ladderと呼ばれるアルゴリズムが使用されてきた。

Safegcd

しかし2019年に、定数時間で高速なユークリッド互除法および逆元の計算を行うSafegcdと呼ばれる新しいユークリッド互助法のアルゴリズムが発表された↓

Fast constant-time gcd and modular inversion

Safegcdでは、divstepと呼ばれる一定回数繰り返すと入力のgcdやモジュラ逆数が明らかになるアルゴリズムを使用している。libsecp256k1のSafegcdの実装ガイドから、この計算方法をハイレベルに記述したのが↓の、fを奇数の整数、gを任意の整数とした場合の最大公約数を求める計算（ruby版）

def gcd(f, g)
  delta = 1
  until g == 0
    if delta > 0 && g.odd?
      delta, f, g = 1 - delta, g, (g - f) >> 1
    elsif g.odd?
      delta, f, g = 1 + delta, f, (g + f) >> 1
    else
      delta, f, g = 1 + delta, f, (g    ) >> 1
    end
  end
  f.abs
end

再帰ではなく単純なループになっており、このループの各反復をdivstepと呼んでいる。各反復で行っているのは、

gが奇数なら、(f, g)を(g, g - f)もしくは、(g, g + f)に置き換えて、gを偶数にする。
gが偶数なら(f, g)を(f, g/2)に置き換える。

というもの。

このコードはg == 0になると計算が終わるが、g == 0になってもfの値はそれ以上変更されなくなるので、その後反復を続けても出力値は変わらない。そのため定数時間にする場合、終了条件をuntil g == 0ではなく、一定値にすれば良い。このアルゴリズムの場合、反復回数の上限＝実行時間になる。

ただ、必要な反復計算の回数（上限）を決定する必要がある。libsecp256k1の場合、入力の数値は256 bitなので、その範囲の数値の拡張ユークリッド互助法の計算をするのに十分な反復回数はいくつだろう？その問に対して、Pieter WuilleがSafegcdの必要な反復回数の境界を算出する方法を提案し↓

github.com

さらに、この方法を使ってSafegcdの変形について調査すると、最大590回で反復を終えられる変形が発見された。これを適用すると、既存のlibsecp256k1の実装に比べて

ECDSAの署名生成速度が25%向上
ECDSAの署名検証速度が15%向上

すると。

そして重要なポイントとして、もしこの上限値以内に計算が終わらないケースが発生すると、誤った逆元の計算が行われてしまう。そこで、この境界の算出方法を正しさを検証するためにCoqを使った定理証明が行われている↓

Coq proof of correctness of divstep and hddivsteps for 256-bit inputs. by roconnor-blockstream · Pull Request #7 · sipa/safegcd-bounds · GitHub

*1:他にも素因数分解などでも解けるが、a, bの値が大きくなるとユークリッド互助法で求めた方が高速

Develop with pleasure!

福岡でCloudとかBlockchainとか。