世界初！ IPAがストリーム暗号「Toyocrypt」を解読

IPAは、世界で初めて、ストリーム暗号の代数的性質を利用した世界最速の解読プログラムの開発に成功したと発表した。

[谷古宇浩司，＠IT]

　独立行政法人 情報処理推進機構（IPA）は9月26日、世界で初めてストリーム暗号（携帯情報機器などの使用される暗号）の代数的性質を利用した世界最速の解読プログラムの開発に成功したと発表した。解読したのは東洋通信機が発明した「Toyocrypt」。解読成功日は9月20日。

IPA セキュリティセンター暗号グループ 研究員 杉田誠氏

　IPAによると、近年、欧・米・アジアの暗号にかかわる国際学術会議では、ストリーム暗号「Toyocrypt」の解読の可能性が主要な論点となっていたという。ストリーム暗号は、暗号化する前の平文を1ビット、または数ビットごとに暗号化・復号化を行う方法で、そのアルゴリズムは暗号鍵から鍵系列と呼ばれる擬似乱数を生成し、それにより平文を逐次暗号化していくものだ。

　このような性質を持つストリーム暗号や一部の公開鍵暗号を解読する方法として、最近話題になっているのが、多次多変数の連立方程式を解くことで鍵の推定をする「代数的攻撃」という手法である。IPAではこの代数的攻撃手法に対する安全性の評価手法を確立する目的で、セキュリティセンター暗号グループ内に「暗号解読プロジェクト」を立ち上げた。

　安全性の評価手法確立にあたり、暗号解読プロジェクトでは、その攻撃に用いられる「グレブナー基底探索アルゴリズム」（多次多変数の連立方程式の解法）プログラム「IPA-SMW」を開発、同プログラムをIPAの暗号研究専用並列コンピュータ（2GHz64ビットCPU×128）に実装した。その結果、2の21乗個の平文と暗号文の対から暗号に用いられた128ビットの秘密鍵を27分で算出することに成功。現在では20分程度にまで解読速度が短縮されている。

　IPAは、今回のプロジェクトで開発したグレブナー基底探索プログラム（IPA-SMW）をほかの暗号アルゴリズムにも適用し、電子政府推奨暗号などの各種暗号アルゴリズムの安全評価を行っていく予定。なお、IPAの暗号解読プロジェクトは、IPAの研究員である 杉田誠氏とIPA認定スーパークリエータに認定されている2人のプログラマで構成されている。