楕円曲線暗号におけるスカラー倍算について
楕円曲線暗号は,公開鍵暗号方式の一つで,楕円離散対数問題の困難さを安全性の根拠としている.近年の計算機能力の向上に伴い,鍵長を大きくせざるを得なくなっているが,他の公開鍵暗号方式に比べ,楕円曲線暗号は短い鍵長でも同強度の安全性を持つと言われており,高速な処理を実現できる.このことから,楕円曲線暗号は注目されており,ECDSA 署名などがSSL/TSL で実用化されている.楕円曲線暗号は楕円曲線上の点P のk 倍点kP を計算すること(スカラー倍算) が主たる演算であるため,kP の計算量を減らすことが高速な処理を実現するために重要である.そのため,使用する座標系や加算連鎖の改良により,全体の計算量を減らせるかが高速処理実現の鍵となる.また,マルチスカラー倍算と呼ばれる,スカラー倍算の拡張ともいえる演算がある.これは点P,Q からuP +vQを計算するもので,演算の高速化につながるため重要なものとなっており,その高速化手法として共同疎形式(JSF)が知られている.スカラー倍算のアルゴリズムは,メモリを利用するかしないかで大別され,前者にはNAF,後者にはWindow 法などがある.既存アルゴリズムの多くは,加算と2 倍算の演算が主な構成要素であり,これら二つの演算の処理時間や消費電力等のサイドチャネル情報を利用し,秘密鍵を得るサイドチャネル攻撃に脆弱である.サイドチャネル攻撃は,単純電力解析攻撃(SPA),差分電力解析攻撃(DPA)に大別される.SPA は演算中の消費電力の波形の観察により秘密鍵を求める攻撃,DPA は本当の秘密鍵との消費電力の差分をとることで秘密鍵を求める攻撃である.
本研究の目的は,メモリを利用しない既存アルゴリズムの長所を用いたスカラー倍算実行を可能とする指標の提案に加え,サイドチャネル攻撃に耐性のある効率的なアルゴリズムを提案することである.また,新しいアルゴリズム構築とは別に,既存アルゴリズムの改良やJSFを利用したスカラー倍算についても考察していく.