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」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- RSA-129のページへのリンク
