Введение

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