20年前に提案された、およそ80兆の平方根を必要とする暗号パズルが、予想よりはるかに早く、わずか3年半で解読された。
暗号化と言っているのは、検証可能な遅延関数 [PDF] 、つまり中程度に難しい暗号化関数が含まれているからです。
この難問は、1999年に、MITコンピュータ科学・人工知能研究所（MIT CSAIL）のコンピュータサイエンス教授で、RSAのRの頭文字をとったロナルド・リベスト氏によって提示されました。彼はこの問題を次のように説明しました。
t、n、z は与えられており、非常に大きな数値です。t は 79685186856218 で、他の 2 つはそれぞれ 616 桁です。
リベスト氏は挑戦を発表する際、タイムカプセルの中身を、MIT人工知能研究所（MIT CSAILに改称）の開設から約70年後の2033年頃、もしくはパズルが解けたときのどちらか早い方に公開することを約束した。
タイムカプセルの中身はほぼ秘密です。ビル・ゲイツは、マイクロソフトの古いプログラミング言語「Altair BASIC」（レドモンドの最初の製品、1975年に開発）の関連資料を提供しました。カプセルに物を隠した他の人物には、インターネットとコンピュータネットワークの先駆者であるティム・バーナーズ＝リー卿とロバート・メトカーフもいます。
月曜日、このパズルはベルギー出身の独学Java開発者、ベルナール・ファブロ氏によって解読されました。そして、5月15日にリベスト氏によってタイムカプセルが開封され、世界に向けて公開されます。そして、秘密のメッセージが明らかになるのです。
大きな問題には賢い解決策が必要
このパズルは2 2 t (mod n) を計算するもので、n は2つの素数の2048ビット積です。この方程式を直接解くこともできますが、時間がかかりすぎます。また、この数学的な謎は、並列計算を用いて総当たり的に解くことができないように設計されています。n の因数分解を知らないと高速に計算できないためです。そして、n を因数分解できないことは当然です。
代わりに、2から始めてnを法とする連続的な2乗法を使うことができます。つまり、i>0に対してW(0) = 2 W(i+1) = (W(i) 2 ) (mod n)と設定し、W(t)を計算します。ここでtは上記の大きな数です。以下に計算例を示します。説明のために、nは253 (11 * 23)、tは10です。すると、以下の式が計算できます。
2 (2 1 ) = 2 2 = 4 (mod 253)
2 (2 2 ) = 4 2 = 16 (mod 253)
2 (2 3 ) = 16 2 = 3 (mod 253)
2 (2 4 ) = 3 2 = 9 (mod 253)
2 (2 5 ) = 9 2 = 81 (mod 253)
2 (2 6 ) = 81 2 = 236 (mod 253)
2 (2 7 ) = 236 2 = 36 (mod 253)
2 (2 8 ) = 36 2 = 31 (mod 253)
2 (2 9 ) = 31 2 = 202 (mod 253)
w = 2 (2 t ) = 2 (2 10 ) = 202 2 = 71 (mod 253)
ムーアの法則への中指
というわけで、nが253、tが10のとき、71がこの問題の魔法の因数分解です。では、実際の数値でこの演習を繰り返してみましょう。リベスト氏は、膨大な計算量とムーアの法則の影響から判断して、この問題は2034年までに解決されると予測しました。
「t の値は、ムーアの法則による計算能力の向上を考慮して選択された」と彼は課題を設定する際に書いた。
SEMATECHの半導体技術ロードマップ（1997年版）に基づくと、チップ内部の速度は、クロック周波数が約10GHzに達する2012年までに全体で約13倍に向上すると予想されます。それ以降の改善は困難と思われますが、2034年までにさらに5倍に向上できる可能性があると推定しています。したがって、全体的な計算速度は2034年までに約6倍に増加すると予想されます。
彼は、1台のコンピューターが35年間連続して稼働し続け、ハードウェアを毎年、利用可能な最速のチップにアップグレードする必要があると考えていました。しかし、彼はハードウェアの進歩を過小評価していたため、この問題は予想よりも早く解決されました。
アディ・シャミールのビザ拒否：RSAのSが自身のRSA会議でブロックされたため、米国政府は非難される
続きを読む
ファブロ氏は数行のCコードでこの方程式を記述し、フリーの数学ソフトウェアライブラリであるGNU Multiple Precision Arithmetic Libraryを用いて79兆回以上の計算を実行した。彼はIntel Core i7-6700プロセッサを搭載したごく普通のPCを使用し、79兆回を超える計算を完了するまでに約3年半を要した。
「計算自体は、ある意味では『簡単』です。同じ演算を『たった』79兆回繰り返すだけです」とファブロ氏はEl Regに語った。「ですから、ソフトウェアベースのアプローチのコードは非常に小さくなります。しかし、3年半もの間、このような計算を実行する忍耐力を持つのは容易ではないと思います。計算を再開し、進捗状況を追跡し、諦めずに続けるには、ある程度の規律が必要です。」
一方、CEOのサイモン・ペファーズ氏が率いるスープラナショナル社は、わずか61日でこのパズルを解こうとしている。ファブロ社の取り組みを知らなかったペファーズ氏とそのチームは、異なるアプローチを採用し、ザイリンクス社のVU9Pチップ（FPGA）向けに最適化された平方アルゴリズムを用いて数値を高速に計算することを選んだ。
「基本的に、FPGA向けに回路を低レイテンシ化することで、汎用CPUよりもはるかに高速に個々の平方演算を実行できるようになりました」とペファーズ氏はThe Registerに語った。「アルゴリズムの改良と専用ハードウェアのおかげで、ソフトウェアによるアプローチと比べて約10倍高速です。」®
