Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Итак, сформулируем основной результат о стойкости криптосистемы GM.
Теорема 14.1. Пусть к — размер двух простых множителей модуля N в криптосистеме RSA. Криптосистема GM с параметром безопасности к является семантически стойкой (стойкой к атаке IND-CPA) тогда и только тогда, когда выполняется предположение о квадратичных вычетах. о
14.3.5 Семантически стойкий вариант криптосистемы / Эль-Гамаля
Как и криптосистема RSA, криптосистема Эль-Гамаля, описанная алгорит-1 мом 8.3, не скрывает того, что исходный текст является квадратичным вычетом, поскольку алгоритм установки открытых параметров (р, д) организован так, чтобы число д было порождающим элементом всей группы Z*. В этом случае тот факт, что исходный текст является квадратичным вычетом, может отразиться на зашифрованном тексте.
Пример 14.1. Допустим, что оракул О устанавливает компоненты открытого ключа (р, д, у) для криптосистемы Эль-Гамаля, описанной алгоритмом 8.3. По критерию Эйлера (теорема 6.13 из раздела 6.5.1) д G QNRp (т.е. число д является квадратичным невычетом по модулю р).
Предположим, что Злоумышленник организовал атаку IND-CPA. Он должен послать сообщения mo G QRp и ту €Е QNRp, применяя алгоритм 6.2. Для Злоумышленника это не сложно. Пусть (cj, с%) — пара зашифрованных окликов, воз-
Глава 14. Определения формальной и сильной стойкости криптосистем... 529
вращенных оракулом О. Тогда
Теперь Злоумышленник может распознать исходный текст, проверив, являются ли квадратичными вычетами числа у, с* и с\. Необходимо рассмотреть несколько случаев.
Сначала проанализируем вариант, когда у 6 QRp. Этот случай весьма прост. Вследствие мультипликативного свойства символа Лежандра (теорема 6.16.2 из раздела 6.5.2) исходный текст равен то тогда и только тогда, когда с*. G QRp.
Вариант yeQNRp распадается на два очень простых частных случая. В первом случае, если CjGQRp, то yfceQRp (поскольку число к является четным), и решение принимается точно так же, как в предыдущем абзаце. Второй случай, когда с\ б 6 QNRp, читатели могут разобрать самостоятельно (учтите, что число к теперь является нечетным). ?
Как всегда, осознание проблемы позволяет ее более или менее легко решить. Если ограничить криптосистему множеством квадратичных вычетов по модулю р, то атака, описанная в примере 14.1, станет невозможной.
Алгоритм 14.2. Семантически стойкий вариант криптосистемы Эль-Гамаля Установка открытых параметров
Пусть G — абелева группа, имеющая следующее описание.
1. Найти случайное простое число q, удовлетворяющие условию \q\ = к.
2. Проверить простоту числа р = 2q + 1. Если число р — простое, вернуться к п. 1.
3. Извлечь случайный порождающий элемент h 6 Z*. Установить параметр д = Ъ? (modp).
4. Пусть desc(G) удовлетворяет условию G = {д).
(* Группа порождается элементом д (см. определение 5.10 в разделе 5.2.3). *)
5. Пусть (р,д) — открытые параметры криптосистемы Эль-Гамаля.
6. Пусть G — пространство исходных текстов. (* Остальная часть совпадает с алгоритмом 8.3. *)
Прежде всего следует отметить, что алгоритм 14.2 обязательно завершит работу, поскольку существует огромное число простых чисел р, таких что число (р — 1)/2 также является простым (например, 7, 11, 23, 39,47 и т.д.). Такие числа называются безопасными простыми числами (safe prime).
yfcmo(modp) с вероятностью 50%, yfcmi(modp) с вероятностью 50%.
530
Часть V. Методы формального доказательства стойкости
По малой теореме Ферма ordp(p) = q — простое число. Следовательно, группа G = (д) имеет большой порядок. Это необходимое условие для того, чтобьи выполнялось предположение о невозможности дискретного логарифмирования (предположение 8.2).
Более того, из критерия Эйлера (теорема 6.13 из раздела 6.5.1) следует, что! pG QRp и, следовательно, G = QRp (теорема 5.2 из раздела 5.2.3). Таким образом J для подобранных исходных сообщений то, тгц G QRp числа д, у, с\ и с\ являются! квадратичными вычетами по модулю р. Следовательно, атака на основе квадра-1 тичных вычетов, продемонстрированная в примере 14.1, становится невозможной! поскольку для всех квадратичных вычетов проверка завершается положительный ответом.
Требование G = QRp не может создать сложностей при шифровании и рас-1 шифровке сообщений. Например, для любого сообщения m < р, если m е QRjj! шифрование закончено, а если m $ QRp, то —m = р — m € G, поскольку
(_1)(р-1)/2 = (_1)<? = („^нечетное число = _1(modp)) (-т)(р-Ч/2 = (-l)^-1)/^^-1)/2 = (-1)(-1) = l(modp), а значит, по критерию Эйлера
-m G QRp = G.
В исправленном варианте криптосистемы Эль-Гамаля перед Злоумышленником стоит несколько задач принятия решений. Получив пару зашифрованньш окликов (с^с^) в ответ на зашифрованные сообщения то и mi, он может вычислить следующую величину.
J ук = ^(modp) с вероятностью 50%, с2/то = < .
I jr (mi /то) (mod р) с вероятностью 50%.
Обратите внимание на то, что в первом случае кортеж
(р, У, 4, ca/mo) = (д, дх, gk,gxk)(modp)
представляет собой четверку Диффи-Хеллмана, а во втором случае — нет. Итак. Злоумышленник должен ответить на следующие вопросы.
