Дело застенчивой скопы. Алгоритм RSA
3 мин
Я думаю эта история будет интересна многим, в том числе людям, не связанным с математикой.
В 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 знаков). Но ситуация изменилась…
В 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 знаков). Но ситуация изменилась…


В последнем 
Компания 

Компания IBM объявила о выпуске двух высокопроизводительных моделей линейки Power Systems — одна из них является самым быстрым в мире компьютером, работающим под управлением UNIX, а другая — суперкомпьютером с уникальной водяной системой охлаждения.