Реферат: Криптографические протоколы
Этап i (0< i <n) :
1. Mi получает множество промежуточных величин { Vk | 1£ k £ n }. (в данном контексте можно сказать, что M1 получает пустое множество на первом этапе):
(r1…ri-1 / rk)(K k1…K k(i-1)) при k £ (i -1)
Vk =
(r1…ri-1)(K k1…K k(i-1)) при k > (i -1) .
2. Mi обновляет каждое Vk следующим образом:
(Vk ) riK ik = (r1…ri / rk)(K k1…K ki) при k < i
Vk = (Vk ) riK ik = (r1…ri)(K k1…K ki) при k > i .
Vk при k = i
(Замечание: на первом этапе M1 выбирает V1 = .)
Этап n :
1. Mn рассылает множество всех Vk участникам группы.
2. При получении Mi выбирает свое Vi = (r1…rn / ri)(K1i…K ni) .
Mi вычисляет (Vk ) ri(K1i-1… K ni-1) = r1…rn .
Заметим, что вместо того, чтобы вычислять n обратных элементов, Mi может вычислять 1 обратный элемент Pi -1 =(K1i -1 … Kni -1 ), где Pi =(K1i … Kni ).
В протоколе SA-GDH.2 требуется, чтобы каждый участник группы имел некоторый общий ключ с любым другим участником (это значение Kji ). Однако, как уже было замечено для каждого такого ключа Kji не требуется нахождение обратного Kji -1 . Таким образом, достаточно получить такие ключи перед началом работы в группе и затем эти ключи могут оставаться постоянными, не добавляя лишних действий в протокол.
Протокол основан на кольцевой схеме взаимодействия, т.е. данные проходят по кругу и лишь на последнем этапе идет широковещательная рассылка. Данные, которые передаются, представляют собой множество из n элементов. i -й элемент содержит своеобразное «накопление ключа» для i -го участника. Во время обновления ключа каждый из участников вносит свой вклад в формирование ключа. Только пройдя полный круг, i -й элемент множества будет иметь вклады всех участников и их секретные ключи для связи с i -м абонентом (рис. 1). Это позволяет избежать явной замены противником одного из значений на какое-то другое, выгодное ему (возможное вмешательство противника рассмотрим далее)
Однако SA-GDH.2 имеет более высокую «вычислительную стоимость» по сравнению с A-GDH.2. Прежде всего, он требует (n -1) экспоненцирование для каждого Mi (кроме первого), в отличие от i экспоненцирований в A-GDH.2. К этому еще добавляется работа по формированию общих ключей для каждой пары абонентов (если они не вычислены заранее): на последнем этапе проводится одно экспоненцирование – как и в A-GDH.2. На рис. 1 приведены примеры протоколов A-GDH.2 и SA-GDH.2.
Как показано в [1], протокол SA-GDH.2 обеспечивает полную аутентификацию группового ключа .
Теорема 2.2.1 Протокол SA-DH обеспечивает полную аутентификацию группового ключа .
Док-во: предположим, Mi и Mj вычислили одинаковый ключ в результате выполнения протокола. Пусть Kn =Sn (Mi )=Sn (Mj ), и предположим, что некто Mp ÎM (p ¹i ,j ) не сделал вклада в этот ключ. Пусть Vi и Vj обозначают величины, полученные Mi и Mj на последнем этапе протокола. Напомним, что в соответствии с протоколом
Sn (Mi )=(Vi )(K1i-1…Kni-1 )ri и Sn (Mj )=(Vj )(K1j-1…Knj-1 )rj .
Поскольку все участники группы сделали вклад в ключ, то можно записать, что
Vi = (r1…rn/rpri )(K1i-1…Kni-1/Kpi-1 ) (для Vj аналогично), и
Sn (Mi )= (r1…rn/rp )Kpi-1 , что должно равняться Sn (Mj )= (r1…rn/rp )Kpj-1 .
Но поскольку Kpi - 1 и Kpj - 1 являются секретными, то получаем противоречие. #
В работе [1] также отмечается, что обсуждаемый протокол обладает устойчивостью к атакам по известному ключу (known key attacks ), однако строгого формального доказательства не приведено, авторы лишь отмечают, что это легко пронаблюдать на приведенной выше атаке на A-GDH.2.
2.3 Особенности ключей протоколов A-GDH.2 и SA-GDH.2
Рассмотрим важное свойство протоколов – а именно подтверждение ключа . Не для каждого протокола это свойство является необходимым: например, оно не нужно, если взаимодействие с полученным ключом происходит немедленно. Но тем не менее свойство подтверждения ключа является желательным для протоколов обмена по следующим причинам:
1. Протоколы обмена становятся более сильными и автономными.