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


    共通鍵暗号の安全性についての研究


    近年のインターネットの爆発的な普及により,情報の価値が見直されるようにな
    った.そのためネットワーク社会では情報の盗聴,改竄,不正アクセスなどの情
    報セキュリティに関する問題が重要なウェイトをしめているといっても過言では
    ない.暗号は情報セキュリティの中でも根幹をなす技術として知られている.暗
    号は情報にスクランブルをかけ,情報が他者に漏洩することを保護することが出
    来る技術である.その暗号技術のひとつに共通鍵ブロック暗号がある.
    
    共通鍵ブロック暗号は排他的論理和や加算,減算,乗算,巡回シフトなどの比較
    的単純な演算で構成されデータを共通の鍵で単純な暗号化関数の繰り返しにより
    攪拌する暗号であるため,数論に基づく公開鍵暗号に比べて非常にコンパクトか
    つ高速に動作する.そのため,ICカードや携帯電話などの低速なCPUの機器や大
    量データの暗号化に利用される.共通鍵暗号の安全性は全数探索より効率的に解
    読が可能な段数で計り,n段攻撃可能とはn段まで全数探索よりも早く解読できる
    ことを意味する.共通鍵ブロック暗号ではさまざまな種類のアルゴリズムが提案
    されているが,本研究ではRC6と言われるアルゴリズムについて安全性の評価を
    行なう.
    
    RC6はRivestらによって提案された共通鍵ブロック暗号方式であり,米国商務省標準技術
    局によって選定される次世代暗号化標準規格(AES)の最終候補の1つだった.
    RC6は算術演算とビットシフトからなるソフトウェア実装向きの仕様のためAES
    の候補のなかではソフトウェア実装において最速の処理が実現できた.wワー
    ドサイズ,rラウンド数,bビットのRC6は一般にRC6-w/r/bのように記述さ
    れる.また,r=20, w=32, b=128, 192, 256が推奨される値である.なお,
    RC6-32は単にRC6と表す.RC6の安全性についてはさまざまな研究が行なわれてい
    るがその中でも特にKnudsenとMeierが2000年に統計的な弱点を利用したカイ2乗攻
    撃が有効であることを示した.その後,RC6においてはカイ2乗攻撃における発表
    が多くなされた.
    KnudsenとMeierは開始ラウンドでのF関数による巡回シフトが0になるようにとる
    ことで鍵を推測した.下山らは,カイ2乗攻撃を使ったDistinguish攻撃の理論的
    な耐性を示した.松中はKey Recovery攻撃の成功確率をDisinguish攻撃の結果を
    用いて理論的に導出する方法を示した.これらの結果よりカイ2乗攻撃の成功確
    率は理論的に求めることができる.また,RC6Pにおいて最終ラウンドから1段復
    号したときのカイ2乗値を求めることによって鍵を推測した.さらに高野らは
    RC6PでのKey Recoveryアルゴリズムを最終段の巡回シフトが0にすることで最終
    段の鍵を推測するように拡張してRC6に対して適用し,RC6/16/192,RC6/16/256
    が総当り攻撃よりも効率よく解読可能であることを示した.
    
    既存研究では基本的な考え方はローテーションシフト量を0に固定して偏
    りを出すことに基づいている.しかし,この考え方では解読に必要な計算量が増加
    する問題がある.既存研究では最終拡大鍵を両方同時に求めているために計算量,
    メモリは膨大になる.そのために本研究では解読に必要な計算量,メモリを削減
    するためにカイ2乗攻撃でのアルゴリズムを改良し効率化を試みた.
    
    既存のアルゴリズムで計算量,メモリが膨大になる要因としてキーリカバ
    リーする鍵のビット数にある.そこで1度に戻す鍵のビット数を減らすために両
    側の鍵を対称ではなく非対称にキーリカバリーすることで計算量とメモリの削減
    を行なった.また,巡回シフトが0となるような集合を大きく取る,つまり鍵を
    粗く篩うことで計算量の削減を実現した.さらに既存のアルゴリズムでは検定す
    るビット位置は対称でなければならなかったが非対称な位置で検定を行なっても
    キーリカバリーが行えることを確認した.
    


    【戻る】