press_IPA-SMW_20050926.html

　「Toyocrypt」は、2000年当時、実質的に永遠に解けない暗号として電子政府推奨暗号候補として提案されましたが採択にいたらなかったものです。近年、欧米亜の暗号に係る国際学術会議において、世界的な研究者間でこの暗号の解読可能性がひとつの主要な論点となっていました。新たに代数的攻撃手法を適用することで理論的に解読可能との研究結果が発表されるなど注目を浴びていますが、解読には高度なプログラミング能力と高速のコンピュータが必要なため、計算機を利用して実際に解読した実証例は皆無でした。
　IPAは、代数的攻撃手法に対する暗号の安全性評価手法を確立するために、IPAが認定したスーパークリエータらを起用し、暗号解読プロジェクトを立ち上げました。プロジェクトの活動の一環として、代数的攻撃に用いる、多次多変数連立方程式の解法 (グレブナー基底探索アルゴリズム)によるプログラム(「IPA-SMW」)を開発しました。これを、IPAが所有する暗号研究専用として使用する世界最高レベルの並列コンピュータ(グリッドコンピュータ)上で高速化および最適化を行った上で、Toyocryptの解読に適用し、世界で初めて、27分間という極めて短い時間での解読に成功しました。
　今後は、このIPA-SMWを用いて、継続的に電子政府推奨暗号等の安全性評価を行っていく予定です。

　2005年9月20日(火)、IPAセキュリティセンター暗号グループは、暗号の安全性解析を行うプロジェクトの一環として、世界最速の、ストリーム暗号※1の代数的性質を利用した鍵探索プログラムを開発し、世界で初めて「Toyocrypt」 (東洋通信機株式会社が発明したストリーム暗号)の解読に適用し、実際に解読可能である事を実証しました。

　近年Algebraic Attack（代数的攻撃）※2と呼ばれる解読法が提案され、この方法を用いたToyocryptや, E0(無線システムBluetooth ※3に用いられているストリーム暗号)などへの具体的な解読手法の理論が報告されています。このため、代数的攻撃によるストリーム暗号などに関する実質的な脅威を検証する必要が生じ、この安全性の評価手法の確立が電子政府推奨暗号の安全性確保のためにも強く求められていました。

　電子政府推奨暗号の安全性評価を行っているIPAでは、2004年にストリーム暗号の安全性の評価手法の開発を主たる目的とし、IPAの未踏ソフトウェア創造事業の中で「IPA認定スーパークリエータ(天才クリエータ)※4」に認定された世界最高レベルのプログラミング能力を誇る光成滋生氏(ユーテン・ネットワークス株式会社)※5、渡辺秀行氏(株式会社アイビス)※6、IPA研究員の杉田を起用した暗号解読プロジェクトを立ち上げました。
　本プロジェクトでは、代数的攻撃手法に対する安全性の評価手法を確立するにあたり、その攻撃に用いるグレブナー基底探索アルゴリズム※7の開発を行い、2004年下期に、グレブナー基底探索プログラム( IPA-SMW )を、IPAが所持する世界最高レベルの性能を持つとされる暗号研究専用に使用している並列コンピュータ (グリットコンピュータ) ※８に実装しました。
　IPA-SMWは、同機グレブナー基底探索プログラムとして従来の世界最高速をしのぐ高速化を達成したプログラムです。
　本IPA-SMWのソースコードは、下記のサイトで公開しております。

　　　　　URL：http://www.ipa.go.jp/security/fy16/development/crypt_stream/

　なお、IPA-SMWはIPAの立ち上げたプロジェクトで開発したプログラムで、開発者の杉田（Sugita）、光成（Mitsunari）、渡辺（Watanabe）の頭文字をとって名づけました。

　Toyocryptとは、2000年に実質上永久に解けないストリーム暗号としてCRYPTREC(総務省および経産省の共同運営による暗号技術評価プロジェクト)※9が公募した電子政府推奨暗号に東洋通信機株式会社から提案された暗号アルゴリズムです。電子政府推奨暗号としては選抜されなかったものの、本アルゴリズムは、近年、欧米亜の暗号研究者が参加する暗号に係る国際学術会議で、安全性についての多数の研究結果の発表がなされており、理論的に解読可能であることが示されています。
　その解読時間は、2002年にCRYPTRECに報告されている攻撃手法を用いた場合、IPAが所有するグリッドコンピュータを用いて実装すると想定したとしても、100億年かかる( Toyocrypt の1ビット処理を1とした場合の計算量：2⁹⁶ )と見積もることが出来ますが、近年新たに提案された代数的性質を利用した攻撃手法を用いることにより、その解読時間を大幅に短縮することが可能であることが示されています。
しかし、解読のためのプログラム作成には高度なプログラミング能力とそれを実装できる十分な環境が必要であり、これまで現実にコンピュータを利用した解読に成功した例は皆無でした。

　IPAでは、2005年上期にIPA-SMWの更なる高速化および並列最適化を行い、プログラム処理の処理時間の短縮化を行った上で、Toyocryptの解読に適用し、Toyocryptの鍵探索プログラムを実装し、解読を試みた結果、極めて短時間で解読可能であることを実証しました。
　　(結果)　27分で解読に成功
2²¹ ビットの平文と暗号文の対から、暗号化に用いられた鍵(128ビット)の算出に成功

　今後は、本プロジェクトにより開発したグレブナー基底探索プログラム（IPA-SMW）を、他の暗号アルゴリズムにも適用し、電子政府推奨暗号等の各種暗号アルゴリズムなどの安全性評価を行っていく予定です。

平文を 1 ビット、または数ビットごとに暗号化・復号を行う方法。そのアルゴリズムは、暗号鍵から鍵系列と呼ばれる擬似乱数を生成し、擬似乱数により平文を逐次暗号化していくものです。

近年話題になった暗号の強力な解読法で、多次多変数の連立方程式を解くことにより鍵の推定をする方法。

この方法は、ストリーム暗号や一部の公開鍵暗号に有効であるとされており、電子政府推奨暗号などの解読にも有効である可能性があるという報告さ近年発表されており、大きな話題となりました。

Ericsson 社、 IBM 社、 Intel 社、 Nokia 社、東芝の 5 社が中心となって提唱している携帯情報機器向けの無線通信技術。ノートパソコンや PDA 、携帯電話などでケーブルを使わずに接続し、音声やデータをやりとりすることができます

IPA の未踏ソフトウェア創造事業において、個人または数名のグループを対象として、次世代の IT 市場創出を担う独創性と優れた能力を持つ研究者（スーパークリエーター）を積極的に発掘しています。渡辺秀行氏と光成滋生氏は 2003 年度のスーパークリエーターに選ばれました。

多次多変数の連立方程式の解法であり、全ての連立方程式の解法が数学的に「グレブナー基底探索」に帰着されます。この探索の代表的なアルゴリズムとしてブッフベルガーアルゴリズム、 F4 アルゴリズム、 F5 アルゴリズムがあります。

※8 暗号研究専用並列コンピュータ ( グリッドコンピュータ )

IPA では、現在、世界最高レベルの性能を持つ暗号の研究専用の並列コンピュータを所有しており、このコンピュータの性能として、近年の 64 ビット CPU (2GHz) の高機能コンピュータの性能を1とした場合 128 倍 (128 台分の並列処理 ) の能力を持ちます。

総務省および経済産業省が共同で開催している暗号技術検討会と、情報通信研究機構 (NICT) および情報処理推進機構 (IPA) が共同で開催する暗号技術監視委員会および暗号モジュール委員会によって構成される暗号技術評価プロジェクトです。

■本件に関するお問い合わせ先

独立行政法人情報処理推進機構　セキュリティセンター・杉田／大久保

Tel:03-5978-7508 Fax:03-5978-7518 E-mail:

■報道関係からのお問い合わせ先

独立行政法人情報処理推進機構　戦略企画部広報グループ　高瀬／横山　

Tel: 03-5978-7503 Fax:03-5978-7510 E-mail:

		トップ\|電子申請\|お問い合わせ\|サイトマップ
		サイト内検索


ご利用条件　　プライバシーポリシー	Copyright(c) Information-technology Promotion Agency, Japan. All rights reserved 2005