創立50周年記念特集：情報処理技術の未来地図　17．我々をとりまく情報社会と暗号危殆化のかかわり

全文

(1)50 17. th Anniversary Information Processing Society of Japan. 我々をとりまく情報社会と暗号危殆化のかかわり. l(bit). 猪俣敦夫（奈良先端科学技術大学院大学）・岡本栄司（筑波大学）. 情報伝達を安全に確立するための要素の 1 つである暗号は，情報と社会の橋渡しを行うために重要な役割を担っている．しかし，暗号が施された文書が数日のうちに解読されてしまうようでは，これは安全な状態であるとは言えない．そして，暗号の安全性がどの程度必要であるか，という問いに簡単に答えることはできない．たとえば，それが 3 日間あるいは数年のうちに解読される可能性が少しでもあるならばそれが安全であると言えるだろうか，画期的な解読アルゴリズムや完全な量子計算機が登場し. 要素技術. たらどうであろうか．インターネットを始めとして，我々を取り巻くさまざ. 図 -1 RSA 暗号危殆化曲線. まな場面において公開鍵暗号が使われている．我々はこれからの社会に. t(ywar). おいて暗号の危殆化を少なからず認識しておくことは重要である．. ている．我が国においても 2000 年より安全性および実装性に優れた暗号. 暗号解読と危殆化：これは，暗号の強度が時間経過とともに脆弱化して. をリスト化するプロジェクト（CRYPTREC）が組織化され，定期的に暗号技. いくことを意味する．たとえば，多項式時間内で解読するアルゴリズムが. 術監視委員会報告書および暗号モジュール委員会報告書を公開している．. 発見された場合には比較的短い時間で解読ができる可能性が高くなる，こ. 2003 年 2 月には，電子政府における調達のための電子政府推奨暗号リスト. れが暗号危殆化である．RSA の開発者の 1 人である Rivest は，1977 年に. を公表したが，すでに共通鍵暗号ではブロック暗号，ストリーム暗号とも. 125 桁の因数分解には 40,000 兆年かかるだろうと述べていたように RSA. に 128bit 以上など 2013 年以降を考慮した新しい推奨暗号を公開するため. の安全性は強固なものとされていた．しかし，素因数分解に関する研究は. の公募を進めている．また，ハッシュ関数についても衝突事例の報告から. 急速に進展し，合成数 n に含まれる最小素因数サイズに依存して実行時. SHA-1 から SHA-2 への移行も進んでおり，2011 年には公表される予定で. 間が決まるアルゴリズムとして試行割算法やρ法，楕円曲線法（ECM）が. ある．一方，暗号モジュールの安全性評価と認定の仕組みも存在し，暗号. 生み出され，さらに n のサイズに依存して実行時間が決まるアルゴリズ. モジュール実装について規定した FIPS140-2 準拠であるかの評価手段とし. ，数ムとして Lehman 法や連分数法，2 次ふるい法（Quadratic Sieve : QS）. て 1995 年に CMVP と呼ばれる評価プログラムが制定され，第三者の試験. 体ふるい法（Number Field Sieve : NFS）が発見された．現在，RSA で使わ. 機関での暗号モジュールテストラボで厳しい審査が行われている．国内で. れている大きな素因数のみを持った合成数に対する最も高速な解読アル. も（独）情報処理推進機構（IPA）により暗号モジュール試験および認証制度. ゴリズムは数体ふるい法とされており，その計算量オーダは合成数を n と. （JCMVP）の運用が開始され，一例としてサイドチャネル攻撃用標準評価ボ. O ] e ] 64/9. すると. ]. g + o ] l g) ] ln n g (lnln n) 1/3. 1/3. 2/3. g. g となる．これは. が JCMVP レベル 1 認証を取得しており，今後，ますます適ード（SASEBO）正かつ厳正な暗号技術の評価体制が確立されるものと思われる．. 準指数時間アルゴリズムであり，今のところ量子計算機を除いて，多項式. 暗号の置き換え：上図より 1024bit では完全に危殆化状態であるのは明. 時間で素因数分解問題を解く方法は知られていない．ところで，現在最. らかである．もちろん 2048bit まで伸張すればおおよそ 30 数年は耐え得. も使われている鍵長の大きさはたかだか 1024bit の大きさである．このた. る可能性があることは示したが，計算量の視点から省メモリ・省力化を考. め数年のうちに暗号危殆化は非常に大きな局面を迎えることになるのは確. 慮し，今後，RSA や Elgamal 暗号のようによく使われる素体の乗法群上. 実である．このように暗号危殆化は国際的にも急務な課題である．こうし. の離散対数問題をベースにした方式をとるのではなく，楕円曲線群を用い. た背景の下，Lenstra と Verheul は，素因数分解に対する RSA の安全性を. ることで署名長を短く構成できる楕円曲線暗号への置き換えも考慮する必. DES の安全性と対比させて検討した 1）．彼らは RSA 危殆化の進行を踏. 要があるだろう．これからの情報社会において暗号危殆化を適切に理解. まえ DES の安全性がきわめて高かった時期を 1982 年と想定し，その時. し，新しい暗号系へのスムーズな移行計画を検討しておくことは重要かつ. 点での DES の安全性と等価であるためには RSA の鍵長サイズがどれだ. 急務な課題である．. け必要であるかを，1．安全性の基準，2．単位コストあたりの計算量，3．解読にかける予算，4．解読アルゴリズムの進化，の 4 つの評価指標を定義して分析している．筆者らも，計算機の進化速度としてムーアの法則を基に RSA 解読予想年について定式化を行った 2），3）．t を解読が予想され（基準年），l を鍵長サイズ（bit），る年，t0 をある鍵長サイズが解読された年 a を t=t0 における計算速度，K を暗号解読時間，c を暗号解読定数とするとt. =. 1 2 3 a$K (l 3 log 3 l - log ( )) + t 0と表せる．解 2 log 2 c. 参考文献 1） Lenstra, A. K. and Verheul, E. R.：Selecting Cryptographic Key Size, Journal of Cryptology, Springer, Vol.14-4, pp.255-293 (2001)． 2）岡本栄司，松浦幹太，冨高政治，猪俣敦夫：暗号における脆弱性について，情報処理，Vol.46, No.6, pp.625-629 (June 2005)． 3）猪俣敦夫，大山義仁，岡本栄司：暗号危殆化に対する暗号 SLA の提案と支援ツールの実現，情報処理学会論文誌，Vol.48, No.1, pp.178-188 (Jan. 2007)．（平成 21 年 10 月 31 日受付）. 読事例として RSA Challenge コンテストの結果から 576bit が解読された. 2003 年 12 月を t0 として上式を図 -1 に示す．推奨暗号：米国 NIST は，政府調達に関する暗号技術の標準について連邦情報処理規格 FIPS（Federal Information Processing Standards）を公開しており，一定期間ごとに標準暗号を見直し，すでに新しい評価指針 FIPS140-3 への移行を進めている．また，SP（Special Publications）800-57 では 2031 年までの使用に耐え得る推奨暗号アルゴリズムと鍵長の大きさについて論じ. 528. 情報処理 Vol.51 No.5 May 2010. 猪俣敦夫（正会員）● [email protected] 2002 年北陸先端科学技術大学院大学情報科学研究科博士後期課程修了．（独）科学技術振興機構を経て，現在，国立大学法人奈良先端科学技術大学院大学情報科学研究科特任准教授．博士（情報科学）．岡本栄司（フェロー会員）● [email protected] 1978 年東京工業大学電子工学専攻博士課程修了．同年日本電気（株）中央研究所，その後，北陸先端科学技術大学院大学，東邦大学を経て，現在，国立大学法人筑波大学大学院システム情報工学研究科教授．工学博士．.

(2)

創立50周年記念特集：情報処理技術の未来地図 17．我々をとりまく情報社会と暗号危殆化のかかわり

創立50周年記念特集：情報処理技術の未来地図　17．我々をとりまく情報社会と暗号危殆化のかかわり