Криптографические протоколы

£n).

Для выполнения этого определения можно модифицировать протокол A-GDH.2 в следующий:
Криптографические протоколыКриптографические протоколыПротокол SA-GDH.2. Этап i (0< i <n): 1. Mi  получает множество промежуточных величин { Vk | 1£ k £ n}. (в данном контексте можно сказать, что M1 получает пустое множество на первом этапе):               a (r1…ri-1 / rk)(K k1…K k(i-1)) при  k £ (i-1) Vk =                a (r1…ri-1)(K k1…K k(i-1)) при  k > (i-1) . 2.  Mi  обновляет каждое Vk следующим образом:               (Vk ) riK ik = a (r1…ri / rk)(K k1…K ki)   при  k < i Vk =       (Vk ) riK ik = a (r1…ri)(K k1…K ki)       при k > i    .               Vk                                              при k = i (Замечание: на первом этапе M1 выбирает V1 = a .) Этап n: 1. Mn рассылает множество всех Vk участникам группы. 2. При получении Mi выбирает свое Vi =a (r1…rn / ri)(K1i…K ni). Mi вычисляет (Vk ) ri(K1i-1… K ni-1)= a 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=a (r1…rn/rpri)(K1i-1…Kni-1/Kpi-1) (для Vj аналогично), и

Sn(Mi)= a (r1…rn/rp)Kpi-1, что должно равняться Sn(Mj)= a (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. Протоколы обмена становятся более сильными и автономными.

2. Исключается возможность вычисления неправильного ключа  без обнаружения этого (в случае перерыва между выработкой общего ключа и непосредственно передачей данных).

С другой стороны, пока еще нет точного определения, что же такое подтверждение ключа для групп. Если брать полное подтверждение ключа, то это достигается путем получения каждым участником ключа и затем доказательства всем, что он знает этот ключ.

Для протоколов A-GDH.2 и SA-GDH.2 исходя из практических соображений было определено подтверждение ключа как подтверждение ключа для контролирующего группы (участника Mn). Это может быть легко достигнуто в обоих протоколах путем добавления

a F(Sn(Mn))

в последнее сообщение протокола (рассылка всем участникам группы), где Sn(Mn) обозначает ключ, вычисленный Mn, а F – хэш-функцию, как это было определено выше.

Таким образом, участник группы Mi вычисляет Sn(Mi) и проверяет равенство:

a F(Sn(Mi)) =?a F(Sn(Mn)) .

В [2,5] замечено, что в A-GDH.2 и SA-GDH.2 подтверждение и неявная аутентификация ключа образуют полезный в некоторых случаях побочный эффект – аутентификацию участника Mn для всех участников группы. Это еще раз доказывает необходимость выделения Mn как отдельного лица – контролирующего группы.

Включение подтверждения ключа в протокол SA-GDH.2 приводит к интересному результату, а именно:

после выполнения протокола каждый участник группы Mi знает, что ключ, выработанный им, содержит вклад каждого участника группы.

Это следует непосредственно из свойств полной аутентификации группового  ключа и подтверждения ключа. Если бы отсутствовало подтверждение ключа, то участники группы не могли бы убедиться в истинности своего ключа.

Опр. 2.3.1. (неформ.) Групповой протокол обмена для выработки общего ключа  обеспечивает целостность группы, если каждый участник протокола уверен в участии каждого другого участника в протоколе.

Опр. 2.3.2. (неформ.) Групповой протокол обмена для выработки общего ключа  является  проверяемо контрибутивным (verifiable contributory), если каждый участник протокола уверен,  что каждый другой участник сделал вклад в групповой ключ.

Свойство проверямой контрибутивности включает в себя свойство целостности группы. Обратное утверждение неверно, поскольку целостность группы может быть обеспечена, если участник группы Mi будет просто подписывать сообщение отсылать его дальше. Проверяемой контрибутивности в данном случае нет. В то же время проверяемая контрибутивность может выполняться, если в формировании ключа участвовало лицо, стороннее по отношению к группе. Таким образом противник может влиять на протокол.

Однако следует заметить, что даже если выполняются свойства (неявной, полной) аутентификации и подтверждения ключа, свойство целостности ключа в вышеприведенном протоколе SA-GDH.2 не достигается.

Рассмотрим приведенный на рис. 2 пример для трех участников.

Криптографические протоколы

Предположим, что имеется активный противник, который может вмешиваться в передачу, подменять и модифицировать данные. Он может провести какое-либо экспоненцирование данных на этапе (1) и/или (2) и это останется незамеченным. Пусть он просто возводит в квадрат все величины на этапе (2). Тогда M3 получит следующие значения: a 2r1K12, a 2r1r2K13K23, a 2r2K21.

В результате M3 вычислит S3(3)= a 2r1r2 r3, т.е. квадрат предполагавшегося ключа. Все остальные участники группы получат то же самое. Подтверждение ключа здесь не помогает, поскольку злоумышленник вторгается в протокол перед тем, как M3 вычисляет свой групповой ключ.

Как было справедливо замечено в [1], протокол SA-GDH.2 подвержен (пока) только мультипликативному (экспоненциальному) влиянию противника на ключ, т.е. можно получить ключ Kc, где с- некоторая константа, а К-ключ, предполагаемый в протоколе. Авторы задаются вопросом: так ли важна целостнось ключа в протоколе обмена с проверяемой контрибутивностью?

Для обеспечения целостности можно воспользоваться сторонними средствами обеспечения целостности данных во время передачи – например, проверять целостность пакетов при отправке по сети. На последнем же широковещательном этапе никаких сторонних средств не требуется, т.к любое вмешательство будет обнаружено из-за свойства подтверждения ключа для контролирующего группы.

2.4 Сравнение эффективности

Приведем таблицу сравнения протоколов (по вычислительным требованиям). Понятно, что различные реализации будут различаться по скорости выполнения и объему кода, а также типа используемых процессоров – это отдельная тема и с математической точки зрения не представляет интереса, нужные таблицы приведены в [2,3,4,5]. Поэтому ограничимся приведением лишь вычислительных характеристик в таблице 1.

Стоимость вычислений GDH.2 A-GDH.2 SA-GDH.2
Экспоненцирований для Mi I+1 i+1 n
Экспоненцирований для Mn N n N
Всего экспоненцирований (n2+3n)/2-1 (n2+3n)/2-1 n2
Вычисления обр. элементов для Mi 1
Вычисления обр. элементов для Mn 1
Всего вычислений обр. элементов n
Умножений для Mi 1 2n-2
Умножений для Mn n-1 2n-2
Всего умножений 2n-2 2n2-2n

Полученные в результате приведенных протоколов общие ключи могут использоваться как ключи для секретной связи внутри группы, служить для аутентификации участников группы, выполнять роль секретного ключа при формировании групповой подписи и т.д.

3 Проект CLIQUES

Целью данного проекта являлась разработка протокола обмена для выработки ключа для групп. Такой протокол должен поддерживать все групповые операции по удалению, включению новых участников в группу. На основе этого протокола необходимо было создать специальный прикладной программный интерфейс (CLQ-API) , позволяющий работать приложениям в неких абстрактных группах. Протокол во многом основывается на вышеописанных протоколах аутентичного обмена. Ограничимся рассмотрением только математических принципов проекта. Не будем рассматривать полученные результаты (по эффективности), программные реализации.

В качестве базового протокола обмена для выработки общего ключа был выбран протокол A-GDH.2 (однако возможно использование и SA-GDH.2). Предполагается, что участники группы уже сформировали общий ключ.

Рассмотрим основные операции, которые позволяет выполнять разработанный протокол.

1. Операции для одного участника группы: включают в себя добавление или удаление одного участника группы. Данные ситуации появляются, когда кто-то хочет присоединиться к группе или покинуть ее. Эти операции могут проводится контролером группы или по согласию каждого участника группы (в зависимости от используемой политики безопасности).

2. Операции для нескольких участников: также включают в себя добавление и удаление. Однако есть отличия, обусловленные желанием проводить операции с несколькими участниками сразу, а не с каждым в отдельности:

массовое присоединение: несколько участников хотят присоединиться к существующей группе;

слияние групп: две или более групп желают соединиться в одну;

массовый выход из группы: несколько участников хотят покинуть группу;

разделение групп: группа распадается на две или более частей.

3. Операции по обновлению ключа обусловлены двумя причинами:

ограничением шифртекста, получаемого на одном ключе для ограничения возможности получения пар открытый текст/шифртекст для проведения криптоанализа (время жизни ключа определяется выбранной политикой);

предохранением от компрометации текущего ключа или вклада каждого участника.

Итак, список операций, выполняемых протоколом, выглядит следующим образом:

присоединение (JOIN): новый участник добавляется в группу;

слияние (MERGE): один или более участников добавляются в группу;

выход из группы (LEAVE): один или более участников покидают группу;

обновление ключа (KEY REFRESH): генерация нового ключа для группы.

Для простоты, считается, что последний участник группы является контролирующим группы (это может быть легко исправлено и не является критическим требованием).

Присоединение

Операция добавляет нового участника Mn+1 к группе из n участников. Во время операции вычисляется новый групповой ключ Sn+1 , и Mn+1 становится новым контролирующим группы. Предполагая, что Mn является текущим контролирующим группы, протокол выглядит следующим образом:

1. Mn вырабатывает новое значение rn’ и получает множество[2] чисел

M={g r1…rn’/ri | iÎ[1,n-1]} È{ g r1…rn-1 }È{ g r1…rn’ }

Затем M посылается Mn+1.

2. После получения сообщения Mn+1 вырабатывает число rn+1 и вычисляет значение g Ki,n+1r1…rn’rn+1/ri для всех i из [1,n]. Затем это множество рассылается всей группе.

3. При получении каждый Mi вычисляет групповой ключ как

(g Ki,n+1r1…rn’rn+1/ri)K-1i,n+1ri= g r1…rn’rn+1= Sn+1. А Mn+1 вычисляет ключ, используя сообщение из шага (1).

Шаги (1) и (2) требуют n экспоненцирований, шаг (3) требует одно экспоненцирование для каждого участника группы. Общее число экспоненцирований для получения ключа равно 2n+1 (считается, что на третьем шаге экспоненцирования происходят одновременно и

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: