Реферат: Применение алгоритма RSA для шифрования потоков данных

, (6)

то единственное условие на выбор показателя степени в отображении (1) есть

. (7)

Итак, лицо, заинтересованное в организации шифрованной переписки с помощью схемы RSA, выбирает два достаточно больших простых числа и . Перемножая их, оно находит число . Затем выбирается число , удовлетворяющее условиям (7), вычисляется с помощью (6) число и с помощью (3) - число . Числа и публикуются, число остается секретным. Теперь любой может отправлять зашифрованные с помощью (1) сообщения организатору этой системы, а организатор легко сможет расшифровывать их с помощью (5).

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

m=11438162575788886766932577997614661201021829672124236256256184293570 6935245733897830597123563958705058989075147599290026879543541

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

,

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

Эта история завершилась спустя 17 лет в 1994 г., когда D. Atkins, M. Graff, А. К. Lenstra и Р. С. Leyland сообщили о расшифровке фразы. Числа и оказались равными

,

.

Этот замечательный результат (разложение на мно­жители 129-значного десятичного числа) был достигнут благодаря ис­пользованию алгоритма разложения чисел на множители, называемого методом квадратичного решета. Выполнение вычислений потребовало колоссальных ресурсов. В работе, возглавлявшейся четырьмя авторами проекта, и продолжавшейся после предварительной теоретической под­готовки примерно 220 дней, на добровольных началах участвовало около 600 человек и примерно 1600 компьютеров, объединённых сетью Inter­net. Наконец, отметим, что премия в 100$ была передана в Free Software Foundation.

2.2.Сложность теоретико-числовых алгоритмов

Сложность алгоритмов теории чисел обычно принято измерять коли­чеством арифметических операций (сложений, вычитаний, умножений и делений с остатком), необходимых для выполнения всех действий, пред­писанных алгоритмом. Впрочем, это определение не учитывает величины чисел, участвующих в вычислениях. Ясно, что перемножить два стозначных числа значительно сложнее, чем два однозначных, хотя при этом и в том, и в другом случае выполняется лишь одна арифметическая опе­рация. Поэтому иногда учитывают ещё и величину чисел, сводя дело к так называемым битовым операциям, т. е. оценивая количество необхо­димых операций с цифрами 0 и 1, в двоичной записи чисел.

Говоря о сложности алгоритмов, мы будем иметь в ви­ду количество арифметических операций. При построении эффективных алгоритмов и обсуждении верхних оценок сложности обычно хватает ин­туитивных понятий той области математики, которой принадлежит алго­ритм. Формализация же этих понятий требуется лишь тогда, когда речь идёт об отсутствии алгоритма или доказательстве нижних опенок слож­ности.

Приведем теперь примеры достаточно быстрых алгоритмов с опен­ками их сложности. Здесь и в дальнейшем мы не будем придерживаться формального описания алгоритмов, стараясь в первую очередь объяснить смысл выполняемых действий.

Следующий алгоритм вычисляет за арифмети­ческих операций. При этом, конечно, предполагается, что натуральные числа и не превосходят по величине .

2.2.1. Алгоритм вычисления

1. Представим в двоичной системе счисления , где , цифры в двоичном представлении, равны 0 или 1, .

2. Положим и затем для вычислим

.

3) есть искомый вычет .

Справедливость этого алгоритма вытекает из сравнения

,

легко доказываемого индукцией по .

Так как каждое вычисление на шаге 2 требует не более трёх умноже­ний по модулю и этот шаг выполняется раз, то сложность алгоритма может быть оценена величиной .

Второй алгоритм - это классический алгоритм Евклида вычисления наибольшего общего делителя целых чисел. Мы предполагаем заданными два натуральных числа и и вычисляем их наибольший общий дели­тель .

2.2.2. Алгоритм Евклида