Schnorr 署名に使われる数学 - 楕円曲線

前置き

本記事は Nostr Advent Calendar 第一会場 12月10日 分の記事として書きました。

Nostr Advent Calener 第一会場

序論

本記事では、secp256k1 に基づいて楕円曲線署名を行うために必要最小限（と筆者が考える）楕円曲線の知識 について述べていきます。

また、前編として Schnorr 署名をするのに必要な初等整数論に関わる知識をこちらに載せています。

Schnorr 署名に使われる数学 - 初等整数論

具体的には、以下の内容について述べます。前節の合同式に関わる知識と合わせてこれくらいの知識があれば、楕円曲線署名署名のアルゴリズムを大づかみするには十分であると考えます。

• 実数の楕円曲線
  • 楕円曲線の方程式
  • 楕円曲線上の点の和
  • 二倍演算
• 合同式上の楕円曲線
  • 和と二倍演算
  • 巨大な数によるスカラー倍の高速計算
• 秘密鍵から公開鍵を計算する

まず、最初に実数上で定義された楕円曲線を説明します。先述の通り署名計算は合同式（整数）上で行われるのですが、視覚的な表現が容易な実数上で楕円曲線を定義し、そこで、加減算を定義します。

そのあと、実数上の楕円曲線で得られた加減算の表式を用いて、合同式上の楕円曲線を定義します。そこで巨大な整数による楕円曲線上のスカラー倍の演算を定義します。

最後に得られた表式をもとにして、秘密鍵から公開鍵を導出する方法について述べます。

実数の楕円曲線

楕円曲線を表す方程式

楕円曲線とは以下の方程式の解で表すことのできる曲線です。 $a$, $b$ は曲線のパラメータで、これらの値によりいろんな形状をとります。

$y^2 = x^3 + ax +b$

以下の図は例です。

赤は $a=0$、$b=7$ の例で、secp256k1 で用いられる曲線です。

青は $a=-2$, $b=1$ とした例です。この例では一つの閉じた曲線と、右側の開いた曲線に分かれているのがわかると思います。

楕円曲線上の演算は上記のような曲線にて、曲線上の点と点を関連づけるものとなっています。

楕円曲線の和

楕円曲線上の以下の三点に対して、

$\mathbf{E}_1 = (x_1, y_1)$

$\mathbf{E}_2 = (x_2, y_2)$

$\mathbf{E}_3 = (x_3, y_3)$

加算、

$\mathbf{E}_1 + \mathbf{E}_2 = \mathbf{E}_3$

を以下の様に定義します。

$\mathbf{E}_1$ と $\mathbf{E}_2$ を直線で結び、直線と曲線上の別の交点を求め、その点を$\mathbf{E}_3’$ とする。

$\mathbf{E}_3’$ から $y$ 軸に並行な垂線$v$を引き、その垂線と曲線との交点を $\mathbf{E}_3$ とする。

交点の計算

$\mathbf{E}_1$ と $\mathbf{E}_2$ を結ぶ直線を、

$l: y = \alpha x + \beta$

$\alpha = \frac{x_2-x_1}{y_2-y_1}$, $\beta = y_1-\alpha x_1$

とします。

楕円曲線の方程式を、

$x^3 + ax + b -y^2 = 0$

としたとき、$\mathbf{E}_1$, $\mathbf{E}_2$ $\mathbf{E}_3’$ は全て楕円曲線上の点のため、

$(x-x_1^2)(x-x_2^2)(x-x_3’^2) = x^3 - (x_1+x_2+x_3’)x^2 + (x_1x_2+x_2x_3+x_3x_1)x - x_1x_2x_3$

と、

$ = x^3 + ax + b - (\alpha x + \beta)^2 = x^3 - \alpha^2 x^2 + (a - 2\alpha\beta)x + b - \beta^2$

は恒等的に等しいはずです。

よって、$x^2$ の係数を比較すると、

$x_1 + x_2 + x’_3 = \alpha^2 $

ですから、

$x’_3 = \alpha^2 - (x_1+x_2)$ である。

そして、

$y’_3 = \alpha x’_3 + \beta = \alpha x’_3 +y_1 - \alpha x_1 = \alpha(x’_3 - x_1) + y_1$

である。図から、$x_3 = x’_3$、$y_3 = -y’_3$ なので、結局、

$x_3 = \alpha^2 - (x_1 + x_2)$

$y_3 = \alpha(x_1 - x_3) - y_1$

として計算できます。

楕円曲線の二倍算

二倍の場合、$\mathbf{E}_1$ と $\mathbf{E}_2$ が 近づいた極限、つまり二点を結ぶ直線ではなく、$\mathbf{E}_1$ の接戦と、曲線の交点、交点との垂線を用いて定義する。つまり、

$2 \mathbf{E}_1 = \mathbf{E}_1 + \mathbf{E}_1 = \mathbf{E}_3$

は、

として、二倍算を定義します。

交点の計算

接戦の方程式、

$y = \alpha x + \beta$

の各パラメータは以下の通りです。 楕円曲線の方程式の両辺を $x$ で 微分すれば、

$ 2y\frac{dy}{dx} = 3x^2 + a$

より、

$\frac{dy}{dx} = \frac{3x^2 + a}{2y}$

なので、

$\alpha = \frac{dy(x_1)}{dx} = \frac{3x_1^2 + a}{2 y_1}$

$\beta = y_1 - \alpha x_1$

です。二点の和の式を流用すれば、$x_1 = x_2$ として、

$x_3 = \alpha^2 - 2x_1$

$y_3 = \alpha(x_1 - x_3) - y_1$

となります。

和の単位元（無限遠点）と逆元

楕円曲線上の点間で和を定義するには、もうひとつ単位元となる要素が必用です。

実は単位元だけは曲線上に定義ができずに、無限遠点という曲線外に定義された要素を使います。

直感的には、有限の $x$ 座標値をもち、プラスマイナスどちらかに $y$ 方向に無限に遠い点の集合・・・つまり、$y$ 方向にプラスマイナス無限大の彼方に、x軸と平行な直線が存在する・・・と考えるとよいと思います。

そこから曲線に線分を引くと、線分はほぼ $y$ 軸と並行になるでしょう。

$\mathbf{E}’_3$ に相当する点は、$\mathbf{E}_1$ と $x$ 軸をはさんで反対側となり、これまでと同じルールを通すと、$\mathbf{E}_3$は自分自身 $\mathbf{E}_1$ということになります。

もう少しいうと、 $\mathbf{E}_3$ と $\mathbf{E}’_3$ をの和をとろうとすると、交点は曲線上に存在しません。

その変わり無限遠点との交点に和の結果を求めることを考えれば、$\mathbf{E}_3$ と $\mathbf{E}’_3$ の和はゼロ（和の単位元なので）、つまりそれぞれは互いに正負逆、逆元の関係にあると考えることができます。

合同式上の楕円曲線

$p$を法とする合同式上の楕円曲線、

$y^2 = x^3 + ax + b \pmod p$

では、座標 $x$、$y$ 両方とも合同式上の整数であり、パラメータ $a$、$b$ も同様に合同式上の整数です。

よって実数上の曲線のように線上に表すことはできず、また、$a$、$b$ の値が等しかったとしても、実数曲線状の整数点、有利点として定義ができません。

つまり、視覚的にイメージをつかむのがすごく難しいです。

いかに、$a=0, b=7, p=29$ とした場合に、上記方程式の解となる整数を集めたものを示します（表計算で計算）。

実数上の楕円曲線と唯一にていることは、$y=14$ と $15$ を挟んで上下対象であることくらいだと思います。

合同式上の和と二倍演算

和と二倍算は表式上は実数の場合のものをそのまま用います。 ただ、$\alpha$ の計算に入っている割り算の部分は、単なる整数の割り算ではなく、合同式上の乗法逆元を求める方法を使う必要があります。

二点の和

• $\alpha = \frac{x_2-x_1}{y_2-y_1} \pmod p$
• $x_3 = \alpha^2 - (x_1 + x_2) \pmod p$
• $y_3 = \alpha(x_1 - x_3) - y_1 \pmod p$

二倍算

• $\alpha = \frac{3x_1^2 + a}{2 y_1} \pmod p$
• $x_3 = \alpha^2 - 2x_1 \pmod p$
• $y_3 = \alpha(x_1 - x_3) - y_1 \pmod p$

バイナリ法による巨大な数によるスカラー倍計算

楕円曲線上の点を複数回和をとる、つまり、

$\mathbf{S} = n\mathbf{E}_1 = \mathbf{E}_1 + \mathbf{E}_1 + \mathbf{E}_1 + … +\mathbf{E}_1 $ (add n times)

が定義できます。

このとき、nが非常に巨大な数であるとき（暗号計算の場合多くのケースがこれにあたるのですが）、高速計算のための方法が必用となります。

合同式上の累乗計算で紹介したバイナリ法がこのケースでも実用的に機能します。バイナリ法が役に立つケースとして紹介します。

巨大な整数 $n$ を、

$n = \sum_{i=0}^{N} d_i 2^i$ 、$(d_i = 0 , or , 1)$

と書くこととします。

ここで、$\mathbf{S} = n \mathbf{E}_1$ は、

$\mathbf{S} = n\mathbf{E_1} = \sum_{i=1}^N\left( d_i \mathbf{E_i} \right)$

で、

$\mathbf{E_i} = 2\mathbf{E_{i-1}}$

となります。

$N$ は $n$ を二進数表現した時の桁数になります。 例えば、64バイトの整数なら $N=8 \times 64=512$ です。

$\mathbf{E_i}$ は反復の過程で、$\mathbf{E_{i-1}}$ を2倍することで、途中の計算過程を再利用することで求めていきます。

（分かりやすいかどうか意見がわかれそうですが）このアルゴリズムを視覚的に表せば、以下のようなフローになります。

秘密鍵から公開鍵を計算する

最後に、秘密鍵から公開鍵の計算方法に言及します。

Schnorr 署名における秘密鍵は、$n_{sec}$ は64バイトの乱数です。

公開鍵は、ベースポイント $\mathbf{G}$ として定義されている楕円曲線上の点を$n_{sec}$倍だけスカラー倍することで計算できます。

• 楕円曲線 $ y^2 = x^3 + 7 \pmod{p_r} $
• $p_r$ = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
• 生成元の楕円曲線上の位置座標
• $\mathbf{G}.x$ = 0x 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
• $\mathbf{G}.y$ = 0x 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

$n_{sec}$ はきわめて大きい整数のため、前述したバイナリ法よるスカラー倍の高速計算が役に立ちます。 楕円曲線上の点 $n_{sec} \mathbf{G}$ の $x$ 座標値が公開鍵となります。

補足と結論

以上、secp256k1 にて Schnorr 署名するのに最低限必要な楕円曲線上の知識について述べました。

一点、本質的なポイントで述べていないところがあるので、ここで言及しておきます。

合同式上の楕円曲線上の計算は、楕円曲線上で完全に閉じています。 つまり、楕円曲線上の和を計算して行きつく先は必ず楕円曲線上の点になっています。

曲線と直線を利用して視覚的に述べるとそれは直感的に理解できるように思えるのですが、合同式上で整数として扱われると、和の行き着く先が本当に楕円曲線上の点なのか、直感的には理解できないように思えます。

これは、モーデル・ヴェイユの定理として解決されている事項ではありますが、証明を読んでも理解がおよびませんでした。定理の説明は記事の末尾に Wikipedia へのリンクを載せますので、興味のある方は読んでみてください。

Reference

• Nostr Implementation Posibilities #01 - NIP-01
• Bitcoin Improvement Proposals #0340 - BIP0340
• モーデル・ヴェイユの定理