Я думаю эта история будет интересна многим, в том числе людям, не связанным с математикой.
В 1976 году Уитфилд Диффи и Мартин Хеллман опубликовали свою статью «Новые направления в криптографии» с революционными идеями шифрования с использованием открытого ключа. А затем, три учёных Рональд Райвест, Ади Шамир и Леонард Адлеман в августе 1977 опубликовали в статью в журнале Scientific American, где они подробно описали свой алгоритм, использующий вычисления в кольце целых чисел. Как многим известно, идея алгоритма заключается в существовании условно-одностронней функции — обычного умножения на множестве простых чисел большой длины
(f:PxP->P*P), обратить которую вычислительно сложно. Иными словами, зная n = p*q (где p и q — простые числа), узнать p и q (или факторизовать число n) при большом n представляется ресурсоёмкой задачей.
В этом же номере, известный математик и учёный Мартин Гарднер по согласию авторов алгоритма, опубликовал математическую задачу, получившую название RSA-129. В ней он написал пару чисел (n, e) — открытый ключ, где длина числа n составляла 129 десятичных знаков, а e было равным 1007, и само зашифрованное сообщение. Дешифровавшему сообщение он обещал вознаграждение в $100, которые он положил в банк под 2% годовых. По подсчётам аналитиков, для разложения такого огромного числа на множители при существавших алгоритмах факторизации и мощности тех компьютеров, потребуется 20.000 лет непрерывной работы (Рон Ривест предполагал 40 квадрильён лет для числа в 125 знаков). Но ситуация изменилась…
Затем, в 1994 году молодой криптограф американской армии Арьен Ленстра разработал усовершенствование агоритма Квадратичного Решета, позволяющий за разумное время найти простые множители числа до 130 цифр. Асимптотика алгоритма составляла O(esqrt(log n * log log n)), где e — основание натурального логарифма. К слову, асимптотика тривиального алгоритма факторизации O(sqrt(n)) , что, дольше для больших n. Сам Ленстра не обладал необходимыми вычислительными мощностями, и тогда он предложил через Интернет добровольцам выделить часть своего процессорного времени на благо математики. Это был один из первых в истории больших проектов, использующих распределённые вычисления. К решению задачи присоединилось 600 человек, предоставив 1600 компьютеров: кроме самых обычных компьютеров участие приняли 3 суперкомпьютера и, если верить русскоязычной Википедии, 2 факс-машины :-). В результате была сформирована итоговая матрица размера 20.000 на 20.000, заполненная единицами и нулями. Далее, в дело вступил метеорологический суперкомпьютер, выделенный самому Ленстре, который за 220 дней непрерывной работы разложил на множители 129 значное число n.
Ответ оказалася таким:
Длины чисел p и q оказались 64 и 65 знаков соответственно. Фраза, зашифрованная Мартином Гарднером, была такая: "The Magic Words are Squeamish Ossifrage", что переводится "Волшебные слова — это Застенчивая Скопа", или, по версии русской Википедии, "Волшебные слова — это брезгливый ягнятник". После этого, рекомендуемая длина ключа была увеличена до 140 знаков до тех пор, пока через 4 года не разложили контрольное число из 140 цифр. В 1998 году Билл Гейтс заявил, что предоставляет неограниченное финансирование и вычислительные ресурсы своей компании для разложения числа в 200 знаков. В данный момент, эта цель уже достигнута в 2005 году, задача RSA-200. Из $100, как не трудно посчитать, по процентам за 17 лет получилось примерно $140, которые и были переданы в фонд свободного программного обеспечения :-)
Вся эта история была прекрасным пиар-ходом для авторов алгоритма и основателей компании, запатентовавшей RSA, и получивших в результате $900 млн прибыли.
Вот что значит делать деньги с умом ;)
Источник: профессор Салий Вячеслав Николаевич, СГУ.
Заранее прошу прощения за неточности.
Всем спасибо за исправления в комментах!
В 1976 году Уитфилд Диффи и Мартин Хеллман опубликовали свою статью «Новые направления в криптографии» с революционными идеями шифрования с использованием открытого ключа. А затем, три учёных Рональд Райвест, Ади Шамир и Леонард Адлеман в августе 1977 опубликовали в статью в журнале Scientific American, где они подробно описали свой алгоритм, использующий вычисления в кольце целых чисел. Как многим известно, идея алгоритма заключается в существовании условно-одностронней функции — обычного умножения на множестве простых чисел большой длины
(f:PxP->P*P), обратить которую вычислительно сложно. Иными словами, зная n = p*q (где p и q — простые числа), узнать p и q (или факторизовать число n) при большом n представляется ресурсоёмкой задачей.
В этом же номере, известный математик и учёный Мартин Гарднер по согласию авторов алгоритма, опубликовал математическую задачу, получившую название RSA-129. В ней он написал пару чисел (n, e) — открытый ключ, где длина числа n составляла 129 десятичных знаков, а e было равным 1007, и само зашифрованное сообщение. Дешифровавшему сообщение он обещал вознаграждение в $100, которые он положил в банк под 2% годовых. По подсчётам аналитиков, для разложения такого огромного числа на множители при существавших алгоритмах факторизации и мощности тех компьютеров, потребуется 20.000 лет непрерывной работы (Рон Ривест предполагал 40 квадрильён лет для числа в 125 знаков). Но ситуация изменилась…
Затем, в 1994 году молодой криптограф американской армии Арьен Ленстра разработал усовершенствование агоритма Квадратичного Решета, позволяющий за разумное время найти простые множители числа до 130 цифр. Асимптотика алгоритма составляла O(esqrt(log n * log log n)), где e — основание натурального логарифма. К слову, асимптотика тривиального алгоритма факторизации
Ответ оказалася таким:
RSA-129 = 3490529510847650949147849619903898133417764638493387843990820577
× 32769132993266709549961988190834461413177642967992942539798288533
Длины чисел p и q оказались 64 и 65 знаков соответственно. Фраза, зашифрованная Мартином Гарднером, была такая: "The Magic Words are Squeamish Ossifrage", что переводится "Волшебные слова — это Застенчивая Скопа", или, по версии русской Википедии, "Волшебные слова — это брезгливый ягнятник". После этого, рекомендуемая длина ключа была увеличена до 140 знаков до тех пор, пока через 4 года не разложили контрольное число из 140 цифр. В 1998 году Билл Гейтс заявил, что предоставляет неограниченное финансирование и вычислительные ресурсы своей компании для разложения числа в 200 знаков. В данный момент, эта цель уже достигнута в 2005 году, задача RSA-200. Из $100, как не трудно посчитать, по процентам за 17 лет получилось примерно $140, которые и были переданы в фонд свободного программного обеспечения :-)
Вся эта история была прекрасным пиар-ходом для авторов алгоритма и основателей компании, запатентовавшей RSA, и получивших в результате $900 млн прибыли.
Вот что значит делать деньги с умом ;)
Источник: профессор Салий Вячеслав Николаевич, СГУ.
Заранее прошу прощения за неточности.
Всем спасибо за исправления в комментах!
