公開鍵暗号方式の一つとして、楕円曲線暗号が注目されている。 楕円曲線暗号の安全性は楕円曲線上の離散対数問題の困難性に基づく。 楕円曲線は様々な体で定義され、 暗号ではソフトウェアやハードウェアでの実装に適した有限体 GF(p)やGF(2n)が用いられる。 暗号化や復号は曲線上の 点のスカラー倍 を求める必要があり、 異なる二点の加算と 点の二倍算の繰り返しで行われる。 楕円曲線をはじめとする公開鍵暗号方式の計算量は秘密鍵暗号方式と比べ大きく、 その高速化は重要な課題である。 点の加算や二倍算は体での加算、減算、乗算、平方、逆元計算に基づいており、 有限体では特に逆元計算の計算量が大きい。
逆元計算の計算回数を減らす手法として、 射影座標を用いるものがある。 点の加算や二倍算では乗算の回数は増えるが逆元計算を行う必要はなく、 計算量を削減している。 逆元計算はスカラー倍の計算終了時に元のアフィン座標に戻すために 一回だけ行えばよい。
本論文ではGF(2n) 上の楕円曲線暗号のための高速演算アルゴリズムを提案する。 このアルゴリズムは楕円曲線をアフィン座標 (x,y)からx=X/Z,y=Y/Z2 の重み付き射影座標(X,Y,Z)に変換し、計算を行う。 射影座標を用いた従来のアルゴリズムと比べ、 点の二倍算の計算量は変わらないが、 異なる二点の加算の乗算回数が少ない。 さらに、提案アルゴリズムを用いて点のスカラー倍を求める場合、 逆元計算の計算量が乗算のおよそ5倍以上であるなら、 アフィン座標で計算を行うアルゴリズムよりも高速であることを示す。
