Криптография

15.2. Стойкость актуальных алгоритмов шифрования

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

15.2.1. RSA

Лемма 15.5. RSA не обладает полиномиальной стойкостью. Доказательство. Предположим, атакующий знает, что пользователь зашифровал только одно из двух сообщений,

или .

15.2.2. Эль-Гамаль

Напомним, что проблема выбора Диффи-Хеллмана (известная как ПВДХ) состоит в определении истинности равенства

х · у = z (mod#)

по данным элементамииз циклической группы

15.3. Семантически стойкие системы

Мы уже видели, что RSA не является семантически стойкой даже в отношении пассивной атаки. Хорошо бы теперь привести пример семантически стойкой системы, основанной на чем-то близком к задаче факторизации целых чисел. Первая такая схема принадлежит Гольдвассеру и Микали, хотя ее и не используют в практических приложениях. Стойкость этой схемы основывается на сложности проблемы квадратичных вычетов. Действительно, очень трудно определить, является ли данное число а квадратичным вычетом по модулю составного N, если не знать разложения последнего на простые множители.

15.3.0.1. Генерирование ключей.

В качестве секретного ключа выбираются два простых числа р и q и вычисляется открытый модуль N = р · q. Кроме того, открытый ключ содержит целое число