Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
е(Р, Q) = е(Р, [п]Р) = е(Р, Р)п = e([n]P, Р) = e(Q, Р).
(I3.3.4J
? = е(РР)с,7? = е(Р,Р)
аЬ
Глава 13. Аутентификация в криптографии с открытым ключом
499
Существует два метода спаривания: модифицированное спаривание Вейля, рассмотренное выше, и спаривание Тэйта (Tate). Второй метод более эффективен. Детали этих алгоритмов выходят за рамки нашей книги. Заинтересованный читатель найдет их в книгах [51, 116]. Оставшаяся часть главы посвящена спариванию Вейля.
13.3.5 Личностная неинтерактивная система разделения ключей Сакаи, Огиши и Касахары
Как и в личностной схеме цифровой подписи Шамира, для установки параметров в системе разделения ключей Сакаи, Огиши и Касахары [252] (SOK key sharing system) необходим доверенный посредник (Трент).
Система разделения ключей SOK обладает следующими свойствами.
• Установка системных параметров. Этот алгоритм выполняется Трентом для установки глобальных системных параметров и вычисления главного ключа.
• Генерация ключа пользователя. Этот алгоритм выполняется Трентом. Получая на вход главный ключ и произвольную строку битов id € {0,1}*, алгоритм вычисляет закрытый ключ, соответствующий строке id. Алгоритм является конкретизацией операции (13.3.1).
• Алгоритм разделения ключей. Этот алгоритм выполняется двумя конечными пользователями. Алгоритм получает закрытый и открытый (id) ключи каждого пользователя и вычисляет секретный ключ, разделенный между обоими пользователями.
Эти три алгоритма разбиваются на следующие этапы.
Установка параметров системы
Перед открытием центра генерации ключей Трент устанавливает параметры системы, выполняя следующие операции.
1. Генерируются две группы (Gi, +) и (G2, ¦), имеющие простой порядок р, и выполняется модифицированное спаривание Вейля1 е : (Gi,+)2 (G2, •)• Выбирается произвольный порождающий элемент Р € G\.
2. Случайным образом извлекается число ? € jyZp и устанавливается параметр РриЬ *— ЩР- Число ? играет роль главного ключа.
3. Выбирается стойкая криптографическая функция хэширования / : {0,1}* G\. Эта хэш-функция представляет собой отображение идентификатора пользователя id в элемент группы G\.
'В исходном варианте схемы разделения ключей SOK использовалось немодифицированное спаривание Вейля. Этот вариант менее удобен, чем описанный в книге.
500
Часть IV. Аутентификация
Трент оглашает системные параметры и их описания (desq(Gi), desq(G2), е, Р, РриЬ, /)
и сохраняет число ? в качестве системного закрытого ключа. Поскольку Трени считается известным всем пользователям, обнародованные параметры системь1 также становятся известными всем пользователям (например, эти параметры мо-1 гут быть зашиты в каждое устройство, использующее данную схему).
Обратите внимание на то, что секретность главного ключа ? защищена слож-1 ностью решения задачи DLP в группе G\.
Теперь Трент открывает центр генерирования ключей.
Генерация ключей пользователей
Пусть IDyi — однозначно определяемый идентификатор Алисы. Будем пред-, полагать, что ID^ обладает достаточной избыточностью, так что любой другой пользователь системы не может иметь такой же идентификатор. Выполнив физи-З ческую идентификацию и убедившись в уникальности идентификатора \DA, Трент] генерирует ключ, выполняя следующие операции.
1. Вычисляется P\<da *— / (Юл) — элемент группы G\ и личностный открытый ключ Алисы.
2. Устанавливается закрытый ключ S\da <— [^]РюА-
Поскольку значение Р\цА хэшируется, оно выглядит как случайное число. Од-i нако идентификатор ID^ обладает достаточной избыточностью и является прооб! разом значения Р|рА относительно криптографической функции хэширования /I Следовательно, элемент Р\<оА является распознаваемым. Таким образом, не имеем существенного значения, что считать открытым ключом Алисы — идентификатор] IDa или число Pida-
Следует отметить, что закрытый ключ Алисы защищен сложностью решения задачи CDH в группе G\. Это объясняется тем, что число РюА должно генериро^ ваться элементом Р (порождающим элементом группы Gi), и его можно обозна-' чить следующим образом: Р\оА = [о]Р, где а < р. Таким образом, вычисление па значениям Р,РриЬ(= ЩР),Р\оА{=: [°]Р) секретного ключа
SlDA = [?)PiDA = [?a]P J
эквивалентно решению задачи CDH в группе G\.
Алгоритм разделения ключей
Идентификаторы Алисы и Боба, ID^ и Юв, известны обоим партнерам. Следовательно, им известны и соответствующие открытые ключи РА = /(ID^) и Рв = = /(Юв).
Глава 13. Аутентификация в криптографии с открытым ключом
501
Алиса может сгенерировать общий ключ Кав G (G-2, ¦) с помощью следующей операции
Кав *- e(S\DA,P\DB).
В свою очередь Боб может сгенерировать общий ключ Kg а €(^2, -), выполнив операцию
КвA +~e(SiDB,P\DA)-Учитывая свойство билинейности 13.1, получаем
Кав = е (5Юл, РЮв) = е (ЩР10а, PIDb) = е (РЬА,РЬв)е -
Аналогично
Ква = е(РЮв,РЮА)е.
Из свойства симметричности модифицированного спаривания Вейля (13.3.4) следует, что
Кав = К в А.
Итак, Алиса и Боб действительно разделяют общий секрет, не взаимодействуя друг с другом.
Постороннему пользователю (не Алисе, Бобу или Тренту) практически невозможно найти число Кав, зная открытые числа (Р,Р\оА, Р\ов,Рриь)- Эта задача называется билинейной задачей Диффи-Хеллмана (bilinear Diffie-Hellman problem) [51]. По существу, она эквивалентна задаче CDH.
