Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
По теореме о простом числе [170] существует не более чем В/ log В простых чисел, которые меньше, чем число В. Отсюда следует, что
А < B^N^ < В*^,
т.е.
\A\<kB\og2< fcPoly(fc).
Очевидно, что правая часть этого неравенства представляет собой полином, зависящий от аргумента к. Следовательно, для вычисления значения aA(modiV) можно выполнить многократное умножение по модулю N (алгоритм 4.3), причем количество операций умножения полиномиально зависит от аргумента к. Отметим, что число А не обязательно конструировать явно. Число aA(modN) можно «аити путем вычисления величины а (mod N) для всех простых чисел
г < В.
Очень легко построить модуль N = pq так, чтобы оценка гладкости чисел р — 1 и q — 1 была небольшой и неполиномиально зависела от \N\. В этом случае алгоритм RSA является стойким по отношению к данному методу факторизации. Можно начать с поиска больших простых чисел р' и q1, таких что р = 2р' + -+-1 и q = 2rf + 1 также являются простыми. Такие простые числа называются .безопасными простыми числами (safe prime), а модули алгоритма RSA, имеющие два безопасных простых множителя, называются безопасными простыми модулями алгоритма RSA (safe-prime RSA modulus). В настоящее время исследо-I ватели ведут дебаты о необходимости применения безопасных простых модулей в криптосистемах RSA. Противники их применения (см. работу [273]) утверждает, что модули алгоритма RSA должны быть как можно более случайными, и для
312
Часть III. Основные методы криптографии
случайно выбранного простого числа р вероятность того, что число р — 1 имеет большой простой множитель, является весьма большой. Однако корректность функционирования многих криптографических протоколов, основанных на сложности разложения целых чисел на множители, обеспечивается именно выбором безопасных простых модулей алгоритма RSA.
Хорошо известно, что частичная информация о простом множителе N позволяет разработать эффективный алгоритм факторизации числа N. Например, если N = pq, где р и q — простые числа, имеющие приблизительно одинаковый размер, знание половины битов числа р позволяет разложить число N за время, полиномиально зависящее от его размера [82].
При отсутствии априорной информации о простых множителях входного составного числа наилучшим алгоритмом факторизации является метод решета числового поля (number field sieve — NFS), временная сложность которого определяется по формуле (4.6.1). Таким образом, как и при выборе параметра безопасности задачи дискретного логарифмирования в конечном поле, для обеспечения надежности в качестве нижней границы размера модуля алгоритма RSA широко используется число 1024.
Эффективность метода решета числового поля, реализованного с помощью большого количества параллельных компьютеров, была продемонстрирована в начале 2000 года: сеть, состоящая из 9 ООО рабочих станций, разложила на множители модуль RSA, состоящий из 512 бит (RSA-512 Challenge), после четырех месяцев работы [70] параллельного алгоритма.
Исследования в области целочисленной факторизации ведутся очень интенсивно. Обзор методов решения задачи RSA дан в работе Бонэ (Boneh) [48]. Достижения и перспективы этой области исследований читатели могут найти в главе 3 книги [198].
8.9 Уязвимость учебного алгоритма RSA
В разделе 8.1 указано, что рассматриваемый вариант алгоритма является учебным и описан в большинстве учебников по криптографии. Перейдем к изучению свойств, обусловливающих стойкость (или нестойкость) учебного алгоритма RSA.
При случайном ключе и случайном сообщении, упомянутых в определении 8.4* и предположении 8.3, утверждение о существовании эффективной атаки на основе подобранного открытого текста должно быть ложным.
Теорема 8.1. Криптосистема RSA устойчива к атаке на основе подобранного открытого текста по принципу "все или ничего " тогда и только тогда, когда выполняются условия неразрешимости задачи RSA. о
Глава 8. Шифрование — асимметричные методы
313
Принцип "все или ничего" объясняется при описании свойства 8.2.1. А применение атаки на основе подобранного открытого текста означает, что атакующий остается пассивным, как и предусмотрено свойством 8.2.2.
Однако такая стойкость имеет не очень высокую практическую ценность.
Во-первых, рассмотрим принцип "все или ничего". Слово "все" означает, что при расшифровке восстанавливается весь блок исходного сообщения: размеры сообщения и модуля совпадают. В приложениях это условие выполняется не всегда. В реальных системах исходный текст, как правило, содержит определенную часть открытой информации, известной атакующему. Учебный вариант алгоритма RSA не скрывает эту информацию. Например, если известно, что зашифрованный текст представляет собой число, не превосходящее 1 ООО ООО (например, секретное предложение цены или размер оклада), то, имея зашифрованное сообщение, атакующий может восстановить исходный текст менее чем за 1 ООО ООО попыток.
Как правило, исходный текст т < N с ненулевой вероятностью можно восстановить, использовав только л/т попыток, если в распоряжении криптоаналитика есть память, имеющая размер л/т. Этот факт установлен Бонэ, Жё (Joux) и Нгуе-ном (Nguen) [52]. Они исходили из того, что факторизация небольшого исходного сообщения не является трудноразрешимой задачей, и использовали мультипликативное свойство функции RSA:
