Проблема RSA. Криптостойкость 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) эквивалентна сложности задачи факторизации, которая в настоящее время относится к классу вычислительно сложных (не имеет эффективного алгоритма решения) и имеет субэкспоненциальную сложность, пропорциональную

L (n) = e^{sqrt (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 должны не сильно отличаться по длине.

Дата добавления: 2013-12-13