PARI GPでMontgomery curvesを用いたECDSAの実装(1)

[mathjax]Weierstrass標準形を併用しながらスカラー倍,点の加算にMontgomery curvesを使った話.

以前はPARI GPの機能を使って,Weierstrass標準形でECDSAを実装した.今回は新しくMontgomery curvesを用いたスカラー倍,点の加算を実装した.そのため,以前行ったWeierstrass標準形での実装と,新しくつくるMontgomery curvesでの実装を見比べてみる.
 
1.スカラー倍
作成したMontgomery ladderのラッパー関数としてscalarという関数を作成した.入力は楕円曲線のパラメータ\(A,B\)とアフィン座標の点\(P\),スカラー\(k\),有限体の位数\(p\)である.出力はアフィン座標の点\(Q=kP\)である.

 
2.点の加算
署名検証で点の加算が必要となるため,点の加算を実装する必要がある.アルゴリズムをそのままコードにして実装する.ただし,\(P_3=P_1+P_2\)とする際に\(P_1=-P_2\)となっている場合は\(P-P=O\)となるため無限遠点を返す.また,\(P_1=P_2\)の場合は\(P+P=2P\)となるため2倍算を行う.

 
3.動作確認
動作確認には\(F_{30011}\)上のMontgomery curves \(y^2=x^3+84x^2+x\)とWeierstrass標準形 \(y^2=x^3-2351x+43876\)を用いる.ベースポイントについてはWeierstrass標準形では\((7796,9454)\),Mongtomery curvesでは\((7768,9454)\)を用いる.なお,点位数\(l=1249\)はとなる.基本的には以前作成したWeierstrass標準形のコードと同時にMontgomery curvesのコードを実行する.以下にコードと実行例を示す.
実行例からWeierstrass標準形の点\(P_W=(x_W,y_W)\)とMontgomery curvesの点\(P_M=(x_M,y_M)\)について\((x_M,y_M)=(x_W-28,y_W)\)が成り立っており,スカラー倍や点の加算が正しく行えていることが分かる.