Я думаю эта история будет интересна многим, в том числе людям, не связанным с математикой.
В 1976 году
Уитфилд Диффи и
Мартин Хеллман опубликовали свою статью «Новые направления в криптографии» с революционными идеями шифрования с использованием открытого ключа. А затем, три учёных
Рональд Райвест,
Ади Шамир и
Леонард Адлеман в
августе 1977 опубликовали в статью в журнале
Scientific American, где они подробно описали свой алгоритм, использующий вычисления в кольце целых чисел. Как многим известно, идея алгоритма заключается в существовании условно-одностронней функции — обычного умножения на множестве простых чисел большой длины
(f:
Px
P->
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 знаков). Но ситуация изменилась…