Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
526
Часть V. Методы формального доказательства стойкости
Алгоритм 14.1. Вероятностная криптосистема Голдвассера и Микали Генерация ключа
Чтобы установить параметры ключа, Алиса должна выполнить следующие one! рации.
1. Выбрать два случайных простых числа р и q, удовлетворяющих условию \p\ = \q\=k.
(* Например, применив алгоритм 4.7 в строке 1к. *)
2. Вычислить значение N — pq.
3. Извлечь случайное целое число у, удовлетворяющее условию = = = -1.
(* Таким образом, у е J(N)\QRN. *)
4. Огласить пару (N, у) в качестве открытого ключа, а пару (р, q) сохранит» в тайне как закрытый ключ.
Шифрование
Чтобы послать Алисе строку т = 6162... be, Боб выполняет следующие операции! for (i = 1,2,...,?) {
if (Ьг == 0)q <- x2(modN); else ci <— yx2(mod N);
}
Боб посылает Алисе сообщение: Epf(m) *— (ci,c2,...,се). Расшифровка
Получив кортеж (ci, c2,..., q), Алиса выполняет следующие операции, for (г = 1,2,...,?) {
if (cj G QRN)h <- 0; else bi *— 1;
}
Set 77H- (01,62,..., fy).
этого алгоритма шифрования равна log2 N: одному биту исходного текста соответствуют log2 N бит зашифрованного текста.
Поскольку для вычисления символа Лежандра по модулю р и по модулю q при условии, что \р\ = \q\ = к, необходимо выполнить Ов{к2) побитовых операции (см. обсуждение алгоритма 6.2 для вычисления символа Якоби), для расшиф-1 ровки кортежа (ci,с2,..., q) требуются Ов(log2 N)2) побитовых операций. Это выражение представляет собой оценку временной сложности расшифровки.
Глава 14. Определения формальной и сильной стойкости криптосистем... 527
Побитовое шифрование, применяемое в криптосистеме GM, свидетельствует о ее крайней неэффективности.
14.3.4 Стойкость криптосистемы GM
Алгоритм шифрования в криптосистеме GM можно рассматривать как безошибочный рандомизированный алгоритм: случайные операции в алгоритме шифрования не могут исказить зашифрованный текст и обладают при этом следующим важным свойством.
Нулевые биты в исходном тексте равномерно распределяются по множеству QRN, а единичные — по множеству J;v(l)\QR^.
Оба распределения являются равномерными, поскольку для нулевого бита, содержащегося в исходном тексте, возведение в квадрат означает отображение группы на множество QR^, а для единичного бита умножение элемента множества OJRN на число у является отображением из множества QR^ на множество J/v(l)\QR;y. Итак, извлечение случайного числа х G иЩ^ в х°Де шифрования означает либо извлечение случайного числа, равномерно распределенного по множеству QR^, если бит в исходном тексте равен нулю, либо извлечение случайного числа, равномерно распределенного по множеству J;v(l)\QR^, если бит в исходном тексте равен единице.
Чтобы формализовать эту процедуру, отметим, что основная трудность в криптосистеме GM связана с решением задачи о распознавании квадратичных вычетов (QR-problem), описанной в определении 6.2 (раздел 6.5.1). Задача QR является общепризнанной трудноразрешимой задачей теории чисел.
Предположение 14.1 (Предположение о квадратичных вычетах (предположение QR)). Пусть XQ — генератор целых чисел, на вход которого поступает строка \к, время работы полиномиально зависит от числа к, а результатом работы является модуль N = pq, состоящий из 2к бит, где числа р и q — к-битовые равномерно распределенные нечетные простые числа.
Генератор XQ удовлетворяет условию о квадратичных вычетах (QR), если для всех достаточно больших чисел к и модуля N <— XQ(lk) ансамбли QR^ и Jn(1)\QR-n являются полиномиально неразличимыми в смысле определения 4.14 из раздела 4.7.
Очевидно, что открытый ключ N необходимо выбирать на пределе возможностей решения задачи о распознавании квадратичных вычетов, поскольку Злоумышленник может знать разложение числа N на простые множители и применять алгоритм расшифровки из криптосистемы GM для решения задачи QR. Следовательно, криптосистема GM основана на предположении, что атакующий использует полиномиально ограниченный алгоритм. По этой причине семантиче-
528
Часть V. Методы формального доказательства стойкости
скую стойкость алгоритмов шифрования часто называют полиномиальной неразличимостью шифрования (polinomial indistinguishability of encryption).
Если предположение о квадратичных вычетах действительно выполняется, I то алгоритм шифрования в криптосистеме GM равномерно распределяет биты исходного текста по пространству зашифрованных текстов J/v(l). Равномерное распределение зашифрованных текстов означает, что попытка угадать исходный текст по соответствующему тексту является совершенно бессмысленной. Именно в этом заключается суть понятия семантической стойкости, предложенного Годдвассером и Микали.
Определение 14.1 (Семантическая стойкость, стойкость по отношению к атаке на основе неразличимых подобранных исходных текстов (стойкость к атаке IND-CPA)). Криптосистема с параметром безопасности к называется семантически стойкой (стойкой к атаке IND-CPA), если после игровой атаки, описанной в протоколе 14.1, организованной полиномиально ограниченным Злоумышленником, преимущество, заданное формулой (14.2.3), является пренебрежимо малой величиной по сравнению с числом к.
