Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Алиса случайным образом выбирает закрытый ключ sa, представляющий собой 160-битовое целое число, вычисляет значение
v «- g~SA(modN)
и передает его Тренту. Затем она доказывает Тренту, что знает число sa, не раскрывая его и используя простой протокол, описанный в разделе 13.3.3.4. Кроме того, Алиса посылает Тренту свой идентификатор 1а-
Трент создает открытый ключ Алисы в виде простой RSA-подписи числа v-Ia-
PA^{v-IA)d(modN).
Трент посылает Алисе число Ра как часть ее открытого ключа. Итак, выполняется следующее уравнение.
1А = Р% ~ v(modJV). (13.3.2)
На первый взгляд, поскольку оба числа Рд и v являются случайными элементами группы щ^, создать уравнение (13.3.2) не составляет большого труда. Например, Алиса может случайным образом извлечь число Ра, а затем, используя числа Р\, 1а и уравнение (13.3.2), вычислить значение v. Однако в этом случае Алиса не сможет вычислить дискретный логарифм числа v по основанию д и модулю N.
Именно способность Алисы демонстрировать знание дискретного логарифма числа v по основанию д и модулю N, т.е. числа — sa, гарантирует, что параметр Ра был сгенерирован Трентом. Простейший способ продемонстрировать это знание — применить вариант протокола обмена ключами Диффи-Хеллмана, описанный в разделе 13.3.3.4.
13.3.3.4 Протокол обмена ключами
Пусть (sа, Ра, 1а) — параметры открытого ключа Алисы, a {sb,Pb,Ib) — параметры открытого ключа Боба. Они могут просто обменяться аутентичными ключами, приняв следующее соглашение.
КАВ = (Р% + *аУв = {Р% + Ib)sa = g~SASB{modN).
В рамках этого соглашения Алиса вычисляет значение (Рв + 1вУА (modA^), а Боб — (Рд + 1аУв (mod А^). Следовательно, это соглашение действительно является элементом протокола обмена ключами Диффи-Хеллмана. Если две стороны могут согласовать один и тот же ключ, значит, они знакомы и могут доказать друг другу свою подлинность.
Жиро также предложил протокол личностной идентификации и личностную схему цифровой подписи, являющуюся частью схемы цифровой подписи Эль-Гамаля [122].
Глава 13. Аутентификация в криптографии с открытым ключом
493
13.3.3.5 Обсуждение
Самосертифицирующиеся открытые ключи Жиро обладают одним преимуществом личностной схемы Шамира: они не нуждаются в верификации дополнительного сертификата ключа, выданного его владельцу доверенным посредником. Верификация выполняется неявно и одновременно с проверкой криптографических способностей владельца ключа.
Однако проверяющая сторона должна, кроме имени пользователя I, знать его открытый ключ Р, причем верификатор не может определить этот ключ по имени пользователя. Это означает, что верификатор должен обратиться к владельцу ключа и попросить его переслать открытый ключ еще до его применения. Таким образом, в протоколе возникает дополнительный этап. Следовательно, систему самосертифицирующихся открытых ключей Жиро нельзя считать неинтерактивной криптографией с открытым ключом (см. раздел 13.3.2). Это свойство является недостатком системы Жиро.
13.3.4 Личностная криптография с открытым ключом на "слабых" эллиптических кривых
Личностная криптосистема с открытым ключом, предложенная Шамиром, представляет собой схему цифровой подписи. Она основана на предположении, что существуют личностные системы шифрования. После того как Шамир впервые сформулировал эту проблему в 1984 году, было предложено несколько личностных криптосистем шифрования [51, 78, 141, 191, 251, 287, 289].
Сакаи (Sakai), Огиши (Ohgishi) и Касахара (Kasahara) [251], а также Жё (Joux) [154] независимо друг от друга выдвинули идею использовать особое свойство функции пересчета пар (pairing-mapping function), применяемой в абелевых группах, состоящих из точек эллиптической кривой (см. раздел 5.5). Работа Сакаи, Огиши и Касахары [251] представляет собой замечательное приложение результатов криптоанализа, описанных выше (см. раздел 13.3.4.1). Она перевела схему Шамира из разряда теоретических разработок в мир реальных приложений. Независимо от Сакаи, Огиши и Касахары в работе [154] Жё использовал тот же прием для создания другого приложения: однораундового трехстороннего разделения ключей Диффи-Хеллмана (Жё назвал его трехсторонним протоколом Диффи-Хеллмана).
Работы Сакаи, Огиши и Касахары [251], а также Жё [154] подтвердили результаты криптоанализа, выполненного Менезесом (Menezes), Окамото (Okamoto) и Ванстоуном (Vanstone) [197]. Эти работы возродили интерес к личностной криптографии.
Особое свойство, использованное Сакаи и его соавторами [251], а также Жё [154], заключается в следующем. В группе, состоящей из точек "слабой" эллип-
494 Часть IV. Аутентификация
тической кривой, допускающей эффективное вычисление функции пересчета пар, задача принятия решений Диффи-Хеллмана (DDH problem — decisional Diffie-Hellman problem) оказывается легко разрешимой, а то время как ее вычислительный аналог — нет. Рассмотрим сначала "слабые" эллиптические кривые и связанную с ними легкую задачу принятия решений Диффи-Хеллмана, а затем схемы согласования ключей с помощью пересчета пар.
13.3.4.1 Класс слабых эллиптических кривых