Алгоритм RSA предложили в 1978 г. три автора: Р.Райвест (Rivest), А.Шамир (Shamir) и А.Адлеман (Adleman). Алгоритм получил свое название по первым буквам фамилий его авторов. Алгоритм RSA стал первым полноценным алгоритмом с открытым ключом, который может работать как в режиме шифрования данных, так и в режиме электронной цифровой подписи.
Надежность алгоритма основывается на трудности факторизации больших чисел и трудности вычисления дискретных логарифмов.
В криптосистеме RSA открытый ключ Кв, секретный ключ kв, сообщение М и криптограмма С принадлежат множеству целых чисел
ZN = {0, 1, 2, ..., N –1}, (2.5)
где N – модуль:
N = P*Q (2.6) .
Здесь P и Q – случайные большие простые числа. Для обеспечения максимальной безопасности выбирают P и Q равной длины и хранят в секрете.
Множество ZN с операциями сложения и умножения по модулю N образует арифметику по модулю N.
|
1< Кв £ j (N), НОД (Кв, j (N)) =1, (2.7)
j (N)=(P –1) (Q –1), (2.8)
где j (N) – функция Эйлера.
Функция Эйлера j (N) указывает количество положительных целых чисел в интервале от 1 до N, которые взаимно проcты с N.
Второе из указанных выше условий означает, что открытый ключ Кв и функция Эйлера j (N) должны быть взаимно простыми.
Далее, используя расширенный алгоритм Евклида, вычисляют секретный ключ kв, такой, что
kв * Кв º 1 (mod j (N)) (2.9)
или
kв = Кв–1 (mod (P –1)(Q –1)).
Это можно осуществить, так как получатель В знает пару простых чисел (P,Q) и может легко найти j (N). Заметим, что kв и N должны быть взаимно простыми.
Открытый ключ Кв используют для шифрования данных, а секретный ключ kв – для расшифрования.
Преобразование шифрования определяет криптограмму С через пару (открытый ключ Кв, сообщение М) в соответствии со следующей формулой:
C = (M) = EВ (M) = (mod N). (2.10)
В качестве алгоритма быстрого вычисления значения C используют ряд последовательных возведений в квадрат целого M и умножений на M с приведением по модулю N.
Обращение функции C = (mod N), т.е. определение значения M по известным значениям C, Кв и N, практически не осуществимо при N » 2 512.
|
М = (С) = DВ (C) = (mod N). (2.11)
Процесс расшифрования можно записать так:
DВ(EВ (М)) = М. (2.12)
Подставляя в (2.12) значения (2.10) и (2.11), получаем:
= М (mod N)
или
= M (mod N). (2.13)
Величина j (N) играет важную роль в теореме Эйлера, которая утверждает, что если НОД (x, N) =1, то
xj(N) º 1 (mod N),
или в несколько более общей форме
xn×j(N)+1 º x (mod N). (2.14)
Сопоставляя выражения (2.13) и (2.14), получаем
Кв * kв = n * j (N) +1
или, что то же самое,
Кв * kв º1 (mod j (N)).
Именно поэтому для вычисления секретного ключа kв используют соотношение (2.9).
Таким образом, если криптограмму
C = (mod N)
возвести в степень kв, то в результате восстанавливается исходный открытый текст М, так как
= = Mn×j(N)+1 º M (mod N).
Таким образом, получатель В, который создает криптосистему, защищает два параметра: 1) секретный ключ kв и 2) пару чисел (P,Q), произведение которых дает значение модуля N. С другой стороны, получатель В открывает значение модуля N и открытый ключ Кв.
Противнику известны лишь значения Кв и N. Если бы он смог разложить число N на множители P и Q, то он узнал бы "потайной ход" – тройку чисел {P,Q,Кв}, вычислил значение функции Эйлера
|
и определил значение секретного ключа kв.
Однако, как уже отмечалось, разложение очень большого N на множители вычислительно не осуществимо (при условии, что длины выбранных P и Q составляют не менее 100 десятичных знаков).
Дата: 2016-10-02, просмотров: 216.