Криптосистема шифрования данных 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, то в результате восстанавливается исходный открытый текст М, так как
Таким образом, получатель В, который создает криптосистему, защищает два параметра:
произведение которых дает значение модуля N. С другой стороны, получатель В открывает значение модуля N и открытый ключ КB.
Противнику известны лишь значения КB и N. Если бы он смог разложить число N на множители Р и Q, то он узнал бы "потайной ход" - тройку чисел {Р,Q, КB}, вычислил значение функции Эйлера
и определил значение секретного ключа kB.
Однако, как уже отмечалось, разложение очень большого N на множители вычислительно не осуществимо (при условии, что длины выбранных Р и Q составляют не менее 100 десятичных знаков).
