Волшебные слова - брезгливая осифраж - The Magic Words are Squeamish Ossifrage

Текст "Волшебные слова - брезгливая осифраж"было решением проблемы зашифрованный текст поставленные изобретателями ЮАР шифр в 1977 г. Проблема появилась в Мартин Гарднер с Колонка "Математические игры" в августовском выпуске 1977 г. Scientific American.[1] Она была решена в 1993–94 гг. В рамках большого совместного компьютерного проекта, координированного Дерек Аткинс, Майкл Графф, Арьен Ленстра и Пол Лейланд.[2][3][4][5] Свой вклад внесли более 600 волонтеров ЦПУ время примерно с 1600 машин (две из которых были факс машин) больше полугода. Координация осуществлялась через Интернет и был одним из первых таких проектов.

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

Сложность взлом шифра RSA - восстановление простой текст сообщение с заданным зашифрованным текстом и открытым ключом - связано с трудностью факторинг большое количество. Хотя неизвестно, эквивалентны ли эти две задачи математически, разложение на множители в настоящее время является единственным общеизвестным методом прямого взлома RSA. В расшифровка шифротекста 1977 года включал разложение 129-значного (426-битного) числа, RSA-129, чтобы восстановить открытый текст.

Рон Ривест по оценкам 1977 г., разложение 125-значного полупростого числа потребовало бы 40 квадриллион лет, используя лучшее алгоритм известные и самые быстрые компьютеры дня.[6] В своей оригинальной статье они рекомендовали использовать 200-значные (663-битные) простые числа, чтобы обеспечить запас прочности от будущих разработок.[7] хотя, возможно, это только отсрочило решение, поскольку в 2005 году было учтено 200-значное полупростое число.[8][9] Но эффективные алгоритмы факторинга в то время мало изучались, и в последующие десятилетия был достигнут большой прогресс. Аткинс и др. использовал квадратное сито алгоритм изобретен Карл Померанс в 1981 году. Хотя асимптотически быстрее числовое поле сито было только что изобретено, тогда не было ясно, что это будет лучше, чем квадратное сито для 129-значных чисел. Требования к памяти нового алгоритма также были проблемой.[10]

В связи с этим испытанием был вручен приз в размере 100 долларов США, который победители пожертвовали Фонд свободного программного обеспечения.

В 2015 году тот же самый номер RSA-129 был разложен примерно за один день с помощью CADO-NFS с открытым исходным кодом сита числового поля с использованием коммерческого сервиса облачных вычислений примерно за 30 долларов.[11]

Смотрите также

Рекомендации

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

внешняя ссылка