Шифросистемы с открытым ключом. Их возможности и применение. (стр. 2 из 4)

4. Скорость работы алгоритма RSA

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

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

Если k – количество битов в модуле, то в обычно используемых для RSA алгоритмах количество шагов необходимых для выполнения операции с открытым (public) ключом пропорционально второй степени k, количество шагов для операций частного (private) ключа – третьей степени k, количество шагов для операции создания ключей – четвертой степени k.

Методы "быстрого умножения" – например, методы основанные на Быстром Преобразовании Фурье (FFT – Fast Fourier Transform) – выполняются меньшим количеством шагов; тем не менее они не получили широкого распространения из-за сложности программного обеспечения, а также потому, что с типичными размерами ключей они фактически работают медленнее. Однако производительность и эффективность приложений и оборудования реализующих алгоритм RSA быстро увеличиваются.

Алгоритм RSA намного медленнее чем DES и другие алгоритмы блокового шифрования. Программная реализация DES работает быстрее по крайней мере в 100 раз и от 1,000 до 10,000 – в аппаратной реализации (в зависимости от конкретного устройства). Благодаря ведущимся разработкам, работа алгоритма RSA, вероятно, ускорится, но аналогично ускорится и работа алгоритмов блокового шифрования.

5. Способы взлома криптосистемы RSA

Существует несколько способов взлома RSA. Наиболее эффективная атака: найти закрытый ключ, соответствующий необходимому открытому (public) ключу. Это позволит нападающему читать все сообщения, зашифрованные открытым (public) ключом и подделывать подписи. Такую атаку можно провести, найдя главные сомножители (факторы) общего модуля n – p и q. На основании p, q и e (общий показатель), нападающий может легко вычислить частный показатель d. Основная сложность – поиск главных сомножителей (факторинг) n; безопасность RSA зависит от разложения на сомножители (факторинга), что является трудонразрешимой задачей, не имеющей эффективных способов решения.

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

Другой способ взломать RSA состоит в том, чтобы найти метод вычисления корня степени e из mod n. Поскольку С = M

⁽mod n), то корнем степени e из (mod n) является сообщение M. Вычислив корень, можно вскрыть зашифрованные сообщения и подделывать подписи, даже не зная закрытый ключ. Такая атака не эквивалентна факторингу, но в настоящее время неизвестны методы, которые позволяют взломать RSA таким образом. Однако, в особых случаях, когда на основе одного и того же показателя относительно небольшой величины шифруется достаточно много связанных сообщений, есть возможность вскрыть сообщения. Упомянутые атаки – единственные способы расшифровать все сообщения, зашифрованные данным ключом RSA.

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

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

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

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

Размер ключа в алгоритме 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-битные ключи уже не обеспечивают достаточную безопасность за исключением очень краткосрочных задач безопасности.