Научная литература
booksshare.net -> Добавить материал -> Криптография -> Алферов А.П. -> "Основы криптографии Учебное пособие" -> 104

Основы криптографии Учебное пособие - Алферов А.П.

Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии Учебное пособие — М.: Гелиос АРВ, 2002. — 480 c.
ISBN 5-85438-025-0
Скачать (прямая ссылка): osnovikriptografii2005.djvu
Предыдущая << 1 .. 98 99 100 101 102 103 < 104 > 105 106 107 108 109 110 .. 126 >> Следующая


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 р. Положим
Предыдущая << 1 .. 98 99 100 101 102 103 < 104 > 105 106 107 108 109 110 .. 126 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed