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 スカラー倍算の高速化

に続きます。

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

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

次は、スカラー倍算の高速化を考えます。

楕円曲線暗号を処理するプログラムでは、暗号を生成するにせよ、暗号を解読するにせよ、スカラー倍算の計算が重要です。そこで、方法を考えてみます。

素体\(\mathbb{F}_p\)上の四則演算では、加算・減算に比べ、乗算、さらには除算はもっと手間がかかります。自分で、適当な数字でやってみれば実感できます。しかし、楕円曲線の加法公式は除算の計算を必要とするため、その計算も長い時間を必要とします。そこで、この除算を避けるため、射影座標と言うものを導入します。

射影座標\((X,Y,Z)\)において、射影座標全体の集合を\(V\)とするとき、\((x,y,z),(X^\prime,Y^\prime,Z^\prime) \in V\)に関して、

\[(X^\prime,Y^\prime,Z^\prime)=(cx,cy,cz)\]

となる\(c\in \mathbb{F}_p\backslash \{0\}\)が存在するとき、この2点を同一視(同じと考える)します。つまり、

\[(X,Y,Z)=(2X,2Y,2Z)=\cdots =(X/Z,Y/Z,1)\]

となります。そこで、普通の座標(アフィン座標)上のある点\((x,y)\)と、射影座標における座標値\((x,y,1)\)を同一視します。このとき、射影座標における点\((X,Y,Z)\)は、アフィン座標上の\((X/Z,Y/Z)\)と同一視できます。

 

射影座標における楕円曲線の定義方程式は、\(y^2=x^3+ax+b\)に\(x=X/Z,y=Y/Z\)を代入して、

\[Y^2Z=X^3+aXZ^2+bZ^3\]

となります。

今までの様に、\(a=2,b=3\)として立体グラフを描いてみました。

目をボヤッと気を抜いた感じにして、重ねて見るヤツです。

\(z\)軸に平行な平面で輪切りにすると、前回のその1のグラフになることが想像できるでしょうか。

また射影座標では、無限遠点は\(X\)座標、\(Z\)座標がともに\(0\)の点と定義します。

射影座標における加法は、以下の様になります。

2点\(P(X_P,Y_P,Z_P),Q(X_Q,Y_Q,Z_Q)\)の和\(R=P+Q=(X_R,Y_R,Z_R)\)を以下の様に定義する。

\(P\neq Q\)のとき、

\(X_R=vA\)

\(Y_R=u(v^2X_P Z_Q-A)-v^3 Y_P Z_Q\)

\(Z_R=v^3 Z_P Z_Q\)

ただし、\(u=Y_Q Z_P-Y_P Z_Q ,v=X_Q Z_P-X_P Z_Q,A=u^2 Z_P Z_Q-v^3-2v^2 X_P Z_Q\)

\(P=Q\)のとき、

\(X_R=2hs\)

\(Y_R=w(4B-h)-8Y_P^2s ^2\)

\(Z_R=8s^3\)

ただし、\(w=aZ_P^2+3X_P^2,s=Y_P Z_P,B=sX_P Y_P,h=w^2-8B\)

では、この方法で\((1,1)+(1,1)\)を計算してみましょう。

射影座標では、\((1,1,1)+(1,1,1)\)

\(w=2\cdot 1^2+3\cdot 1^2=0\)

\(s=1\cdot 1=1\)

\(B=1\cdot 1\cdot 1=1\)

\(h=0^2-8\cdot 1=2\)

よって

\(X_R=4\)

\(Y_R=2\)

\(Z_R=3\)

ゆえに、\((x,y)=(\frac{4}{3},\frac{2}{3})=(3,4)\)

見事に、前回の計算と一致しました。

 

では、等しいはずの\((2,2,2)+(1,1,1)\)も、確認のために計算してみましょう。これは同じ点であることに注意して、

\(w=2\cdot 2^2+3\cdot 2^2=0\)

\(s=2\cdot 2=4\)

\(B=4\cdot 2\cdot 2=1\)

\(h=0-8\cdot 1=2\)

よって、

\(X_R=1\)

\(Y_R=3\)

\(Z_R=2\)

ゆえに、\((x,y)=(\frac{1}{2},\frac{3}{2})=(3,4)\)

やはり一致しました。

 

射影座標を用いてスカラー倍算を計算するには、アフィン座標\((x,y)\)を射影座標\((x,y,1)\)として計算し、最後にその結果\((X,Y,Z)\)をまたアフィン座標に戻せばよいので、除算は最後のみ必要になります。こうすることで、計算コストを削減できます。

さらに計算コストを削減するアルゴリズムもありますが、それらはここでは言及しません。

nemの楕円曲線暗号を基礎から学んでみる(数式)-その3 楕円曲線離散対数問題

に続きます。

nemの楕円曲線暗号を基礎から学んでみる(数式)-その3 楕円曲線離散対数問題

nemの楕円曲線暗号を基礎から学んでみるシリーズ

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

次はいよいよ、楕円曲線暗号の解読が実質的に、ほとんど不可能な理由を考えていきましょう。

前回まで、素体\(\mathbb{F}_p\)上の楕円曲線の有理点の集合で、適当にベースポイント\(P\)を選びスカラー倍算を計算するのは、比較的簡単であることを学びました。

計算の分野では問題の難しさは、その問題が入力に対し、どれぐらいの時間で解けるかを目安に考えることが多いです。特に、ある入力の長さ\(n\)に対して平均でどれぐらい時間がかかるかとか、最悪どれぐらいかかるかなんかを考えたりします。ここでいう簡単とか難しいと言うのは、そういう意味です。

つまり、実質的に不可能とは、現在用いられているコンピュータの性能を以て問題に取り組んでも、入力の長さが大きい場合などは、現実的な時間(せいぜい数年)では解けないことを意味します。

 

ここでは今までとは逆に、点\(Q\)が点\(P\)の何倍になっているのかを求める問題を考えます。これは、楕円曲線離散対数問題と呼ばれます。

この問題に対する解法ですぐに思いつくのは、総当たり法です。

しかし、その1の\(p=5\)の場合など、点位数が小さい場合はいいですが、NEMのTechnical Referenceを見てみれば、

「曲線上の巡回群\(G\)に対応するベースポイントを\(B\)とします。この群は、\(q=2^{252}-27742317777372353535851937790883648493\)個の元を持ちます。」

とあります。CPUのクロック周波数は\(5GHz\)程度ですから、一秒に\(5\times10^{9}\)回命令を回せます。本当は命令と言うと語弊がありますが、ここでは無視しましょう。シングルコアを想定して、楕円曲線離散対数問題の正解が、\(d=2^{200}\)のところにあった場合を考えます。一年は\(3\times 10^7\)程度ですから、

\[{2^{200}}/{5\times 10^9}/{(3\times 10^7)}\simeq 10^{43}年\]

かかってしまいます。ベースポイントの位数を\(l\)とすれば、かかる時間は最悪の場合、最悪計算量\(O(l)\)(\(l\)に比例する程度の時間)になります。

(逆に今まで考えてきた掛け算の場合は、\(100\times P=(64+32+4)\times P\)のような計算ができますから、比較的簡単です。つまり、もとの問題の計算時間の\(log\)程度で抑えることができます。)

ちょっと現実的ではありません。もうちょっと簡単に暗号を打ち破る方法はないのでしょうか。

 

Baby-step Giant-step法

楕円曲線離散対数問題\(Q=d\times P\)に対し、ベースポイント\(P\)の位数\(l\)を用いて、\(m=[\sqrt{l}]\) ([]はガウス記号)とします。このとき、\(d=sm+t\)(\(s\)は\(d\)を\(m\)で割った商\(,t\)は\(d\)を\(m\)で割ったあまり)とします。

\(R=m\times P\)として、

\[Q=d\times P=(sm+t)\times P=s\times R+t\times P\]

となるから、\(s,t\)は以下を満たします。

\[Q-t\times P=s\times R\]

そこで、

\(\{Q-t\times P|t\in \mathbb{N},0\leq t\leq m-1\}\),

\(\{s\times R|s\in \mathbb{N},0\leq s\leq m-1\}\)

のデータベースをあらかじめ計算し、この中で互いに同じものがあれば、それは答えになります。

 

しかしこれでも、計算量は\(O(\sqrt{l})\)です。

ちなみに、\(y=log(x),y=x,y=\sqrt{x}\)のグラフはこんな感じです。

 

\(l\)がさらに大きいところだと、コイツらの差はアホみたいに大きくなります。それぐらい、計算量のオーダーは大事だと言うことです。

 

さらに、\(\rho\)法と言う、よりすぐれたアルゴリズムがあります。最近の、大きなサイズの離散対数問題を突破した手法に関しては、全てこの方法が用いられています。

楕円曲線離散対数問題\(Q=d\times P\)に対し、何らかの方法(実際にはランダム)で

\[s\times P+t\times Q=s^\prime \times P+t^\prime \times Q\]

となる、互いに異なる\(s,s^\prime,t,t^\prime\)が見つかったとします。

すると、

\[(t-t^\prime)\times Q=(s^\prime-s)\times P\]

よって、\(\frac{s^\prime-s}{t-t^\prime }\)(ベースポイント\(P\)の点位数\(l\)の\(mod(l)\)での除算)が答えになります。

\(i\)番目にランダムに選ばれた点を\(R_i=s_i\times P+t_i\times Q\)とすると、このような点同士をいかに早く見つけるかが問題です。この特別な点どうしを、コリジョンペアと言います。

ランダムな点を効率的に求めるためには、つぎの\(R\)として、以下の\(f(R)\)を用います。

\[f(R)=R+M_i(ここで、i=x(R)mod4)\]

ただし、\(M_0,M_1,M_2,M_3\)はあらかじめランダムにとった点であり、\(x(R)\)は\(R\)の\(x\)座標です。

 

この\(4\)という数字は、大規模な問題の場合はランダム性の向上のため\(20\)などの大きな数にします。

これは、線形合同法と言う基本的な乱数生成法で、C言語のrandは線形合同法を用いています。ちなみに、pythonはメルセンヌツイスタです。

 

この\(rho\)法を用いた攻撃は、誕生日攻撃と呼ばれます。

点の集合から2つの点をランダムに選んで試すのと、

クラスから2人同じ誕生日の人を選んでくるのが、同じ構造を持っているからです。

詳細は省きますが、誕生日攻撃において、\(50\%\)の確率で攻撃が成功する試行回数は\(O(\sqrt{N})\)であることが、それほど難しくない数理的解析から分かります。これはBaby-step Giant-step法と同じですが、ある方法を用いることで保存すべき情報が減らせるから、こちらの方が優れているとされています。

このように、暗号の生成(スカラー倍算)に比べ、楕円曲線離散対数問題を解くのにメチャクチャ時間がかかる(少なくとも、それよりいいアルゴリズムが見つかっていない)ため、楕円曲線暗号の安全性が保障されています。

ちなみに、量子計算機を用いた楕円曲線離散対数問題の効率的な解法はすでに知られているようで、これが最近ニュースでよく見る暗号の問題かと、やっと納得に至りました。