Алгоритм RSA

RSA является наиболее известным алгоритмом с открытым ключом. Может использоваться как для шифрования, так и для создания подписи. 

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

Функция шифровки, используемая в RSA, выглядит так: C = T^EmodN, где T представляет собой шифруемый текст, C - зашифрованный текст, а E представляет собой открытый ключ. Другими словами, T возводится в степень E по модулю N. Функция дешифрования выглядит так: T = C^DmodN где D представляет собой секретный ключ. Пара ключей E и D должна быть выбрана так, что E является обратным к D по отношению к операции возведения в степень по модулю N. Иными словами, (T^EmodN)^DmodN = T^EDmodN = 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^EmodN)^DmodN = T^EDmodN.

Оказывается,что умножать показ. степени E и D мы должны с использ. modJ(N),а не modN.Для того, чтобы для заданного показателя шифровки E найти подходящее обратное число D, нам следует удовлетворить равенство: T^EDmodN = T.

Для этого достаточно, чтобы EDmodJ(N) = 1, так как T^1 modN = T. Так что проблема нахождения D сводится к проблеме нахождения числа, обратного E по модулю J(N), что с вычислительной точки зрения тривиально. Тривиальные комбинации E и D (например E = D) отбрасываются как неподходящие с точки зрения секретности, и тогда выбираем новое E.

Когда мы выбрали значение N и сгенерировали наши ключи E и D, можно забыть о P, Q и J(N). Мы имеем подходящ. ключи шифровки и дешифровки E и D.

C = T^EmodNandT = C^DmodN. Не зная чисел 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^EmodN