Обзор методов вскрытия криптосистемы RSA

Хороший анализ защиты, обеспечиваемой определенной длиной модуля, приведен в описании модуля дискретного логарифма Rivest , но то же можно применить и к алгоритму RSA. В более позднем обзоре защита, предлагаемо ключами RSA различной длины, анализируется на основе методов разложения на множители (факторинга), существовавших в 1995 и перспективах их развития, а также рассматривает возможность привлечения больших вычислительных ресурсов по информационным сетям. Проведенная в 1997 году оценка показала, что 512-битный ключ RSA может быть вскрыт (факторингом) за $ 1,000,000 и восемь месяцев. В 1999 году 512-битный ключ был вскрыт за семь месяцев и это означает, что 512-битные ключи уже не обеспечивают достаточную безопасность за исключением очень краткосрочных задач безопасности.

В настоящее время Лаборатория RSA рекомендует для обычных задач ключи размером 1024 бита, а для особо важных задач – 2048 битов (например, для главного Мастера Сертификатов).

Некоторые недавно введенные стандарты устанавливают для общих задач минимальный размер ключа 1024 бита. Менее ценная информация может быть надежно зашифрована ключом 768-битной длины, поскольку такой ключ все еще недосягаем для всех известных алгоритмов взлома. Для оценки уровней безопасности различных размеров ключей можно использовать модель предлагаемую Lenstra и Verheul.

Обычно ключ индивидуального пользователя имеет определенный срок жизни, который истекает через некоторое время, например, через год. Это дает возможность регулярно заменять ключи и обеспечивать необходимый уровень безопасности. После истечения срока жизни ключа, пользователь должен создать новый ключ, предварительно удостоверившись, что параметры криптосистемы остались прежними, в частности, что система использует ключи той же длины. Конечно, замена ключа не защищает от нападения на сообщения, зашифрованные прежним ключом, но для этого размер ключа должен подбираться согласно ожидаемому времени актуальности данных. Возможность замены ключей позволяет поддерживать криптографическую систему в соответстствии с текущими рекомендациями о размерах ключей, которые регулярно публикует Лаборатория RSA.
Пользователям необходимо учитывать, что оцениваемое время взлома системы RSA – только усредненное значение, а массированная атака на тысячи модулей в каком-то случае может дать положительный результат в относительно короткий срок. 
Хотя надежность любого отдельного ключа все еще высока, некоторые методы факторинга всегда оставляют нападающему маленький шанс быстро найти некоторый ключ.

Что же касается затруднения взлома увеличением размера ключа, то удвоение длины модуля в среднем увеличивает время операций открытого ключа (шифрование и проверка подписи) в четыре раза, а время операций частного ключа (расшифровка и подпись) в восемь раз. Разница между временем работы отрытого и секретного ключей возникает потому, что открытый показатель может оставаться неизменным, в то время как модуль будет увеличен, а длина частного показателя будет увеличена пропорционально увеличению длины ключа. Время создания ключей при удвоении модуля увеличивается в 16 раз, но это нечасто выполняемая операция и потому на общей производительности это практически не сказывается.

Надо отметить, что размеры ключей в криптосистеме RSA (а также и в других криптосистемах открытого ключа) намного больше размеров ключей систем блокового шифрования типа DES, но надежность ключа RSA несравнима с надежностью ключа аналогичной длины другой системы шифрования.

Итоги

На основании перечисленных атак можно сформулировать следующие ограничения при ис­пользовании RSA:

- знание одной пары показателей шифрования/дешифрования для данного модуля позволяет злоумышленнику разложить модуль на множители;

- знание одной пары показателей шифрования/дешифрования для данного модуля позволяет злоумышленнику вычислить другие пары показателей, не раскладывая модуль на множители;

- в криптографических протоколах с использованием RSA общий модуль использоваться не должен. (Это является очевидным следствием предыдущих двух пунктов.);

- для предотвращения раскрытия малого показателя шифрования сообщения должны быть дополнены («набиты») случайными значениями;

- показатель дешифрования должен быть большим.

Отметим, что недостаточно использовать криптостойкий алгоритм; безопасной должна быть вся криптосистема, включая криптографический протокол. Слабое место любого из трех этих компонентов сделает небезопасной всю систему.

Литература:

1.      Чмора А.Л.:  Современная прикладная криптография. 2-е изд., стер. – М.: Гелиос АРВ., 2002.

2.      http://www.cryptography.ru

3.      http://www.ciphersbyritter.com

4.      http://theory.lcs.mit.edu/~rivest/homepage.html

5.      http://www.enter.net/~chronos/cryptolog1.html