nemの楕円曲線暗号を基礎から学んでみる(数式)-その1 数学的準備

ブロックチェーンnemにも使われていると言うことで、僕も楕円曲線暗号を一から勉強してみることにしました。

ちなみに、nemのとか書いていますが楕円曲線暗号そのものは広く使われていて、基本的な考え方は全て同じです。

こんなpdfがあったので、大いに参考にしています。

https://written.4403.biz/source/ecc_rev30r.pdf

前提知識として、集合論とかはある程度知っておいた方が理解しやすいと思います。

 

まず、素数\(p\)について、集合

\[\mathbb{F}_p=\{ 0,1,..p-1\} \]

を考えます。

このちょっと変な集合の上では、要素\(n\)は、普通の整数の\( \{…,n-2p,n-p,n,n+p,n+2p,…\}\)と同じと考えます。

ここでは例として、\(p=5\)とします。

\[\mathbb{F}_5=\{ 0,1,2,3,4\} \]

つまり、この集合での足し算は\(3+4=2(=7-5)\)、

引き算は\(1-4=2(=-3+5)\)

掛け算は\(2\times 3=1(=6-5)\)

割り算は\(3\div 4=2(=(3+5)\div 4)\)

のようになります。

自分でいろいろ適当な数で計算して、遊んでみてもいいかもしれません。ここで不思議なのは、なぜ\(p\)を最初から素数にしたのかです。実際、\(p=9\)などの非素数にしてみると、割り算がうまくいきません。

\[1\div 3=(1+9)\div 3=(1+9\times 2)\div 3=… \]

ここまで来ればお気づきでしょう。9が3で割り切れてしまうからです。なぜ\(p\)が素数の時はすべてうまくいくのかは、ちょっと考えてみてください。

数学では、可算減算積算除算のできる集合を体(有理数体、実数体など)と言いますが、特に、ここで挙げた\(\mathbb{F}_p\)を、素体と言います。

 

次に、楕円曲線の定義をします。

\(y^2=x^3+ax+b (a,b\in \mathbb{F}_p,4a^3+27b^2\neq0)\)

なる曲線を、\(\mathbb{F}_p\)上の楕円曲線と言います。

\(4a^3+27b^2\neq0\)は、異なる\(x\)で同じ\(y\)になる(解が重複する)のを防ぐための条件で、二次方程式の場合の\(b^2-4ac\neq 0\)と同じものです。

例えば、\(a=2,b=3\)とした\(y^2=x^3+2x+3\)は、\(\mathbb{F}_5\)上の楕円曲線のひとつです。

そして楕円曲線上で、\((x,y)\)の両方が\(\mathbb{F}_p\)に属する点を、\(\mathbb{F}_p\)-有理点と言います。さらに無限遠点と言う特別な点\(\mathcal{O}\)も、この\(\mathbb{F}_p\)-有理点の仲間に入れてやります。

では、素体\(\mathbb{F}_5=\{0,1,2,3,4\}\)上の楕円曲線\(y^2=x^3+2x+3\)の有理点を列挙してみましょう。

\((1,1),(1,4),(2,0),(3,1),(3,4),(4,0),\mathcal{O}\)

確認してみてください。

(この場合は、\(x=0\)のときは有理点がありません。また、\(x\)座標が同じで\(y\)座標が\(\mathbb{F}_5\)の和に関する逆元同士(つまり足して5)になっている有理点の組がいくつかあります。この理由もちょっと考えてみて下さい。)

次に、この\(\mathbb{F}_p\)-有理点の集合での加法を考えてみます。以下は、このようにするとうまくいくよ~という計算法です。

1.2点\(P,Q\)を通る直線を引く

2.楕円曲線と直線の交点\(R^\prime \)とする。

3.\(R^\prime\)の\(x\)軸に対する対称点(ようは、\(y\)座標をひっくり返したモノ)\(R\)を和\(P+Q\)とする。

 

 

ホントにうまくいくの?と思いますが、例えば、

1.\((1,1),(2,0)\)を通る直線は、\(y=4x+2\)です。

2.\(y=4x+2\)と楕円曲線\(y^2=x^3+2x+3\)の交点は、\((2,0)\)です。

3.対称点は、\((2,0)\)です。

なんと、ちゃんと和の結果が元の仲間に入っている(有理点の集合は和について閉じて)います。

 

一般に、楕円曲線の有理点の集合は加法群(加法、減法について閉じている)になっています。

この方法に、ちゃんとした定義を与えます。

和\(R=P+Q\)に関して、

\(P\ or\ Q=\mathcal{O}\)のとき、それぞれ\(R=P,Q\)とする。

\(y_P=-y_Q\)のとき、\(R=\mathcal{O}\)とする。(\(P\)は\(Q\)の逆元\(-P\))

\(y_P\neq -y_Q\)のとき、\(x_R=\lambda^2-x_P-x_Q,y_R=\lambda(x_P-x_R)-y_P\)

ここで、\(\lambda\)は2点を通る直線(\(P=Q\)のときは接線)の傾きを表す。

\(\lambda= \frac{y_P-y_Q}{x_P-x_Q}\ or\ \frac{3x_P^2+a}{2y_P}\)

適当に素体\(\mathbb{F}_p\)上の楕円曲線上の点を選びます。これをベースポイントと呼びます。適当な整数\(d\)に対し、

\[d\times P=P+P+…+P\]

を求めることを、スカラー倍算と呼びます。

では、素体\(\mathbb{F}_5=\{0,1,2,3,4\}\)上の楕円曲線\(y^2=x^3+2x+3\)の有理点の集合\(\{ (1,1),(1,4),(2,0),(3,1),(3,4),(4,0),\mathcal{O}\} \)において、\((1,1)\)のスカラー倍算を求めてみましょう。

\((1,1)\times 2=(1,1)+(1,1)\)

\(\lambda=\frac{3\cdot 1^2+2}{2\cdot 1}=0\)

よって、\((3,4)\)

 

次に、

\((1,1)\times 3=(3,4)+(1,1)\)

\(1+4=0\)でるから、\(\mathcal{O}\)

このような、楕円曲線上の有理点のなす加法群をMordel-Weil群と呼び、加法群の要素の個数を、群位数と呼びます。この場合は、群位数は7です。

また、楕円曲線上のスカラー倍算はじゅんぐり回っていって、かならず途中で計算結果が無限遠点\(\mathcal{O}\)に等しくなります。この、何倍して無限遠点に等しくなったかを、ベースポイントの点位数と呼ばれます。

例えばこの場合は、ベースポイント\((1,1)\)に対する点位数は、\(3\)です。

また、じゅんぐりになる群を、巡回群と呼びます。よって、楕円曲線上の有理点の集合からじゅんぐりになるものだけ抜き出し集合は、巡回群です。

この場合は、\(\{ \mathcal{O} ,(1,1),(3,4)\} \)は巡回群をなします。

さて、ここらあたりでブロックチェーンNEMのTecnical Reference(リンクは日本語版)をチラッと読んでみると、だいぶん理解が進んだことに気付くのではないでしょうか。

ちなみに、NEMのこの数字がなぜ分数なのか

\[\frac{121655}{121656}\]

も、除算の説明のところを復習すればわかるでしょう。

nemの楕円曲線暗号を基礎から学んでみる(数式)-その2 スカラー倍算の高速化

に続きます。