Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
Семейство подмножеств называется семейством LLInep-нера, если ни одно из них не содержится в другом.
Теорема 3. Семейство {S1,..., Sn} подмножеств
множества К, I К I = q, образует KDP(n,q)-cxeMy в том и только в том случае, если множество { S1 п Sj | I < / <j < п } образует семейство Шпернера.
Докажите теорему 3 самостоятельно в качестве упражнения.
Теорема 4 (Sperner9 1928). Если подмножества
{$!,..., Sm} множества К, I К I = q, образуют семейство Шпернера, то
т<С
Равенство достигается только в случае, если множество {S'],..., Sm) совпадает с множеством всех w-элементных подмножеств множества К, где w = q/1 при четном q и w = (<7+1)/2 или (q - 1)/2 при нечетном q.
396
/ юотоколы распределения ключей
Доказательство. Пусть семейство {S]9...9Sm} подмножеств множества К состоит из максимально возможного числа элементов. Покажем, что существует семейство LLInep-нера с не меньшим, чем т, числом множеств, каждое их кото-
q
рых имеет мощность
Обозначим w = max |. Предположим, что w > -
/=1,/7
что подмножества S\9 ..., Sh t <п, состоят из w элементов. Рассмотрим подмножества R\, Ru множества K9 каждое из которых состоит из w-І элементов и содержится хотя бы в одном из подмножеств S\9 ...,Sf/. Нетрудно видеть, что семейство
Ru •••? Sf+ \9..., Sm
также образует семейство Шпернера. Покажем, что u>t.
Каждое подмножество S1 содержит ровно w подмножеств Rj. С другой стороны, каждое подмножество Rj входит не более чем в (q - w +1) подмножеств S1. Поэтому, вычисляя двумя способами число ребер в двудольном графе, вершинами которого являются подмножества S\щ...JSt и R\9...9RU9 а ребра соединяют вложенные подмножества Rj Cl S1, получаем неравенство wt <(q -W +1 )и. Отсюда следует, что
или
Л
+ 1
< wt < (q - w + \)и <
/ ч_ \
ч-
V _2_ )
и,
и >
Г ¦" L + 1
Ч~ Я
_2_
t>t
397
І лава 1b
Таким образом, можно считать, что в семействе
{Sj,...,Sn} все элементы состоят не более чем из
эле-
шим, чем
числом элементов, то, переходя к семейству
ментов.
Если В семействе { SJ,..., Sn } имеется множество с мень-
.2.
{Sf1 ,...,Sfn }, состоящему из подмножеств S\ = K\Sn которое также составляет семейство Шпернера, и, повторяя приведенные выше рассуждения, получаем семейство, в котором все множества имеют одинаковое число элементов. Теорема доказана.
Теорема 5. Для любой KDP(п,с[)-схемы каждый абонент должен иметь не менее log2 п ключей. Если п > 4, то q > 2 Iog2 п.
Доказательство. Если у какого-либо абонента имеется множество, состоящее менее чем из Iog2 п ключей, то с их помощью можно построить не более чем п-2 различных подмножеств ключей. Поэтому он не сможет сформировать различные ключи для связи с п - 1 абонентами.
Вторая оценка получается из очевидного неравенства
C [я!2 J > с1
которое справедливо в силу предыдущей теоремы.
Схемы разделения секрета
Схема разделения секрета представляет собой схему предварительного распределения ключей между уполномоченными группами пользователей, в которой ключ заранее определен и одинаков для каждой уполномоченной группы. При этом каждый пользователь получает свою долю или “часть секрета”. Схема включает два протокола: протокол 398
І Іротокольї распределения ключей
формирования долей (разделения секрета) и распределения их между пользователями и протокол восстановления секрета группой пользователей. Схема должна позволять восстанавливать ключ только тем группам пользователей, которые имеют на это полномочия, и никакая другая группа не должна иметь возможности для восстановления ключа или получения о нем какой-либо информации.
Основное назначение схемы разделения секрета — защита ключа от потери. Обычно для защиты от потери делают несколько копий ключа. С возрастанием числа копий ключа возрастает вероятность его компрометации. Если число копий мало, то зелик риск потери ключа. Поэтому лучше “разделить” ключ между несколькими лицами так, чтобы допускалась возможность восстановления ключа при различных обстоятельствах несколькими уполномоченными группами с заранее оговоренным составом участников. Тем самым исключается риск безвозвратной потери ключа.
Еще одно положительное качество схем разделения секрета заключается в разделении ответственности за принятие решения, которое автоматически вводится при определении состава уполномоченных групп. Такая коллективная ответственность нужна для многих приложений, включая принятие важных решений, касающихся применения систем оружия, подписания корпоративных чеков или допуска к банковскому хранилищу.
В простейшем случае, когда имеется только одна группа, состоящая из t пользователей, уполномоченная формировать ключ, схему разделения секрета можно построить следующим образом. Предположим, к примеру, что ключ представляет собой двоичный вектор s длины т. Выберем случайным образом t векторов s\, ...,St так, чтобы их сумма совпадала с вектором S9 и распределим их между пользователями. Теперь, собравшись вместе, они могут легко восстановить значение ключа S9 в то время как никакая группа, состоящая из меньшего числа пользователей, не сможет этого сделать. Действительно, в данном случае отсутствие хотя бы одной доли при-
