レンストラ氏は、11カ月にわたる分散コンピューティング・プロジェクトの末に、この難問を解くことに成功した。同氏はこの結果について、「電子商取引などで広く使われている1,024ビットのRSA暗号技術が、コンピュータと数学的手法の進歩に伴い、いずれ有効性を失うことを示している」と語る。
RSA暗号化アルゴリズムは、公開鍵と秘密鍵のシステムを使ってメッセージの暗号化と復号を行っている。公開鍵は、きわめて大きな2つの素数を掛けることで算出される。素数とは、2、3、5、7など、その数自体と1以外では割り切れない数のことだ。
公開鍵の作成に使われた2つの素数を特定できれば、秘密鍵を計算してメッセージを復号することができる。しかし、きわめて大きな整数の基になっている2つの素数を特定するのは、膨大な数のコンピュータを使って長時間演算を行わないかぎり、ほとんど不可能だ。
レンストラ氏らは今回、EPFLやボン大学などにある300～400台の市販コンピュータを使い、307ケタの整数を因数分解して2つの素数を算出することに成功した。因数分解とは、整数を素数の積にすることであり、例えば12を因数分解すると2×2×3になる。
レンストラ氏は、他の数に比べ因数分解が容易になるような特性を持つ307ケタの数を慎重に選択した。今回使われたのは、2の1,039乗から1を引いた数だった。
しかしそれでも、素数を計算するために作成した専用の数式を複数のコンピュータで処理するのに11カ月を要したという。
こうした作業の果てに、ようやく307ケタの数から作られた暗号鍵を割り出して、メッセージを読むことができたわけだが、RSA暗号化アルゴリズムを使用するシステムは、異なる鍵をそれぞれのユーザーに割り当てており、これらの鍵を破るには、素数の算出作業を繰り返さなければならない。
レンストラ氏によると、現在使われているRSAの1,024ビット公開鍵から素数成分を算出できるようになるのは5～10年先だという。公開鍵は通常、およそ150ケタの素数を2つ掛け合わせることで生成されており、今回のプロジェクトで使用された307ケタの整数よりも因数分解が難しいからだ。
レンストラ氏の次のターゲットは768ビットの公開鍵だ。「いずれは1,024ビットの公開鍵にも挑戦したい」と同氏は語っている。
(ジェレミー・カーク／IDG News Service ロンドン支局)
ローザンヌ連邦工科大学（スイス）
http://www.epfl.ch/