Стандарты безопасности применяющие RSA

Еще один потенциальный недостаток связан с десятикратным увеличением памяти справочника открытых ключей. Однако разбалансированность открытых ключей позволяет устранить и эту проблему. Обозначим через G генератор псевдослучайных последовательностей, применяемый для отображения идентификационной информации u (имени, адреса электронной почты и т.д.) в уникальную 5000-битную псевдослучайную последовательность t. Предполагается, что G всем известно. Каждый пользователь генерирует 500-битное простое число р, затем генерирует q — простое число из интервала [а, а + 250], где а наименьшее целое, большее или равное t/p. Поскольку простых чисел достаточно много, такое q почти всегда существует. В результате разница в разрядности модуля n = pq и t не будет превышать 550 бит. Каждый пользователь и может опубликовать число s = п-t в качестве своего открытого ключа. Тогда каждый абонент-отправитель криптосети может получить 5000-битный открытый ключ абонента-получателя, вычислив KO=G(u)+s. Необходимо отметить, что описанный метод не облегчает задачу факторизации модуля п:единственное отличие заключается в том, что стартовая точка в процедуре генерации q не просто выбирается случайным образом, а задается как отношение  случайного и простого числа. Поскольку закон распределения простых чисел отличается от равномерного, число а также не является равномерно распределенным. Для сглаживания побочных эффектов неравномерности граница интервала, в котором выбирается q. задается как а + 250. Таким образом, представление модуля п в виде s ничем не хуже, и тот факт, что ( не является истинно случайным числом, не влияет на его криптостойкость.  

Необходимо также отметить, что разбалансированность может использоваться для удвоения производительности существующих в настоящее время реализации RSA, в которых делители р иq имеют одинаковый размер. Причем для RSA-подписи такая оптимизация не подходит, так как проверяющему неизвестен делитель р. Кроме того, способ, при котором опубликованный короткий открытый ключ на самом деле является длинным, является чрезвычайно полезным при ограничениях на размер модуля, аналогичных экспортным ограничениям на длину ключа для симметричных криптосистем.

Гилберт (Н. Gilbert), Гупта (D. Gupta), Одлыжко (A. Odiyzko) и Квискватер (J.-J. Quisquater) показали, что разбалансированная RSA может быть успешно атакована при помощи специального протокола взаимодействия между отправителем и получателем.

Предположим, что n и е — открытый ключ Боба. Задача Алисы — раскрытие р и q. Для этого Алиса шифрует сообщение m > р и посылает Бобу шифротекст me mod n. Боб дешифрует шифротекст и получает т. Так как т > р, то . Предположим теперь, что Алиса каким-либо образом получила доступ к сообщению , тогда она может проверить, что р | (т — т). При соблюдении ограничений 0<m, <n Китайской теоремы об остатках следует, что q † (т -). Следовательно, Алиса может восстановить р, вычислив          НОД(т -,n).

Отметим, что при определенных обстоятельствах Боб может раскрыть Алисе сообщение (например, в сообщениях типа «Что за «мусор»  ты мне прислала

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

Однако этого недостаточно. Рассмотрим пример, в котором Алиса посылает сообщение типа «Переведите на счет Боба сумму в размере 101,74 долл. с моего счета №123 в банке г. Замухрышина». Сообщение «набивается» до нужной длины (исходя из размера делителя р) и заверяется цифровой подписью Алисы. Если m > p, сообщение   будет отвергнуто. Если     m < р и  = m, сообщение будет принято и денежный перевод инициирован. Факт денежного перевода позволит Алисе узнать, что т < р. Подобная стратегия позволяет раскрывать биты р. Стоимость раскрытия одного бита р можно уменьшить, даже при условии, что сумма в 100 долл. является минимальной для инициирования денежного перевода. Предположим, что Алиса сумела установить границы р, например, 6 х 2k < р < 7 х 2k. Тогда с помощью бинарного поиска Алиса могла бы приблизительно оценить т как 13 х 2k-1. Однако Алиса может попытаться раскрыть битыр методом последовательных приближений: сначала опробовав т как 111 х 2k-4, затем, если р < 111 х 2k-4, как 110 х 2k-4 и так далее. Метод позволяет раскрыть четыре бита р вместо одного при той же стоимости. Отметим, что метод требует большого числа попыток; соответственно, возросшая активность может вызвать подозрение и взаимодействие будет заблокировано.

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

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

4.2 Пакетная RSA

Пакетная RSA (batch RSA) представляет собой метод, позволяющий выполнять множество RSA-дешифрований (порядка n/log2 (n), где n — секретный параметр, логарифм берется по основанию 2) с вычислительной эффективностью одиночного RSA-дешифрования. При этом предполагается, что используется единый модуль, но различные и попарно взаимно простые экспоненты шифрования е. Проблема вычислительной эффективности RSA возникает в ряде криптографических приложений с централизованным управлением. Так, например некоторые схемы цифровой подписи предполагают наличие депозитарно-распределительного центра, генерирующего заверенные цифровой подписью квитанции для каждой транзакции. В других распространенных приложениях центральный компьютер должен обслуживать поток запросов в режиме on-line, например, при управлении ключами в сетях со звездообразной топологией. Таким образом, пакетная RSA позволяет минимизировать вычислительную нагрузку центра. 

 

 

ГЛАВА 5 РЕКОМЕНДАЦИЯ ПРИ РАБОТЕ С RSA

Размер ключа в алгоритме RSA связан с размером модуля n. Два числа p и q, произведением которых является модуль, должны иметь приблизительно одинаковую длину поскольку в этом случае найти сомножители (факторы) сложнее, чем в случае когда длина чисел значительно различается. Например, если предполагается использовать 768-битный модуль, то каждое число должно иметь длину приблизительно 384 бита. Обратите внимание, что если два числа чрезвычайно близки друг к другу или их разность близка к некоторому предопределенному значению, то возникает потенциальная угроза безопасности, однако такая вероятность – близость двух случайно выбранных чисел – незначительна.

Оптимальный размер модуля определяется требованиями безопасности: модуль большего размера обеспечивает большую безопасность, но и замедляет работу алгоритма 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. Платонов, В.В. Программно-аппаратные средства защиты информации: учебник для студ. учреждений высш. проф. образования / В.В. Платонов. – Москва : Академия, 2013. – 336 с.
2. Ростовцев, А.Г., Маховенко, Е.Б. Теоретическая криптография / А. Г. Ростовцев, Е. Б. Маховенко – Москва : Изд. Профессионал, 2005. – 490 с.
3. Шнайер, Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си / Брюс Шнайер – Москва : Триумф, 2002. – 816 с.
4. Венбо Мао. Современная криптография. Теория и практика / Венбо Мао – Москва : Вильямс, 2005г. — 768 с.

Москва

2014г.