Криптосистема шифрования данных RSA

       

Криптосистема шифрования данных RSA


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

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

В криптосистеме RSA открытый ключ КA, секретный ключ КB, сообщение М и криптограмма С принадлежат множеству целых чисел

ZN={0,1,2,...,N-1}, (5)

где N - модуль:

N = P*Q. (6)

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

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

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

, (7)

, (8)

где - функция Эйлера.

Функция Эйлера указывает количество положительных целых чисел в интервале от 1 до N,которые взаимно просты с N.



Второе из указанных выше условий означает, что открытый ключ КA и функция Эйлера должны быть взаимно простыми.

Далее, используя расширенный алгоритм Евклида, вычисляют секретный ключ kB, такой, что

kB * КB = 1 (mod() (9)

или

.

Это можно осуществить, так как получатель В знает пару простых чисел (P,Q) и может легко найти . Заметим, что kB и N должны быть взаимно простыми.

Открытый ключ КB используют для шифрования данных, а секретный ключ kB -для расшифрования.

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

(10)

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

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

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


. (11)

Процесс расшифрования можно записать так:

DB(ЕB (М)) = М. (12)

Подставляя в (12) значения (10) и (11), получаем:

или

(13)

Величина играет важную роль в теореме Эйлера, которая утверждает, что если НОД (х,N)=1, то

,

или в несколько более общей форме

(14)

Сопоставляя выражения (4.13) и (4.14), получаем

или, что то же самое,

.

Именно поэтому для вычисления секретного ключа kB используют соотношение (9).

Таким образом, если криптограмму

возвести в степень kB, то в результате восстанавливается исходный открытый текст М, так как

Таким образом, получатель В, который создает криптосистему, защищает два параметра:



  • секретный ключ kB и


  •  


  • пару чисел (P,Q),


  • произведение которых дает значение модуля N. С другой стороны, получатель В открывает значение модуля N и открытый ключ КB.

    Противнику известны лишь значения КB и N. Если бы он смог разложить число N на множители Р и Q, то он узнал бы "потайной ход" - тройку чисел {Р,Q, КB}, вычислил значение функции Эйлера

    и определил значение секретного ключа kB.

    Однако, как уже отмечалось, разложение очень большого N на множители вычислительно не осуществимо (при условии, что длины выбранных Р и Q составляют не менее 100 десятичных знаков).






    Содержание раздела