Top | 研究室紹介 | メンバー紹介 | 研究室業績 | 学会関連 | 関連情報 | イベント | English


    効率的な楕円曲線上のスカラー倍算


    
    現在, インターネット上に様々なサービスが提供されるようになった結果, ネットワーク
    上に様々な情報が流れるようになった. このようなインターネット社会の懸念として, 
    情報の盗聴, 成りすましによる不正操作などが新しい問題が発生しており, これらの問題を
    解決する暗号技術は重要性を増してきている. 暗号技術は大きく分けて共通鍵方式と公開鍵
    方式に分類できる. 
    共通鍵方式は, 暗号化と復号で同じ鍵を使用する. このため利用者間で
    鍵を送受信する際に安全に鍵配送する必要があり, また通信相手ごとに異なる鍵を用意する
    必要があるため, 通信の相手が増加するにつれ鍵の管理が困難になる.
    これに対し公開鍵方式は, 暗号化で使う鍵と復号で使う鍵が異なる. 暗号化鍵を公開する
    ため鍵配送の問題はなく, 利用者は自分の復号鍵を管理すればよいという長所を持つ.
    公開鍵暗号方式は, 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 
    攻撃に耐性を持ちつつ, 既知の対策に比べより少ない計算量でスカラー倍算を実行できた.
    
    


    【戻る】