Является наиболее известным
алгоритмом с открытым ключом. Может использоваться как для шифрования, так и
для создания подписи.
RSA использует операцию возведения
в степень по модулю для шифровки и дешифровки сообщения, которое получается
путем перевода текста в цифровую форму.
Функция шифровки,
используемая в RSA, выглядит так: C = T^E mod N, где T представляет собой шифруемый текст, C - зашифрованный текст, а E представляет собой открытый ключ. Другими словами, T возводится в степень E по модулю N.
Функция дешифрования выглядит так: T = C^D mod N где D представляет собой секретный ключ. Пара ключей E и D должна быть
выбрана так, что E является обратным к D по отношению к операции возведения в степень по модулю
N. Иными словами, (T^E mod N)^D mod N = T^ED mod N = T.
Чтобы найти подходящую пару,
для которой это равенство верно, нам надо знать функцию J(N) для данного
значения модуля N. Функция представляет собой
количество чисел в интервале от 1 до N-1, которые
являются простыми относительно N. Для
нахождения функции J(N) нaдо, в свою
очередь, найти простые факторы N.
Итак, нам надо найти набор
простых факторов числа N для того,
чтобы вычислить функцию J(N).
Практический способ
сгенерировать пару ключей - это сначала сгенерировать само N путем умножения двух больших простых чисел P и Q, так что
простые факторы N мы уже знаем. Для числа, которое
имеет только два простых фактора: J(N) = (P-1)(Q-1)
Теперь мы выбираем некоторое
число E, которое является простым относительно J(N) . Нам надо
найти D, которое является обратным к E по отношению к операции возведения в степень по
модулю N. Это можно сделать, зная J(N).
Операция возведения в степень
использует модуль N и показатели экспонент должны
использовать модуль J(N).Например рассмотрим,(T^E mod N)^D mod N = T^ED mod N.
Оказывается,что умножать
показ. степени E и D мы должны с использ. mod J(N),а не mod N.Для того, чтобы для заданного показателя шифровки E найти подходящее обратное число D, нам следует удовлетворить равенство: T^ED mod N = T.
Для этого достаточно, чтобы ED mod J(N) = 1, так как T^1 mod N = T. Так что
проблема нахождения D сводится к проблеме нахождения
числа, обратного E по модулю J(N), что с
вычислительной точки зрения тривиально. Тривиальные комбинации E и D (например E = D) отбрасываются
как неподходящие с точки зрения секретности, и тогда выбираем новое E.
Когда мы выбрали значение N и сгенерировали наши ключи E и D, можно забыть
о P, Q и J(N). Мы имеем
подходящ. ключи шифровки и дешифровки E и D.
C = T^E mod N
and T = C^D mod N. Не
зная чисел P и Q практически невозможно вычислить J(N) и найти D по заданному E при больших значениях N, так что шифрование является надежным.
Итоговый список шагов, необходимых для генерации ключа
Выбираем пару произвольных
больших простых чисел P и Q и находим N путем
умножения
Вычисляем функцию Эйлера
числа N, J(N) = (P-1)(Q-1)
Выбираем число E так, чтобы оно было относительно простым по отношению
к J(N)
Находим D, обратное число к E по отношению к операции умножения по модулю J(N), и
тривиальные значения отбраковываем как несекретные (E=D)
Найдя подходящую пару ключей,
ключ E объявляем открытым и его можно использовать для
шифровки сообщений, адресованных владельцу пары E и D: C = T^E mod N
Ключ D держится в секрете и используется для дешифровки
полученных сообщений: T = C^D mod N.
|