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

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

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

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

2. Вычисляем модуль . Формируем функцию Эйлера.

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

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

(7.1)

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

СКАОКА (mod )1 или СКА=ОКА^-1 (mod (P-1)  (Q-1))

(7.2)

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

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

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

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

(7.3)

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

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

(7.4)

Получатель А, который создает ключевую пару (ОК_А,СК_А) защищает два параметра:

• секретный ключ СК_А.

• пару чисел P и Q.

Рассекречивание данных чисел приводит к тому, что злоумышленник сможет вычислить , а значит и вычислить секретный ключ СК_А согласно (7.3).

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

Пример 7.1

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

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

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

2. Найдем

3. .

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

ОК_А = 5.

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

определяемое подбором. Оно не единственно. Действительно, .

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

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

1. Представим отправляемое сообщение в виде последовательности целых чисел от 0 до 63. Присвоим букве А

номер 1, букве B – 2, С – 3, D – 4 и т.д. Тогда открытый текст DAC запишется в виде последовательности чисел

413, то есть M₁=4, M₂=1, M₃=3.

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

, , .

2. B отправляет для A криптограмму {C₁, C₂, C₃ }= {49, 1, 48}.