Top | 研究室紹介 | メンバー紹介 | アクティビティ | 学会投稿案内 | リンク | English


    ”超楕円曲線暗号の最適化に関する研究”


     1976年にDiffieとHellmanによって公開鍵暗号の概念が提案されて以降, RSA暗号, ElGamal暗号などさまざまな公開鍵暗号が提案されている. しかし, RSA暗号, ElGamal暗号は様々な攻撃法が提案され, 安全性が危惧されているため, 次世代の暗号開発が急務である. その次世代暗号の一つに楕円曲線暗号, 超楕円曲線暗号が上げられ, 盛んに研究されている.
     楕円曲線暗号は, 楕円曲線上の加法群を利用した離散対数問題の困難性に基づく公開鍵暗号である. 楕円曲線暗号はRSAなどの公開鍵暗号系に比べて, 小さい定義体上で安全性を確保できるため, 小さい多倍長演算で暗号系を構築することができる. また, 超楕円曲線暗号は, 楕円曲線暗号に比べて, 小さな定義体で高い安全 性を確保できることから, 楕円曲線より小さい多倍長演算で暗号系を構築することができる. このことから, 楕円曲線・超楕円曲線暗号は, メモリ制限の大きいスマートカード等での用途が期待されている. その一方で, スマートカード等の実装で特に問題となるのはサイドチャネル攻撃(SCA)である. サイドチャネル攻撃は, 暗号デバイスの実際の 暗号処理から漏洩するサイドチャネル情報を利用した攻撃方法で, 大きな脅威となりうるため, 様々な研究が行われている. 特にKocherらにより提案された単純電力解析攻撃(SPA), 差分電力解析攻撃(DPA), DPAの改良である演算処理の例外処理を利用したRPA, ZPAへの対策は必須と言える. SPA耐性を高める方法にfixed procedure法とindistinguishable法がある.
     SPA対策の無いべき演算は, 鍵の情報による加算・2倍算の処理分岐が生じるため, 暗号処理中の電力を解析することで, 秘密情報の漏洩が起きる. Fixed Procedure法はダミー演算を挿入したり, 秘密情報自体を変更することで加算・2倍算を一定周期で処理することができるが, 計算量・メモリ量が多くなる欠点がある.
     Indistinguishable法は加算・2倍算を同じ計算パターンにした加算公式を利用する方法である. 計算パターンはが同じでも, 加算の回数が秘密情報に依存するため, 暗号処理中 の電力消費量や処理時間で加算の回数が漏洩し(鍵のハミングウェイトの漏洩), 鍵を推定する情報を与えることになる. このため, 加算・2倍算の演算回数が一定となるアルゴリズムが必須となる. また, 加算公式中の乗算・2乗算を区別することで 加算・2倍算の分岐を明らかにする方法も提案されているため, 乗算・2乗算の区別ができないアルゴリズムも必要となる.
     本研究では$d$に対するSigned binary表現が一意でないことを利用し, NAF及び$w$NAF表現を改良することでハミングウェイトの出ない表現に変換する方法を提案した. これにより, indistinguishable法の利用が可能になり, fixed procedure法と比べ, メモリサイズを抑えた 耐SPAスカラー倍算が可能となる. また, 超楕円曲線暗号においては, 加算公式の複雑さから効率の良い加算・2倍算の同一化法が提案されていないため, 超楕円曲線暗号におけるメモリ・計算量を考慮に入れた効率の良い加算・2倍算の同一化手法も合わせて提案した.


    【戻る】