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 楕円曲線離散対数問題

に続きます。