Введение в криптографию
[an error occurred while processing this directive]

Система шифрования RSA - часть 3


Для иллюстрации своего метода Ривест, Шамир и Адлеман зашифровали таким способом некоторую английскую фразу. Сначала она стандартным образом (a=01, b=02, ..., z=26, пробел=00) была записана в виде целого числа , а затем зашифрована с помощью отображения () при


и . Эти два числа были опубликованы, причем дополнительно сообщалось, что , где и  - простые числа, записываемые соответственно и десятичными знаками. Первому, кто дешифрует соответствующее сообщение

была обещана награда в 100$.

Эта история завершилась спустя 17 лет в 1994 г., см. [], когда D. Atkins, M. Graff, A. K. Lenstra и P. C. Leyland сообщили о дешифровке фразы, предложенной в []. Она1) была вынесена в заголовок статьи [], а соответствующие числа и оказались равными

Интересующиеся могут найти детали вычислений в работе []. Здесь же мы отметим, что этот замечательный результат (разложение на множители 129-значного десятичного числа) был достигнут благодаря использованию алгоритма разложения чисел на множители, называемого методом квадратичного решета. Выполнение вычислений потребовало колоссальных ресурсов. В работе, возглавлявшейся четырьмя авторами проекта, и продолжавшейся после предварительной теоретической подготовки примерно 220 дней, на добровольных началах участвовало около 600 человек и примерно 1600 компьютеров, объединенных сетью Internet. Наконец, отметим, что премия в 100$ была передана в Free Software Foundation.

Описанная выше схема RSA ставит ряд вопросов, которые мы и попробуем обсудить ниже. Например, как проводить вычисления с большими числами, ведь стандартное математическое обеспечение не позволяет перемножать числа размером по 65 десятичных знаков? Как вычислять огромные степени больших чисел? Что значит быстрый алгоритм вычисления и что такое сложная вычислительная задача? Где взять большие простые числа? Как, например, построить простое число в 65 десятичных знаков? Существуют ли другие способы решения сравнения ()? Ведь, если можно найти решение (), не вычисляя секретный показатель или не разлагая число на простые сомножители, да еще сделать это достаточно быстро, вся система RSA разваливается. Наверное, читателю могут прийти в голову и другие вопросы.




- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]