Устойчивые числа и их применение в криптосистеме rsa

В литературе, описывающей алгоритм RSA, часто указывается, что при выборе пары чисел для создания модуля n необходимо, чтобы выбранные числа p и q являлись “устойчивыми". Устойчивые числа имеют некоторые свойства, которые затрудняют разложение на множители их произведение n определенными методами факторинга; одно из этих свойств, например, существование больших главных делителей (факторов) p - 1 и p + 1. Причиной таких мер являются некоторые методы факторинга (разложения на множители) например, метод Pollard (p – 1) и Pollard (p + 1) особенно подходят для таких чисел p, когда (p – 1) или (p + 1) имеют только маленькие делители (факторы); устойчивые числа устойчивы в частности к таким атакам. Требование использовать устойчивые числа выдвигается в частноси стандатом ANSI X9.31.

Однако, достижения последних десяти лет, похоже, сводят на нет преимущества устойчивых чисел; одной из перспективных разработок является алгоритм разложения на множители (факторинга) эллиптических кривых. Новые методы факторинга имеют столь же высокие шансы на успех как для устойчивых, так и для слабых p и q, поэтому сам по себе выбор устойчивых чисел существенно безопасность не увеличивает. В отличии от этого выбор достаточно большого устойчивого числа гарантирует надежную защиту, хотя для этого может потребоваться более длинное число. В будущем, возможно, будут разработаны новые алгоритмы разложения на множители (факторинга) чисел с определенными свойствами, но и в этом это случае защиту можно усилить, увеличив длину числа.

Рекомендуемая длина ключа

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

1. Возьмем M = (p+q)/2

2. При p < q, имеем 0 м – sqrt (n) (q - p) .

Поскольку p = M*( ), то значения p и q можно легко найти, если разность p - q достаточно мала.

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

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

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

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

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

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

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

В том случае если кто-то посылает одно и то же сообщение M трем корреспондентам, каждый из которых использует общий показатель e = 3. Зная это, нападаюший может перехватить эти сообщения и расшифровать сообщение M. Такую атаку можно предотвратить вводя в сообщение перед каждым шифрованием несколько случайных бит. Также существуют несколько атак по зашифрованному тексту (или атаки отдельных сообщений с целью подделки подписи), при которых нападающий создает некоторый зашифрованный текст и получает соответствующий открытый текст, например, заставляя обманным путем зарегистрированного пользователя расшифровать поддельное сообщение.

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