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

From CryptoWiki
Jump to: navigation, search

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

Contents

Описание

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

Начальные параметры протоколов, термины и обозначения

  • n - число участников протокола;
  • i, j - индексы для участников групп;
  • Mi.jpg - i-ый участник группы;
  • G - подгруппа Zp .jpg порядка q, где p и q – простые;
  • q - порядок алгебраической группы;
  • α, g - образующие элементы в группе G;
  • Xi.jpg - долговременный секретный ключ Mi.jpg;
  • Ri.jpg - случайное (секретное) число ∈ Zq, вырабатываемое Mi.jpg;
  • Sn.jpg - групповой ключ n участников;
  • Sn(Mi).jpg - вклад Mi.jpg-го участника в групповой ключ;
  • Kij.jpg - долговременная секретная величина, выработанная Mi.jpg и Mj.jpg, ij.

Все вычисления проводятся в циклической группе G простого порядка q, которая является подгруппой Zp .jpg порядка p, где p=kq+1 для некоторого kN.

Протокол Диффи-Хеллмана для групп

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

Протокол A-DH

Существует множество разнообразных протоколов обмена с аутентификацией ключа, но одни из них не поддерживают двусторонний вклад в общий ключ, другие требуют большого числа сообщений или предполагают априорный доступ к сертифицированным долговременным ключам. Многие не обладают свойством совершенной опережающей секретности. Поэтому, наиболее подходящим протоколом для групп в считают протокол Диффи-Хеллмана с аутентификацией (A-DH) [1]. Данный протокол предполагает наличие у участников аутентичных открытых ключей друг друга.

A-DH.jpg

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

Протокол GDH.2

Рисунок 1 — Схема передачи сообщений в протоколе GDH.2

Протокол Диффи-Хеллмана для групп является расширением протокола Диффи-Хеллмана на n участников. Алгоритм GDH.2 (Group Diffie-Hellman) [2] является незначительно улучшенной модификацией алгоритма GDH.1, поэтому рассматриваться будет только алгоритм GDH.2.

GDH.2.jpg

Протокол A-GDH.2

Рисунок 2 — Схема передачи сообщений в протоколе A-GDH.2

Протокол GDH.2 можно модифицировать для обеспечения свойства аутентификации ключа [1]. Модификация представляет из себя замену последнего этапа протокола. Предполагается, что Mn.jpg имеет с каждым Mi.jpg общий секрет A-GDH F1.jpg, где Xi.jpg - секретное долговременное значение Mi.jpg, A^xi.jpg mod p – долговременный открытый ключ Mi.jpg.

A-GDH.2.jpg

В этом протоколе каждый участник группы вырабатывает общий аутентичный ключ с Mn.jpg. Более того, если участник Mn.jpg является доверенным, то каждый участник группы может быть уверен, что такой же ключ имеют и все остальные участники группы, т.е. был выработан общий групповой ключ. Очевидно, что протокол обладает свойством контрибутивности, поскольку в результирующем ключе Sn.jpg есть вклад i-го участника группы в виде степени Ri.jpg. Так же протокол обладает свойством совершенной опережающей секретности.

Дополнительно протокол A-GDH.2 выполняет аутентификацию ключа, но в довольно слабой форме, поскольку ключ не аутентифицируется непосредственно между каждыми любыми двумя Mi.jpg и Mj.jpg участниками (ij). Последний участник Mn.jpg (который называется контролирующим группы, поскольку через него проводятся ключевые операции протокола) отвечает за использование аутентичных ключей Kin.jpg, i=1,...,n-1, от которых и зависит аутентификация. Следовательно, участник Mn.jpg должен быть лицом, которому все доверяют, например, доверенным сервером. В противном случае Mn.jpg сможет разбить группу на две части без обнаружения этого.

Протокол SA-GDH.2

Рисунок 3 — Схема передачи сообщений в протоколе SA-GDH.2

Протокол обеспечивает явную аутентификацию группового ключа, если для каждых i,j (0<ijn) участники Mi.jpg и Mj.jpg вычислят общий ключ Si,j.jpg, только если Si,j.jpg был получен при участии каждого участника группы. Другими словами, явная аутентификация группового ключа есть аутентичный обмен для выработки ключа между всеми парами (Mi.jpg,Mj.jpg) при (0<ijn).

Для обеспечения этого свойства протокол A-GDH.2 был модифицирован, в результате чего появился протокол Complete Group Key Agreement (SA-GDH.2) [1].

SA-GDH.2.jpg

Протокол TGDH

Рисунок 4 — Пример TGDH-дерева

Альтернативными методами получения общего группового ключа, отвечающими определенным групповой семантикой операциям изменения состава группы, являются методы, основанные на использовании бинарных деревьев ключей [3]. Дерево ключей представляет собой бинарное дерево, узлы которого хранят информацию о промежуточных ключах, на основе которых вычисляется общий ключ, а непосредственно участники группового взаимодействия представлены листьями дерева. В общем случае алгоритм построения бинарного дерева ключей называется алгоритмом TGDH (Tree-Based Group Diffie-Hellman). Бинарное дерево ключей строится по следующей схеме. Для узлов дерева вводится строгая индексация. Корень находится на уровне 0 и имеет индекс (0,0). Полагаем, что узел (l,v) — v-й узел на уровне l. Потомки данного узла будут иметь индексы (l+1, 2v) и (l+1, 2v+1). С каждым из узлов ассоциируется пара ключей: K(l,v) и BK(l,v) = f(K(l,v)), являющимся скрытым ключом, где f — функция модулярного экспоненцирования в поле простых чисел, к примеру TGDH F1.jpg по аналогии с алгоритмом Диффи–Хеллмана. Листья дерева ассоциируются с членами группы, и для них значения K(l,v) выбираются случайным образом. Для промежуточных узлов значение вычисляется по следующей рекурсивной формуле: TGDH F2.jpg

Для вычисления ключа узла необходимо знание ключа одного из потомков и скрытого ключа другого. Для каждого из листов определяется путь к вершине начиная непосредственно с самого листа. При условии владения набором скрытых ключей всех узлов, имеющих общего родителя с узлами, составляющими путь от листа к вершине, член группы, представляемый листом, имеет возможность вычисления общего группового ключа, равного значению K(0,0). На рис. 4 приведен пример сбалансированного по высоте TGDH-дерева высоты 3, содержащего 6 элементов. К примеру, для участника M2 путь составляют вершины {(3,1), (2,0), (1,0), (0,0)}. Для вычисления K(0,0) необходим набор ключей {K(3,1), BK(3,0), BK(2,1), BK(1,1)}. Конечная формула вычисления группового ключа для M2 будет иметь вид: TGDH F3.jpg

Однораундовый алгоритм ключевого соглашения Диффи-Хеллмана на основе мультилинейных отображений

Однораундовый алгоритм (n+1)-стороннего ключевого соглашения Диффи-Хеллмана [4], в основе которого лежат мультилинейные отображения, является обобщением алгоритма Антуана Жу на билинейных спариваниях. Пусть есть (n+1) абонентов, которые хотят выработать групповой ключ, используя алгоритм, в котором каждый абонент группы рассылает остальным только одно сообщение. После рассылки каждый абонент вычисляет общий ключ S.

Этапы алгоритма:

  1. Инициализация: G1.jpg и G2.jpg — конечные циклические мультипликативные группы порядка l. Выбирается MultilinearMap.jpgn-мультилинейное отображение, g — образующий элемент группы G1.jpg.
  2. Публикация: i-ый абонент выбирает случайное число Ai.jpg ∈ [1, l - 1], и вычисляет Hi F.jpg. Абонент рассылает значение Hi.jpg остальным абонентам, а значение Ai.jpg сохраняет в секрете;
  3. Выработка ключа: j-ый абонент вычисляет ключ S следующим образом: S F1.jpg.

Благодаря свойству мультилинейности отображения μ: S F2.jpg. Таким образом, все (n+1) абонентов получат одинаковый групповой ключ S.

Глоссарий

Библиографический указатель

Перейти к списку использованных источников.

Корнев Д.К., 2016