Loading article…
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番号は、ネットワーク接続のないコンピュータで生成されました。その後、コンピュータのハードドライブは破壊され、因数分解チャレンジの解答の記録はどこにも残らないようにしました。[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-129 は RSA 因数分解チャレンジの一部ではありませんでしたが、 Scientific Americanの Martin Gardner のコラムに関連していました。
- ^ abcdefghijkl この数字はチャレンジ終了後に因数分解されました。
- ^ RSA-170は2日後にSAダニロフとIAポポビアンによっても独立に因数分解された。[11]
- ^ abcd この賞が授与される前にチャレンジは終了しました。
参照
- RSA番号、その数の10進展開、既知の因数分解
- LC35 について
- 魔法の言葉は、1977年に出された別のRSAチャレンジに対する1993年に発見された解決策であるSqueamish Ossifrageです。
- RSA 秘密鍵チャレンジ
- 整数因数分解レコード
注記
- ^ バート・カリスキー (1991 年 3 月 18 日)。 「『RSAファクタリングチャレンジ』開催のお知らせ」2021 年3 月 8 日に取得。[リンク切れ ]
- ^ レイデン、ジョン（2001年7月25日）。「RSAが20万ドルの暗号チャレンジを提起」。The Register 。 2021年3月8日閲覧。
- ^ RSA Laboratories. 「新しい RSA ファクタリングの課題」。2001 年 7 月 14 日時点のオリジナルよりアーカイブ。
- ^ RSA Laboratories. 「RSA チャレンジ番号」。2001 年 8 月 5 日時点のオリジナルよりアーカイブ。
- ^ ab RSA Laboratories. 「RSA Factoring Challenge」。2013年9月21日時点のオリジナルよりアーカイブ。2008年8月5日閲覧。
- ^ ab RSA Laboratories. 「RSA Factoring Challenge FAQ」。2013年9月21日時点のオリジナルよりアーカイブ。2008年8月5日閲覧。
- ^ RSA Laboratories. 「RSA Challenge Numbers」。2013年9月21日時点のオリジナルよりアーカイブ。2008年8月5日閲覧。
- ^ abcde 「RSA データセキュリティファクタリングチャレンジに関する状況/ニュースレポート (2000 年 3 月 30 日現在)」。 2002 年 1 月 30 日。
- ^ abc RSA 名誉ロール
- ^ 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。
- ^ ab Danilov, SA; Popovyan, IA (2010 年 5 月 9 日). 「RSA-180 の因数分解」(PDF) . Cryptology ePrint Archive .
- ^ RSA-210 因数分解、mersenneforum.org
- ^ INM RAS ニュース
- ^ Kleinjung, Thomas (2010 年 2 月 18 日). 「768 ビット RSA 係数の因数分解」(PDF)。
{{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です - ^ Thomé, Emmanuel (2019 年 12 月 2 日). 「795 ビット因数分解と離散対数」. cado-nfs-discuss (メーリング リスト).
- ^ Zimmermann, Paul (2020年2月28日). 「RSA-250の因数分解」. cado-nfs-discuss (メーリングリスト).