Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
399
І лава 1Ь
водит к полной неопределенности относительно значения секрета, поскольку для каждого значения искомого секрета найдется возможный вариант значения отсутствующей доли.
Заметим, что если бы мы в предыдущем примере просто разбили вектор на t частей, то такая схема не могла быть схемой разделения секрета, так как знание любой доли давало бы частичную информацию о секрете s
Другой пример схемы разделения секрета дает пороговая схема Шамира [Sha79].
Пусть I <t <п . Схема разделения секрета между п пользователями называется (іn,t)-nopoaoeoii, если любая группа из t пользователей может восстановить секрет, в то время как никакая группа из меньшего числа пользователей не может получить никакой информации о секрете.
Для построения (я,/)-пороговой схемы А. Шамир предложил использовать многочлен степени t - 1 над конечным полем с достаточно большим числом элементов. Как известно, многочлен степени t - 1 можно однозначно восстановить по его значениям в t различных точках, но при этом меньшее число точек использовать для интерполяции нельзя.
Выберем поле F и зафиксируем п различных несекретных элементов гь ..., гпєР, отличных от нуля. Каждый элемент V1 приписан /-му абоненту сети, і = 1, п . Выберем также t случайных элементов а0,...,а/_/ поля F и составим из них многочлен/(х) над полем F степени /-1, I <t<n,
(-1
f(x) = ^alX1.
/=0
Положим s =J(O) = a0. Вычислим теперь значения s\=f(n), -, sn=f{r„)
и распределим в качестве долей между участниками наборы
(r„ S1), І= 1,п.
400
І іротокольї распределения ключей
Для восстановления секрета S можно воспользоваться интерполяционной формулой Лагранжа [Лид88]. Путь имеются t пар (х/9 V,), где уt =/(х,). Тогда формула Лагранжа имеет вид
Так как s =/(0), то из формулы Лагранжа получаем равенства
причем коэффициенты C1 не зависят от коэффициентов мно-гочленаДх) и могут быть вычислены заранее.
С помощью полученной формулы любая группа из / пользователей может легко восстановить секрет. В то же время можно показать, что никакая группа из меньшего числа пользователей не может получить никакой информации о секрете (докажите это самостоятельно).
Схема Шамира удобна тем, что она позволяет легко увеличивать число пользователей. Для этого не нужно ничего менять, кроме множества {г\9 ..., гп}, к которому следует добавить новые элементы гп+1, ..., r„+w. Заметим, что компрометация одной доли делает из (//,^-пороговой схемы (/1-І, /-1)-пороговую схему.
§ 15.5. Способы установления ключей для конференц-связи
Еще один тип распределения ключей между группами пользователей дают протоколы распределения ключей для проведения конференц-связи. Несмотря на внешнюю схожесть с протоколами разделения секрета, они имеют несколько принципиальных отличий. Если протоколы разделения
401
І лава Tb
секрета осуществляют предварительное распределение одного и того же ключевого значения (секрета) по секретным каналам между привилегированными группами пользователей, то протоколы конференц-связи осуществляют динамическое распределение ключей по открытым каналам связи между привилегированными группами пользователей. При этом ключи должны быть различными для каждой группы.
Тривиальный пример распределения ключей для проведения конференц-связи дает использование централизованного распределения ключей с помощью одного из трехсторонних протоколов передачи ключей, используемых для симметричных шифрсистем. Для реализации такого подхода нужно выделить одного из пользователей группы и возложить на него функции центра генерации и распределения ключей. Естественно, что при этом возрастают требования к доверенности и безопасности выделенного пользователя, что вносит серьезную асимметрию между участниками конференц-связи.
Другой подход основан на использовании идеи открытого распределения ключей.
Приведем примеры протоколов, в которых все участники группы имеют одинаковые полномочия и выполняют симметричные функции.
Простейший пример такого протокола для группы из трех участников можно получить, слегка модифицировав протокол открытого распределения ключей Диффи — Хеллмана. Участники протокола заранее договариваются о значениях большого простого числа р и образующего элемента а мультипликативной группы Z* = {1,2,...,/? - 1} . Для выработки общего ключа к пользователи A9B \\ С должны сгенерировать соответственно случайные числа х9 у и z9 I < x9y9z < р - 2 . Затем они должны обменяться сообщениями согласно следующему протоколу:
402
Протоколы распределения ключей
(1) А—* В: X - ax mod р,
(2) В—* С: Y = ау mod р ,
(3) С —* A'. Z = а: modр,
(4) Л —> В: Z'=Zx modр,
(5) В С: X1=XyHiod р,
(6) С—>Л: Y'=Yzmodp.
Искомый общий ключ k = axyz mod р теперь вычисляется пользователями A9 В и С по формулам:
к - (Ff) * mod р , к = (Zf) ^ mod /?, к = (Х?) z mod р
соответственно.
Рассмотрим теперь протокол формирования общего ключа для конференц-связи группы из t пользователей ?/<>,...,С/,-1, предложенный в статье [Впп90]. Как и в предыдущем протоколе, каждый пользователь U1 должен сгенерировать секретное случайное число rl9 I < гг < р — 2 , и вычислить открытую экспоненту Zi = ar' mod р. Положим