Стойкость к компрометации заданного числа абонентов

При построении ключевой структуры для сети с большим числом га абонентов необходимо, с одной стороны, обеспечить ее безопасное функционирование при компрометации ключей части абонентов. С другой стороны, нужно минимизировать затраты, связанные со сменой ключей, включающей в себя выработку и доставку новых ключей абонентам.

Лучшим решением первой задачи является ключевая структура типа «полная матрица» К = (ку), когда у каждого абонента имеется полный набор индивидуальных ключей для связи с остальными (га — 1) абонентами. При этом, ключ кц служит для обмена зашифрованной информацией между абонентами г и j.

В этом случае даже при компрометации ключей у (га — 2) абонентов у оставшихся двух абонентов будет секретный, не скомпрометированный ключ для связи между собой. Вместе с тем данный тип ключевой структуры связан с максимальными нагрузками на процедуры генерации и доставки ключей абонентам сети.

Лучшим решением второй задачи является сеть с общим ключом. Однако она полностью становится неработоспособной при компрометации ключа у одного абонента.

Определение 12.2. Ключевая структура в системе из га абонентов называется стойкой к компрометации ключей у гп абонентов, если при компрометации ключей у т абонентов противнику невозможно определить ни один из ключей для связи между остальными (га — гга) абонентами.

В качестве примера такой схемы рассмотрим схему Блома^[1] распределения ключей между п абонентами, построенную на основе симметричного многочлена от двух переменных над конечным нолем F₉. Каждому абоненту поставим в соответствие номер (идентификатор) - ненулевой элемент гу € F₉, j = 1,2,... , п. При этом данные элементы попарно различны и не являются секретными.

Выберем многочлен от двух переменных над нолем F₉ степени 2т, 1 ^ т < п, с симметричной матрицей коэффициентов А - (а*/)

Матрица коэффициентов А является секретной и хранится в центре распределения ключей. Каждый абонент j в качестве исходного ключа получает многочлен

В таком случае для связи между абонентами г и j ими вычисляется ключ

Удобно использовать также векторную форму для вычисления разовых ключей:

Лемма 12.1. Пусть т < пи заданы ключевые многочлены (ц,..., д_т абонентов (без потери общности полагаем, что это абоненты с номерами г, Г2,..., г_т). Тогда существуют ровно |F_f;| = q симметричных матриц А = Ai, I = 1,2,.... q, соответствующих данным ключевым многочленам, для которых выполняется соотношение (123) при всех i,j = 1,2,..., гг.

Доказательство. Пусть t - фиксированное число, принимающее произвольное значение из множества {m + 1, т + 2,... п}. Введем в рассмотрение матрицы К и R размера (rn + 1) х (гп + 1):

для которых будет выполняться матричное равенство

где через R¹ обозначается матрица, транспонированная к матрице R.

Матрица К является симметричной, то есть К — К¹, и в ней при заданных многочленах д,д2, ? ? ? ,д_т фиксированы все элементы, кроме одного кц-

Матрица R является матрицей Вандермонда, см. [1] и, следовательно, обратима. При этом при любой фиксации ки = I € F_(/ в силу обратимости матрицы R, существует единственная матрица А = Ai, являющаяся решением уравнения (12.5):

Матрица А будет симметричной, т.к.

Очевидно также, что разным значениям ки = I G F_(/ будут соответствовать разные матрицы А = Л/. ?

Лемма 12.2. Пусть т < п — 2 и заданы ключевые многочлены gi,..., g_m абонентов (как и в лемме 12.1, полагаем, что это абоненты с номерами ri,V2, ?.. ,r_m). Пусть t,s принадлежат множеству {ш+1, гп + 2,, п}, t Ф s. Тогда для любого фиксированного k_st € F_(/ существует в точности одна симметричная матрица А, которая соответствует данным ключевым многочленам, ключу k_st и для которой выполняется соотношение (12.3) при всех i,j — 1,2.... ,п.

Доказательство. В соответствии с леммой 12.1 существует ровно q симметричных матриц А = Л/, которые соответствуют заданным многочленам g, д2, ? ? ? ,д_т и для которых выполняются соотношения (12.3) при всех i,j = 1,2,...,п. В таком случае для любой такой матрицы будет выполнено матричное равенство

где

а матрица R определена равенством (12.4).

В силу обратимости матриц R и S из (12.6) получаем, что разным матрицам Л/ будут соответствовать разные матрицы К1. А так как в матрице К1 все элементы, кроме /с₅*, однозначно задаются при фиксации многочленов gi,g2> • • • ,.9m> то разным матрицам Л/ в равенстве (12.6) будут соответствовать разные ключи k_st. Следовательно, значением ключа k_st может являться любой элемент поля W_q. И при его фиксации симметричная матрица А определяется однозначно. ?

Таким образом, из лемм 12.1-12.2 непосредственно получаем справедливость следующего утверждения.

Теорема 12.1. Схема Блома распределения ключей между п абонентами на основе симметричного многочлена от двух переменных степени 2га, 1 ^ га < п, является стойкой к компрометации ключей га абонентов.

Вместе с тем следует понимать, что при компрометации га абонентов ключи связи k_st между остальными абонентами сильно кор- релированы между собой, так что знание одного из них приводит к раскрытию всех.

• [1] ! См. Blom R. Nonpublic key distribution//Advances in Cryptology. -Proceedings of EUROCRYPT-’82. - Plenum. New York. - 1983. - pp. 231-236.