Криптосистемы с открытым ключом. Алгоритм шифрования RSA

ght"> .                            (2)

При некоторых  условиях на и это сравнение имеет единственное решение .

     Для того, чтобы описать эти условия и объяснить, как можно найти решение, нам потребуется одна теоретико-числовая функция, так называемая функция Эйлера. Эта функция натурального аргумента обозначается и равняется количеству целых чисел на отрезке от 1 до , взаимно простых с . Так и для любого простого числа и натурального . Кроме того, для любых натуральных взаимно простых и . Эти свойства позволяют легко вычислить значение , если известно разложение числа на простые сомножители.

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

                                           .                   (3)

Такое число существует, поскольку  , и притом единственно. Здесь и далее символом будет обозначаться наибольший общий делитель чисел и . Классическая теорема Эйлера, утверждает, что для каждого числа , взаимно простого с , выполняется сравнение и, следовательно.

                                                 .                          (4)

Таким образом, в предположении , единственное решение сравнения (2) может быть найдено в виде

                                          .                                            (5)

Если  дополнительно предположить, что  число  состоит из различных простых сомножителей, то сравнение (5) будет выполняться и без предположения . Действительно, обозначим и . Тогда делится на , а из (2) следует, что . Подобно (4), теперь легко находим . А кроме того, имеем . Получившиеся сравнения в силу дают нам (5).

     Функция (1), принятая в системе RSA, может быть вычислена достаточно быстро. Обратная к функция вычисляется по тем же правилам, что и , лишь с заменой показателя степени на . Таким образом, для функции (1) будут выполнены указанные выше свойства 1) и 2).

     Для вычисления функции (1) достаточно знать  лишь числа  и . Именно они составляют открытый ключ для шифрования. А вот для вычисления обратной функции требуется знать число . оно и является «секретом», о котором речь идёт в пункте в). Казалось бы. ничего не стоит. зная число . разложить его на простые сомножители, вычислить затем с помощью известных правил значение и, наконец, с помощью (3) определить нужное число . Все шаги этого вычисления могут быть реализованы достаточно быстро, за исключением первого. Именно разложение числа на простые множители и составляет наиболее трудоемкую часть вычислений. В теории чисел несмотря на многолетнюю её историю и на очень интенсивные поиски в течение последних 20 лет, эффективный алгоритм разложения натуральных чисел на множители так и не найден. Конечно, можно, перебирая все простые числа до , и. деля на них , найти требуемое разложение. Но, учитывая, что количество простых в этом промежутке, асимптотически равно , находим, что при , записываемом 100 десятичными цифрами, найдётся не менее простых чисел, на которые придётся делить при разложении его на множители. Очень грубые прикидки показывают, что компьютеру, выполняющему миллион делений в секунду, для разложения числа таким способом на простые сомножители потребуется не менее, чем лет. Известны и более эффективные способы разложения целых чисел на множители, чем простой перебор простых делителей, но и они работают очень медленно.

     Авторы  схемы 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 компьютеров, объединённых сетью Internet. Наконец, отметим, что премия в 100$ была передана в Free Software Foundation.

  

 

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

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

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

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

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

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

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

.

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

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

,

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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