Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Поясним, почему для шифрования (расшифровки) достаточно выполнить четыре (две) операции возведения в степень, а не пять (три), как ясно указано в схеме. Это возможно потому, что произведение двух степеней в формуле gxhy можно вычислить с помощью одного возведения в степень. Этот метод описывается алгоритмом 15.2. Легко видеть, что этот алгоритм завершает работу, тах(|ж|, |у|) раз выполнив операцию "возведения в квадрат с последующим умножением". Обратите внимание на то, что ни этот алгоритм, ни описание схемы Крамера-Шоупа, не содержат групповых операций. Действительно, группой G может быть любая абелева группа, в которой выполняется предположение о неразрешимости задачи DDH.
Оценка производительности криптосистемы Крамера-Шоупа демонстрирует, что как по пропускной способности каналов, так и по эффективности вычислений, криптосистема Крамера-Шоупа вдвое превышает показатели криптосистемы Эль-Гамаля.
15.3.3 Доказательство стойкости
Читатели, которых интересует лишь описание криптосистемы Крамера-Шоупа, могут ограничиться изучением алгоритма 15.3.2.1 и перейти к разделу 15.4. Те же, кого интересует интуитивное доказательство стойкости этой криптосистемы, могут продолжать чтение раздела.
Для того чтобы разобраться в доказательстве стойкости криптосистемы Крамера-Шоупа, не требуется никаких специальных математических знаний. Достаточно знать основные сведения из теории групп, содержащиеся в разделе 5.2, и элементарные факты из линейной алгебры.
Доказательство стойкости криптосистемы Крамера-Шоупа основано на "сведении к противоречию": т.е. на редукции атаки IND-CCA2 к решению трудноразрешимой задачи. В частности, стойкость криптосистемы Крамера-Шоупа основана на неразрешимости следующей задачи.
Пусть G — группа, имеющая простой порядок q, a (ffi,ff2>uiiu2) ? GG4 - произвольная четверка, в которой дх ф 1 и д2 ф 1. Вопрос состоит в следующем: является ли кортеж (gi,g2,u\,u2) четверкой Диффи-Хеллмана? Иначе говоря, существуют ли числа а, Ь G [0, q), удовлетворяющие условию
02 = <7i,«i=<7i,"2 = 3i*? (15.3.1)
Поскольку группа G имеет простой порядок, то число gi ф 1 является ее порождающим элементом (следствие 5.3). Следовательно, всегда существуют целые
584
Часть V. Методы формального доказательства стойкости
Алгоритм 15.2. Произведение степеней ИСХОДНЫЕ ДАННЫЕ:
д. h Е А, где А — алгебраическая структура;
х, у: целые числа из интервала (О,
Ехр(и, z): операция возведения в степень, возвращающая число и2 (* см. алгоритм 4.3*) РЕЗУЛЬТАТ:
дхНУ
1. if(M>M)
{
и«- Ехр(д,х(той2Ы-Щ; (* Операция возведения в степень использует \х\ — \у\ младших битов числа х. *)
х <— х-т- 2'ХН!'1; (* Символ -f- обозначает целочисленное деление.
Эта операция отбрасывает \х\ — \у\ младших битов числа х. Следовательно,
теперь \х\ = \у\. *)
}
2. if(M>N)
{
и Exp(h,x(mod2M-W)); у <- у -г 2|г/|_|а:|;
}
3. v <— gh; (* Теперь |а;| = |у|. *)
4. while (х ф 0) do
{
а) и <— и2;
б) if (a;(mod2) == 1 Л y(mod2) == 1)и <— uv\
в) if (a;(mod 2) == 1 Л y(mod 2) —= 0)и <— ид;
г) if (a;(mod 2) - 0 Л y(mod 2) — l)w <— uh;
д) а; ч— х -г- 2; у <— у 2; (* Младший бит отбрасывается. *)
}
5. return (и);
(* Общее количество операций "возведения в квадрат с последующим умножением" равно тах(|з;|, |у|). *)
Глава 15. Доказуемо стойкие и эффективные криптосистемы.
585
числа а, 6 ? [0, q), удовлетворяющее двум первым уравнениям в системе (15.3.1). Вот почему знак вопроса относится только к последнему уравнению. Достаточно просто проверить, что система (15.3.1) эквивалентна уравнению
loggi Щ = logfl2 u2(modg).
Из предположения Диффи-Хеллмана (предположение 14.2) следует, что в общем случае для абелевой группы эта задача является трудноразрешимой.
15.3.3.1 Схематичное описание доказательства стойкости
Предположим, что существует атакующий алгоритм А, способный взломать криптосистему Крамера-Шоупа с помощью атаки IND-CCA2 со значимым преимуществом. Мы построим эффективный алгоритм редукции, прибегнув к помощи специального агента Саймона-имитатора, способного решить трудноразрешимую задачу Диффи-Хеллмана.
Саймон получает произвольную четверку (ffi,ff2juiiu2) ? G4, где д\ ф 1 и <72 Ф 1- Этот кортеж может быть четверкой Диффи-Хеллмана (обозначим этот случай как (gi,g2, mi, и2) ? D, а может и не быть ею (обозначим этот случай как {91,92,Щ,и2) <? D).
Используя входную информацию, Саймон может создать для атакующего алгоритма А открытый ключ РК = (gi,g2,c,d,h,H). Кроме того, в ходе атаки IND-CCA2 Саймон может по запросу атакующего алгоритма А конструировать зашифрованный оклик С* = (щ,и2,е,ь), шифрующий подобранный исходный текст ть ? и{гпо, "т-\\- (Здесь то и тп\ — исходные тексты, подобранные атакующим алгоритмом А, однако бит Ь атакующему не известен.)
Зашифрованный оклик С* обладает следующими свойствами.
1. Если (gi, д2, щ, U2) ? D, то оклик С* является корректным зашифрованным текстом Крамера-Шоупа, шифрующим сообщение тпъ с помощью открытого ключа РК. Доказательство корректности отклика С* содержится в разделах 15.2.3.3 и 15.3.3.4. Независимо от того, применяется ли открытый ключ или нет, атакующий А проходит курс обучения криптоанализу, точно имитируемый Саймоном. Доказательство этого факта приведено в разделе 15.3.3.5. Итак, Саймон просит атакующего А напрячь все свои силы.
