RSA использует операцию возведения в степень (мы будем обозначать эту операцию символом ^) по модулю для шифровки и дешифровки сообщения, которое получается путем перевода текста в цифровую форму (если речь идет о компьютерах, то текст и так имеет цифровую форму, так что данное замечание тривиально).
Для того, чтобы найти подходящую пару, для которой это равенство верно, нам надо знать функцию Эйлера переноса (Euler's totient function), J(N) для данного значения модуля N. Функция Эйлера представляет собой количество чисел в интервале от 1 до N-1, которые являются простыми относительно N. Для нахождения функции J(N) нaдо, в свою очередь, найти простые факторы N.
Фундаментальная теорема арифметики: Любое не простое число может быть представлено как произведение уникального набора простых чисел.
Относительно простые числа: Два числа называются относительно простыми, если среди их простых факторов нет одинаковых.
Итак, нам надо найти набор простых факторов числа N для того, чтобы вычислить функцию Эйлера. J(N). Нахождение этих факторов является задачей чрезвычайно сложной - практически абсолютно невозможно для достаточно больших N, и именно этот факт и делает PGP таким надежным методом шифрования. Для заданных N и E вы не можете найти D (и, таким образом, расшифровать сообщение) не зная простых факторов числа N, что настолько трудно, что PGP является виртуально невскрываемой при достаточно больших 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), что с вычислительной точки зрения тривиально. Следует отметить, что в модульной арифметике есть закон, гласящий, что для заданного модуля M число может иметь обратное относительно операции умножения по модулю M только если оно является относительно простым по отношению к M. Вот почему мы выбирали E как не имеющее общих простых факторов с J(N), так, чтобы у него имелось обратное D по модулю 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
(на самом деле совершенно не важно какой из ключей
D или
E считается ключом шифровки). Не зная чисел P и Q
практически невозможно вычислить
J(N) и, следовательно, найти D
по заданному E при больших значениях N, так что шифрование
является надежным.
Важно отметить, что не было доказано, что безопасность RSA целиком зависит от проблемы нахождения простых факторов большого числа. Однако все другие способы нахождения D по заданному E оказались эквивалентны по затратам задаче факторизации N. Есть вероятность, что будет найден алгоритм для нахождения E-того корня по модулю N более простым путем, чем факторизация N. Тем не менее, до сих пор не был найден такой алгоритм и RSA выдержал огромное число попыток вскрытия.