効率的な楕円曲線暗号に関する研究
1976年にDiffieとHellmanによって公開鍵暗号の概念が提案されて以降，RSA暗号をはじめとして，さまざまな公開鍵暗号が提案されている．公開鍵暗号は暗号鍵と復号鍵が異なるもので暗号鍵を公開し，復号鍵を秘密にしておく暗号方式であり，データの暗号化・復号化だけでなく電子署名にも利用されている．しかし，計算機能力の向上や新しい解読法の提案により素因数分解問題や離散対数問題を安全性の根拠にもつ暗号の鍵長が長くなる問題が起こっている．そのため次世代の暗号の一つとして楕円曲線暗号，超楕円曲線暗号が上げられ，盛んに研究されている．楕円曲線暗号は楕円曲線上の有理点が加法群になることを利用し，楕円曲線上の離散対数問題(ECDLP)を安全性の根拠にした暗号で，KoblitzとMillerによって1985年に提案された．楕円曲線暗号はRSA暗号等に比べて短い鍵長で安全性が確保できるという長所があり，この特徴から，メモリの少ないスマートカード等で利用されている．
近年，外部電力供給型のデバイスであるスマートカード等に対し，電力消費量などから内部の秘密鍵を特定するサイドチャネル攻撃が脅威となっている．これは楕円曲線暗号の実装から秘密鍵に依存した電力消費量が測定されることを利用する解析である．単純な電力解析から秘密鍵を特定する手法はSimple Power Analyze(SPA)と呼ばれ，攻撃者がテスト鍵との差分を利用することにより秘密情報を探る方法をDifferential Power Analyze(DPA)という．DPAはSPAより強力な攻撃法である．SPA, DPAともに対策が数多く提案されてきたが，現在SPA対策として有限体上の演算をブロックと呼ばれる小さな演算集合にわけるSide Channel Atomicity，DPA対策としては楕円曲線上のランダムな点を初期点に加えるRandom Initial Point(RIP)が主たる防御法である．
楕円曲線暗号は楕円曲線上のスカラー倍算，すなわちスカラーkと楕円曲線上の点Pに対して，kP=P+P+ ... +Pを求める演算で構成される．一般的にスカラー倍算は大きく２種類に分けることができ，予め与えられた有理点(固定点)に対し事前計算点をテーブルとして保持し，演算をおこなう固定点スカラー倍算と，任意に与えられた有理点(任意点)に対するスカラー倍算である．固定点スカラー倍算には加算のみでスカラー倍算を行うBGMW法やMOC法等があり，任意点スカラー倍算にはバイナリ法，Window法等がある．効率的な楕円曲線暗号の実現にはスカラー倍算の高速化が必要不可欠であり，併せてスマートカードのようなリソースが乏しいデバイスへの実装を鑑みて少ないメモリでのアルゴリズムが求められている．
本研究では，効率的な固定点スカラー倍算としてMOC法にモンゴメリトリック(MT)を適用した高速アルゴリズムを提案した．通常2変数(Affine座標型)で代数曲線を扱うとき，有限体の楕円曲線上の有理点演算には逆元を求めるステップが必要であり，逆元演算は乗算や2乗算に比べてコストがかかるため，楕円曲線を3変数(Projective, Jacobian座標型)へ変換し，逆元演算を1回のみにする手法が取られる．提案法ではAffine座標型において，MOC法のテーブルの持ち方を改良し，そこへMTを適用することにより少ない逆元演算でスカラー倍算を実現した．MTはn個の逆元が必要なとき，1回の逆元演算と数回の乗算に計算量を削減する手法である．この方法は，種数2以上の曲線にも適用可能なことから，超楕円曲線暗号へも応用でき計算量の削減に成功した．
また本研究では，任意点スカラー倍算に関して基数を3つにしたスカラー倍算法を提案した．この方法はテーブルを必要としない．バイナリ法では基数2であるため，2P, 2P+Qの演算を繰り返し使用するが，これにCiet等が提案した3P ± Qを加え新たに5P ± Q, 5P ± 2Qの計算式を導入し高速化を実現した．この方法はAffine座標型で高速である．更にDimitrov等が提案した2,3を基数にするスカラー倍算法に5倍算法を加えることによりJacobian座標型での高速化に成功した．
これらの提案法は何れもSide Channel Atomicity，及びRIP法と組み合わせることが可能であり，サイドチャネル攻撃にも耐性を持つアルゴリズムに応用可能である．
