RSA-129
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/06/15 05:03 UTC 版)
1977年、マーティン・ガードナーがコラムを連載していたサイエンティフィック・アメリカン誌に129桁の合成数 n と公開鍵 e=9007 を使ったRSA方式で暗号化されたメッセージを掲載した。解読が成功した者にマサチューセッツ工科大学から100米ドルを与えるという懸賞金問題だった。当時、解読には2万年は必要だろうと予測されていた。掲載から16年後に、オックスフォード大ポール・レイランド(英語版)、アイオワ州立大マイケル・グラフ、マサチューセッツ工科大学デレク・アトキンス、アリエン・レンストラ(英語版)らが、インターネット上で(南極大陸を除くすべての大陸から20か国以上の)約600名のボランティアの協力を得て、二次ふるい法によってRSA-129に対する大規模攻撃を開始した。8か月で800万以上の下位問題が解かれ、得られた50万行50万列以上の疎行列から188614行188160列の行列による連立方程式を作った。これをスーパーコンピュータMP-1で45時間をかけて構造的ガウスの消去法によって解き、解読に成功した(1994年4月)。答えは“The magic words are squeamish ossifrage”[ossifrage(ヒゲワシ)はジョークで「骨折り」の意]。
※この「RSA-129」の解説は、「RSA暗号」の解説の一部です。
「RSA-129」を含む「RSA暗号」の記事については、「RSA暗号」の概要を参照ください。
- RSA-129のページへのリンク