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

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

 

ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ

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

ПРЕДШЕСТВУЮЩИЙ УРОВЕНЬ ТЕХНИКИ

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

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

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

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

Криптографические ключи распределяют и устанавливают между объектами-участниками вовлеченными посредством различных способов, основанных на криптографии с открытым ключом, центре распределения ключей или других симметричных методиках. В частности, в течение прошлых лет было выполнено исследование конструкций схем распределения ключей в сетях датчиков. Были предложены схемы случайного предварительного распределения ключей, схемы распределения ключей на основе доверительного центра или применение криптографии с открытым ключом. Во многих из этих схем можно найти компромисс между безопасностью и эффективностью. Например, в схемах со случайным предварительным распределением ключей каждому узлу в WSN распределяют некоторое количество ключей W, случайным образом выбранных из пула ключей M. Таким образом, для двух узлов существует вероятность p совместного использования общего ключа, которая зависит от W и M и от возможности установления безопасной линии связи. Однако эти схемы могут быть взломаны с помощью захвата узлов и сохраненных ключей. Кроме того, для этого требуется хранение относительно большого количества ключей, например, между 50 и 200, что эквивалентно 500 или 2000 байтам для 100-битовых ключей. В основанных на открытом ключе схемах согласования ключей требуется хранение одного ключа, но алгоритмы генерации ключа весьма сложны. Кроме того, данная система является все еще медленной с вычислительной точки зрения, так как несколько секунд требуются для квитирования согласования ключа. Некоторыми обычными схемами распределения ключей являются схемы распределения части ключевого материала, которые называют «альфа-безопасностью», в которых узел, принадлежащий сети, непосредственно обеспечивают не готовым криптографическим ключом, а некоторым специфичным для узла ключевым материалом, который предоставляет ему возможность вычислять ключ, который совместно используют с другим узлом сети для обеспечения безопасности связи. Эта специфичная для узла информация является частью ключевого материала, полученным из корневого ключевого материала, содержащегося в устройстве администрирования сети. Эти схемы обеспечения «альфа-безопасности» предлагают компромисс между эффективностью, доступностью и безопасностью. Основной недостаток этих систем относится к тому факту, что корневой ключевой материал является таким, что захват альфа-узлов, и таким образом - объединения частей ключевого материала «альфа» компрометирует весь корневой ключевой материал.

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

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

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

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

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

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

Для этой цели настоящее изобретение осуществляет способ обеспечения безопасности связи между первым узлом и вторым узлом в сети, которая дополнительно содержит устройство администрирования, обеспеченное механизмом генерации симметричного ключа (SKGE). Механизм генерации симметричного ключа SKGE(.) является криптографическим блоком, который предоставляет возможность первому объекту-участнику, Алисе, генерировать парный с любым другим объектом-участником в сети, например, с Бобом, ключ, который имеет три желаемых рабочих свойства. Прежде всего, он в вычислительном отношении намного более эффективен, чем ассиметричное квитирование для согласования ключа. Во-вторых, механизм генерации ключа можно хранить очень эффективно, т.е. ему требуется память, равная нескольким байтам, по сравнению с N-1 ключами тривиальной схемы распределения симметричных ключей. В-третьих, данный механизм трудно взломать.

Для общности SKGE объекта R_A, например узла, определяют как структуру, которая предоставляет возможность объекту R_A быстро и эффективно генерировать симметричные ключи с любым другим объектом R_Z в системе при заданном идентификаторе другого объекта. SKGE объекта R_A основан на одном и том же секретном ключевом материале KM_A. Эта секретная информация является объединением некоторого количества n наборов ключевого материала KM_A-j, сгенерированных из n независимых частей KM'_A-j ключевого материала. Части KM'_i-j ключевого материала для различных объектов R_i генерируют из некоторого корневого ключевого материала KM^root _j.

Корневой ключевой материал KM_A-j и части KM'_i-j ключевого материала являются, например основанными на хорошо известных математических функциях, используемых в криптографии. Эти математические функции могут включать в себя полиномы, матрицы, комбинаторные структуры и т.п. Математические операции можно выполнять над конечным полем или другой математической структурой, такой как алгебраические структуры, включающие в себя группы, поля, кольца, векторные пространства и т.д.

Работа SKGE содержит следующие этапы, на которых:

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

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

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

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

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

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

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

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

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

В еще одном варианте осуществления изобретения корневым ключевым материалом является полином степени 1 с коэффициентами в конечном поле GF(q)_n, где q_n - простое число, равное 2ⁿ-1, где n - целое число.

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

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

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

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

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

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

- средство для передачи своего идентификатора на устройство администрирования,

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

- средство для приема идентификатора другого узла, и

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

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

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

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

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

Фиг. 3 показывает обычный процесс генерации ключа в основном механизме генерации симметричного ключа.

Фиг. 4a показывает процесс генерации ключа согласно изобретению.

Фиг. 4b показывает другой процесс генерации ключа согласно изобретению.

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

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

ПОДРОБНОЕ ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

Эта сеть содержит устройство 2 администрирования, обеспечиваемое корневым ключевым материалом во время фазы конфигурирования CONFIG. В примерном варианте осуществления корневым ключевым материалом является симметричный двумерный полином F(x, y) степени 1 с коэффициентами в конечном поле GF(q). Полином можно записать следующим образом: F(x, y) =a₀₀+a₀₁x+a₁₀y+a₁₁xy, где a₀₁=a₁₀.

В одном из вариантов осуществления характеристика поля GF(q) является простым числом Мерсенна q_n=2ⁿ-1, где n - целое число, например, n=17, 127 или 521.

Во время этой фазы конфигурирования CONFIG каждый узел (N1, N2) сети, соответственно, обеспечивают идентификатором (ID1, ID2). Эти идентификаторы имеют длину r битов, где r - целое число, которое меньше n. В примере r равно целочисленной части n/3. Эта фаза конфигурирования в общем случае происходит во время фазы, предшествующей вводу в действие сети, т.е. прежде, чем узлы фактически присоединят к сети.

Как только узлы ввели в действие, устройство администрирования генерирует, во время фазы GENER, законченную часть ключевого материала для узла N1, основываясь на корневом ключевом материале F(x, y) и на идентификаторе ID1. Законченная часть ключевого материала для узла N1 равна f_ID1(y)=b_{ID1_1}*y+b_{ID1_0}, где коэффициенты этого полинома вычисляют следующим образом: b_{ID1_1}=a₁₀+a₁₁*ID1(mod q) и b_{ID1_0}=a₀₀+a₀₁*ID1(mod q). Эти операции выполняют по модулю q, как все другие операции, выполняемые в этом способе, потому что система работает над конечным полем GF(q).

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

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

- корневым ключевым материалом, обеспечиваемым в устройстве администрирования, является F(x, y)=a₀₀+a₀₁x+a₁₀y+a₁₁xy, который можно разложить на множители в форме F (x, y)=(a₀₀+a₀₁x)+(a₁₀+a₁₁x)y,

- коэффициенты F(x, y) выражают в форме трех конкатенированных сегментов,

- сеть содержит два узла, идентификаторами которых являются R и V.

Первым этапом является генерация части ключевого материала для узла R посредством оценки F(x, y) при x = R, затем генерируя F_R(y) = b_{R_0} + b_{R_1}*y.

Эта оценка показана в верхней части фиг. 3 с:

- в левой верхней части - вычислением b_{R_0}=(a₀₁R+a₀₀) (mod q), и

- в правой верхней части - вычислением b_{R_1}=(a₁₁R+a₁₀)mod(q).

Затем, в обычной системе законченную часть ключевого материала, сгенерированную с помощью устройства администрирования, передают на узел R, т.е. шесть сегментов: b_{R_0-1}, b_{R_0-2}, b_{R_0-3}, b_{R_1-1}, b_{R_1-2}, b_{R_1-3}.

Когда связь необходимо установить между узлом R и узлом V, идентификатор V обеспечивают на узел R так, чтобы он мог сгенерировать законченный ключ для обеспечения безопасности связи. Этот ключ является парным ключом, который согласовали между собой оба узла. Его вычисляют с помощью оценки части ключевого материала узла F_R(y) при y=V. Это вычисление показано в нижней части фиг.3. Вычисление b_{R_1}*V+b_{R_0} обеспечивает ключ K, состоящий из трех конкатенированных сегментов K1, K2 и K3.

Элементы W1 и z1 соответствуют переносам, которые зависят от размера конечного поля.

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

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

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

Эти сегменты, которые также называют подэлементами, выбирают таким образом, чтобы предоставить возможность генерации части законченного ключа. Таким образом, в примерном варианте осуществления устройство администрирования распределяет узлу N1 только следующие коэффициенты: b_{ID1_0-3}, b_{ID1_1-1} и b_{ID1_1-3}, показанные в выделенных полужирной линией квадратах на фиг. 4. Эти элементы, которые формируют частичную часть ключевого материала, затем распределяют узлу N1.

Затем, когда связь необходимо установить между узлами N1 и N2, идентификатор ID2 передают к N1 и выполняют процесс генерации ключа (KEY GEN). Как можно заметить на фиг. 4, если узел N1 обеспечивают только b_{ID1_0-3}, b_{ID1_1-1} и b_{ID1_1-3}, то он не может вычислять все элементы ключа K1, K2 и K3, но может генерировать самые старшие биты ключа K3. Читатель, может понять это, анализируя соотношение между различными частями коэффициентов и выполненные модульные операции. Частичный ключ K3 затем используют для шифрования связей между узлом N1 и узлом N2.

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

Подэлементы, выбранные для коэффициентов второго полинома, соответствуют подэлементам, выбранным для формирования частичной части ключевого материала первого узла. В этом контексте термин «соответствующие элементы» означает подэлементы, которые находятся в одной и той же позиции, т.е. b_{ID2_0-3}, b_{ID2_1-1} и b_{ID2_1-3}, которые представляют третий элемент первого коэффициента, и первый и третий элементы второго коэффициента.

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

Следует отметить, что в настоящем варианте осуществления используют только самые старшие биты результирующего ключа, т.е. два объекта-участника, которые используют настоящий вариант осуществления простого механизма генерации симметричного ключа, могут согласовывать только самые старшие биты K3. Это происходит потому, что операции выполняют «вне исходного поля» GF(q), и часть информации теряется. В частности, ни один из объектов-участников не хранит информацию, которая включает в себя влияние переносов в фазе генерации ключа. Однако это влияние минимально, поскольку вероятность распространения переноса уменьшается с количеством битов. В частности, можно доказать, что два узла могут согласовать общий ключ с вероятностью 1 - 2 ^-b после удаления b самых младших битов результирующих ключей.

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

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

Размер конечного поля	q=2127-1	q=2521-1	q=2127-1
Количество сегментов	1	1	3
Размер {ID, bR-1-3, bR-0-3}	[127/3]=42 бита	[127/3]=173 бита	[127/3]=42 бита
Размер bR-1-0	43 бит	175 бит	43 бит
Требования к памяти	127 бит	521 бит	381 бит
(Объединенный) размер ключа K'3	Около 40 бит	Около 160 бит	Около 120 бит
Вычислительные потребности	Умножение 42×42 бита Умножение 42×43 бита Сложение 42+42 бита	Умножение 173×173 бита Умножение 175×173 бита Сложение 173+173 бита	3 умножения 42×42 бита 3 умножения 42×43 бита 3 сложения 42+42 бита

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

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

Чтобы показать обеспечение безопасности SKGE, сначала сравнивают эту концепцию с хорошо известной концепцией блочного шифра. Блочный шифр - это схема шифрования, работающая с блоками открытого текста фиксированной длины. Блочный шифр состоит из двух преобразований: преобразование шифрования c=E_K (m) и преобразование дешифрования m'=D_K (c). K - это секретный ключ, используемый в обоих преобразованиях. Объект-участник Алиса может использовать E_K (.) для шифрования сообщения с ключом K и отправки его Бобу. Боб может использовать тот же самый ключ и преобразование дешифрования D_K(.) для дешифрования принятого зашифрованного сообщения и получения исходного сообщения. Если предполагают атаку на открытый текст, т.е. атакующий знает пары незашифрованных и зашифрованных сообщений {m_i, c_i}, то атакующий может попытаться восстановить секретный ключ K. Атака на SKGE в некотором смысле аналогична. Атакующий может захватывать некоторое количество узлов, получая некоторое количество N_c пар {R_i,KM_i}, где KM_i - это ключевой материал, используемый в SKGE объекта R_i. Атакующий стремится восстановить корневой ключевой материал, используемый при генерации механизма генерации симметричного ключа каждого объекта в системе при использовании захваченных N_C пар {R_i,KM_i}. Если сравнивать эту атаку с атакой на блочный шифр, то можно сказать, что корневой ключевой материал SKGE играет ту же самую роль, что и ключ шифрования в блочном шифре. Кроме того, пары {R_i,KM_i} аналогичны парам открытого/цифрованного текста.

Как объяснено выше, это основное SKGE может подвергаться нападению с помощью компрометации некоторого количества N_c пар {R_i, KM_i}. В данном случае описывают только последовательность операций атаки:

- Предварительная информация:

* KM_i содержит три подэлемента {b_ID2,0,3, b_lD2,1,3, b_lD2,1,3}, как изображено на фиг. 3. {b_lD2,1,3, b_lD2,1,3} являются частью коэффициента b₁=a₁₁*ID+a₀₁(mod q) совместного используемого ресурса полинома степени 1, связанного с узлом ID1.

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

- Процесс восстановления a₁₁ с помощью захвата некоторого количества N_c пар {R_i,KM_i}.

* Берут подэлементы {b_lD2,1,3, b_lD2,1,3} двух объектов R_A и R_B. Так как эти подэлементы получают из b_R-1=a₁₁*R+a₀₁(mod q), можно вычислять разность между ними, т.е. {b_RA,1,3, b_RA,1,3}-{b_RB,1,3, b_RB,1,3}, и таким образом получать результат, сильно коррелированный с b_RA-1-b_RB-1=a₁₁*(R_A-R_B) (mod q). Результат {b_RA,1,3, b_RA,1,3}-{b_RB,1,3, b_RB,1,3} имеет длину 2*k бит, в то время как b_RA-1-b_RB-1 имеет длину 3*k бит, причем k=[n/3]. Можно записать:

Затем, вычисляя обратное значение (R_A-R_B) над GF(q), можно непосредственно получать:

k бит (из n ≈ 3*k) a₁₁ можно получить таким образом.

Для оставшихся 2*k битов атакующий может сделать следующее: он ищет пары объектов (R_A, R_B) таким образом, чтобы разность между R_A и R_B стремилась к 1. Это можно выполнять за некоторое количество этапов. В конце концов, атакующий может сгенерировать или найти пару (R_A-R_B)=1 так, чтобы соответствующие значения, связанные с этими двумя идентификаторами, были равны a₁₁

Ожидаемое количество пар N_c, которое требуется для этого, должно быть равно приблизительно 2*k.

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

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

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

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

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

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

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

SKGE, ОСНОВАННОЕ НА ПОЛИНОМАХ БОЛЬШОЙ СТЕПЕНИ

В основном варианте осуществления в качестве корневого ключевого материала используют двумерный полином степени α=1, т.е. f(x,y)= $${\displaystyle {\sum }_{ij}^1{\alpha }_{ij}}{x}^i{y}^j(\mathrm{mod}q)$$ . В данном варианте осуществления q - простое число в форме 2ⁿ - 1, и системные идентификаторы выбирают так, чтобы они имели длину $$\left[\frac{n}{3}\right]$$ бит. Как объясняется ранее, такая конфигурация предоставляет возможность ограничивать влияние сверточной модульной операции на некоторое количество бит. Следуя этим рассуждениям, необходимо уменьшать соотношение между размером поля в битах и размером идентификатора, равным k битам. В частности, можно сделать это соотношение равным 3*α, где α является степенью полинома. Если принимают α=3, и существует полином f(x,y)= $${\displaystyle {\sum }_{ij}^{\alpha =3}{\alpha }_{ij}}{x}^i{y}^j(\mathrm{mod}q)$$ и его оценивают при x=R, R имеет длину $$\frac{[\log q]}{2*\alpha +1}$$ бит, то получают часть полинома g(y)= $${\displaystyle {\sum }_i^{\alpha =3}{b}_j}{y}^j(\mathrm{mod}q)$$ . Каждый коэффициент b_j вычисляют, как b_j= $${\displaystyle {\sum }_{i=0}^{\alpha =3}{\alpha }_{ij}}{R}^i(\mathrm{mod}q)$$ . Такая конструкция может предоставлять возможность создания SGKE с выходным ключом приблизительно [log q/соотношение] битов. Соотношение, без потери общности, равно 2*α+1. Для α=1 соотношение равно 3 (основной вариант осуществления).

В частности подэлементы, которые соответствуют SKGE, можно обозначать как: c₀=b₀(mod2^k); c₁₀=b₁(mod2^k); c₁₁=b₁>>(n-k); c₂₀=b₂(mod2^k); c₂₁=b₂>>(n-2k); c₃₀=b₃(mod2^k) и c₃₁=b₃>>(n-3k). SKGE для узла N1 можно использовать для генерации ключа с помощью N2 как

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

В общем случае операцию для SKGE узла N1, который использует в качестве корневого ключевого материала двумерный полином степени α над конечным полем CF(2ⁿ - 1) для генерации ключа с помощью узла N2, можно записать как:

В данном случае, k = $$\frac{n}{2*\alpha +1}$$ без потери общности. Значения [C₀, C₁₀..., C_i0,... C_α0, C₁₁..., C_j1,...C_α1) содержат подэлементы SKGE объекта N1 и зависят от коэффициентов исходной части полинома, как:

Это уравнение представляет более общее определение основного варианта осуществления SKGE, описанного в начале этого документа, в котором используют единственный двумерный полином с α=1.

Каждый из этих подэлементов SKGE объекта N1 зависит от α+1 коэффициентов исходного корневого двумерного полинома. На фиг. 5 изображают 4 коэффициента исходного корневого ключевого материала {A₃₃, A₂₃, A₁₃, A₀₃}, которые участвуют в генерации коэффициента b₃ части полинома для узла N1. Также указывают два подэлемента {C₃₀, C₃₁} SKGE, которые генерируют из b₃. Коэффициенты делят на k-битные блоки. Блоки, отмеченные X, являются блоками, которые участвуют в генерации элементов SKGE. Эти сгенерированные элементы SKGE отмечены XX.

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

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

Предполагая, что сгенерированный ключ является блоком k-бит длиной, коэффициенты двумерного полинома степени α имеют длину 2*α+1 k-битных блоков. В данном случае используют то же самое соотношение, которое определено выше. Для двумерного полинома степени 1 существует четыре коэффициента {α₀₀, α₀₁; α₀₁, α₁₁}. Каждый из них делят на три блока длиной k-битов. Это разделение удобно для анализа, какие части корневого ключевого материала имеют влияние на биты элементов SKGE {C₀, C_i0}. Это можно понять, например, анализируя фиг.4b. Из него можно получить некоторые заключения:

- Во-первых, для полинома степени α, элементы SKGE {C₀, C_i0} с 1≤i≤α имеют длину только один блок, но имеют влияние на α+1 и $$\frac{{\alpha }^2+3\alpha +2}{2}$$ блоки. Элементы {C_i1} SKGE, при 1≤i≤α, сложности α, имеют длину i блоков и зависят от $$\frac{(\alpha +1)(2i+\alpha )}{2}$$ блоков. Знание этого может быть полезным, если систему хотят атаковать, так как атакующий может начать анализ этих элементов SKGE, которые зависят от меньшего количества блоков корневого ключевого материала.

- Во-вторых, в генерации элементов SKGE участвуют все биты коэффициента только самой высокой степени. Это эквивалентно тому, чтобы сказать, что «реальная» модульная операция используется только для этого коэффициента.

SKGE, ОСНОВАННОЕ НА ОБЪЕДИНЕНИИ ПОЛИНОМОВ НАД ДВУМЯ РАЗЛИЧНЫМИ КОНЕЧНЫМИ ПОЛЯМИ

Более сложное и безопасное SKGE можно создавать, беря два двумерных полинома f_k(x, y)= $${\displaystyle {\sum }_{ij}^1{\alpha }_{kij}}{x}^i{y}^j(\mathrm{mod}q)$$ степени 1 над двумя различными полями GF(q₁) и GF(q₂). В частности, q₁ можно взять как простое число Мерсенна в форме 2ⁿ-1, а q₂ - другое простое число в форме 2ⁿ-2^[n/3]-β. В данном случае β - наименьшее положительное целое число, для которого 2ⁿ-2^[n/3]-β - простое число. Эти определенные значения выбирают таким образом, что:

(i) части полинома, сгенерированные из этих двух полиномов, имеют влияние на различные поля, но

(ii) поля все еще достаточно аналогичны для объединения некоторых подэлементов этих частей полинома, и

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

Основная концепция этого конкретного варианта осуществления показана на фиг. 4 и фиг. 4c. В данном случае можно заметить результат умножения двух элементов α_A и α_B n битов длиной на идентификатор R [n/3] бит длиной.

Длину R выбирают таким образом, что немодульное умножение R*α_A и R*α_B имеет длину 4*[n/3] бит. Из-за специальной формы выбранных полей, [n/3] самых старших битов этих 4*[n/3] бит длиной результатов влияют на [n/3] самых младших битов обоих результатов и на [n/3] самых старших битов после применения модульной операции в случае второго поля GF(q_B). Левая часть фиг. 4 представляет, таким образом, умножение над конечным полем GF(2ⁿ-1). Это умножение может быть любым умножением, изображенным на фиг. 3, которое участвует в, например, генерации частей ключевого материала для этих объектов.

Учитывая это, система, которая использует этот подход, работает следующим образом. Объект конфигурирования использует два указанных выше двумерных полинома для генерации в общей сложности четырех частей полинома для двух объектов N1 и N2. Это выполняют обычным образом, т.е. оценивая оба двумерных полинома с переменной x для идентификаторов обоих объектов. Четыре части полинома:

Где i и j в g_Ni|j(y) указывают, соответственно, принадлежит ли часть полинома к N1 или к N2, и выполняют ли вычисления над GF(q₁) или над GF(q₂ ). Каждый из коэффициентов этих частей полинома делят на различные подэлементы, как сделано в случае основного варианта осуществления. Например, b_N1|1-Q можно рассматривать, как конкатенацию трех элементов, т.е.

где || представляет конкатенацию. Таким же образом

Объект конфигурирования учитывает специальную форму полей, участвующих в вычислении элементов, которые будет содержать SKGE обоих объектов, как объединение подэлементов частей полинома. В частности, если три элемента SKGE узла Ni {C_i-0, C_i-10, C_i-11} при i={1, 2}, тогда:

Общая операция SKGE узла Ni, при заданном идентификаторе другого узла Nj, находится следующим образом в данном варианте осуществления:

Следует отметить, что элементы {C_i-0, C_i-10, C_i-11} SKGE получают, как сложение двух подэлементов из различных частей полинома. Если удаляют второй подэлемент при каждом этом суммировании, то возвращаются к основному варианту осуществления SKGE.

Это усовершенствование вводит интересные особенности, которые делают атаку на SKGE трудной. Корневой ключевой материал содержит, в этом конкретном случае, полиномы над полями различного порядка. Если атакующий хочет выполнить ту же атаку, что и в основном варианте осуществления, то он обнаружит основное препятствие. Действительно, теперь он не сможет вычислить обратное значение идентификатора, так как это - элемент двух различных полей. Дополнительно, в предыдущей атаке на основное SKGE было указано, что безопасность системы основывается на коэффициент α₁₁. Подробный анализ показывает, что в этом определенном и примерном варианте осуществления атакующий должен найти 4*[n/3] битов вместо n битов, делая анализ системы труднее. В этом смысле способ измерения надежности SKGE относится к соотношению между количеством битов корневого ключевого материала, участвующего в генерации подэлементов, содержащих SKGE, и длиной этих подэлементов SKGE в битах.

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

Другое усовершенствование, в котором используют некоторые корневые ключевые материалы над различными алгебраическими структурами, такими как поля, относится к объединению простого и расширенного конечных полей, например, двух полей, одно использует простое число для модульных операций, а другое порядка p^r, причем p простое число, использует полином для упрощений. Причина состоит в том, что операции «несовместимы» из-за конструкции этих полей.

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

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

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

кроме последнего, из которого извлекают три элемента. Также предполагают, что SKGE содержит три различных элемента {C_i-0,4, C_i-10,4, C_i-11,4}, как в основном варианте осуществления SKGE, и что ключ генерируют как

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

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

ЗАКОНЧЕННАЯ КОНСТРУКЦИЯ SKGE

Эта конструкция SKGE основывается на двух предыдущих конструкциях. Эта конструкция мотивирована тем фактом, что в SKGE, основанном на одном двумерном полиноме степени α, только все биты коэффициента α_α,α участвуют в вычислении частей/ключей полинома. Причина для этого состоит в том, что указанные выше схемы разработаны с соотношением между размером поля и размером ключа, равным $$\frac{n}{2\alpha +1}$$ . Хотя коэффициент α_α,α включает в себя влияние модульной операции, влияние остальной части коэффициента меньше. Фактически, их влияние можно сравнивать с влиянием немодульной операции. Дополнительно, используется только один корневой ключевой материал. Таким образом, система все еще весьма линейна.

Для решения этой проблемы описывают законченную конструкцию SKGE, включающую в себя α+1 двумерных полиномов в качестве корневого ключевого материала степеней 1, 2..., α и α, соответственно. В этом определенном варианте осуществления эти двумерные полиномы находятся над следующими полями:

причем 2ⁿ - 1 простое число больше, чем 2^(2α+1)k.

В данном случае предполагают, что SKGE генерирует ключ длиной k бит. Форма простого числа q_i=2^(2i+1)k-2^(i+1)k-β_i 2^(i+1)k-1-1 для полинома степени i полагается на следующие факты. Элемент 2^(2i+1)k появляется из желаемого количества k-битных «блоков» для коэффициентов корневого ключевого материала. 2^(i+1)k необходим, чтобы иметь модульную операцию, влияющую на i самых старших k-битных блоков, или другими словами, на j*k самых старших битов. 1 выбирают, чтобы иметь возможность объединять операции, т.е. генерировать ключ при использовании только части частей полинома. Наконец, элемент β_i 2^(i+1)k-1  используется для получения простого числа. Значение «бета» - наименьшее положительное целое число, для которого число β_i 2^(i+1)k-1  является простым числом.

Идея состоит в том, чтобы разработать систему, в которой модульные операции f₁(x, y) влияют на коэффициенты степени 1 f₂(x, y) и т.д.; то же самое для f₂(x, y) и f₃(x, y). В общем случае, вклад f_i(x, y) влияет на все полиномы с более высоким идентификатором {i + 1, i + 2,..., α + 1}.

Эти конструкции объединяют преимущества обоих указанных выше SKGE и также обеспечивают новые. Во-первых, эта система разработана таким образом, что все биты коэффициента самой высокой степени всех полиномов участвуют в генерации ключей. Это особенно важно, так как эти коэффициенты являются коэффициентами, которые участвуют в модульных операциях. Во-вторых, используют поля различного размера, который измеряют в битах, что таким образом делает инвертирование любого элемента намного труднее. В частности, так как один и тот же идентификатор используют при генерации этих четырех полиномов, а эти полиномы над различными полями, то очень трудно вычислять обратный элемент идентификатора для восстановления части или всех коэффициентов корневых ключевых материалов. Этот факт также делает намного сложнее атаку на основе интерполяции, так как теперь атакующий стремится аппроксимировать поведение SKGE посредством полинома. Однако такой полином должен включать в себя влияние информации, созданной в различных полях и под влиянием неизвестных битов. Это делает ожидаемую степень полинома интерполяции очень высокой, и, таким образом, система очень эластична. В-третьих, порядок полей выбирают таким образом, чтобы подэлементы, сгенерированные из частей ключевого материала (частей полинома) из различных корневых ключевых материалов (т.е. двумерных полиномов f₁(x, y), f₂(x, y), f₃(x, y) или f₄(x, y)), нарушали друг друга, делая восстановление истинного корневого ключевого материала сложнее. Это нарушение относится к влиянию коэффициента самой высокой степени полинома f_i(x, y) на коэффициенты полиномов с более высоким идентификатором, таким как f_i->1(x, y). Дополнительный факт относится к влиянию модульных операций из-за элемента 2^(i+1)k в простых числах. Эти элементы сильно влияют на элементы SKGE в форме C_i,1, вводя нелинейный эффект, который фактически появляется из-за различных полиномов над различными конечными полями. Взаимоотношения между другими элементами [C₀, C_i0} SKGE и коэффициентами корневого ключевого материала остаются такими же, как были, с тем отличием, что эти элементы также зависят от всех α+1 корневых ключевых материалов. Таким образом, операция, используемая в алгоритме для SKGE, остается неизменной по отношению к операции, которая представлена в разделе «SKGE, основанное на полиномах степени > 1». Это SKGE:

становится теперь:

Где элементы SKGE {C₀, C_i1, C_j1} генерируют, как объединение элементов α+1 частей ключевого материала, следуя указанным выше подходам. Теперь это выражение намного сложнее аппроксимировать, например, посредством методик интерполяции, так как эти элементы повторно вводят нелинейное влияние модульных операций над различными конечными полями.

Реализация системы требует немодульных умножений длинных целых чисел, если сложность системы растет, т.е. если выбрано большое значение α. В данном случае найден компромисс между эффективностью и безопасностью. Чем выше сложность SKGE, тем выше уровень безопасности. Это сопоставимо с работой блочных шифров, в которых безопасность шифра зависит от количества циклов. Этот компромисс является особенно стимулирующим, так как количество умножений растет экспоненциально. Это можно понять с помощью анализа последнего элемента , указанного выше SKGE. Элемент j в указанной выше сумме включает в себя умножение двух элементов j*k бит длиной. Даже при том, что это немодульная операция, она очень затратная для больших значений j. Эффективность вычислений также зависит от второго элемента , но не так сильно. Для i-го индекса существует умножение двух элементов k и i*k бит длиной. На фиг.9 показывают экспоненциальный рост умножений. Следует отметить, что в данном случае обращаются к количеству k-битных умножений.

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

Во-первых, узел N1 может предварительно вычислять степени N2 для обоих элементов

и

Это можно сделать эффективно, вычисляя их рекурсивным способом. Это требует α k-битных умножений. В общем случае:

Во-вторых, при заданных указанных выше предварительно вычисленных степенях N2, вклад второго элемента в указанном выше SKGE можно вычислять, как умножение k самых младших битов i-й степени N2 и элемента SKGE C_i,0. Это сокращает количество необходимых k-битных умножений с α(α+1)/2 до α, т.е. на множитель (α+1)/2.

Третья оптимизация улучшает эффективность третьего элемента

вышеупомянутого SKGE. Чтобы понять это, можно наблюдать умножение двух элементов A и B 4-k бит длиной. В данном случае выбираются операнды 4-k бит длиной без потери общности. A и B содержат 4 подэлемента, каждый длиной k-бит. Это умножение представляет конкретное умножение элемента

когда i=4. Результатом умножения является переменная C длиной 8*k битов. Однако не требуется иметь всю C, а только k битов C. Поэтому вычисление каждого из элементов в сумме можно заменить оптимизированной версией. Это оптимизированное выражение с точки зрения вычисления для показано ниже. Следует отметить, что C_j1 и N^j ₂ содержат j k-битных элементов каждый. Этими элементами являются

и

Это означает, что эта оптимизированная генерация j-го элемента суммы предоставляет возможность сокращать количество k-битных умножений с j² до 2*j-1. Как обычно и как указано выше, эта аппроксимация требует удаления некоторых битов результата, так как эта оптимизация не включает в себя влияние предыдущих элементов, так что она не включает в себя влияние переноса, происходящих из суммирований. Однако это является незначительным фактом, если k является достаточно большим, и особенно если сравнивают эффективность системы с и без указанных выше трех оптимизаций. Эти оптимизации поэтому предоставляют возможность использования SKGE высокой сложности. В данном случае сложность относится к сложности восстановления начальных корневых двумерных полиномов, так как выбор более высоких значений α вводит большее количество полиномов.

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

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

Основным применением является использование для систем безопасности, воплощаемых в беспроводных сетях датчиков. Такими сетями являются, например:

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

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

- более конкретно, любая беспроводная сеть датчиков, основанная на стандарте IEEE 802.15.4/ZigBee.

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

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

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

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

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

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

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

1. Способ обеспечения безопасности связей между первым узлом (N1) и вторым узлом (N2) в сети (1), дополнительно содержащей устройство (2) администрирования, обеспечиваемое корневыми ключевыми материалами, содержащими симметрический многочлен, имеющий пару переменных, обозначенных х и y, причем способ содержит следующие этапы, на которых:
- устройство администрирования генерирует (GENER), основываясь на корневых ключевых материалах, пару частей ключевого материала, содержащую:
- часть первого ключевого материала для первого узла (N1), причем часть первого ключевого материала содержит набор коэффициентов первого многочлена с одной переменной, полученный посредством оценки симметрического многочлена в x=ID1, ID1 является идентификатором первого узла; и
- часть второго ключевого материала для второго узла (N2), причем часть второго ключевого материала содержит набор коэффициентов второго многочлена с одной переменной, полученный посредством оценки симметрического многочлена в y=ID2, ID2 является идентификатором второго узла,
- коэффициент, разделяемый на некоторое количество сегментов так, что каждая из части первого ключевого материала и части второго ключевого материала содержит соответствующие сегменты, имеющие соответствующие позиции соответственно в первом многочлене с одной переменной и втором многочлене с одной переменной; и
- части первого и второго ключевого материала выполнены с возможностью генерирования законченного ключа для обеспечения безопасности связей между первым узлом (N1) и вторым узлом (N2),
- устройство администрирования выбирает (SELECT) соответствующие сегменты из части первого ключевого материала так, чтобы сформировать часть первого частичного ключевого материала, причем устройство администрирования дополнительно выбирает соответствующие сегменты из части второго ключевого материала так, чтобы сформировать часть второго частичного ключевого материала, посредством чего соответствующие сегменты, выбранные из части первого ключевого материала, и соответствующие сегменты, выбранные из части второго ключевого материала, имеют соответствующие позиции соответственно в первом многочлене с одной переменной и втором многочлене с одной переменной, причем количество выбранных сегментов меньше или равно общему количеству сегментов, имеющихся в частях первого и второго ключевого материала,
- устройство администрирования передает часть первого частичного ключевого материала и часть второго частичного ключевого материала соответственно на первый узел и второй узел так, чтобы позволить первому узлу и второму узлу генерировать первый частичный ключ и второй частичный ключ, основываясь соответственно на идентификаторе второго узла и идентификаторе первого узла, причем первый частичный ключ и второй частичный ключ идентичны и используются для обеспечения безопасности связей между первым и вторым узлом.

2. Способ по п.1, в котором корневой ключевой материал содержит различные симметрические многочлены.

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

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

5. Устройство (2) администрирования, обеспечиваемое корневым ключевым материалом, содержащим симметрический многочлен, имеющий пару переменных, обозначенных х и y, в сети (1), дополнительно содержащей первый узел (N1) и второй узел (N2), причем устройство администрирования содержит:
средство для генерирования (GENER) пары частей ключевого материала, содержащей:
- часть первого ключевого материала для первого узла (N1), причем часть первого ключевого материала содержит набор коэффициентов первого многочлена с одной переменной, полученный посредством оценки симметрического многочлена в x=ID1, ID1 является идентификатором первого узла; и
- часть второго ключевого материала для второго узла (N2), причем часть второго ключевого материала содержит набор коэффициентов второго многочлена с одной переменной, полученный посредством оценки симметрического многочлена в y=ID2, ID2 является идентификатором второго узла,
- коэффициент, разделяемый на некоторое количество сегментов так, что каждая из части первого ключевого материала и части второго ключевого материала содержит соответствующие сегменты, имеющие соответствующие позиции соответственно в первом многочлене с одной переменной и втором многочлене с одной переменной; и
- части первого и второго ключевого материала выполнены для генерирования законченного ключа для обеспечения безопасности связей между первым узлом (N1) и вторым узлом (N2),
средство для выбора (SELECT) соответствующих сегментов из части первого ключевого материала так, чтобы сформировать часть первого частичного ключевого материала, причем устройство администрирования дополнительно выбирает соответствующие сегменты из части второго ключевого материала так, чтобы сформировать часть второго частичного ключевого материала, посредством чего соответствующие сегменты, выбранные из части первого ключевого материала, и соответствующие сегменты, выбранные из части второго ключевого материала, имеют соответствующие позиции соответственно в первом многочлене с одной переменной и втором многочлене с одной переменной, количество выбранных сегментов меньше или равно общему количеству сегментов, имеющихся в частях первого и второго ключевого материала, и
- средство для передачи части первого частичного ключевого материала и части второго частичного ключевого материала соответственно первому узлу и второму узлу так, чтобы позволить первому узлу и второму узлу генерировать первый частичный ключ и второй частичный ключ, основываясь соответственно на идентификаторе второго узла и идентификаторе первого узла, причем первый частичный ключ и второй частичный ключ идентичны и используются для обеспечения безопасности связей между первым и вторым узлом.

6. Сеть (1), содержащая устройство (2) администрирования по п.5 и устройство связи, обеспеченное идентификатором (ID1), и содержащее:
- средство для передачи своего идентификатора устройству администрирования,
- средство для приема от устройства администрирования части частичного ключевого материала,
- средство для приема идентификатора (ID2) другого узла, и
- средство для генерирования (KEYGEN), основываясь на принятой части частичного ключевого материала и принятом идентификаторе другого узла, ключа для связи с другим узлом.