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

Алгоритм RSA был предложен в 1978 году Р.Райвестом, А. Шамиром, А. Адлеманом и был назван по первым буквам фамилий его авторов. Данный алгоритм стал первым алгоритмом шифрования с открытым ключом. Надежность данного алгоритма основывается на трудности факторизации больших чисел и вычисления дискретных логарифмов [13,8].

В криптосистеме RSA открытый ключ ОК, секретный ключ СК, исходное сообщение М и шифротекст С являются целыми числами от 0 до N-1, где N – модуль.

Пусть пользователь А является получателем сообщения, которое ему должен переслать отправитель B.

Пользователь A должен вначале сгенерировать ключевую пару RSA. Это он делает следующим образом.

Алгоритм формирование ключевой пары пользователем А

1. Выбираем случайные большие простые числа P и Q. Для обеспечения максимальной безопасности P и Q выбирают примерно равной длины и хранят в секрете.

2. Вычисляем модуль . Согласно формуле (4.1) , где - функция Эйлера.

3. Открытый ключ ОК_А выбирается случайно таким образом, чтобы выполнялись следующие условия:

1<ОКA£ , НОД(ОКА, )=1

(5.11)

4. Секретный ключ СК_A находится по сформированному открытому ключу так, что

СКА×ОКАº1 (mod ) или СКА=ОКА-1 (mod (P-1) × (Q-1))

(5.12)

Пользователь A может легко найти СК_А, используя расширенный алгоритм Евклида, зная числа P и Q, а значит и .

Любой другой пользователь не может зная открытый ключ ОК_А вычислить СК_А, так как ему не известны числа P и Q. Для их нахождения ему потребуется факторизовать известное ему число N, что является вычислительно сложной задачей.

Шифрование и дешифрование сообщений в криптосистеме RSA

Для того, чтобы зашифровать открытое сообщение M, отправитель B должен возвести его в степень открытого ключа пользователя А по модулю N. То есть преобразование шифрования выполняется в соответствие с формулой (5.13).

(5.13)

Обращение данной функции, то есть определение значения M по известным значениям С, ОК_А, N практически не осуществимо при больших N ( ).

Однако, знание секретного ключа СК_А позволяет обратить данную функцию, то есть решить задачу дешифровки криптограммы C. Для дешифровки криптограммы С необходимо возвести ее в степень секретного ключа пользователя А по модулю N. Таким образом, дешифровка сообщения выполняется в соответствие с формулой (5.14).

(5.14)

Действительно,

В теории чисел известна теорема Эйлера, утверждающая, что если НОД(x,N)=1, то .

Согласно 5.12, СК_А×ОК_Аº1 (mod ), то есть СК_А×ОК_А=k× +1. Таким образом,

Таким образом, показано, что .

Получатель А, который создает ключевую пару (ОК_А,СК_А) защищает два параметра: 1) секретный ключ СК_А; 2) пару чисел P и Q. Рассекречивание данных чисел приводит к тому, что злоумышленник сможет вычислить , а значит и вычислить секретный ключ СК_А согласно (5.12).

Открытыми в криптосистеме RSA являются только значения ОК_А и N.

В настоящее время разработчики криптоалгоритмов с открытым ключом на базе RSA предлагают применять в качестве чисел P,Q,N – числа длиной не менее 200-300 десятичных разрядов.

Пример 5.11

Зашифруем сообщение DAC по алгоритму RSA. Для простоты вычислений будем оперировать с небольшими числами P и Q.

Действия получателя А

1. Выберем P = 5 и Q = 13

2. Модуль

3.

4. В качестве ОК_А необходимо выбрать значение, удовлетворяющее условиям , . Пусть ОК_А = 5.

5. Необходимо найти СК_А, такой что . Это СК_А=29. Действительно, .

6. Отправляем пользователю B пару чисел (N=65, ОК_А=5)

Действия отправителя B

1. Представим отправляемое сообщение в виде последовательности целых чисел от 0 до 64. Присвоим букве А номер 1, букве B – 2, С – 3, D – 4. Тогда открытый текст DAC запишется в виде последовательности чисел 413, то есть M₁=4, M₂=1, M₃=3.

2. Сформируем шифротекст по формуле 5.13:

,

,

.

3. Пользователь B отправляет A криптограмму C₁, C₂, C₃=49, 1, 48.

Действия пользователя A

1. Раскрываем шифротекст по формуле 5.14:

,

,

.

Таким образом, восстановлено исходное сообщение M₁=4=D, M₂=1=A, M₃=3=C. Исходное сообщение – DAC.