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

6935245733897830597123563958705058989075147599290026879543541

и [pic]. Эти два числа были опубликованы, причем дополнительно сообщалось,

что [pic]. где [pic] и [pic] - простые числа, записываемые соответственно

64 и 65 десятичными знаками. Первому, кто расшифрует соответствующее

сообщение

[pic],

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

Эта история завершилась спустя 17 лет в 1994 г., когда D. Atkins, M.

Graff, А. К. Lenstra и Р. С. Leyland сообщили о расшифровке фразы. Числа

[pic] и [pic] оказались равными

[pic],

[pic].

Этот замечательный результат (разложение на множители 129-значного

десятичного числа) был достигнут благодаря использованию алгоритма

разложения чисел на множители, называемого методом квадратичного решета.

Выполнение вычислений потребовало колоссальных ресурсов. В работе,

возглавлявшейся четырьмя авторами проекта, и продолжавшейся после

предварительной теоретической подготовки примерно 220 дней, на добровольных

началах участвовало около 600 человек и примерно 1600 компьютеров,

объединённых сетью Internet. Наконец, отметим, что премия в 100$ была

передана в Free Software Foundation.

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

Сложность алгоритмов теории чисел обычно принято измерять количеством

арифметических операций (сложений, вычитаний, умножений и делений с

остатком), необходимых для выполнения всех действий, предписанных

алгоритмом. Впрочем, это определение не учитывает величины чисел,

участвующих в вычислениях. Ясно, что перемножить два стозначных числа

значительно сложнее, чем два однозначных, хотя при этом и в том, и в другом

случае выполняется лишь одна арифметическая операция. Поэтому иногда

учитывают ещё и величину чисел, сводя дело к так называемым битовым

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

в двоичной записи чисел.

Говоря о сложности алгоритмов, мы будем иметь в виду количество

арифметических операций. При построении эффективных алгоритмов и обсуждении

верхних оценок сложности обычно хватает интуитивных понятий той области

математики, которой принадлежит алгоритм. Формализация же этих понятий

требуется лишь тогда, когда речь идёт об отсутствии алгоритма или

доказательстве нижних опенок сложности.

Приведем теперь примеры достаточно быстрых алгоритмов с опенками их

сложности. Здесь и в дальнейшем мы не будем придерживаться формального

описания алгоритмов, стараясь в первую очередь объяснить смысл выполняемых

действий.

Следующий алгоритм вычисляет [pic] за [pic] арифметических операций.

При этом, конечно, предполагается, что натуральные числа [pic] и [pic] не

превосходят по величине [pic].

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

1) Представим [pic] в двоичной системе счисления [pic], где [pic], цифры в

двоичном представлении, равны 0 или 1, [pic].

2) Положим [pic] и затем для [pic] вычислим

[pic].

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

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

[pic],

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

Так как каждое вычисление на шаге 2 требует не более трёх умножений

по модулю [pic] и этот шаг выполняется [pic] раз, то сложность алгоритма

может быть оценена величиной [pic].

Второй алгоритм - это классический алгоритм Евклида вычисления

наибольшего общего делителя целых чисел. Мы предполагаем заданными два

натуральных числа [pic] и [pic] и вычисляем их наибольший общий делитель

[pic].

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

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

2) Если [pic], то [pic] есть искомое число.

3) Если [pic], то заменим пару чисел [pic] парой [pic] и перейдем к

шагу 1.

Теорема 1. При вычислении наибольшего общего делителя [pic] с помощью

алгоритма Евклида будет выполнено не более [pic] операций деления с

остатком, где [pic] есть количество цифр в десятичной записи меньшего из

чисел [pic] и [pic].

Доказательство. Положим [pic] и определим [pic] - последовательность

делителей, появляющихся в процессе выполнения шага 1 алгоритма Евклида.

Тогда

[pic].

Пусть также [pic], [pic], [pic], [pic], - последовательность Фибоначчи.

Индукцией по [pic] от [pic] до [pic] легко доказывается неравенство [pic].

А так как [pic], то имеем неравенства [pic] и [pic].

Немного подправив алгоритм Евклида, можно достаточно быстро решать

сравнения [pic] при условии, что [pic]. Эта задача равносильна поиску целых

решений уравнения [pic].

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

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

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

[pic].

Если [pic], то второй столбец матрицы [pic] даёт вектор [pic]

решений уравнения.

3) Если [pic], то заменим матрицу [pic] матрицей [pic].

4) Заменим пару чисел [pic] парой [pic] и перейдем к шагу 1.

Если обозначить через [pic] матрицу [pic], возникающую в процессе

работы алгоритма перед шагом 2 после [pic] делений с остатком (шаг 1), то в

обозначениях из доказательства теоремы 1 в этот момент выполняется

векторное равенство [pic]. Поскольку числа [pic] и [pic] взаимно просты,

имеем [pic], и это доказывает, что алгоритм действительно даёт решение

уравнения [pic]. Буквой [pic] мы обозначили количество делений с остатком,

которое в точности такое же, как и в алгоритме Евклида.

Три приведённых выше алгоритма относятся к разряду так называемых

полиномиальных алгоритмов. Это название носят алгоритмы, сложность которых

оценивается сверху степенным образом в зависимости от длины записи входящих

чисел. Если наибольшее из чисел, подаваемых на вход алгоритма, не

превосходит [pic], то сложность алгоритмов этого типа оценивается величиной

[pic], где [pic] - некоторая абсолютная постоянная. Во всех приведённых

выше примерах [pic].

Полиномиальные алгоритмы в теории чисел - большая редкость. Да и

опенки сложности алгоритмов чаше всего опираются на какие-либо не

доказанные, но правдоподобные гипотезы, обычно относящиеся к аналитической

теории чисел.

Для некоторых задач эффективные алгоритмы вообще не известны. Иногда

в таких случаях все же можно предложить последовательность действий,

которая, «если повезет», быстро приводит к требуемому результату.

Существует класс так называемых вероятностных алгоритмов, которые дают

правильный результат, но имеют вероятностную опенку времени работы. Обычно

работа этих алгоритмов зависит от одного или нескольких параметров. В

худшем случае они работают достаточно долго. Но удачный выбор параметра

определяет быстрое завершение работы. Такие алгоритмы, если множество

«хороших» значений параметров велико, на практике работают достаточно

эффективно, хотя и не имеют хороших опенок сложности.

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

отличать алгоритмы в обычном смысле от вероятностных алгоритмов.

Как пример, рассмотрим вероятностный алгоритм, позволяющий эффективно

находить решения полиномиальных сравнений по простому модулю. Пусть [pic] —

простое число, которое предполагается большим, и [pic] - многочлен, степень

которого предполагается ограниченной. Задача состоит в отыскании решений

сравнения

[pic].

(8)

Например, речь может идти о решении квадратичных сравнений, если степень

многочлена [pic] равна 2. Другими словами, мы должны отыскать в поле [pic]

все элементы, удовлетворяющие уравнению [pic].

Согласно малой теореме Ферма, все элементы поля [pic] являются

однократными корнями многочлена [pic]. Поэтому, вычислив наибольший общий

делитель [pic], мы найдем многочлен [pic], множество корней которого в поле

[pic] совпадает с множеством корней многочлена [pic], причем все эти корни

однократны. Если окажется, что многочлен [pic] имеет нулевую степень, т. е.

лежит в поле [pic], это будет означать, что сравнение (8) не имеет решений.

Для вычисления многочлена [pic] удобно сначала вычислить многочлен

[pic], пользуясь алгоритмом, подобным описанному выше алгоритму возведения

в степень (напомним, что число [pic] предполагается большим). А затем с

помощью аналога алгоритма Евклида вычислить [pic]. Всё это выполняется за

полиномиальное количество арифметических операций.

Таким образом, обсуждая далее задачу нахождения решений сравнения

(8), мы можем предполагать, что в кольце многочленов [pic] справедливо

равенство

[pic]

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

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

2) Вычислим наибольший общий делитель [pic].

3) Если многочлен [pic] окажется собственным делителем [pic], то многочлен

[pic] распадётся на два множителя и с каждым из них независимо нужно

будет проделать все операции, предписываемые настоящим алгоритмом для

многочлена [pic].

4) Если окажется, что [pic] или [pic], следует перейти к шагу 1 и. выбрав

новое значение [pic], продолжить выполнение алгоритма.

Количество операций на шаге 2 оценивается величиной [pic], если

вычисления проводить так, как это указывалось выше при нахождении [pic].

Выясним теперь, сколь долго придётся выбирать числа [pic], пока на шаге 2

не будет найден собственный делитель [pic].

Количество решений уравнения [pic] в поле [pic] не превосходит [pic]. Это

означает, что подмножество [pic] элементов [pic], удовлетворяющих условиям

[pic],

состоит не менее, чем из [pic] элементов. Учитывая теперь, что каждый

ненулевой элемент [pic] удовлетворяет одному из равенств [pic], либо [pic],

заключаем, что для [pic] одно из чисел [pic] будет корнем многочлена [pic],

а другое - нет. Для таких элементов [pic] многочлен [pic], определённый на

шаге 2 алгоритма, будет собственным делителем многочлена [pic].

Итак, существует не менее [pic] «удачных» выборов элемента [pic], при

которых на шаге 2 алгоритма многочлен [pic] распадётся на два собственных

множителя. Следовательно, при «случайном» выборе элемента [pic],

вероятность того, что многочлен не разложится на множители после [pic]

повторений шагов алгоритма 1-4. не превосходит [pic]. Вероятность с ростом

[pic] убывает очень быстро. И действительно, на практике этот алгоритм

работает достаточно эффективно.

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

многочлена [pic]. При [pic] эта вероятность, конечно, еще меньше. Более

тонкий анализ с использованием опенок А. Вейля для сумм характеров

показывает, что вероятность для многочлена [pic] не распасться на множители

при однократном проходе шагов алгоритма 1-4. не превосходит [pic]. Здесь

постоянная в [pic] зависит от [pic].

Если в сравнении (8) заменить простой модуль [pic] составным модулем

[pic], то задача нахождения решений соответствующего сравнения становится

намного более сложной. Известные алгоритмы её решения основаны на сведении

сравнения к совокупности сравнений (8) по простым модулям — делителям

[pic], и. следовательно, они требуют разложения числа то на простые

сомножители, что, как уже указывалось, является достаточно трудоемкой

задачей.

3. КАЧЕСТВЕННАЯ ТЕОРИЯ АЛГОРИТМА RSA

Существует довольно эффективный способ убедиться, что заданное число

является составным, не разлагая это число на множители. Согласно малой

теореме Ферма, если число [pic] простое, то для любого целого [pic], не

делящегося на [pic], выполняется сравнение

[pic].

(9)

Если же при каком-то [pic] это сравнение нарушается, можно утверждать, что

[pic] - составное. Проверка (9) не требует больших вычислений, это следует

из алгоритма 1. Вопрос только в том, как найти для составного [pic] целое

число [pic], не удовлетворяющее (9). Можно, например, пытаться найти

необходимое число [pic], испытывая все целые числа подряд, начиная с 2. Или

попробовать выбирать эти числа случайным образом на отрезке [pic].

К сожалению, такой подход не всегда даёт то, что хотелось бы. Имеются

составные числа [pic], обладающие свойством (9) для любого целого [pic] с

условием [pic]. Такие числа называются числами Кармайкла. Рассмотрим,

например, число [pic]. Так как 560 делится на каждое из чисел 2, 10, 16, то

с помощью малой теоремы Ферма легко проверить, что 561 есть число

Кармайкла. Можно доказать, что любое из чисел Кармайкла имеет вид [pic],

где все простые [pic] различны, причем [pic] делится на каждую разность

[pic]. Лишь недавно, была решена проблема о бесконечности множества таких

чисел.

В 1976 г. Миллер предложил заменить проверку (9) проверкой несколько

иного условия. Если [pic] - простое число, [pic], где [pic] нечётно, то

согласно малой теореме Ферма для каждого [pic] с условием [pic] хотя бы

одна из скобок в произведении

[pic]

делится на [pic]. Обращение этого свойства можно использовать, чтобы

отличать составные числа от простых.

Пусть [pic] - нечётное составное число, [pic], где [pic] нечётно.

Назовем целое число [pic], [pic], «хорошим» для [pic], если нарушается одно

из двух условий:

1) [pic] не делится на [pic];

2) [pic] или существует целое [pic], [pic], такое, что

[pic].

Из сказанного ранее следует, что для простого числа [pic] не

существует хороших чисел [pic]. Если же [pic] составное число, то, как

доказал Рабин, их существует не менее [pic].

Теперь можно построить вероятностный алгоритм, отличающий составные

числа от простых.

3.1. Алгоритм, доказывающий непростоту числа

1) Выберем случайным образом число [pic], [pic], и проверим для

этого числа указанные выше свойства 1) и 2) п.2.

2) Если хотя бы одно из них нарушается, то число [pic] составное.

3) Если выполнены оба условия 1) и 2) п.2, возвращаемся к шагу 1.

Из сказанного выше следует, что составное число не будет определено

как составное после однократного выполнения шагов 1-3 с вероятностью не

большей [pic]. А вероятность не определить его после [pic] повторений не

превосходит [pic]. т. е. убывает очень быстро.

Миллер предложил детерминированный алгоритм определения составных

чисел, имеющий сложность [pic], однако справедливость его результата

зависит от недоказанной в настоящее время так называемой расширенной

гипотезы Римана. Согласно этому алгоритму достаточно проверить условия 1) и

2) п.2 для всех целых чисел [pic], [pic]. Если при каком-нибудь [pic] из

указанного промежутка нарушается одно из условий а) или б), число [pic]

составное. В противном случае оно будет простым или степенью простого

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

Напомним некоторые понятия, необходимые для формулировки расширенной

гипотезы Римана. Они понадобятся нам и в дальнейшем. Пусть [pic] - целое

число. Функция [pic] называется характером Дирихле по модулю [pic], или

просто характером, если эта функция периодична с периодом [pic], отлична от

нуля только на числах, взаимно простых с [pic], и мультипликативна, т. е.

для любых целых [pic] выполняется равенство [pic]. Для каждого [pic]

существует ровно [pic] характеров Дирихле. Они образуют группу по

умножению. Единичным элементом этой группы является так называемый главный

характер [pic], равный 1 на всех числах, взаимно простых с [pic], и 0 на

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

элемента мультипликативной группы характеров.

С каждым характером может быть связана так называемая [pic] - функция

Дирихле - функция комплексного переменного [pic], определённая рядом[pic].

Сумма этого ряда аналитична в области [pic] и может быть аналитически

продолжена на всю комплексную плоскость. Следующее соотношение [pic]

связывает L - функцию, отвечающую главному характеру, с дзета-функцией

Римана [pic]. Расширенная гипотеза Римана утверждает, что комплексные нули

всех L -функций Дирихле, расположенные в полосе [pic], лежат на прямой

[pic]. В настоящее время не доказана даже простейшая форма этой гипотезы -

классическая гипотеза Римана, утверждающая такой же факт о нулях дзета-

функции.

В 1952 г. Анкени с помощью расширенной гипотезы Римана доказал, что

для каждого простого числа [pic] существует квадратичный невычет [pic],

удовлетворяющий неравенствам [pic]. Константа 70 была сосчитана позднее.

Именно это утверждение и лежит в основе алгоритма Миллера. В 1957 г.

Берджесс доказал существование такого невычета без использования

расширенной гипотезы Римана, но с худшей оценкой [pic], справедливой при

любом положительном [pic] и [pic], большем некоторой границы, зависящей

от[pic].

Алгоритм Миллера принципиально отличается от алгоритма 2.1., так как

полученное с его помощью утверждение о том, что число [pic] - составное,

опирается на недоказанную расширенную гипотезу Римана и потому может быть

неверным. В то время как вероятностный алгоритм 2.1. даёт совершенно

правильный ответ для составных чисел. Несмотря на отсутствие оценок

сложности, на практике он работает вполне удовлетворительно.

3.2. Нахождение больших простых чисел

Конечно же, большие простые числа можно строить сравнительно быстро.

При этом можно обеспечить их случайное распределение в заданном диапазоне

величин. В противном случае теряла бы всякий практический смысл система

шифрования RSA. Наиболее эффективным средством построения простых чисел

является несколько модифицированная малая теорема Ферма.

Теорема 2. Пусть [pic] - нечётные натуральные числа, [pic], причем

для каждого простого делителя [pic] числа [pic] существует целое число

[pic] такое, что

[pic]. (10)

Тогда каждый простой делитель [pic] числа [pic] удовлетворяет сравнению

[pic].

Доказательство. Пусть [pic] - простой делитель числа [pic], a [pic] -

некоторый делитель [pic]. Из условий (10) следует, что в поле вычетов [pic]

справедливы соотношения

[pic].

(11)

Обозначим буквой [pic] порядок элемента [pic] в мультипликативной группе

поля [pic]. Первые два из соотношений (11) означают, что [pic] входит в

разложение на простые множители числа [pic] в степени такой же, как и в

разложение [pic], а последнее - что [pic] делится на [pic]. Таким образом,

каждый простой делитель числа [pic] входит в разложение [pic] в степени не

меньшей, чем в [pic], так что [pic] делится на [pic]. Кроме того, [pic]

четно. Теорема 2 доказана.

Следствие. Если выполнены условия теоремы 2 и [pic], то [pic] -

простое число.

Действительно, пусть [pic] равняется произведению не менее двух

простых чисел. Каждое из них, согласно утверждению теоремы 2, не меньше,

чем [pic]. Но тогда [pic]. Противоречие и доказывает следствие.

Покажем теперь, как с помощью последнего утверждения, имея большое

простое число [pic], можно построить существенно большее простое число

[pic]. Выберем для этого случайным образом чётное число [pic] на промежутке

[pic] и положим [pic]. Затем проверим число [pic] на отсутствие малых

простых делителей, разделив его на малые простые числа; испытаем [pic]

некоторое количество раз с помощью алгоритма 5. Если при этом выяснится,

что [pic] - составное число, следует выбрать новое значение [pic] и опять

повторить вычисления. Так следует делать до тех пор, пока не будет найдено

число [pic], выдержавшее испытания алгоритмом 5 достаточно много раз. В

этом случае появляется надежда на то, что [pic] - простое число, и следует

попытаться доказать простоту с помощью тестов теоремы 2.

Для этого можно случайным образом выбирать число [pic], и проверять

Страницы: 1, 2, 3