楕円曲線のスカラー倍算アルゴリズム Part 2

前回の投稿では、楕円曲線のスカラー倍算のアルゴリズムとしてバイナリ法やWindow法のアルゴリズムについて、また射影座標を用いた高速化手法について解説した↓

techmedia-think.hatenablog.com

今回は、もともとスカラー倍算の高速化について調査するきっかけとなったGLV法を用いた方法について。

GLVという名前は、発明者のRobert Gallant、Robert Lambert、Scott A. Vanstoneの３名の名前から来ており、自己準同型写像を持つ楕円曲線のスカラー倍算を高速化する。このアルゴリズムは特許が取られていたけど、それが2020年9月に有効期限切れになったため、Bitcoin Coreでもデフォルトで有効化された↓

github.com

検証自体は、故Hal Finneyにより2011年に行われ署名検証が約25%高速化すると報告されている。また、Pieter Wuille によりlibsecp256k1にも実装されたが、↑の特許のためデフォルトで無効化されていた。

GLV法

具体的に、GLV法ではどうやってスカラー倍算を高速化するのか見ていこう。この方法の解説は、Hal Finneyのbitcointalkへの投稿が分かりやすい（Hal Finneyが参考にしたのはScott A. Vanstoneが執筆したこの本）。

ここではスカラー値をk、乗算する点をQとする。つまりk*Qを計算する。

自己準同型の性質

secp256k1曲線は、楕円曲線上の任意の点Q（x, y）について、以下を満たす自己準同型の性質を持つらしい。

${\lambda Q = (beta * x \mod p, y)}$

ここで、pは楕円曲線のパラメータの１つでベースとなる有限体の素数、 ${\lambda, beta}$ は、それぞれ

${\lambda = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72}$
${beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee}$

実際に↑の性質があるかは↓のように検証できる。

require 'ecdsa'
require 'bitcoin'

lambda = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72
beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee

# 任意の点Qを作成
key = Bitcoin::Key.generate
Q = key.to_point

# 検証用にλQを計算
lambda_q = Q.multiply_by_scalar(lambda)

# beta * x mod p を計算
field = ECDSA::Group::Secp256k1.field
x = field.mod(beta * Q.x)

# λQが(beta * x \mod p, y)と同じであるかチェック
puts lambda_q.x == x && lambda_q.y == Q.y

結果、任意の点に対してこの性質が成立してるのが確認できる。

高速化

続いて、↑の性質を利用して、スカラー値kをλを使って以下を満たすnの約半分のビット長の ${k_1, k_2}$ に分割する（nは曲線の位数）。

${k = k_1 + k_2 * \lambda \mod n}$

つまりk*Qは、

${kQ = (k_1 + k_2 * \lambda)Q = k_1Q + k_2 * \lambda Q }$

となる。ここで ${Q' = \lambda Q}$ を先に計算しておく、つまり ${kQ = k_1Q + k_2Q'}$ 。このQ'の計算は ${\lambda Q}$ を単純にスカラー倍算するのではなく、↑の特性を利用して ${Q(x, y)}$ に対して ${(beta * x \mod p, y)}$ を計算することで、つまりmod pの乗算を１回するだけで、効率的に計算することができる。

${k_1, k_2}$ の分割方法

kをそれぞれ半分のビット長の ${k_1, k_2}$ の分解するアルゴリズムは↑の書籍の、Algorithm 3.74 Balanced length-two representation of a multiplieで紹介されている。Hal Finneyの投稿では、以下の手順で計算している。

a1 = 0x3086d221a7d46bcde86c90e49284eb15
b1 = -0xe4437ed6010e88286f547fa90abfe4c3
a2 = 0x114ca50f7a8e2f3f657c1108d9d44cfd8
b2 = 0x3086d221a7d46bcde86c90e49284eb15

とし（a1=b2）、

c1 = (b2 * k / n.to_f).round
c2 = (-b1 * k / n.to_f).round
k1 = (k - c1 * a1 - c2 * a2) % n
k2 = (-c1 * b1 - c2 * b2) % n

のように分割する。後は、 ${k_1Q + k_2Q'}$ を計算する。ここで、 ${k_1, k_2}$ は、それぞれ半分のビット長であるため、計算する際のビット長が約半分になり、計算速度が向上すると。この計算量の削減によりスカラー倍算を高速化するというのがGLV法の仕組みっぽい。

Rubyでこのアルゴリズムを書くと↓のようになる。

require 'ecdsa'
require 'bitcoin'

beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee
n = ECDSA::Group::Secp256k1.order

q = Bitcoin::Key.generate.to_point

# beta * x mod n を計算
field = ECDSA::Group::Secp256k1.field
x = field.mod(beta * q.x)
# Q' = λQ
lambda_q = ECDSA::Point.new(ECDSA::Group::Secp256k1, x, q.y)

# k
k = 1 + SecureRandom.random_number(n - 1)
a1 = 0x3086d221a7d46bcde86c90e49284eb15
b1 = -0xe4437ed6010e88286f547fa90abfe4c3
a2 = 0x114ca50f7a8e2f3f657c1108d9d44cfd8
b2 = 0x3086d221a7d46bcde86c90e49284eb15

# kを分割
c1 = (b2 * k / n.to_f).round
c2 = (-b1 * k / n.to_f).round
k1 = (k - c1 * a1 - c2 * a2) % n
k2 = (-c1 * b1 - c2 * b2) % n

# k1Q + k2Q'を計算
glv = q.multiply_by_scalar(k1) + lambda_q.multiply_by_scalar(k2)

※ 厳密にはこのコードでは、最後のk1Q + k2Q'のmultiply_by_scalarを個別にやってるので速度は向上しない。速度向上させるためには、multiply_by_scalarの計算を1回のループで同時にやるよう修正する必要がある。

Develop with pleasure!

福岡でCloudとかBlockchainとか。

楕円曲線のスカラー倍算アルゴリズム Part 2

GLV法

自己準同型の性質

高速化

${k_1, k_2}$ の分割方法