Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Текст « Слова Магии брезгует гриф » был решением переходящего шифротекста , исходящего от изобретателей RSA шифра в 1977 г. Проблемы появилась в Martin Gardner «s колонке Математических игр в выпуске августа 1977 Scientific American . [1] Она была решена в 1993–94 годах в результате большого совместного компьютерного проекта, координированного Дереком Аткинсом , Майклом Граффом , Арьеном Ленстрой и Полом Лейландом . [2] [3] [4] [5] Более 600 добровольцев внесли свой вклад в CPUвремя примерно с 1600 аппаратов (два из которых были факсимильными ) в течение шести месяцев. Координация осуществлялась через Интернет и была одним из первых подобных проектов.

Ossifrage (« разрушитель костей», от латинского) - старое название бородатого стервятника , падальщика, известного тем, что бросал кости животных и живых черепах на камни, чтобы взламывать их. В 1993–94 годах началась традиция использования слова «брезгливая оссифраж» в криптоаналитических задачах.

Сложность взлома шифра 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]

См. Также [ править ]

Ссылки [ править ]

  1. ^ Сингх, Саймон (1999). Книга кодов: наука секретности от Древнего Египта до квантовой криптографии (изд. Первые якорные книги). Нью-Йорк: якорные книги. С.  278 . ISBN 978-0-385-49532-5.
  2. ^ "Мудрости" . ПРОВОДНОЙ . Марта 1996 года . Проверено 24 мая 2016 .
  3. ^ Аткинс, Дерек; Графф, Майкл; Ленстра, Арьен К .; Лейланд, Пол С. (1994). Волшебные слова - это Брезгливая Оссифраж . Труды Asiacrypt '94 . Springer-Verlag. С. 263–277. DOI : 10.1007 / BFb0000440 . ISBN 978-3-540-59339-3.
  4. Перейти ↑ Yan, Song Y. (28 ноября 2012 г.). Вычислительная теория чисел и современная криптография . Джон Вили и сыновья. стр. 1–. ISBN 978-1-118-18861-3.
  5. ^ Хейс, Брайан (июль 1994). «Волшебные слова - брезгливая оссифраж» (PDF) . Достижения в криптологии - ASIACRYPT'94 . Проверено 28 сентября 2015 года . CS1 maint: обескураженный параметр ( ссылка )
  6. ^ Гарднер, Мартин (1977). "Математические игры, август 1977 г." (PDF) . Scientific American . 237 (2): 120–124. DOI : 10.1038 / Scientificamerican0877-120 .
  7. ^ Ривест, RL; Шамир, А .; Адлеман, Л. (1978-02-01). «Метод получения цифровых подписей и криптосистем с открытым ключом» (PDF) . Commun. ACM . 21 (2): 120–126. CiteSeerX 10.1.1.607.2677 . DOI : 10.1145 / 359340.359342 . ISSN 0001-0782 .   
  8. ^ Торстны Kleinjung (2005-05-09) Мы учли RSA200 по нефакторным услугам Архивированных 2008-03-22 в Wayback Machine . Проверено 10 марта 2008.
  9. ^ RSA Laboratories, RSA-200 учтено! . Проверено 10 марта 2008.
  10. Перейти ↑ Stinson, DR (1995). «ЮАР, факторинг и щепетильная оссифраж» . Университет Ватерлоо . Проверено 28 сентября 2015 года . CS1 maint: обескураженный параметр ( ссылка ), Дополнительные материалы к изданию 1995 года его книги « Теория и практика криптографии» см. На веб-странице .
  11. ^ Мак, Натаниэль (2015-03-26). «Нат МакХью: Волшебные слова - это брезгливая оссифраж - факторизация RSA-129 с использованием CADO-NFS» . Нат МакХью . Проверено 25 мая 2016 .

Внешние ссылки [ править ]

  • Технический документ на веб-сайте Дерека Аткинса (файл postscript)