Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Однако не следует быть слишком большими оптимистами! Зашифрованный текст в схеме Эль-Гамаля — это не отдельный блок с2, а пара (ci,c2), причем числа с\ и с2 статистически связаны между собой. Следовательно, как и все криптосистемы с открытым ключом, стойкость криптосистемы Эль-Гамаля зависит от условий неразрешимости задачи, лежащей в ее основе. Более того, как будет показано в разделе 8.13.1, для того, чтобы обеспечить идеальное семантическое свойство, исходное сообщение должно принадлежать группе {д). К сожалению, в реальных системах это условие, как правило, не выполняется.
Рассмотрим стойкость криптосистемы Эль-Гамаля по принципу "все или ничего".
Теорема 8.3. Для исходного сообщения, равномерно распределенного по всему пространству исходных сообщений, криптосистема Эль-Гамаля является стойкой к атаке на основе подобранного открытого текста по принципу "все или ничего " тогда и только тогда, когда задача Диффи-Хеллмана является трудноразрешимой.
Доказательство. (=>-) Необходимо показать, что, если криптосистема Эль-Гамаля является стойкой, выполняются условия неразрешимости задачи Диффи-Хеллмана.
324
Часть III. Основные методы криптографии
Допустим противное — условия неразрешимости задачи Диффи-Хеллмана не выполняются. Тогда при заданном тексте (ci, С2) = (дк, ykm)(modp), зашифрованном с помощью открытого ключа у = gx(modp), оракул задачи Диффи-Хеллмана вычислит по четверке (р, д, дх,дк) число gxk=yk(modp) с ненулевым преимуществом. Затем с тем же преимуществом вычисляется величина т <— C2/yk(modp). Это противоречит стойкости криптосистемы Эль-Гамаля.
(<=) Теперь необходимо показать, что при условиях неразрешимости задачи Диффи-Хеллмана не существует ни одного эффективного алгоритма, позволяющего с преимуществом, которое не является пренебрежимо малым, восстановить исходное сообщение, зашифрованное с помощью криптосистемы Эль-Гамаля.
Допустим противное — существует эффективный оракул О, позволяющий взламывать криптосистему Эль-Гамаля, т.е. для любых параметров открытого ключа (р,д,у) и зашифрованного текста (ci,c2) оракул О с преимуществом <5, которое не является пренебрежимо малым, вычисляет значение
т ч- 0(p,g,y,ci,c2),
удовлетворяющее условию
^=p0°g9*/log9ci)(modp)_ т
Затем для произвольного варианта задачи Диффи-Хеллмана (р, 5,51,52) тройка! (Pi5i5i) выбирается в качестве параметров открытого ключа, а пара (д2,с2) — в качестве зашифрованной пары, где с2 6 F*. Тогда с преимуществом S оракул (л вычисляет значение
т <- 0(p,g,gi,g2,c2), которое удовлетворяет условию
^=p(l°g95llQgss2)(modp).
Это противоречит условиям неразрешимости задачи Диффи-Хеллмана. ?
Поскольку стойкость криптосистемы Эль-Гамаля к атаке CPA эквивалентна неразрешимости задачи Диффи-Хеллмана, все утверждения, касающиеся пара-, метров открытого ключа (раздел 8.4), относятся и к криптосистеме Эль-Гамаля.] Как и в протоколе обмена ключами Диффи-Хеллмана, криптосистема Эль-Гама^] ля работает в подгруппе группы Fq, порядок которой является большим простым! числом, или в большой группе точек эллиптической кривой, определенной над конечным полем.
Глава 8. Шифрование — асимметричные методы 325
8.13.1 Атака "встреча посередине" и активная атака на учебную криптосистему Эль-Гамаля
Алгоритм 8.3, описывающий криптосистему Эль-Гамаля, является учебным, поскольку его схема шифрования очень слаба. Попробуем разобраться в причинах ее слабости.
Обычная схема шифрования Эль-Гамаля, применяемая в реальных приложениях, допускает частичную утечку информации даже при пассивных атаках. На практике в криптосистеме Эль-Гамаля для достижения большей эффективности часто используется элемент д, имеющий порядок г = ordp(<?) «С р. Если в этом случае сообщение т не принадлежит подгруппе (д), то атака "встреча посередине" на криптосистему Эль-Гамаля почти не отличается от подобной атаки ha криптосистему RSA (см. пример 8.3). По зашифрованному тексту (ci,C2) = '= (дк,укт)(modp) Злоумышленник может найти число
Crj = mr(modp).
Наким образом, Злоумышленник преобразовал "вероятностную" схему шифрова-ния в криптосистеме Эль-Гамаля в детерминированную*. Более того, криптосистема Эль-Гамаля обладает таким же мультипликативным свойством, что и криптосистема RSA (см. раздел 8.9). Следовательно, при пересылке коротких сообщений, которые легко разложить на простые множители, Злоумышленник может органи-ровать атаку "встреча посередине" точно так же, как это делается в криптосистеме PISA [52].
Итак, если исходное сообщение не принадлежит подгруппе, порожденной Элементом д, криптосистема Эль-Гамаля становится детерминированной. Такие криптосистемы допускают частичную утечку информации, поскольку уязвимы ¦ля атаки путем перебора коротких исходных сообщений, например, секретных предложений цены или зарплат сотрудников.
Покажем теперь, что криптосистема Эль-Гамаля уязвима для активной атаки.
Пример 8.9. Допустим, что Злоумышленник имеет частичный доступ к блоку касшифровки Алисы в криптосистеме Эль-Гамаля. Как и в примере 8.5, разумно предположить, что в ответ на бессмысленное сообщение, полученное от Злоумышленника, Алиса должна вернуть ему результат расшифровки.
