Проблема RSA.
Криптостойкость RSA
Зная n, e, M, C,(mod n) найти d
Можно определить четыре возможных подхода для криптоанализа алгоритма RSA:
- Метод «грубой силы»: перебор все возможные закрытые ключи.
- Факторизация (разложение числа n на два простых сомножителя). Это дает возможность вычислить Φ(n) = (p-1) · (q-1) и d = e-1 (mod (n)).
- Определить Φ(n) непосредственно, без начального определения р и q. Это также даст возможность определить d = e-1 (mod Φ(n)).
- Определить d непосредственно, без начального определения Φ(n).
Контрмера против атаки методом «грубой силы»стандартная: использовать большие ключи. Однако при этом надо учитывать, что сложность вычислений таких функций не является линейной от количества битов ключа, а возрастает быстрее, чем ключ. Таким образом, размер ключа должен быть достаточно большим, чтобы сделать лобовую атаку непрактичной, и достаточно маленьким для возможности практического шифрования.
Сложность остальных атак (при достаточно больших n) эквивалентна сложности задачи факторизации, которая в настоящее время относится к классу вычислительно сложных ( не имеет эффективного алгоритма решения) и имеет субэкспоненциальную сложность, пропорциональную
L (n) = esqrt (ln n * ln (ln n))Задача факторизации имеет большую историю, однако работы в этой области активизировались с появлением криптографии с открытым ключом. Прогресс в области факторизации приведен в таблице 2.10.4.
Таблица 2.10.4.
Размер N (бит) | Размер N (дес. разрядов) | Дата факторизации | Оценка трудоемкости | Примечание |
7 MIPS лет | ||||
830 MIPS лет | ||||
5000 MIPS лет | ||||
1000 MIPS лет | ||||
2000 MIPS лет | ||||
8000 MIPS yeas | ||||
2.7 Pentium 1GHz лет | ||||
13.2 Pentium 1GHz лет | ||||
121 Pentium 1GHz лет |
В 2003г. были разработаны СБИС для вскрытия криптосистемы RSA. Стоимость порядка $10 млн. С их использованием факторзация числа длиной 512 бит выполняется за 10 мин., а длиной 1024 бита –менее, чем за 1 год.
Поэтому рекомендуемая длина модуля n – не менее 2048 бит.
Для того чтобы избежать выбора значения n, которое могло бы легко раскладываться на сомножители, на р и q должно быть наложено много дополнительных ограничений, например, р и q должны не сильно отличаться по длине.