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

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

width="2048" height="221" align="ABSMIDDLE" />, (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. Алгоритм Евклида

  1. Вычислим - остаток от деления числа на , , .

  2. Если , то есть искомое число.

  3. Если , то заменим пару чисел парой и перейдем к
    шагу 1.

Теорема 1. При вычислении наибольшего общего делителя с помощью алгоритма Евклида будет выполнено не более операций де­ления с остатком, где есть количество цифр в десятичной записи меньшего из чисел и .

Доказательство. Положим и определим - последовательность делителей, появляющихся в процессе выполнения ша­га 1 алгоритма Евклида. Тогда

.

Пусть также , , , , - последователь­ность Фибоначчи. Индукцией по от до легко доказывается неравенство . А так как , то имеем неравенства и .

Немного подправив алгоритм Евклида, можно достаточно быстро ре­шать сравнения при условии, что . Эта задача равносильна поиску целых решений уравнения .

2.2.3. Алгоритм решения уравнения

0) Определим матрицу .

1) Вычислим - остаток от деления числа на , , .

  1. Если , то второй столбец матрицы даёт вектор
    решений уравнения.

  2. Если , то заменим матрицу матрицей .

  3. Заменим пару чисел парой и перейдем к шагу 1.

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

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

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

Для некоторых задач эффективные алгоритмы вообще не известны. Иногда в таких случаях все же можно предложить последовательность действий, которая, «если повезет», быстро приводит к требуемому ре­зультату. Существует класс так называемых вероятностных алгоритмов, которые дают правильный результат, но имеют вероятностную опен­ку времени работы. Обычно работа этих алгоритмов зависит от одного или нескольких параметров. В худшем случае они работают достаточно долго. Но удачный выбор параметра определяет быстрое завершение ра­боты. Такие алгоритмы, если множество «хороших» значений параметров велико, на практике работают достаточно эффективно, хотя и не имеют хороших опенок сложности.

Мы будем иногда использовать слова детерминированный алгоритм, чтобы отличать алгоритмы в обычном смысле от вероятностных алго­ритмов.

Как пример, рассмотрим вероятностный алгоритм, позволяющий эф­фективно находить решения полиномиальных сравнений по простому мо­дулю. Пусть — простое число, которое предполагается большим, и - многочлен, степень которого предполагается ограничен­ной. Задача состоит в отыскании решений сравнения

. (8)

Например, речь может идти о решении квадратичных сравнений, если степень многочлена равна 2. Другими словами, мы должны отыскать в поле все элементы, удовлетворяющие уравнению .

Согласно малой теореме Ферма, все элементы поля являются од­нократными корнями многочлена . Поэтому, вычислив наибольший общий делитель , мы найдем многочлен , множест­во корней которого в поле совпадает с множеством корней многочлена , причем все эти корни однократны. Если окажется, что многочлен имеет нулевую степень, т. е. лежит в поле , это будет означать, что сравнение (8) не имеет решений.

Для вычисления многочлена удобно сначала вычислить многочлен , пользуясь алгоритмом, подобным описанному выше алгоритму возведения в степень (напомним, что число предполагается большим). А затем с помощью аналога алгоритма Евклида вычислить . Всё это выполняется за полиномиальное количество арифметических операций.

Таким образом, обсуждая далее задачу нахождения решений сравне­ния (8), мы можем предполагать, что в кольце многочленов спра­ведливо равенство

2.2.4. Алгоритм нахождения делителей многочлена в коль­це

1) Выберем каким-либо способом элемент .

  1. Вычислим наибольший общий делитель .

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

4) Если окажется, что или , следует перейти к шагу 1 и. выбрав новое значение , продолжить выполнение алгоритма.

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

Количество решений уравнения в поле не превосходит . Это означает, что подмножество элементов , удовлетворяющих условиям

,

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

Итак, существует не менее «удачных» выборов элемента , при которых на шаге 2 алгоритма многочлен распадётся на два соб­ственных множителя. Следовательно, при «случайном» выборе элемента , вероятность того, что многочлен не разложится на множители после повторений шагов алгоритма 1-4. не превосходит . Вероят­ность с ростом убывает очень быстро. И действительно, на практике этот алгоритм работает достаточно эффективно.

Заметим, что при опенке вероятности мы использовали только два корня многочлена . При

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: