Волшебные слова — брезгливые Оссифраге
« The Magic Words are Squeamish Ossifrage » было решением проблемы шифротекста, поставленной изобретателями шифра RSA в 1977 году. Задача появилась в колонке «Математические игры » Мартина Гарднера в выпуске журнала Scientific American за август 1977 года . [1] Она была решена в 1993–1994 годах в ходе большого совместного компьютерного проекта, координируемого Дереком Аткинсом , Майклом Граффом , Арьеном Ленстра и Полом Лейландом . [2] [3] [4] [5] Более 600 добровольцев предоставили процессорное время примерно с 1600 машин (две из которых были факсимильными аппаратами) в течение шести месяцев. Координация осуществлялась через Интернет и была одним из первых подобных проектов.
Ossifrage (лат. «костелом») — старое название бородатого стервятника , падальщика, известного тем, что бросает кости животных и живых черепах на вершины камней, чтобы их расколоть. Усилия 1993–94 годов положили начало традиции использования слов «щепетильный ossifrage» в криптоаналитических задачах.
Трудность взлома шифра RSA — восстановления открытого текста сообщения по зашифрованному тексту и открытому ключу — связана со сложностью факторизации больших чисел. Хотя неизвестно, эквивалентны ли эти две проблемы математически, факторизация в настоящее время является единственным общеизвестным методом прямого взлома RSA. Расшифровка зашифрованного текста 1977 года включала факторизацию 129-значного (426-битного) числа RSA-129 для восстановления открытого текста.
Рон Ривест в 1977 году подсчитал, что факторизация 125-значного полупростого числа потребует 40 квадриллионов лет, используя лучший из известных алгоритмов и самые быстрые компьютеры того времени. [6] В своей оригинальной статье они рекомендовали использовать 200-значные (663-битные) простые числа, чтобы обеспечить запас прочности на случай будущих разработок, [7] хотя это могло только задержать решение, поскольку 200-значное полупростое число было факторизовано в 2005 году. [8] [9] Однако эффективные алгоритмы факторизации в то время не были изучены достаточно хорошо, и в последующие десятилетия был достигнут большой прогресс. Аткинс и др. использовали алгоритм квадратичного решета , изобретенный Карлом Померансом в 1981 году. Хотя асимптотически более быстрое решето числового поля только что было изобретено, в то время не было ясно, будет ли оно лучше квадратичного решета для 129-значных чисел. Требования к памяти нового алгоритма также вызывали беспокойство. [10]
В рамках конкурса был предусмотрен приз в размере 100 долларов США, который победители пожертвовали в Фонд свободного программного обеспечения .
В 2015 году то же число RSA-129 было рассчитано примерно за один день с помощью реализации CADO-NFS с открытым исходным кодом для решета числовых полей с использованием коммерческого сервиса облачных вычислений примерно за 30 долларов США. [11]
Смотрите также
Ссылки
- ^ Сингх, Саймон (1999). Книга кодов: Наука секретности от Древнего Египта до квантовой криптографии (Первое издание Anchor Books). Нью-Йорк: Anchor Books. С. 278. ISBN 978-0-385-49532-5.
- ^ "Острословы". WIRED . Март 1996. Получено 24.05.2016 .
- ^ Аткинс, Дерек; Графф, Майкл; Ленстра, Арьен К.; Лейланд, Пол К. (1994). Волшебные слова — брезгливые оссифраге. Springer-Verlag. стр. 263–277 . doi :10.1007/BFb0000440. ISBN 978-3-540-59339-3.
{{cite book}}:|work=проигнорировано ( помощь ) - ^ Ян, Сонг И. (28 ноября 2012 г.). Вычислительная теория чисел и современная криптография. John Wiley & Sons. стр. 1–. ISBN 978-1-118-18861-3.
- ^ Хейс, Брайан (июль 1994 г.). «Волшебные слова — брезгливые оссифраги» (PDF) . Достижения в криптологии – ASIACRYPT'94 . Получено 28 сентября 2015 г.
- ^ Гарднер, Мартин (1977). «Математические игры, август 1977» (PDF) . Scientific American . 237 (2): 120– 124. doi :10.1038/scientificamerican0877-120.
- ^ Ривест, Р. Л.; Шамир, А.; Адлеман, Л. (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.
- ^ Торстен Кляйнджунг (2005-05-09), Мы разложили RSA200 с помощью GNFS Архивировано 2008-03-22 на Wayback Machine . Получено 2008-03-10.
- ^ RSA Laboratories, RSA-200 факторизован!. Получено 10.03.2008.
- ^ Стинсон, DR (1995). "RSA, Factoring, and Squeamish Ossifrage". Университет Ватерлоо . Получено 28 сентября 2015 г., Дополнительный материал к изданию его книги «Теория и практика криптографии» 1995 года , см. веб-страницу.
- ^ Макхью, Натаниэль (2015-03-26). "Nat McHugh: Волшебные слова - это брезгливые оссифраги - факторизация RSA-129 с использованием CADO-NFS". Nat McHugh . Получено 2016-05-25 .
Внешние ссылки
- Техническая статья на веб-сайте Дерека Аткинса (файл postscript)
