Проблема RSA.

Криптостойкость RSA

Зная n, e, M, C,(mod n) найти d

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

1. Метод «грубой силы»: перебор все возможные закрытые ключи.
2. Факторизация (разложение числа n на два простых сомножителя). Это дает возможность вычислить Φ(n) = (p-1) · (q-1) и d = e^-1 (mod (n)).
3. Определить Φ(n) непосредственно, без начального определения р и q. Это также даст возможность определить d = e^-1 (mod Φ(n)).
4. Определить d непосредственно, без начального определения Φ(n).

Контрмера против атаки методом «грубой силы»стандартная: использовать большие ключи. Однако при этом надо учитывать, что сложность вычислений таких функций не является линейной от количества битов ключа, а возрастает быстрее, чем ключ. Таким образом, размер ключа должен быть достаточно большим, чтобы сделать лобовую атаку непрактичной, и достаточно маленьким для возможности практического шифрования.

Сложность остальных атак (при достаточно больших n) эквивалентна сложности задачи факторизации, которая в настоящее время относится к классу вычислительно сложных ( не имеет эффективного алгоритма решения) и имеет субэкспоненциальную сложность, пропорциональную

Задача факторизации имеет большую историю, однако работы в этой области активизировались с появлением криптографии с открытым ключом. Прогресс в области факторизации приведен в таблице 2.10.4.

Таблица 2.10.4.

В 2003г. были разработаны СБИС для вскрытия криптосистемы RSA. Стоимость порядка $10 млн. С их использованием факторзация числа длиной 512 бит выполняется за 10 мин., а длиной 1024 бита –менее, чем за 1 год.

Поэтому рекомендуемая длина модуля n – не менее 2048 бит.

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