1. /
  2. /
  3. PARI GPによるECDSAの実装

PARI GPによるECDSAの実装

[mathjax]今回はPARI GPを用いてECDSAを実装する．

最初に環境構築として，公式サイトからzipを落として展開する．なお，このときにCドライブ直下など権限が必要な場所ではうまくいかないことがあるため，デスクトップなどに展開する．展開するとgp.exeがあり，これを起動するとPARI GP用のコマンドラインが立ち上がる．今回はgp.exeと同じフォルダにecdsa.gpとしてソースコードを書き，実行する．
GPファイルは{}で囲まれた部分を，C言語におけるmain関数のように実行する．今回は関数を標準ライブラリのものだけで実装するので，関数の作成は行わず{}の中にコードを記述していく．ECDSAのアルゴリズムについては，このページの楕円曲線暗号入門のp.56に記載されているものを参考にする．なお，今回例として使用するパラメータは\(a=84,b=12,p=251\)とする．つまり\(F_{251}\)上での\(y^2=x^3+84x+12\)となる．
アルゴリズムを準備・鍵生成・署名生成・署名検証・結果表示の5段階に分けて１つずつ記述していく．
 
1.準備
最初に楕円曲線を生成する．PARI GPでは楕円曲線をellinit関数を用いてつくる．なお，ellinitの中の行列はWeierstrass標準形の\(a_1,a_2,a_3,a_4,a_6\)に対応しており，コード中の\(p\)は有限体\(F_p\)の\(p\)を表す．ベースポイント\(P\)に関しては\((183, 12)\)とする．また，点位数\(l\)が必要なので計算しておく．点位数\(l\)は\(lP=O\)を満たす巨大な素数である．
 

a=84;b=12;p=251;
e=ellinit([0,0,0,a,b],p);
P=[Mod(183, p), Mod(12, p)];
l=ellorder(e,P);

 
2.鍵生成
乱数\(d_B\)を生成し，\(P_B=d_B\times P\)を計算する．\(d_B\)が秘密鍵となり，\(P_B\)が公開鍵となる．乱数\(d_B\)に関しては，0と1が都合が悪いため除外するようにしている．スカラー倍はellmul関数を用いる．

d_B=random(l-2)+2;
P_B=ellmul(e,P,d_B);

 
3.署名生成
乱数rを1からlまでの範囲で生成し，\(U=r\times P\)を計算している．また，メッセージはハッシュ化して固定長にする必要があるが，ここでは簡略化のため乱数mをメッセージをハッシュ化したものとみなす．\(u\)には点\(U\)の\(x\)座標を\(mod\ l\)したものがはいる．点は\(x\)座標と\(y\)座標が行列形式で格納されているため，点\(U\)の場合\(U[1]\)で\(x\)座標，\(U[2]\)で\(y\)座標にアクセスできる．lift関数がついているのは，点\(U\)が\(mod\ p\)で計算されているためMod(xx,p)という形式になっており，Modを外す必要があるため．

r=random(l-1)+1;
U=ellmul(e,P,r);
m=random(p);
u=lift(U[1])%l;v=((m+u*d_B)/r)%l;

 
4.署名検証
\(d\)と\(V\)については，定義どおりコードを書くだけで良い．

d=(1/v)%l;
V=elladd(e,ellmul(e,P,d*m),ellmul(e,P_B,d*u));

 
5.結果表示
結果が正しいかどうかは\(u\)と，点\(V\)の\(x\)座標を\(mod\ l\)したものが等しいかどうかで判断する．等しいなら署名は正しく，等しくないなら署名は正しくないことを示す．PARI GPの条件分岐はif(条件式，真，偽)で記述する．

if(u==(lift(V[1])%l),
	print("OK");,
	print("NG");
);

 
 
以下に中間結果の表示を追加した全体のコードとその実行例を示す．なお，意図的にNGを出力したい場合は署名検証の最初で\(m\)の値をずらせば良い．
 
 

{
	\\準備
	a=84;b=12;p=251;
	e=ellinit([0,0,0,a,b],p);
	print("y^2=x^3+",a,"x+",b," on F_",p);
	P=[Mod(183, p), Mod(12, p)];
	print("base point P=",P);
	l=ellorder(e,P);
	print("order l=",l);
	\\鍵生成
	d_B=random(l-2)+2;
	P_B=ellmul(e,P,d_B);
	print("secret key d_B=",d_B);
	print("public key P_B=",P_B);
	\\署名生成
	r=random(l-1)+1;
	print("random value r=",r);
	U=ellmul(e,P,r);
	print("U=",U);
	m=random(p);
	print("m=",m);
	u=lift(U[1])%l;
	v=((m+u*d_B)/r)%l;
	print("signature (u,v)=(",u,",",v,")");
	\\署名検証
	d=(1/v)%l;
	print("d=",d);
	V=elladd(e,ellmul(e,P,d*m),ellmul(e,P_B,d*u));
	print("V=",V);
	\\結果表示
	if(u==(lift(V[1])%l),
		print("OK");,
		print("NG");
	);
}

 

(16:33) gp > \r ecdsa.gp
y^2=x^3+84x+12 on F_251
base point P=[Mod(183, 251), Mod(12, 251)]
order l=241
secret key d_B=111
public key P_B=[Mod(237, 251), Mod(46, 251)]
random value r=192
U=[Mod(118, 251), Mod(240, 251)]
m=93
signature (u,v)=(118,80)
d=238
V=[Mod(118, 251), Mod(240, 251)]
OK