Система распределения ключей и способ ее функционирования

Система распределения ключей и способ ее функционирования

Иллюстрации

Показать все

Реферат

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

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

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

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

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

Однако указанные способы не применимы к современным сетям (ad hoc сети), так как типичная ad hoc сеть, например сенсорная, состоит из большого числа узлов, обладающих умеренными или даже слабыми вычислительными ресурсами процессора и ограниченным объемом памяти. В такой сети применение инфраструктуры открытых ключей неоправданно. Кроме того, топология ad hoc сети, как правило, не известна заранее и может быть установлена только после развертывания сети. В ряде приложений топология может изменяться во времени. Это означает, что управляющая инфраструктура сети не может быть спроектирована заранее. (Здесь под инфраструктурой понимается совокупность компонентов, обеспечивающих маршрутизацию, поддержание работоспособного состояния, а также организационные и административные функции.) Поскольку проблема распределения ключей в ad hoc сетях не может быть эффективно решена традиционным способом, необходим поиск простых решений, принимающих во внимание специфические особенности таких сетей.

Существует способ, более подходящий для решения задачи распределения ключей в ad hoc сетях, - способ предварительного распределения ключей (СПРК) [11]. В СПРК доверенный центр распределяет секретную информацию (ключевой материал) среди совокупности узлов U={1,...,N}. Порция информации u_i передается узлу i по секретному каналу, например во время создания сети. Переданный ключевой материал позволяет устанавливать общий секретный ключ для заранее заданной группы узлов (разрешенная группа). После распределения ключевого материала доверенный центр прекращает свою работу.

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

Существует две простейшие (тривиальные) СПРК.

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

Это решение имеет очевидный недостаток: компрометация хотя бы одного узла (получение доступа к его ключевому материалу) компрометирует всю сеть.

Другая тривиальная система [11] состоит в том, чтобы у каждой пары узлов был свой уникальный ключ. Для сети из N узлов доверенный центр должен сгенерировать и распределить N(N-1)/2˜N²/2 различных ключей - по одному для каждой пары. При этом каждый узел получит N-1 ключей.

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

СПРК, которые могут быть использованы в практических приложениях, расположены между двумя описанными тривиальными схемами: ослабляя требования криптостойкости, зачастую удается снизить требования к объему памяти.

Известно решение Даера и соавторов [8], реализующее способ распределения ключей. В известном способе:

- генерируют доверенным центром долговременные ключи и ключевые блоки из долговременных ключей;

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

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

Данное решение выбрано в качестве прототипа заявленного изобретения.

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

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

Желаемый технический результат получают за счет создания новой системы распределения ключей.

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

- доверенный центр содержит генератор псевдослучайных чисел;

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

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

- доверенный центр выполнен с возможностью формирования посредством исполнительной схемы процессора первичной подматрицы инцидентности меньшего размера с целью построения матрицы инцидентности требуемого размера;

- доверенный центр выполнен с возможностью формирования посредством исполнительной схемы процессора столбцов половинного веса (веса Хэмминга) с требуемым числом двоичных разрядов с целью построения матрицы инцидентности требуемого размера на основе первичной подматрицы меньшего размера;

- доверенный центр выполнен с возможностью формирования посредством исполнительной схемы процессора матрицы инцидентности требуемого размера на основе первичной подматрицы инцидентности и столбцов половинного веса;

- доверенный центр выполнен с возможностью формирования посредством исполнительной схемы процессора матрицы инцидентности, в которой строки соответствуют долговременным ключам, а столбцы - узлам сети по следующему правилу: если j-й узел сети владеет i-м ключом, то на пересечении j-го столбца и i-й строки расположена единица, в противном случае - ноль;

- доверенный центр выполнен с возможностью расширения матрицы инцидентности в зависимости от числа узлов сети, участвующих в связи друг с другом;

- матрица инцидентности имеет число строк, равное общему числу долговременных ключей, при этом каждый долговременный ключ имеет номер, соответствующий номеру строки матрицы требуемого размера;

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

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

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

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

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

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

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

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

- генерируют при помощи генератора псевдослучайных чисел доверенного центра долговременные ключи;

- формируют посредством исполнительной схемы процессора доверенного центра ключевые блоки из долговременных ключей;

- генерируют доверенным центром первичную подматрицу инцидентности меньшего размера, с целью построения матрицы инцидентности требуемого размера, причем размер первичной подматрицы задается произведением числа строк на число столбцов;

- генерируют доверенным центром столбцы половинного веса (веса Хэмминга) с требуемым числом двоичных разрядов с целью построения матрицы инцидентности требуемого размера на основе первичной подматрицы меньшего размера;

- формируют доверенным центром матрицу идентичности требуемого размера на основе первичной подматрицы и столбцов половинного веса;

- формируют исполнительной схемой процессора доверенного центра матрицу инцидентности таким образом, что строки соответствуют долговременным ключам, а столбцы - узлам, по следующему правилу: если j-й узел владеет i-м ключом, то на пересечении j-го столбца и i-й строки расположена единица, в противном случае - ноль;

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

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

- передают посредством исполнительной схемы процессора доверенного центра ключевые блоки узлам сети;

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

- формируют общий секретный ключ в узле отправителе и узле получателе.

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

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

Для реализации способа функционирования системы существенно, чтобы доверенный центр генерировал матрицу идентичности требуемого размера на основе первичной подматрицы и столбцов половинного веса посредством следующих операций:

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

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

- формируют вторую вспомогательную подматрицу путем инвертирования столбцов первой вспомогательной подматрицы;

- увеличивают число строк первичной подматрицы путем добавления строк, входящих в состав первой вспомогательной подматрицы;

- увеличивают число строк подматрицы-дубликата первичной подматрицы путем добавления строк, входящих в состав второй вспомогательной подматрицы;

- формируют матрицу инцидентности требуемого размера путем объединения первичной подматрицы с увеличенным числом строк и подматрицы-дубликата первичной подматрицы с увеличенным числом строк таким образом, что число столбцов в результирующей матрице инцидентности равно удвоенному числу столбцов первичной подматрицы;

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

- передают от узла отправителя к узлу получателю полный список номеров долговременных ключей, входящих в принадлежащий узлу отправителю ключевой блок;

- определяют в узле получателе номера ключей, общих для ключевых блоков узла отправителя и узла получателя путем сравнения полного списка номеров долговременных ключей, полученного от отправителя со списком номеров долговременных ключей, входящих в ключевой блок получателя;

- передают от узла получателя к узлу отправителю номера долговременных ключей, общих для ключевых блоков узла отправителя и узла получателя;

- вычисляют в узле отправителе общий секретный ключ путем применения однонаправленной хэш-функции к набору долговременных ключей - общих для ключевых блоков узла отправителя и узла получателя;

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

Для реализации способа функционирования системы применение однонаправленной хэш-функции должно состоять, предпочтительно, из следующих операций:

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

- вычисления значения однонаправленной хэш-функции от конкатенации долговременных ключей.

Для реализации способа функционирования системы существенным требованием является, чтобы присвоение номера долговременным ключам, входящим в ключевые блоки, осуществлялось следующим образом:

- долговременному ключу присваивают номер строки матрицы инцидентности только в том случае, если на пересечении соответствующих столбца и строки расположена единица, в противном случае - номер не присваивается;

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

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

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

Требования к объему памяти системы близки к оптимальным. Число ключей в пуле и блоке существенно меньше, чем в тривиальных и других известных детерминированных системах.

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

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

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

Для обеспечения более глубокого понимания функционирования системы распределения ключей далее приводится подробное описание ее работы и чертежи.

Фиг.1 - блок-схема системы распределения ключей, выполненной согласно изобретению.

Фиг.2 - последовательность операций для реализации способа согласно изобретению.

Система распределения ключей состоит из узлов 1₁...1_j сети, доверенного центра 2, каналов 3 связи. При этом доверенный центр 2 содержит управляющую схему 4 процессора, память 5 и генератор б псевдослучайных чисел (ГПСЧ), а каждый из узлов 1₁...1_j сети содержит собственную управляющую схему 7 процессора и память 8.

При функционировании системы генератор псевдослучайных чисел 6 генерирует долговременные ключи (шаг 1), из которых посредством исполнительной схемы процессора 6 доверенного центра 2 формируют ключевые блоки (шаг 2), после чего генерируют первичную подматрицу инцидентности меньшего размера (шаг 3), в которой строки соответствуют ключам, а столбцы узлам сети. Генерируют доверенным центром столбцы половинного веса (веса Хэмминга) (шаг 4).

После генерирования первичной подматрицы и столбцов половинного веса производят ряд операций с целью получения из первичной подматрицы инцидентности матрицы инцидентности требуемого размера, то есть производят масштабирование. Для этого формируют подматрицу-дубликат путем дублирования первичной подматрицы меньшего размера (шаг 5) с последующим расширением исходной первичной подматрицы методом добавления столбцов подматрицы-дубликата таким образом, что число строк в результирующей матрице остается таким же, как у исходной первичной подматрицы, а число столбцов удваивается. Формируют первую вспомогательную подматрицу, состоящую из столбцов половинного веса (шаг 6) с требуемым числом двоичных разрядов таких, что любая пара столбцов имеет не менее одного общего разряда, в котором расположена единица, причем число столбцов в первой вспомогательной подматрице равно числу столбцов в первичной подматрице, четное число строк первой вспомогательной подматрицы равно биномиальному коэффициенту - числу различных столбцов половинного веса с заданным числом двоичных разрядов таких, что любая пара столбцов не является комплементарной и имеет не менее одного общего разряда, в котором расположена единица, а комплементарная пара - пара двоичных векторов такая, что один из векторов является двоичной инверсией другого вектора пары, причем число строк первой вспомогательной подматрицы должно быть не меньше удвоенного числа столбцов первичной подматрицы. Формируют вторую вспомогательную подматрицу путем инвертирования столбцов первой вспомогательной подматрицы (шаг 7). Увеличивают число строк первичной подматрицы путем добавления строк, входящих в состав первой вспомогательной подматрицы (шаг 8).

Увеличивают число строк подматрицы-дубликата первичной подматрицы путем добавления строк, входящих в состав второй вспомогательной подматрицы (шаг 9). Формируют матрицу инцидентности требуемого размера путем объединения первичной подматрицы с увеличенным числом строк и подматрицы-дубликата первичной подматрицы с увеличенным числом строк (шаг 10) таким образом, что число столбцов в результирующей матрице инцидентности равно удвоенному числу столбцов первичной подматрицы. В полученной матрице инцидентности требуемого размера строки соответствуют долговременным ключам, а столбцы - узлам, по следующему правилу: если j-ыи узел владеет i-м ключом, то на пересечении j-го столбца и i-й строки расположена единица, в противном случае - ноль, кроме того, каждый ключевой блок ассоциирован со столбцом матрицы инцидентности.

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

После того как список номеров долговременных ключей передают узлам сети, в узле отправителе и узле получателе, которые участвуют в обмене данными между собой, формируют общий секретный ключ следующим образом. Передают от узла отправителя к узлу получателю полный список номеров долговременных ключей, входящих в принадлежащий узлу отправителю ключевой блок (шаг 14); Определяют в узле получателе номера ключей, общих для ключевых блоков узла отправителя и узла получателя (шаг 15) путем сравнения полного списка номеров долговременных ключей, полученного от отправителя со списком номеров долговременных ключей, входящих в ключевой блок получателя. Передают от узла получателя к узлу отправителю номера долговременных ключей, общих для ключевых блоков узла отправителя и узла получателя (шаг 16). Вычисляют в узле отправителе и узле получателе общий секретный ключ путем применения однонаправленной хэш-функции к набору долговременных ключей - общих для ключевых блоков узла отправителя и узла получателя (шаг 17).

Далее рассмотрим построение и функционирование заявленной системы на конкретных примерах.

Пусть сеть состоит из n узлов, a k - общее число ключей в сети. Каждому узлу сети поставим в соответствие индекс j, j=1, ..., n, а ключи пронумеруем с помощью индекса i, i=1, ..., k. Здесь и далее предполагается, что ключи выбираются случайно и независимо. Разрядность ключей фиксирована.

Построим двоичную матрицу А=[a_ij], строки которой соответствуют ключам, а столбцы узлам сети по следующему правилу. Если 7-му узлу принадлежит i-й ключ, то a_ij=1, в противном случае а_ij=0. Матрица A является матрицей инцидентности.

Пример 1. Рассмотрим следующую матрицу инцидентности

Эта матрица описывает СПРК в сети с 5 узлами. Каждый узел располагает четырьмя долговременными ключами. В частности, узлу 1 принадлежат ключи key₁, key₂, key₃ и key₅. Узлу 2 - ключи key₁, key₂, key₃ и key₅, и т.д.

Общими для двух узлов являются ключи с номерами равными номерам строк, где в результирующем столбце расположены единицы. Следовательно, в примере 1 общими ключами для узлов 1 и 2 являются key₁, key₂, и key₃.

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

Ниже приводится способ построения 1-устойчивой СПРК на пересекающихся множествах для сети с произвольным числом узлов.

Для описания нам понадобятся столбцы половинного веса. Столбцом половинного веса называется двоичный вектор, Хэммингов вес которого (число единиц в столбце) равен ровно половине его длины. Естественно, что длина столбца половинного веса есть четное число. Примеры столбцов половинного веса длин 6, 8 и 10 приведены ниже

Существует ровно столбцов половинного веса длины m.

Разделим все столбцы половинного веса заданной длины на две части следующим образом. Если в одну из частей входит некоторый столбец, то во вторую входит комплементарный к нему. Далее, расположим столбцы из обеих частей в виде матриц В и (столбец половинного веса есть некоторый столбец в матрице), причем так, что взаимно комплементарные столбцы в обеих матрицах будут располагаться на одной и той же позиции. Например, существует 20 столбцов половинного веса длины 6

0	1	0	0	1	1	1	1	1	1	1	0	0	0	0	0	0	0	1	1
1	0	1	1	1	1	1	1	0	0	0	1	0	0	0	0	1	1	0	0
1	0	0	1	1	0	0	0	1	1	1	1	0	1	1	1	0	0	0	0
0	0	0	1	0	1	0	0	1	0	0	0	1	0	1	1	1	1	1	1
1	1	1	0	0	0	1	0	0	1	0	0	1	1	0	1	0	1	0	1
0	1	1	0	0	0	0	1	0	0	1	1	1	1	1	0	1	0	1	0

Их можно разделить, в частности, так:

Существует много способов разбиения столбцов половинного веса на две матрицы: в точности !! способов, что, например, для m=6 дает 3715891200≈2³². Для наших целей подойдет любое такое разбиение.

Пусть k×n матрица инцидентности А задает 1-устойчивую СПРК для сети из n узлов. Тогда матрица

есть матрица инцидентности, задающая 1-устойчивую СПРК для сети из 2n узлов. Здесь В и суть m×n комплементарные матрицы, состоящие из столбцов половинного веса длины m такой, что

(При необходимости матрицы усекаются до n столбцов в каждой.) Рассмотрим два примера построения СПРК с различным числом узлов.

Пример 2. Построим матрицу инцидентности для 1-устойчивой системы для 6 узлов. Сначала построим матрицу

- матрицу инцидентности минимального размера 1-устойчивой СПРК для 3 узлов, которая является матрицей меньшего размера для искомой матрицы инцидентности. Построим далее столбцы половинного веса длины 4:

Упорядочим их так:

Получим, согласно способу формирования матрицы инцидентности (2):

- матрица инцидентности для 1-устойчивой системы для 6 узлов.

Пример 3. Построим матрицу инцидентности 1-устойчивой СПРК для 8 узлов.

Матрица

- матрица инцидентности минимального размера 1-устойчивой СПРК для 4 узлов. Поскольку , но , построим столбцы половинного веса длины 6 и согласно способу формирования матрицы инцидентности (2) получим:

- матрицу инцидентности 1-устойчивой СПРК для 8 узлов.

В любой СПРК различают два типа ключевого материала. Первый тип - это совокупный ключевой материал, которым располагает доверенный центр. Назовем этот материал ключевым пулом. Ключевой материал, который доверенный центр передает каждому узлу сети, будем называть ключевым блоком.

Определим минимальное число ключей в системе и ключевом блоке. Для того чтобы минимизировать пул и блок, необходимо выбирать минимально допустимую величину m, удовлетворяющую условию (3).

Оценим m=m(N) как функцию от N, где N=2n - число узлов в сети, для которой строится СПРК. Известно [9], что

что при больших m дает

Упрощая, получим

где lgx=log₂x.

В качестве первого приближения возьмем

Обозначив , для второго приближения получим

Вычислим теперь размер ключевого пула V для сети из N узлов. Начнем построение с сети из n₀ узлов, для которой имеется СПРК с матрицей инцидентности А размера V₀×n₀. На первом шаге будет получена СПРК для сети с числом узлов и ключевым пулом из V₀+m(2n₀) ключей. Далее получим сеть из узлов и пулом из V₀+m(2n₀)+m(4n₀) ключей. И так далее. Сеть из N узлов будет иметь пул из

V=V₀+m(2n₀)+m(4n₀)+m(8n₀]+...+m(N)

ключей. Из конструкции следует, что на некотором шаге i число узлов сети N(i)=n₀·2ⁱ.

Сумма в этой формуле имеет вид

Подставив m(N) из выражения (7), вычислим по отдельности каждый член суммы.

Складывая все, имеем

предполагая, что n₀<<N и ограничиваясь лишь асимптотикой по N, получим

Таким образом, число ключей в пуле растет чуть быстрее половины квадрата логарифма от числа узлов в сети.

Таблица 1Объем пула V для сети из N узлов при n0=3
N	3	6	12	24	48	96	768	3072	49152	786432
V	3	7	13	21	29	39	73	101	171	259
Таблица 2Объем пула V для сети из N узлов при n0=4
N	4	8	16	32	64	128	512	1024	32768	1048578
V	6	12	18	26	34	44	68	82	162	272

Пример 4. Продолжая предыдущие примеры, определим точный объем ключевого пула V в 1-устойчивой СПРК для сети из N узлов, начиная построения с сети из n₀=3 (матрица (4)) и n₀=4 узлов (матрица (5)). Результаты приведены в таблицах.

В соответствии с конструкцией объем ключевого блока равен в точности K(N)=K_o+V(N)/2 ключам, где К₀ - число ключей в блоке для сети из n₀ узлов. При К₀=V₀/2, как, например, при n₀=4 выше, ключевой блок в два раза меньше общего числа ключей в системе.

Сложность построения представленной СПРК определяется сложностью построения матрицы инцидентности С в уравнение (2), и следовательно, сложностью построения столбцов половинного веса. (Мы предполагаем, что первоначальная матрица инцидентности А для начальной СПРК уже известна. В противном случае мы заранее можем зафиксировать некоторый набор матриц А для наперед заданного числа узлов n₀=3,...4,.)

В литературе описано несколько алгоритмов построения столбцов половинного веса заданной длины, см., например, [10].

Ниже мы приводим модификацию одного из алгоритмов построения выборок типа "k из m" произвольного веса k, приспособленную специально под наши условия: k=m/2.

Обозначим через с_i, i=1, ..., m/2 позиции в столбце длины m, на которых расположены единицы. Алгоритм 4.4.1 порождает столбцы половинного веса.

Алгоритм 4.4.1. Построение столбцов половинного веса
for i=1 to m/2 do
ci←i
j←2
while j≠1 do
output (c1, c2,...,cm/2)
j←m/2
while cj=m/2+j do
j←j-1
cj←cj+1
for i=j+1 to m/2 do
ci←ci-1+1

Пример 5. Следующая последовательность столбцов половинного веса длины 6 появится на выходе алгоритма 4.4.1.

Нетрудно видеть, что алгоритм 4.4.1 порождает ровно половину от общего числа векторов половинного веса длины m. Более того, у всех порожденных столбцов в первой позиции расположена 1. Поэтому среди порожденных столбцов нет комплементарных, и все эти столбцы могут быть непосредственно использованы в матрице В (2). Для создания оставшихся столбцов достаточно вычислить матрицу , комплементарную к В.

Сложность алгоритма 4.4.1 (вычисление матрицы В) составляет операции над двоичными векторами длины m. Вычисление комплементарной матрицы требует гораздо меньшего числа операций и этой сложностью можно пренебречь. Поскольку СПРК создается для сети из N узлов на основе СПРК для n₀ узлов, общая сложность вычисления матрицы С составляет

Эта сложность пропорциональна числу узлов в сети и является асимптотически минимально возможной для СПРК на пересекающихся множествах.

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