4.1.1. Криптосистема rsa

Алгоритм RSA предложили в 1978 г. три автора: Р.Райвест (Rivest), А.Шамир (Shamir) и А.Адлеман (Adleman). Алгоритм получил свое название по первым буквам фамилий его авторов. Алгоритм RSA стал первым полноценным алгоритмом с открытым ключом, который может работать как в режиме шифрования данных, так и в режиме электронной цифровой подписи.

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

В криптосистеме RSA открытый ключ e, секретный ключ d открытый текст М и шифртекст С принадлежат множеству целых чисел

где N – модуль: . Здесь Р и Q – случайные большие простые числа. Для обеспечения максимальной безопасности выбирают Р и Q равной длины и хранят в секрете.

Множество Z_N с операциями сложения и умножения по модулю N образует арифметику по модулю N.

Число e выбирают случайным образом так, чтобы выполнялись условия:

,

,

где – функция Эйлера, НОД(a,b) – наибольший общий делитель чисел a и b. Функция Эйлера указывает количество положительных целых чисел в интервале от 1 до N, которые взаимно просты с N. Второе из указанных выше условий означает, что e и функция Эйлера должны быть взаимно простыми. Это гарантирует существование величины d, такой, что

или .

В RSA число e рассматривают как открытый ключ и используют для шифрования данных, а d – как секретный ключ для расшифрования.

Вычислить секретный ключ d по известным значениям e и можно с помощью расширенного алгоритма Евклида, который позволяет решить следующую задачу: даны целые неотрицательные числа a и b ( ), найти целые x, y, c, такие, что ax + by = c, где c = НОД(a,b).

Приведем его описание.

НА ВХОДЕ: два неотрицательных числа a и b:

НА ВЫХОДЕ: c = НОД(a, b) и целые x, y: ax + by = c.

1. Положить x₂:=1, x₁:=0, y₂:=0, y₁:=1

2. Пока b > 0 выполнят шаги 2.1 и 2.2

2.1. q:=a div b, r:=a – qb, x:=x₂ – qx₁, y:=y₂ – qy₁

2.2. a:=b, b:=r, x₂:=x₁, x₁:=x, y₂:=y₁, y₁:=y

3. Положить c:=a, x:=x₂, y:=y₂ и возвратить (c, x, y). Конец.

Нахождение d сводится к выполнению указанного алгоритма при значениях входных параметров a = и b = e. В этом случае искомое значение d есть выходной параметр y.

В RSA преобразование шифрования определяет шифртекст С через пару (открытый ключ e, открытый текст М) в соответствии со следующей формулой:

.

В качестве алгоритма быстрого вычисления значения С используют ряд последовательных возведений в квадрат целого М и умножений на М с приведением по модулю N.

Обращение функции , т.е. определение значения М по известным значениям С, e и N, практически не осуществимо при .

Однако обратную задачу можно решить, используя пару (секретный ключ d, шифртекст С) по следующей формуле:

.

Рассмотрим конкретный пример:

1. Выбрать два простых числа: P = 7, Q = 17;

2. Вычислить ;

3. Вычислить ;

4. Выбрать е так, чтобы е было взаимнопростым с и меньше, чем : пусть е = 5;

5. Определить d так, чтобы и d < 96: d = 77, т.к. 775 = 385 = 496 + 1;

6. Зашифровать сообщение М = 19: ;

7. Расшифровать C = 66: .

Общая процедура шифрования/расшифрования в криптосистеме RSA представляет собой следующую последовательность действий.

1. Получатель сообщения формирует значения , e и d, так, как было описано выше. Параметры N и e являются общедоступными, и могут быть распространенны по незащищенному каналу связи. Параметры P, Q и d являются секретными.

2. Отправитель сообщения, зная N и e, осуществляет шифрование сообщения. Если открытый текст представляет собой число , то он разбивается на блоки, каждый из которых может быть представлен в виде числа . Каждый такой блок подвергается преобразованию:

.

В итоге получается шифртекст , который отправляется получателю.

3. Получатель расшифровывает принятый шифртекст , используя секретный ключ d по формуле:

.

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