Алгоритм шифрования RSA

Несмотря на довольно большое число различных СОК, наиболее популярна - криптосистема RSA, разработанная в 1977 году и получившая название в честь ее создателей: Рона Ривеста[2], Ади Шамира и Леонарда Эйдельмана.

Они воспользовались тем фактом, что нахождение больших простых чисел в вычислительном отношении осуществляется легко, но разложение на множители произведения двух таких чисел практически невыполнимо. Доказано (теорема Рабина), что раскрытие шифра RSA эквивалентно такому разложению. Поэтому для любой длины ключа можно дать нижнюю оценку числа операций для раскрытия шифра, а с учетом производительности современных компьютеров оценить и необходимое на это время.

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

В настоящее время алгоритм RSA используется во многих стандартах, среди которых SSL, S-HHT P, S-MIME, S/WAN, STT и P CT.

Рассмотрим математические результаты, положенные в основу этого алгоритма.

Теорема 1. (Малая теорема Ферма.)

Если р - простое число, то

x^{p -1} = 1 (mod p) (1)

для любого х, и

x^p = х (mod p) (2)

для любого х.

Доказательство. Достаточно доказать справедливость уравнений (1) и (2) для х ОZ. Проведем доказательство методом индукции.

Очевидно, что уравнение (8.2.2) выполняется при х=0 и 1. Далее

x^p =(x -1+1) ^p = е C(p,j)(x -1)^j=(x -1) ^p +1 (mod p), 0?j? p

так как C(p,j)=0(mod p) при 0<j< p. С учетом этого неравенства и предложений метода доказательства по индукции теорема доказана.

Определение. Функцией Эйлера j(n) называется число положительных целых, меньших n и простых относительно n.

n
j(n)

Теорема 2. Если n = pq, (p и q - отличные друг от друга простые числа), то

j(n)=(p -1)(q -1).

Теорема 3. Если n = pq, (p и q - отличные друг от друга простые числа) и х - простое относительно р и q, то

x ^j(n) (mod n) = 1

Следствие. Если n = pq, (p и q - отличные друг от друга простые числа) и е простое относительно j(n), то отображение Е_e,n: x ® x ^e (mod n) является взаимно однозначным на Z _n.

Очевиден и тот факт, что если е - простое относительно j(n), то существует целое d, такое, что

ed (mod j(n)) = 1

Числа называются взаимно простыми, если их наибольший общий делитель (НОД) = 1. Наиболее эффективным методом поиска НОД является алгоритм Евклида. Этот алгоритм существует в двух модификациях. Первая – основана на вычитании, вторая – на делении.

Идея метода на основе вычитания проста. Из набора выбираются любые два ненулевых числа, и большее из них (или любое, если числа равны) заменяется разностью этих чисел. Этот процесс повторяется до тех пор, пока не останется одно ненулевое число. Это число и будет наибольшим общим делителем исходного набора, состоящего из натуральных чисел.

В таблице 1 как пример представлен протокол работы алгоритма Евклида, основанном на методе вычитания, для чисел 72, 84, 132, 144 наибольший общий делитель НОД(72, 84, 132, 144) = 12.

Номер	шага	1-ечисло	2-ечисло	3-ечисло	4-ечисло	Сумма чисел
Шаг
Шаг
Шаг
Шаг
Шаг
Шаг
Шаг
Шаг
Шаг
Шаг
Шаг
Шаг
Шаг

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

На этих математических фактах и основан популярный алгоритм RSA.

Алгоритм RSA – несимметричный, т. е. для шифрования и расшифровывания используются разные ключи. Любой из ключей может быть открытым, т. е. кто угодно сможет зашифровать текст, но расшифровать -- только тот, кто знает секретный ключ (хорошие системы парольной идентификации -- пароли хранятся в зашифрованном виде, ввод шифруется и сравнивается с паролем -- т. е. даже полностью разобравшись в логике шифратора нельзя узнать исходный пароль, т. к. ключ для расшифровывания будет физически отсутствовать) или, наоборот, прочитать текст может каждый, но зашифровать -- только один человек (системы подтверждения подлинности; программы, зашифрованный код которых нельзя изменить, даже зная алгоритм шифрования).

Вот краткое изложение алгоритма:

1. Выбираются два достаточно больших простых числа -- P и Q;

2. N:= P ´ Q;

3. Вычисляется ф-ция Эйлера: j(N) = M = (P-1) ´ (Q-1);

4. Выбирается число D, взаимно простое с M, т. е. НОД(D,M) = 1;

5. Вычисляется число E взаимно обратное D, так чтобы (E ´ D) = 1 mod M;

6. Теперь пара (E,N) -- открытый ключ, (D,N) -- закрытый.

Шифрование происходит так:

1. Данные разбиваются на блоки (С), каждый из которых может быть представлен числом от 0 до N-1;

2. Для шифрования полагаем C:= (B^E) mod N;

3. Для расшифровывания полагаем B:= (C^D) mod N.

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

Так как криптостойкость основана сложности разложения на множители, рекомендуется использовать в качестве ключей достаточно большие числа – от 512 до 2048 двоичных разрядов

Для достижения хорошей секретности, кроме того, необходимо, чтобы числа (P-1) и (Q-1) имели большие простые делители (т. е. число 2^X+1 является "плохим"). Кроме того, при регулярном использовании алгоритма, лучше, если у разных ключей будут отличаться оба числа в паре (т. е. нежелательно использовать ключи (E1,N) и (E2,N) или (E,N1) и (E,N2)).

На сегодняшний день RSA является самым распространенным криптографическим алгоритмом с открытым ключом.

Очевидно, для того чтобы найти секретный ключ D по отношению к открытому ключу E, требуется знание множителей P и Q. Время выполнения наилучших из известных алгоритмов разложения при N =10¹⁰⁰ на сегодняшний день выходит за пределы современных технологических возможностей.