Войти
Текст «Волшебные слова - это щепетильный костнозавод » был решением проблемы зашифрованный текст, предложенный изобретателями RSA шифра в 1977 году. Проблема появилась в Мартин Гарднер в столбце Mathematical Games в августовском номере журнала Sc научный американец. Она была решена в 1993–94 годах в результате большого совместного компьютерного проекта, координированного Дереком Аткинсом, Майклом Граффом, Арьеном Ленстра и Полом Лейландом. Более 600 добровольцев предоставили CPU время примерно с 1600 машин (два из которых были факсами ) в течение шести месяцев. Координация осуществлялась через Интернет и была одним из первых подобных проектов.
Ossifrage («костолом», от латинского) - старое название бородатого стервятника, падальщика, известного тем, что бросал кости животных и живых черепах на камни, чтобы взламывать их. В 1993–94 годах началась традиция использования слов «брезгливая оссифраж» в криптоаналитических задачах.
Сложность взлома шифра RSA - восстановления сообщения с открытым текстом с учетом зашифрованного текста и открытого ключа - связана с трудностью факторизации большие цифры. Хотя неизвестно, эквивалентны ли эти две задачи математически, разложение на множители в настоящее время является единственным общеизвестным методом прямого взлома RSA. Расшифровка зашифрованного текста 1977 года включала факторизацию 129-значного (426-битного) числа, RSA-129, для восстановления открытого текста.
Рон Ривест в 1977 году подсчитал, что разложение 125-значного полупростого числа потребует 40 квадриллионов лет, используя лучший алгоритм из известных и самые быстрые компьютеры того времени. В своей исходной статье они рекомендовали использовать 200-значные (663-битные) простые числа, чтобы обеспечить запас прочности на случай будущих разработок, хотя это могло только задержать решение, поскольку 200-значное полупростое число было учтено в 2005 году. Но эффективные алгоритмы разложения на множители этого не сделали. в то время много изучались, и в последующие десятилетия был достигнут большой прогресс. Аткинс и др. использовали алгоритм квадратного сита, изобретенный Карлом Померансом в 1981 году. Хотя асимптотически более быстрое числовое сито только что было изобретено, в то время не было ясно, что это было бы лучше, чем квадратное сито для 129-значных чисел. Требования к памяти для нового алгоритма также вызвали озабоченность.
С испытанием был связан приз в размере 100 долларов США, который победители пожертвовали Фонду свободного программного обеспечения.
В 2015 году тот же RSA Факторизация числа -129 производилась примерно за один день с помощью реализации сита числового поля с открытым исходным кодом CADO-NFS с использованием коммерческого сервиса облачных вычислений примерно за 30 долларов.
