Обсуждение криптоанализа

Можно определить четыре возможных подхода для криптоанализа алгоритма RSA:

1. Лобовая атака: перебрать все возможные закрытые ключи.

2. Разложить n на два простых сомножителя. Это даст возможность вычислить .

3. Определить непосредственно, без начального определения р и q. Это также даст возможность определить .

4. Определить d непосредственно, без начального определения .

Защита от лобовой атаки для RSA и ему подобных алгоритмов состоит в использовании большой длины ключа. Таким образом, чем больше битов в е и d, тем лучше. Однако, так как вычисления необходимы как при создании ключей, так и при шифровании/ дешифровании, чем больше размер ключа, тем медленнее работает система.

Большинство дискуссий о криптоанализе RSA фокусируется на задаче разложения n на два простых сомножителя. В настоящее время неизвестны алгоритмы, с помощью которых можно было бы разложить число на два простых множителя для очень больших чисел (т.е. несколько сотен десятичных цифр). Лучший из известных алгоритмов дает результат, пропорциональный:

L (n) = e^{sqrt (ln n * ln (ln n))}

Пока не разработаны лучшие алгоритмы разложения числа на простые множители, можно считать, что величина n от 100 до 200 цифр в настоящее время является достаточно безопасной. На современном этапе считается, что число из 100 цифр может быть разложено на множители за время порядка двух недель. Для дорогих конфигураций (т.е. порядка $10 млн) число из 150 цифр может быть разложено приблизительно за год. Разложение числа из 200 цифр находится за пределами вычислительных возможностей. Например, даже если вычислительный уровень в 10¹² операций в секунду достижим, что выше возможностей современных технологий, то потребуется свыше 10 лет для разложения на множители числа из 200 цифр с использованием существующих алгоритмов.

Для известных в настоящее время алгоритмов задача определения по данным е и n, по крайней мере, сопоставима по времени с задачей разложения числа на множители.

Для того чтобы избежать выбора значения n, которое могло бы легко раскладываться на сомножители, на р и q должно быть наложено много дополнительных ограничений: р и q должны друг от друга отличаться по длине только несколькими цифрами. Таким образом, оба значения р и q должны быть от 10⁷⁵ до 10¹⁰⁰.

Оба числа (р - 1) и (q - 1) должны содержать большой простой сомножитель.

gcd (p -1, q - 1) должен быть маленьким.