Лекция: Атаки на систему RSA

Обозначим через(ℤ/N)* – мультипликативную группы вычетов кольца ℤ/N. Система RSA основана на использовании однонаправленной функции f:(ℤ/N)*→ (ℤ/N)*, где

f(x) º xe (mod N) (1)

для составного числа N, факторизация которого секретна, и натурального e такого, что НОД(e,j(N))=1. Для вычисления значений f(x) достаточно знать числа N и e. Если d такое натуральное число, что ed º 1 (modj(N)), то функция f(x) может быть легко обращена. Действительно,

(xe)d º xed º x1+j(N)k º x (mod N), (2)

где ed = 1+j(N)k для натурального k. Мы воспользовались теоремой Эйлера xj(N) º 1 (mod N) для (x, N)=1.

Известен алгоритм вычисления x (mod N) из сравнения (1) при условии, что известно каноническое разложение N. Очевидно, что если известна факторизация
N = N1N2, то решение (1) сводится к решению того же сравнения по mod N1 и mod N2 . Поэтому чтобы усложнить факторизацию модуля N обычно берут N = pq, где p, q различные нечетные простые числа близкие по величине к. Имеются другие ограничения на выбор p, q. Эти ограничения вводятся для того, чтобы затруднить факторизацию N посредством известных методов разложения больших целых чисел.

Проблема RSA.Пусть имеется эффективный алгоритм вычисления x из сравнения xe º y (mod N) при некотором e¹1, НОД(e,j(N))=1 и любых yÎ(ℤ/N)*. Построить эффективный алгоритм факторизации N.

Покажем, что знание числа d эквивалентно факторизации N. Очевидно, что знание p, q таких, что N = pq позволяет вычислить j(N)=(p-1)(q-1). Отсюда d легко найти из сравнения

ed º 1 (modj(N)). (3)