Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Криптосистема Крамера-Шоупа описывается алгоритмом 15.3.2.1.
Легко видеть, что часть зашифрованного текста (щ,е) представляет собой зашифрованную пару из семантически стойкой криптосистемы Эль-Гамаля. Из
Глава 15. Доказуемо стойкие и эффективные криптосистемы.
581
Алгоритм 15.1. Криптосистема с открытым ключом Крамера-Шоупа Параметры ключа
Пусть G — абелева группа, имеющая большой простой порядок q. Группа G является пространством исходных текстов.
(* Предполагается, что существует схема шифрования, позволяющая зашифровать любой исходный текст в виде битовой строки и расшифровать его вновь. При заданном описании группы desc(G) такое шифрование легко реализовать, используя методы, описанные в разделе 14.3.5. *)
Чтобы установить компоненты ключа, Алиса должна выполнить следующие инструкции.
1. Выбрать два случайных простых числа дх,д2 ? иG.
2. Выбрать пять случайных целых чисел х\, х2, Уъ У2, z ? г/[0, q).
3. Вычислить значения с «— gxig22,d «— g^ff^ih <— д\.
4. Выбрать криптографическую функцию хэширования Н : G3 у-» [0, q).
5. Огласить кортеж (gx, д2, с, d, h, Н) в качестве параметров открытого ключа, а кортеж (х\, х2, ух, у2, z) сохранить как закрытый ключ.
Шифрование
Чтобы послать Алисе строку m?G, Боб извлекает случайное число г 6 u[0,q) и выполняет следующие вычисления.
их <— д[, и2 <— д2, е *— hrm, а <— Н (щ,и2, е), v *— с*(Га.
Зашифрованным текстом является кортеж (их, и2, е, v). Расшифровка
Чтобы расшифровать кортеж (щ,и2, е, v), Алиса должна выполнить следующие операции.
1. а «— Н(их,и2,е).
2. Вывести <
т - 4г- если иХ1+таиХ2+У2а = v, и\
ОТКАЗ в противном случае.
теоремы 14.2 (раздел 14.3.5) следует, что схема Эль-Гамаля является стойкой к атаке IND-CPA при условии неразрешимости задачи DDH.
Как и любая другая схема шифрования, стойкая к атаке ССА2, процедура расшифровки предусматривает проверку целостности данных. Допустим, что на пути к Алисе зашифрованный текст не подвергался изменениям. Тогда
иХ1+У1аиХ2+ша = (uXluX2) (u\xaufa) = (д?хд?2) (дГхтад2ша) = сТ(Га = v.
582
Часть V. Методы формального доказательства стойкости
После проверки целостности данных процедура расшифровки полностью совпадает с семантически стойкой криптосистемой Эль-Гамаля. В дальнейшем будет показано, что процедура проверки целостности данных является очень эффективной: она предотвращает возможность создания корректного зашифрованного текста без применения соответствующей процедуры шифрования. Может возникнуть следующий вопрос.
"Почему стойкость этой схемы базируется исключительно на предположении о неразрешимости задачи DDH? Поскольку процедура проверки целостности данных использует функцию хэширования Н, почему стойкость криптосистемы не зависит от ее свойств, например, от свойств случайного оракула?"
Разумеется, функция хэширования, применяемая в этой схеме, не должна быть слабой. Однако следует отметить, что защита, предусмотренная на этапе проверки целостности данных, основана исключительно на свойстве однонаправленности функции хэширования. Таким образом, необходимость использовать свойства случайного оракула отпадает. Например, функцию хэширования Н(х) можно реализовать с помощью операции дх, выполненной в той же самой группе G. В этом случае будет использовано только свойство однонаправленности дискретного логарифма (задача DL, см. определение 8.2 в разделе 8.4). Связанное с этим предположение о неразрешимости задачи DL, является стандартным. Кроме того, оно слабее предположения о неразрешимости задачи DDH в этой же группе. Иначе говоря, если бы мы использовали предположение о неразрешимости задачи DDH в группе G, то предположение о неразрешимости задачи DL в группе G выполнялось бы автоматически. Именно по этой причине мы утверждаем, что стойкость схемы основана исключительно на предположении о неразрешимости задачи DDH. В противоположность этому анализ атаки Шоупа на схему /-ОАЕР (раздел 15.2.3.3) показывает, что доказательство стойкости этой схемы не может быть основано только на свойстве однонаправленности функции хэширования или предположении о неразрешимости соответствующей задачи.
15.3.2.1 Производительность
На первый взгляд, криптосистема Крамера-Шоупа использует более длинные ключи и больше операций возведения в степень, чем криптосистема Эль-Гамаля. Однако более глубокий анализ показывает, что разница между этими криптосистемами не так велика, как кажется.
Открытый ключ в схеме Крамера-Шоупа состоит из пяти элементов, принадлежащих группе G, полученных путем добавления дополнительных компонентов к открытому ключу схемы Эль-Гамаля. Зашифрованный текст представляет собой четверку элементов из группы G, т.е. вдвое больше, чем в схеме Эль-Гамаля. Для шифрования необходимо выполнить "пять" (на самом деле четыре) операций
Глава 15. Доказуемо стойкие и эффективные криптосистемы.
583
возведения в степень, в то время как в схеме Эль-Гамаля — только две. Для расшифровки необходимо выполнить "три" (на самом деле две) операции возведения в степень, в то время как в схеме Эль-Гамаля — только одну.
