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

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

х · у = z (mod#)

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

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

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

Чтобы найти Y, сначала определяются элементыи, удовлетворяющие соотношениям

В системе Гольдвассера-Микали шифруется один бит информации за один раз. Для шифрования бита b поступают следующим образом:

- берут произвольный элемент х(Z/NZ)*

- и вычисляют С =(mod N).

Отметим, что любой шифротекст С принадлежит множеству. Причем если бит b сообщения равен 0, то С будет квадратичным вычетом, в противном случае — квадратичным невычетом. Таким образом, для дешифрования сообщения необходимо уметь решать проблему квадратичных вычетов по модулю N. Законный пользователь, естественно, знает разложение N на простые множители. Поэтому он может вычислить символ Лежандра