Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
т + - = ± = ± ( т + - 1 (modTV).
Однако, поскольку
из теоремы 6.17 следует, что
gcd (т! + ^ ± + ^ , N^j =р или q. (8.11.1)
Иначе говоря, число N можно разложить на множители с ненулевым преимуществом е/2. Это противоречит предположению о невозможности факторизации модулей алгоритма RSA при условиях неразрешимости задачи о разложении целых чисел на простые множители. Итак, утверждение I доказано.
Утверждение II является тривиальным, если атакующий может получить доступ к блоку расшифровки сообщений: в этом случае блок расшифровки играет роль оракула, использованного в доказательстве утверждения I! Поскольку атакующий генерирует зашифрованный текст для его последующей расшифровки оракулом, такая атака является атакой на основе подобранного зашифрованного текста. ?
Из теоремы 8.2 следуют два вывода. Во-первых, криптосистема Рабина является доказуемо стойкой в рамках подхода "все или ничего", описанного свойством 8.2.1, и зависит от сложности разложения целых чисел на простые множители (если текст не содержит никакой априорной информации). Это значительный результат, поскольку он относится к стойкости учебной схемы шифрования Рабина. Если задача о разложении целых чисел на простые множители является трудноразрешимой, то предполагаемый оракул С в доказательстве утверждения 1 не может существовать. Однако следует уделить особое внимание модификации принципа "все или ничего" в отношении стойкости криптосистемы по отношению к атакам на основе подобранного открытого текста. Здесь слово "все" означает, что в общем случае восстанавливается весь блок исходного текста, т.е. размер сообщения совпадает с размером модуля. Очевидно, что, поскольку шифрование
318
Часть III. Основные методы криптографии
Предположим, что Боб зашифровал исходное сообщение т = 31 с помощью алгоритма шифрования Рабина.
с = 31 х (31 + 183) = 155(mod209).
Результирующий зашифрованный текст равен 155.
Для расшифровки зашифрованного текста, равного 155, Алиса вычисляет величину Дс по формуле (8.10.2).
Дс = Ъ2 + 4с = 1832 + 4 х 155s42(mod209).
Теперь, применяя алгоритм 6.5, Алиса определяет четыре квадратных корня числа 42 по модулю 209, т.е. числа 135, 173, 36, 74. В заключение она может применить формулу (8.10.1) и получить четыре результата расшифровки: 185, 204, 31 и 50. В реальной криптосистеме Рабина исходный текст должен содержать дополнительную информацию, позволяющую распознать среди полученных ответов искомый результат. ?
8.11 Уязвимость учебной криптосистемы Рабина
Существует чрезвычайно эффективная активная атака против криптосистемы Рабина. В ее основе лежит следующая теорема.
Теорема 8.2.
/. Криптосистема Рабина является доказуемо стойкой к атаке на основе подобранного открытого зашифрованного текста в рамках подхода "все или ничего ", если и только если задача о разложении целого числа на простые множители является трудноразрешимой.
2. Криптосистема Рабина является абсолютно беззащитной перед атакой на основе подобранного зашифрованного текста.
Доказательство. I. Поскольку процедура расшифровки в криптосистеме Рабина использует разложение модулей алгоритма RSA на простые множители, стойкость криптосистемы Рабина означает невозможность факторизации этих модулей. Следовательно, достаточно показать обратное утверждение: неразрешимость задачи о разложении целого числа на простые множители означает стойкость криптосистемы Рабина.
Допустим, что существует оракул О, взламывающий криптосистему Рабина с ненулевым преимуществом е, т.е.
Prob
О (с, N) = Ъ (mod N)\ce uZ*N^ > е.
320
Часть III. Основные методы криптографии
Рабина является детерминированным алгоритмом, в некоторых случаях расшифровка сообщений не обязательно так же сложна, как и разложение целых чисел на простые множители. Мы еще вернемся к этому утверждению, когда будем рассматривать атаку "встреча посередине" на схему Рабина в конце этого раздела.
Во-вторых, очевидно, что в криптосистеме Рабина никто и никогда не должен играть роль оракула. Атака на основе подобранного зашифрованного текста уничтожает криптосистему Рабина: в результате такой атаки восстанавливается не только отдельная информация об исходном тексте (как в случае атаки CCA2I против криптосистемы RSA в примере 8.5), но и раскрывается секретный ключ. Следовательно, атакующий получает возможность читать все секретные сообщения, зашифрованные с помощью открытого ключа.
Пример 8.7. В примере 8.6, посвященном криптосистеме Рабина, были рассмот-1 рены параметры открытого ключа (N, Ь) = (209,183) и четыре результата расшифровки сообщения 31: числа 185,204,31 и 50.
Если эти числа станут известны постороннему лицу, не владеющему открытым ключом, например, в результате атаки ССА, он может использовать их для факторизации числа 209. Применяя формулу (8.11.1), получаем, что
gcd(204- 185,209) = 19
или
gcd((31 + 183/2) + (50 + 183/2), 209) = gcd(264,209) = 11. G
Хотя мы предупреждали, что владелец открытого ключа в схеме шифрования Рабина не должен предоставлять услуги расшифровки, в реальных приложени-] ях не стоит полагаться на высокую бдительность пользователей. Следовательно, учебный вариант схемы шифрования Рабина не пригоден для практического при-j менения. Реальные варианты криптосистем Рабина и RSA будут описаны в гла! ве 15. Там же приводится формальное доказательство стойкости практически* схем шифрования.
