効率的な楕円曲線上のスカラー倍算
現在, インターネット上に様々なサービスが提供されるようになった結果, ネットワーク上に様々な情報が流れるようになった. このようなインターネット社会の懸念として, 情報の盗聴, 成りすましによる不正操作などが新しい問題が発生しており, これらの問題を解決する暗号技術は重要性を増してきている. 暗号技術は大きく分けて共通鍵方式と公開鍵方式に分類できる.
共通鍵方式は, 暗号化と復号で同じ鍵を使用する. このため利用者間で鍵を送受信する際に安全に鍵配送する必要があり, また通信相手ごとに異なる鍵を用意する必要があるため, 通信の相手が増加するにつれ鍵の管理が困難になる. これに対し公開鍵方式は, 暗号化で使う鍵と復号で使う鍵が異なる. 暗号化鍵を公開するため鍵配送の問題はなく, 利用者は自分の復号鍵を管理すればよいという長所を持つ. 公開鍵暗号方式は, Diffie とHellman によって提案された概念であり, その後Ron Rivest, Adi Shamir とLen Adleman にによって実現された. この暗号方式をRSA 暗号と呼ぶ.
楕円曲線暗号はMillar らが提案した暗号で, 楕円曲線上の離散対数問題を安全性の根拠とする公開鍵暗号である. 従来のRSA 暗号に比べ, 短い鍵長で高い安全性を保持できるため, スマートカードのような搭載メモリが制限されたデバイスに応用されている. スマートカード等の楕円曲線暗号の実装では秘密鍵は耐タンパ性デバイスの中に保持される. 情報を破壊することなしにカードからキーを取り出すのは不可能とされている. これに対する脅威としてサイドチャネル攻撃がある. サイドチャネル攻撃は暗号処理中の消費電力や, サイドチャネル情報と呼ばれる情報, 特に消費電力情報を使い秘密鍵を求める攻撃である. 消費電力を使うサイドチャネル攻撃は単純電力解析攻撃(SPA), 差分電力解析攻撃(DPA) に分類できる. SPA はスカラー倍算の消費電力の曲線を解析することで, スマートカード内の秘密鍵を求める攻撃である. DPA は秘密鍵の仮定をしてシミュレーションを行い, 消費電力の差分をとることで秘密鍵を求める攻撃である.
今日デバイスやメモリにエラーを引き起こすための様々な方法が報告されている. Bonehらは1997 年, 新しいSide Chanel Attack: Fault Attack が報告した. これはデバイス内の秘密鍵を復元するためにRSA 暗号の計算中のエラーを使う方法である. Biel らはこれを楕円曲線上のスカラー倍算に応用した. Ciet らはデバイス内のメモリに記憶されているシステムパラメータ(体K, 楕円曲線を定義するa, b, ベースポイントP の座標) にエラーを引き起こすことでd を復元できる可能性について述べた. 通常, 楕円曲線を定義するシステムパラメータは, デバイス内の不揮発性メモリに記憶され, 暗号化・復号の計算が実行される時にワーキングメモリに転送される. Permanent Faults 攻撃は不揮発性メモリ上でエラーを引き起こし, システムパラメータを改ざんすることで秘密鍵d を復元する攻撃である. 対処法としては, 全てのシステムパラメータのダイジェスト値(例. CRC) を不揮発性メモリ内に保持しておき, 計算時に使用するシステムパラメータのダイジェスト値との比較を行なう. もし値が同じならば計算結果を出力し, 異なればエラーを出力することで攻撃を防げる. TransientFaults は, 不揮発性メモリからワーキングメモリにデータを転送する時にエラーを引き起こし秘密鍵d を復元する攻撃である. 対処法として, 計算結果の出力時, dP がデバイスに実装された楕円曲線上にあるか確認する, もしこの曲線上の点ならば計算結果を出力し, そうでなかったならばエラーを出力することで攻撃を防げる. 以上のFault Attack はスカラー倍算の計算にエラーを起こさせるものでありエラーが起こされた計算はオリジナルの曲線上では行なわれない.
これらに対し, Sign Change Faults 攻撃はデバイスに実装されている楕円曲線を変化させないため, 従来のFaults 攻撃の対策手法であったシステムパラメータをチェックする方法が有効ではない. Sing Change Faults 攻撃の対策手法としては, 2 つの楕円曲線を使用する方法, ランダム化線形変換座標を利用する方法があるが, 計算量が増大する欠点がある. 本稿では, 単位元に無限遠点ではなく, これとは別の三重接点を選び, 楕円曲線上の加法を提案する. 新しい提案手法はSign Change Fault 攻撃に耐性を持ちつつ, 既知の対策に比べより少ない計算量でスカラー倍算を実行できた.