Loading article…
「マジックワードは気難しいオシフラージュ」は、1977年にRSA暗号の発明者らが出したチャレンジ暗号文の解答だった。この問題は、 1977年8月号のサイエンティフィック・アメリカン誌のマーティン・ガードナーの「数学ゲーム」コラムに掲載された。 [1]これは、デレク・アトキンス、マイケル・グラフ、アルジェン・レンストラ、ポール・レイランドがコーディネートした大規模な共同コンピュータプロジェクトによって1993年から1994年にかけて解決された。[2] [3] [4] [5] 600人以上のボランティアが、 6か月間にわたり約1,600台のマシン（うち2台はファックス機）からCPU時間を提供した。コーディネートはインターネット経由で行われ、この種のプロジェクトとしては最初のものだった。
オシフラージュ（ラテン語で「骨を砕くもの」の意味）は、動物の骨や生きたカメを岩の上に落として割ることで有名な腐肉食動物、ヒゲワシの古い名前です。1993年から1994年にかけての取り組みにより、暗号解読の挑戦で「気難しいオシフラージュ」という言葉を使用する伝統が始まりました。
RSA 暗号の解読の難しさ(暗号文と公開鍵が与えられた場合に平文メッセージを復元する) は、大きな数を因数分解する難しさと関係があります。2 つの問題が数学的に同等であるかどうかは不明ですが、因数分解は現在、RSA を直接解読する唯一の公に知られている方法です。1977年の暗号文の解読では、平文を復元するために 129 桁 (426 ビット) の数字RSA-129を因数分解する必要がありました。
ロン・リベストは1977年に、当時知られている最良のアルゴリズムと最速のコンピュータを使用しても、125桁の半素数を因数分解するには4京年かかると見積もった。 [6]彼らは最初の論文で、将来の開発に対する安全域を提供するために200桁（663ビット）の素数を使用することを推奨したが、[7] 200桁の半素数が因数分解されたのは2005年であったため、解決を遅らせただけかもしれない。[8] [9]しかし、当時は効率的な因数分解アルゴリズムはあまり研究されておらず、その後の数十年間で多くの進歩が遂げられた。アトキンスらは、カール・ポメランスが1981年に発明した二次ふるいアルゴリズムを使用した。漸近的に高速な数体ふるいが発明されたばかりだったが、当時はそれが129桁の数に対して二次ふるいよりも優れているかどうかは明らかではなかった。新しいアルゴリズムのメモリ要件も懸念事項であった。[10]
このチャレンジには100ドルの賞金がかけられ、優勝者はそれをフリーソフトウェア財団に寄付した。
2015年には、同じRSA-129番号がCADO-NFSのオープンソース実装の数体ふるいによって、商用クラウドコンピューティングサービスを使用して約30ドルで約1日で因数分解されました。[11]
参照
参考文献
- ^ シン、サイモン（1999年）。『コードブック：古代エジプトから量子暗号まで秘密の科学』（アンカーブックス初版）。ニューヨーク：アンカーブックス。278ページ。ISBN 978-0-385-49532-5。
- ^ 「Wisecrackers」. WIRED . 1996年3月. 2016年5月24日閲覧。
- ^ アトキンス、デレク; グラフ、マイケル; レンストラ、アルジェン K.; レイランド、ポール C. (1994). 魔法の言葉は、気難しいオシフラージュです。シュプリンガー出版社。pp. 263–277。doi :10.1007/ BFb0000440。ISBN 978-3-540-59339-3。
{{cite book}}:|work=無視されました (ヘルプ) - ^ Yan, Song Y. (2012年11月28日). 計算数論と現代暗号. John Wiley & Sons. pp. 1–. ISBN 978-1-118-18861-3。
- ^ Hayes, Brian (1994 年 7 月)。「The Magic Words are Squeamish Ossifrage」(PDF)。Advances in Cryptology – ASIACRYPT'94。2015年9 月 28 日閲覧。
- ^ ガードナー、マーティン (1977). 「数学ゲーム、1977年8月」(PDF) .サイエンティフィック・アメリカン. 237 (2): 120–124. doi :10.1038/scientificamerican0877-120.
- ^ Rivest, RL; Shamir, A.; Adleman, L. (1978-02-01). 「デジタル署名と公開鍵暗号システムを取得する方法」(PDF) . Commun. ACM . 21 (2): 120–126. CiteSeerX 10.1.1.607.2677 . doi :10.1145/359340.359342. ISSN 0001-0782. S2CID 2873616.
- ^ Thorsten Kleinjung (2005-05-09)、We have factored RSA200 by GNFS Archived 2008-03-22 at the Wayback Machine。2008-03-10 に取得。
- ^ RSA Laboratories、「RSA-200 は因数分解されました!」。2008 年 3 月 10 日に取得。
- ^ Stinson, DR (1995). 「RSA、Factoring、およびSqueamish Ossifrage」。ウォータールー大学。 2015年9月28日閲覧。、1995 年版の『暗号理論と実践』の補足資料。Web ページを参照してください。
- ^ Mchugh, Nathaniel (2015-03-26). 「Nat McHugh: 魔法の言葉は気難しいオシフラージュ - CADO-NFS を使用した RSA-129 の因数分解」Nat McHugh . 2016-05-25閲覧。
外部リンク
- Derek Atkins の Web サイトにある技術論文 (PostScript ファイル)