Волшебные слова — брезгливая костница
« Волшебные слова — это брезгливая костеобразование » было решением проблемы зашифрованного текста, поставленной изобретателями шифра в RSA 1977 году. Задача появилась в колонке Мартина Гарднера « Математические игры» в августовском выпуске журнала Scientific American за 1977 год . [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]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Сингх, Саймон (1999). Кодовая книга: наука о секретности от Древнего Египта до квантовой криптографии (изд. First Anchor Books). Нью-Йорк: Anchor Books. стр. 278 . ISBN 978-0-385-49532-5 .
- ^ «Остроумники» . ПРОВОДНОЙ . Март 1996 года . Проверено 24 мая 2016 г.
- ^ Аткинс, Дерек; Графф, Майкл; Ленстра, Арьен К.; Лейланд, Пол К. (1994). Волшебные слова — брезгливая костница . Спрингер-Верлаг. стр. 263–277. дои : 10.1007/BFb0000440 . ISBN 978-3-540-59339-3 .
{{cite book}}:|work=игнорируется ( помогите ) - ^ Ян, Сон Ю. (28 ноября 2012 г.). Вычислительная теория чисел и современная криптография . Джон Уайли и сыновья. стр. 1–. ISBN 978-1-118-18861-3 .
- ^ Хейс, Брайан (июль 1994 г.). «Волшебные слова — брезгливая костница» (PDF) . Достижения криптологии – ASIACRYPT'94 . Проверено 28 сентября 2015 г.
- ^ Гарднер, Мартин (1977). «Математические игры, август 1977 г.» (PDF) . Научный американец . 237 (2): 120–124. doi : 10.1038/scientificamerican0877-120 .
- ^ Ривест, РЛ; Шамир, А.; Адлеман, Л. (1 февраля 1978 г.). «Метод получения цифровых подписей и криптосистем с открытым ключом» (PDF) . Коммун. АКМ . 21 (2): 120–126. CiteSeerX 10.1.1.607.2677 . дои : 10.1145/359340.359342 . ISSN 0001-0782 . S2CID 2873616 .
- ^ Торстен Кляйнджунг (9 мая 2005 г.), Мы учли RSA200 с помощью GNFS. Архивировано 22 марта 2008 г. в Wayback Machine . Проверено 10 марта 2008 г.
- ^ RSA Laboratories, RSA-200 учтен! . Проверено 10 марта 2008 г.
- ^ Стинсон, Д.Р. (1995). «RSA, факторинг и брезгливая костеобразование» . Университет Ватерлоо . Проверено 28 сентября 2015 г. Дополнительный материал к изданию 1995 года его книги «Теория и практика криптографии» , см. веб-страницу .
- ^ Мчух, Натаниэль (26 марта 2015 г.). «Нэт МакХью: Волшебные слова - это брезгливая костеобразование - факторизация RSA-129 с использованием CADO-NFS» . Нат МакХью . Проверено 25 мая 2016 г.
Внешние ссылки
[ редактировать ]- Технический документ на веб-сайте Дерека Аткинса (постскриптум)