メモリを考慮した事前計算点生成手法の提案

摘要

楕円曲線暗号は次世代の公開鍵暗号として注目されている．楕円曲線暗号の効率性を決定付ける演算はスカラー倍算と呼ばれ　高速化や使用するメモリ量の削減など多く研究されている．我々は既存研究の中で連続2倍算公式，Conjugate Additionと2-and-3倍算公式に着目した.本論文では2-and-3倍算公式の改良と混合ダブル2倍算公式を提案し，事前計算点生成手法の改良を行った．事前計算に必要とする計算量とメモリ量を求め，既存手法と比較を行った．そして，Fractional window NAF法へ適用し，スカラー倍算全体の計算量とメモリ量の評価を行った．結果，事前計算点生成手法では事前計算点数5つ（m＝11）の場合，既存手法より2変数分のメモリ量を削減できた．また，事前計算点を4つ以上保持する場合．I／M比が5．6より大きい実装環境において提案手法が高速となった．また，Fractional window NAFを利用してI／M比が14．15より大きい実装環境において16メモリ量で計算できる．I／M比が7≦I／M≦14．15の実装環境において22メモリ量で計算できる．%Elliptic Curve Cryptography (ECC) attract attention as a effective Public Key Cryptography. A central arithmetic on ECC has called scalar multiplication and more studied on method of faster arithmetic and lesser memory usage. We focused attention on successive doubling formulae, Conjugate Addition formulae and Double-and-Tripling formulae in previous work. In this paper, we improved successive doubling formulae and proposed a method of generate some precomputation points using improved formula. And we calculate required complexity and memory amount while some precomputation points is generated, and compare previous work. As a result, we saved memory amount of two variable numbers in a case of m = 11. Also we faster than previous work in some case of 9 ≦ m ≦ 15 and the environment of I/M > 5.6. And we evaluated kP using Fractional window NAF with some precomputation points. As a result, When I/M > 14.15, our method can be efficiently computed kP with 16 memory amount.