СИСТЕМА РАСПРЕДЕЛЕНИЯ КЛЮЧЕЙ И СПОСОБ ЕЕ ФУНКЦИОНИРОВАНИЯ Российский патент 2008 года по МПК H04L9/08 

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

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

В симметричном криптографическом преобразовании один и тот же ключ используется для шифрования и дешифрования данных. При этом криптографические ключи распределяются исполнительной схемой процессора таким образом, что каждая пара узлов сети имеет общий секретный ключ [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

010011111110000000111011111100010000110010011000111101110000000101001000101111111110001001001101010101100001001111101010

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

Существует много способов разбиения столбцов половинного веса на две матрицы: в точности !! способов, что, например, для 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 узлов при n₀=3N3612244896768307249152786432V371321293973101171259Таблица 2
Объем пула V для сети из N узлов при n₀=4N481632641285121024327681048578V612182634446882162272

Пример 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 c_i←i j←2 while j≠1 do output (c₁, c₂,...,c_m/2) j←m/2 while c_j=m/2+j do j←j-1 c_j←c_j+1 for i=j+1 to m/2 do c_i←c_i-1+1 

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

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

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

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

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

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

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

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

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

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

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

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

Предложенная СПРК является 1-устойчивой, но не 2-устойчивой, поскольку всегда найдется пара узлов, чей общий ключ может быть вычислен другой парой узлов. Для компрометации СПРК, то есть для восстановления всего ключевого пула, необходимо собрать коалицию, как минимум, из 3 узлов. Действительно, предположим, что 2 пользователя, объединившись, могут восстановить весь пул для сети из n₀ узлов. Это означает, что соответствующие им столбцы в матрице инцидентности различны. При удвоении числа узлов в сети эти узлы получат новые ключи в соответствии со столбцами половинного веса. Но у двух столбцов половинного веса не менее одной общей единицы, и следовательно, они имеют не меньше одного общего нуля. Поэтому два рассматриваемых узла не смогут восстановить ключ, соответствующий общему нулю.

Число ключей в пересечении ключевых блоков зависит от выбранной пары узлов. Однако минимальный объем пересечения не меньше, чем , где k₀ - минимальный объем пересечения для сети из n₀ узлов. Как минимум один из ключей, находящихся в пересечении, является уникальным для заданной пары. В более общем виде полученное пересечение не входит как подмножество в ключевой блок любого другого узла сети. Отметим однако, что если трактовать пересечение как некоторое множество, то произвольные подмножества этого множества могут входит в ключевые блоки других узлов. Поскольку в пересечение входит не менее одного ключа уникального для заданной пары, то число двоичных разрядов отдельного ключа определяет достижимый уровень криптостойкости системы в целом.

Сравним новую СПРК с уже известными СПРК на пересекающихся множествах, а именно с системами Гонга и Уилера [3] и системой Даера и соавторов [8].

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

Результаты приводится в таблицах.

Таблица 3
Объем пула V для сети из N узловN→10010³10¹10⁵10⁶Новая3982129195272Даер и соавт.406080100120Гонг и Уилер2002·10³2·10⁴2·10⁵2·10⁶Таблица 4
Объем блока К для сети из N узловN→10010³10⁴10⁵10⁶Новая224064100137Даер и соавт.2740546780Гонг и Уилер20642006342·10³Таблица 5
Сложность построения СПРК (число операций) для сети из N узловN→10010³10⁴10³10⁶Новая3·10²3·10³3·10⁴3·10⁵3·10⁶Даер и соавт.4.3·10⁷6.4·10¹⁰8.6·10¹³10¹⁷1.3·10²⁰Гонг и Уилер2·10³6.3·10⁴2·10⁶6.3·10⁷2·10⁹

Оценки показывают, что требуемый объем памяти в новой системе по порядку величины совпадает с тем же объемом в системе Даера, и при N>1000 гораздо меньше, чем для системы Гонга и Уилера. Если главным критерием выбора является сложность, то новая система лучше системы Даера и соавторов при любых N, и также лучше, чем система Гонга и Уилера. К тому же систему Даера практически нельзя реализовать для N>10⁵.

Из сказанного следует, что новая система по совокупности параметров оказывается наилучшим выбором при числе узлов сети N>1000.

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

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

Систему легко построить. Сложность построения системы минимально возможная и пропорциональна числу узлов в сети.

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

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

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

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

Тем не менее, наиболее полезной разработанная СПРК окажется в сетях со следующими свойствами:

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

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

- создание и масштабирование сети должны быть простыми.

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

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

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

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

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

Список литературы

[1] Патент US 5150411, H04L 9/30, 22.09.92.

[2] US 4876716, H04L 9/02, 24.10.89.

[3] http://webs.cs.berkeley.edu/tos/.

[4] R.Blom. An Optimal Class of Symmetric Key Generation Systems - In: Advances in Cryptology, EUROCRYPT84, LNCS 209, 1985, 335-338.

[5] L. Gong, D. J. Wheeler. A Matrix Key Distribution Scheme. - Journal of Cryptology, vol.2(2), 1990, 51-59.

[6] С. Blundo, A. De Santis, A. Herzberg, S. Kutten, U. Vaccaro and M. Yung. Perfectly Secure Key Distribution for Dynamic Conferences.- In: Advances in Cryptology - CRYPTO'92, LNCS 740, 1993, 471-486.

[7] A.Fiat, M.Naor. Broadcast Encryption. - In: Advances in Cryptology - CRYPTO'93, LNCS 773, 1994, 480-491.

[8] M.Dyer, T.Fenner, A.Frieze, A.Thomason. On Key Storage in Secure Networks. - Journal of Cryptology, vol.8(4), 1995, 189-199.

[9] Т.H.Carmen, С.Е.Leiserson, and R.L.Rivest, Intoduction to Algorithms. New York. NY:MacGrow-Hill, 1990.

[10] E.Reingold, J. Nievergelt, N. Deo. Combinatorial Algorithms. Theory and Practice. - Prentice-Hall: NJ, 1977.

[11] А.П.Алферов, А.Ю.Зубков, А.С.Кузьмин, А.В.Черемушкин. Основы криптографии. M.: "Гелиос Ассоциация Российских вузов", 2002.

Изобретение относится к области защиты информации в компьютерных сетях передачи данных. Технический результат заключается в упрощении способа предварительного распределения ключей. Сущность изобретения заключается в том, что система и способ защиты информации в компьютерных сетях, основанные на распределении ключей, включают множество узлов и доверенный центр (ДЦ), при этом все узлы сети связаны между собой и с ДЦ каналами связи, а каждый узел сети и ДЦ имеют исполнительную схему процессора и память, при этом ДЦ содержит генератор псевдослучайных чисел, выполненный с возможностью генерации долговременных ключей, формирования ключевых блоков, формирования первичной подматрицы инцидентности меньшего размера для построения матрицы инцидентности (МИ) требуемого размера; формирования столбцов половинного веса с требуемым числом двоичных разрядов для построения МИ требуемого размера на основе первичной подматрицы меньшего размера; с возможностью расширения МИ в зависимости от числа узлов сети, участвующих в связи друг с другом; передачи сформированных ключевых блоков узлам сети, вовлеченным в процесс обмена данными по каналам связи, причем каждому узлу соответствует один ключевой блок; узлы сети формируют исполнительными схемами их процессоров общий секретный ключ с целью обеспечения конфиденциальности при передаче информации между узлами сети. 2 н. и 8 з.п. ф-лы, 2 ил., 5 табл.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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