公開鍵暗号は暗号鍵と復号鍵が異なるもので暗号鍵を公開し, 復号鍵を秘密にしておく暗号方式であり,
メッセージの暗号化, 復号だけでなく電子署名にも利用されている.
従来の公開鍵暗号である, RSA暗号やエルガマル暗号は, 暗号解読の改良により,
安全性が脅かされている. そのために次世代の暗号として, 楕円曲線暗号や超楕円曲線暗号の研究が盛んに行われている.
楕円曲線暗号は楕円曲線上の点が群になることを利用した暗号であり, 楕円曲線上の離散対数問題に基づく暗号で,
KoblitzとMillerによって提案された. 楕円曲線暗号はRSA暗号等に比べて鍵が短く, コンパクトに処理
できるという特徴がある. この特徴から, メモリの少ないスマートカード等で利用されている.
楕円曲線暗号の中心となる演算は暗号文の復号, 署名生成に関わらず, 楕円曲線
上の点Pと秘密鍵dに対する, スカラー倍算dPの演算である.
楕円曲線暗号の スマートカードの実装で脅威となるのはサイドチャネル攻撃
である. サイドチャネル攻撃は暗号処理中の消費電力や, 実行時間等のサイド
チャネル情報を用いて, 秘密鍵を得る攻撃である.
一般的にスカラー倍算dPを行う際は二進展開法による加算連鎖を実行する.
xはbit列で表現されているため, bitが0の場合の演算と, bitが1の場合の演算
とでは消費電力が異なるため, サイドチャネル攻撃によって
秘密鍵の情報が漏洩してしまう. その為, サイドチャネル攻撃の対策が研究されてきている.
サイドチャネル攻撃は大きく二つに分けて, 単純電力解析攻撃(SPA), 差分電力解析攻撃(DPA)がある.
SPAは演算中の消費電力の波形を一回の観察により, 秘密鍵を得る攻撃である.
SPAを防ぐには秘密情報と電力消費の依存関係をなくす必要がある.
既存の対策法としては, 演算中にダミー演算を挿入し, 波形を一定にさせる方法
がある.
DPAは秘密鍵の仮定をしてシミュレーションを行い, 本当の秘密鍵との消費電力
の差分をとることで秘密鍵を求める方法である. またDPAには, Data-bit DPA(DDPA)と
Address-bit DPA(ADPA)に大別される.
既存のDDPA対策法としてはスカラーをランダムにする方法と, ランダムな点を用
いる方法があり, ADPA対策はスカラーをランダム化する方法と, スカラーとアドレスの関係を
隠す方法がある. しかし, SPA, DDPA, ADPAに対する既存の対策法は共に計算量とメモリが増える傾向にある.
また, 各々の対策法は特定の攻撃方法でしか安全ではないという問題点がある.
本研究では, この問題点を考慮し, SPA, DDPA, ADPA共に適応できるアルゴリズムを加算連鎖を改良することで,
計算量・メモリ量も考慮した効率的なスカラー倍算dPを求めるアルゴリズムを
提案する.
本研究ではスカラー倍算法として, window法を用いる. window法は予備演算テーブ
ルを用いることで, 高速計算が可能な計算法である. 提案法では, window法にお
けるDDPA対策とADPA対策を提案する. window法に対しSPA対策を施す場合,
window幅を固定するため, テーブルサイズが大きくなる. また, DDPA対策では,
ランダムな点やデータを用いることで, テーブル作成での計算量が増加してしま
う. 提案法では, SPA対策にSide channel atomicityを適用し, DDPA対策では, スカラーをラン
ダム化する方法を用いている.
具体的には, (100\bar{8})_2=0 (\bar{8} =-8)となることを利用し, 演算するwindowごとに
表現の変換を実行するかをランダムに決定することにより, スカラーのランダム
化を行っている. このことにより, スカラー表現のランダム化が可能である. さ
らにランダム化数を増加ために, 0bitの場合にも変換の有無を乱数で与える. 通
常, window法ではwindow内のbit列の最下位bitが0の場合, 2倍算のみを行うが,
提案法では0bitにおいても, スカラー値に影響しないような加算の挿入の有無を
乱数によって行う. 0bit時での処理の選択により, ランダム化数がさらに増加す
る. 実際に計算量を犠牲にするが, 既存のスカラー表現のランダム化手法より,
ランダム化数が増加した.
また, ADPA対策はスカラーとアドレスの関係を隠す方法を用い
ている. テーブルのデータとアドレスの関係をランダムに回転させることで, 関
係を隠している. 両対策共, メモリを一つ加えることで, 対策が施されている.
提案ADPA対策は, すべてのスカラー倍算法に適用可能となる.
これらの対策に加え, SPA対策も考慮した, window法アルゴリズムを提案した.
|