RSAファクタリングチャレンジ

RSA因数分解チャレンジは、1991年3月18日[ 1 ]にRSA研究所が提起したチャレンジで、計算数論の研究と、大きな整数の因数分解や暗号化で使用されるRSA鍵の解読の実際的な困難さを奨励することを目的としていました。彼らはRSA数と呼ばれる半素数（ちょうど2つの素因数を持つ数）のリストを公開し、それらの因数分解に成功した人に賞金を出しました。そのうちの最小の数であるRSA-100と呼ばれる100桁の数は、 1991年4月1日までに因数分解されました。より大きな数の多くは未だ因数分解されておらず、当分の間因数分解されないままであると予想されていますが、量子コンピュータの進歩により、ショアのアルゴリズムのためにこの予測は不確実になっています。

2001年、RSA研究所は因数分解チャレンジを拡大し、576ビットから2048ビットまでの数を因数分解した人に1万ドルから20万ドルの賞金を用意した。[ 2 ] [ 3 ] [ 4 ]

RSA因数分解チャレンジは2007年に終了しました。[ 5 ] RSA研究所は、「現在、業界では共通対称鍵および公開鍵アルゴリズムの暗号解読強度に関する理解がかなり進んでいるため、これらのチャレンジはもう行われていません。」と述べています。 [ 6 ] 2007年にチャレンジが終了した時点で、2001年のチャレンジ番号から因数分解されたのはRSA-576とRSA-640のみでした。[ 7 ]

因数分解チャレンジは、整数因数分解の最先端技術を追跡することを目的としていました。主な応用分野は、RSA公開鍵暗号方式の鍵長の選択です。このチャレンジの進展は、どの鍵長が安全であり、どの程度の期間安全であるかについての洞察を与えるはずです。RSAラボラトリーズはRSAベースの製品のプロバイダーであるため、このチャレンジは学術コミュニティがRSAソリューションの中核を攻撃し、その強度を証明するためのインセンティブとして利用されました。

RSA番号は、ネットワーク接続を一切行っていないコンピュータ上で生成されました。その後、コンピュータのハードドライブは破壊され、因数分解チャレンジの解法に関する記録はどこにも残らないようにしました。[ 6 ]

最初に生成されたRSA番号であるRSA-100からRSA-500、およびRSA-617は、10進数の桁数に基づいてラベル付けされていました。その他のRSA番号（RSA-576以降）は後に生成され、2進数の桁数に基づいてラベル付けされました。以下の表の番号は、10進数から2進数への移行にもかかわらず、昇順で並べられています。

数学

RSA研究所は、各RSA番号nに対して、次のような 素数pとqが存在すると述べています。

n = p × qです。

問題は、nのみが与えられたときに、これら 2 つの素数を見つけることです。

賞と記録

以下の表は、すべてのRSA番号の概要を示しています。RSA因数分解チャレンジは2007年に終了しており[ 5 ]、これより大きな数字を因数分解しても賞金は授与されません。

白線のチャレンジ番号は元のチャレンジの一部であり、10進数で表されますが、黄色の線のチャレンジ番号は2001年の拡張の一部であり、2進数で表されます。
RSA番号 小数点 2進数 賞金提供 考慮される 因数分解
RSA100100 330 1,000米ドル[ 8 ]1991年4月1日[ 9 ]アリエン・K・レンストラ
RSA110110 364 4,429米ドル[ 8 ]1992年4月14日[ 9 ]アリジェン・K・レンストラとMS・マナッセ
RSA120120 397 5,898米ドル[ 8 ]1993年7月9日[ 10 ]T. デニー他
RSA129 [ a ]129 426 100米ドル 1994年4月26日[ 9 ]Arjen K. Lenstra他
RSA130130 430 14,527米ドル[ 8 ]1996年4月10日 Arjen K. Lenstra他
RSA140140 463 17,226米ドル 1999年2月2日 Herman te Riele他
RSA150150 496   2004年4月16日 青木一麿他
RSA155155 512 9,383米ドル[ 8 ]1999年8月22日 Herman te Riele他
RSA160160 530   2003年4月1日 イェンス・フランケら。、ボン大学
RSA170 [ b ]170 563   2009年12月29日 D. Bonenberger と M. Krone [ c ]
RSA576174 576 1万ドル 2003年12月3日 イェンス・フランケら。、ボン大学
RSA180 [ b ]180 596   2010年5月8日 SA ダニロフと IA ポポヴィアン、モスクワ州立大学[ 11 ]
RSA190 [ b ]190 629   2010年11月8日 A.ティモフィーエフとIAポポビアン
RSA640193 640 2万ドル 2005年11月2日 イェンス・フランケら。、ボン大学
RSA200 [ b ]  ?200 663   2005年5月9日 イェンス・フランケら。、ボン大学
RSA210 [ b ]210 696 2013年9月26日[ 12 ]ライアン・プロッパー
RSA704 [ b ]212 704 3万ドル 2012年7月2日シー・バイ、エマニュエル・トーメ、ポール・ジマーマン
RSA220 [ b ]220 729   2016年5月13日 S. バイ、P. ゴードリー、A. クルッパ、E. トーメ、P. ツィンマーマン
RSA230 [ b ]230 762   2018年8月15日 サミュエル・S・グロス、Noblis, Inc.
RSA232 [ b ]232 768   2020年2月17日[ 13 ]NL ザマラシキン、DA ゼルトコフ、SA マトヴェエフ。
RSA768 [ b ]232 768 5万ドル 2009年12月12日 トルステン・クラインジュンら。[ 14 ]
RSA240 [ b ]240 795   2019年12月2日[ 15 ]F. ブドー、P. ゴードリー、A. ギレヴィック、N. ヘニンガー、E. トーメ、P. ツィマーマン
RSA250 [ b ]250 829   2020年2月28日[ 16 ]F. ブドー、P. ゴードリー、A. ギレヴィック、N. ヘニンガー、E. トーメ、P. ツィマーマン
RSA260260 862  
RSA270270 895  
RSA896270 896 75,000米ドル[ d ]
RSA280280 928  
RSA290290 962  
RSA300300 995  
RSA309309 1024  
RSA1024309 1024 10万ドル[ d ]
RSA310310 1028  
RSA320320 1061  
RSA330330 1094  
RSA340340 1128  
RSA350350 1161  
RSA360360 1194  
RSA370370 1227  
RSA380380 1261  
RSA390390 1294  
RSA400400 1327  
RSA410410 1360  
RSA420420 1393  
RSA430430 1427  
RSA440440 1460  
RSA450450 1493  
RSA460460 1526  
RSA1536463 1536 15万ドル[ d ]
RSA470470 1559  
RSA480480 1593  
RSA490490 1626  
RSA500500 1659  
RSA617617 2048  
RSA2048617 2048 20万ドル[ d ]
  1. ^ RSA-129 は RSA Factoring Challenge の一部ではありませんでしたが、 Scientific Americanの Martin Gardner のコラムと関連していました。
  2. ^ a b c d e f g h i j k lこの数字はチャレンジ終了後に因数分解されました。
  3. ^ RSA-170は2日後にSAダニロフとIAポポビアンによっても独立に因数分解された。 [ 11 ]
  4. ^ a b c dこの賞が授与される前にチャレンジは終了しました。

参照

注記

  1. ^バート・カリスキー (1991 年 3 月 18 日)。『「RSAファクタリングチャレンジ」開催のお知らせ』. 2023年8月11日時点のオリジナルよりアーカイブ。2021年3月8日閲覧。
  2. ^レイデン、ジョン（2001年7月25日）「RSAが20万ドルの暗号チャレンジを提起」 The Register 。 2021年3月8日閲覧。
  3. ^ RSA Laboratories. 「The New RSA Factoring Challenge」 . 2001年7月14日時点のオリジナルよりアーカイブ。
  4. ^ RSA Laboratories. 「RSAチャレンジ番号」 . 2001年8月5日時点のオリジナルよりアーカイブ。
  5. ^ a b RSA Laboratories. 「RSA Factoring Challenge」 . 2013年9月21日時点のオリジナルよりアーカイブ。2008年8月5日閲覧。
  6. ^ a b RSA Laboratories. 「RSA Factoring Challenge FAQ」 . 2013年9月21日時点のオリジナルよりアーカイブ。2008年8月5日閲覧。
  7. ^ RSA Laboratories. 「RSAチャレンジ番号」 . 2013年9月21日時点のオリジナルよりアーカイブ。2008年8月5日閲覧。
  8. ^ a b c d e「RSAデータセキュリティファクタリングチャレンジの現状/ニュースレポート（2000年3月30日現在）」 2002年1月30日。
  9. ^ a b c RSA名誉ロール
  10. ^ Denny, T.; Dodson, B.; Lenstra, AK; Manasse, MS (1994). RSA-120の因数分解について.暗号学の進歩 – CRYPTO' 93.コンピュータサイエンス講義ノート. 第773巻. pp.  166– 174. doi : 10.1007/3-540-48329-2_15 . ISBN 978-3-540-57766-9。
  11. ^ a b Danilov, SA; Popovyan, IA (2010年5月9日). 「RSA-180の因数分解」(PDF) . Cryptology ePrint Archive .
  12. ^ RSA-210 因数分解、mersenneforum.org
  13. ^ INM RASニュース
  14. ^クラインユング、トルステン;青木一麿；他。 （2010年）。「768 ビット RSA モジュラスの因数分解」(PDF)。タル・ラビン編（編）。暗号学の進歩 – CRYPTO 2010。ベルリン、ハイデルベルク：シュプリンガー ベルリン ハイデルベルク。 pp.  333–350。土井: 10.1007/978-3-642-14623-7_18。ISBN 978-3-642-14623-7。
  15. ^ Thomé, Emmanuel (2019年12月2日). 「795ビット因数分解と離散対数」 . cado-nfs-discuss (メーリングリスト).
  16. ^ Zimmermann, Paul (2020年2月28日). 「RSA-250の因数分解」 . cado-nfs-discuss (メーリングリスト).
「 https://en.wikipedia.org/w/index.php?title=RSA_Factoring_Challenge&oldid=1319804293」より取得