Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
Имеют место следующие результаты.
Лемма. Пусть имеется матрица Вандермонда
1 rX 'О
1 4 ... гт rI
Гт+Х 'Li - гт ' rm+\J
Если элементы г и г2, гт у попарно различны и отличны от нуля, тогда обратима над полем F.
392
і іротокольї распределения ключей
Теорема 1. Схема Блома предварительного распределения ключей между п абонентами, использующая многочлен степени т, 1 <т<п, является стойкой к компрометации ключей т абонентов. Это означает, что при раскрытии ключевых материалов, принадлежащих любым т абонентам, злоумышленник, зная их значения, не сможет определить ни один из ключей для связи между остальными (п - т) абонентами.
Доказательство. Запишем выражение для общего ключа абонентов AnB9 вычисляемого по формуле
многочлена/(х9 у) и является симметричной.
Абонент А имеет секретный набор (а{0А\ а\А\..., а^)9 представляющий собой коэффициенты многочлена
Предположим, что известны ключевые материалы, принадлежащие т абонентам. Покажем, что по ним нельзя опре-
т т
kAB = ЯГАSb ) = ЦИа'/лгв >
/=O J=о
в матричном виде:
Vат 0 ^mO
атт J т VB J
из коэффициентов
Здесь матрица Л = (а;/)
составлена
gA W =f(x,rA) = a(f + а\А)х +...+ a,^ хт,
или иначе
г”1)-А.
393
І лава 1Ь
делить ни один из ключей для связи между оставшимися (п -т) абонентами.
Пусть, например, известны секретные наборы ключевых материалов т абонентов —AfBf...,С. Будем искать ключ для связи между абонентами U и W9 не входящими в множество [AtB,...,С}. Для этого рассмотрим матричное равенство
(к kAA kAB ... I kAC к ^ kAU
^ BA kBB і ^BC kBO
к(А kCB ... і Kc kC и
JiWA kWB ... kW( kWU J
/ rA Л . гт) .. ГА f I 1 ... 1 I
1 rB rB •• rA rB ... гс rU
... A- Л гкв *6
1 ГС ^ .. ...
V rW 4 •• rW J Га гвт
В матрице из левой части равенства не известен только искомый ключ kwu. В правой части неизвестная матрица A умножается слева и справа на обратимые матрицы, так как по лемме их определители не равны нулю.
Выражая теперь матрицу Л из данного равенства, замечаем, что при произвольно заданном значении ключа кт из поля F матрица Л находится как произведение трех матриц. (Проверьте, что данная матрица должна быть симметричной матрицей, составленной из коэффициентов многочлена.)8
Таким образом, при каждом значении ключа kwu может быть найден многочлен/(х9 у), при котором данный ключ по-
8 Указание замените в нижней строке рассматриваемого матричного равенства символ W на U и заметьте, что нижняя строка полученной матрицы будет линейной комбинацией строк исходной матрицы
394
І іротокольї распределения ключей
лучается в качестве решения. Это свидетельствует о невозможности получения информации об этом ключе на основании известных значений.
С другой стороны, если известны ключевые материалы, принадлежащие т + 1 абонентам, то, очевидно, из рассматриваемого равенства матрица (a ) всегда находится однозначно. Теорема доказана.
Теорема 2. Если схема предварительного распределения ключей между п абонентами является стойкой к компрометации ключей т абонентов, I < т < п, и использует I-битовые ключи, то каждый абонент должен хранить не менее 1{т + 1) бит ключевых материалов.
Докажите эту теорему самостоятельно в качестве упражнения.
Из теорем 1 и 2 следует, что для заданного числа т схема Блома дает минимальное по объему количество хранимых у абонента ключевых материалов.
Рассмотрим еще одну схему предварительного распределения ключей, которая также позволяет значительно сократить общее число хранимых и передаваемых секретных ключей. Она называется KDP (key distribution patterns) и основана на схеме пересечений множеств (см. [Dye95]).
Пусть имеется п9 п > 2, абонентов (пользователей) и множество секретных ключей К, I КI = q. Будем считать, что все ключи перенумерованы числами 1,2,..., q. Выберем некоторое семейство {Si9...9Sn} подмножеств множества {1,2,..., q). Предварительно абоненту і по защищенному каналу передается множество секретных ключей с номерами из подмножества S19 і=\9п. Таким образом, семейство
{Sl9...9Sn} представляет собой таблицу с номерами ключей каждого пользователя. Хотя данная таблица является несекретной, она должна быть защищена от модификаций и подделок.
395
І лава 1Ь
Если абонент і хочет связаться с абонентом у, то он использует для выработки общего ключа множество ключей, номера которых содержатся в пересечении S1 n Sj. Если каждый ключ представлен некоторой битовой строкой, то для формирования общего связного ключа можно взять, например, их сумму, или значение некоторой хэш-функции от строки, составленной из ключей, номера которых входят в пересечение множеств S1 nS,.
Схемой распределения ключей типа KDP, или KDPO?,#)-схемой, назовем всякое семейство {S]9...,Sn) подмножеств множества К, удовлетворяющее следующему условию:
если при некоторых i, j, г є {1, п} выполнено включение S1 Г\ Sj с^, то либо і = г, либо j = г.
Это условие означает, что общий ключ двух абонентов не должен быть известным никакому другому абоненту.
