Threshold diffie - hellman protocol.pdf Пусть sk - закрытый ключ участника протокола Диффи - Хеллмана. Будем называть функцией Диффи - Хеллмана функцию DH(sk,Q), которая принимает на вход закрытый ключ sk (скаляр) и точку Q на эллиптической кривой и возвращает точку sk • Q. Под протоколом Диффи - Хеллмана обычно понимают следующую последовательность вычислений (G - образующий элемент подгруппы простого порядка q группы точек эллиптической кривой E над конечным полем): 1) Алиса генерирует случайное число a G Zq, вычисляет значение A = DH(a, G) и отправляет его Бобу; 2) Боб генерирует случайное число b G Zq, вычисляет значение B = DH(b, G) и отправляет его Алисе; 3) Алиса вычисляет общий секрет как K = DH(a,B), а Боб - как K = DH(b, A). Идея пороговой схемы Диффи - Хеллмана заключается в том, чтобы сгенерировать закрытый ключ участника протокола x с помощью распределённого алгоритма некоторыми сущностями, а затем делегировать им вычисление значения функции DH(x, Q), используя методы пороговой криптографии. Будем называть таких сущностей агентами, а участником протокола Диффи - Хеллмана будем называть группу агентов, которая представляет одну из сторон протокола Диффи - Хеллмана и выполняет установленные протоколом шаги. Если в классическом протоколе Диффи - Хеллмана участником является атомарная сущность (человек, процесс и т. д.), то теперь участник протокола - это группа сущностей - агентов (людей, процессов, ...), которые взаимодействуют между собой посредством разработанных протоколов так, что для внешних сущностей (другого участника протокола, сторонних наблюдателей и т. д.) группа агентов неотличима от обычного участника протокола Диффи - Хеллмана. При этом по результатам выполнения этих протоколов любой из агентов знает открытый ключ группы и может представлять группу при взаимодействии с другим участником протокола. Так как группа агентов неотличима для внешних сущностей от обычного участника, то для простоты изложения далее будем считать, что только один из участников протокола Диффи - Хеллмана представлен группой агентов. При этом неважно, какой именно из участников протокола состоит из агентов, так как вычисления, выполняемые участниками, симметричны. Первым этапом предлагаемой схемы является генерация долей закрытого ключа, а также вычисление открытого ключа соответствующего участника протокола Диффи - Хеллмана. Вычисленный открытый ключ известен каждому агенту из группы, а соответствующий закрытый ключ неизвестен никому и существует только в виде сгенерированных долей. Этот этап описывается протоколом генерации ключей. Протокол генерации ключей основан на идее распределенной генерации ключей, которая строится с использованием проверяемой схемы разделения секрета Фельдмана [1]. Каждому агенту Pj ставится в соответствие индекс, который определяет получаемую им долю в схеме Фельдмана. Для простоты будем считать, что индексом агента Pj является значение j (в качестве индексов могут быть использованы любые значения, на которых определены многочлены схемы Фельдмана, если эти значения различны для всех агентов; они устанавливаются на фазе подготовки, не являются секретными и должны быть известны всем агентам). Тогда во всякой схеме Фельдмана агент Pj получает долю f (j), где f - многочлен схемы Фельдмана. При этом генерация итоговых долей на агентах происходит без участия дилера, в результате чего секретная доля закрытого ключа каждого агента известна только ему самому. Это достигается за счёт того, что каждый агент по очереди выступает в роли дилера в схеме Фельдмана, разделяя некоторое случайное значение ui, а затем благодаря свойству схемы Фельдмана (сумма долей ai и bi от значений a и b соответственно является долей от значения a + b) агенты, складывая полученные значения, получают новые доли от значения x = ui, которое не было разделено явным образом. i В ходе протоколов агенты обмениваются открытыми значениями друг с другом, используя схемы обязательств для фиксации передаваемых значений. Обозначения, использованные для описания протоколов, взяты из [2]: 1) Каждый агент Pi выбирает случайное значение ui G R Zq и вычисляет [KGCi, KGDi] = Com(yi), где yi = ui•G; Com - алгоритм схемы обязательства; KGCi - вычисленное с помощью алгоритма обязательство; KGDi - строка, позволяющая его раскрыть. Затем агент отправляет KGCi всем агентам. 2) Каждый агент Pi отправляет KGDi всем агентам, а затем разделяет значение ui между всеми агентами, используя (t, ^-схему Фельдмана. Открытый ключ соответствующего участника протокола Диффи - Хеллмана равен y yi = = Ui • G. i 3) Каждый агент складывает доли, полученные в схемах Фельдмана, для вычис ления своей закрытой доли xi. Итоговое значение закрытой доли агента xi является долей от закрытого ключа x ui в (t, ^-схеме Шамира. При этом i закрытый ключ x не восстанавливается ни в какой момент выполнения протокола и существует только в форме долей. Для вычисления общего секрета предлагается протокол выработки общего секрета. Получая на вход открытый ключ Y другого участника протокола Диффи - Хеллмана, агенты вычисляют общий секрет S = x * Y, используя свои доли закрытого ключа, при этом не раскрывая их в ходе протокола: 1) Каждый агент Pi вычисляет коэффициент Лагранжа Ai и значение wi = Aixi, которое является долей данного агента в аддитивной (t - 1, £)-схеме разделения секрета от значения x. Здесь Ai - значение i-го базисного многочлена в схеме интерполяции Лагранжа в точке 0. 2) Агент вычисляет значения Si = wi • Y, [EXCi,EXDi] = Com(Si), где Com - это алгоритм схемы обязательства, EXCi - вычисленное с помощью алгоритма обязательство и EXDi - строка, позволяющая его раскрыть. Затем агент отправляет EXCi другим участникам. 3) Агенты отправляют друг другу значения EX Di. Общий секрет равен S = Si. i Пороговая схема позволяет расширить число сценариев применения протокола Диффи - Хеллмана, в том числе представляет возможность улучшения свойств безопасности закрытых ключей участников протокола Диффи - Хеллмана: если в классической схеме злоумышленнику достаточно получить доступ к узлу сети, который хранит соответствующий закрытый ключ, то теперь необходимое количество узлов зависит от порога и всегда больше единицы. Предложенная схема реализована для протоколов Диффи - Хеллмана на кривых Curve25519 и NIST P-256. Препринт статьи доступен на arxiv.org [3].

Скачать электронную версию публикации