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

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

Иллюстрации

Показать все

Реферат

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

Настоящее изобретение относится к способу обеспечения безопасности связей и к сетям связи, которые имеют устройства связи, использующие средства обеспечения безопасности, такие как система шифрования для обеспечения безопасности связей. Данное изобретение находит применение преимущественно в сетях связи, таких как мобильные беспроводные сети датчиков и исполнительных механизмов (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)= ∑ i j 1 α i j x i y j ( mod q ) . В данном варианте осуществления q - простое число в форме 2ⁿ - 1, и системные идентификаторы выбирают так, чтобы они имели длину [ n 3 ] бит. Как объясняется ранее, такая конфигурация предоставляет возможность ограничивать влияние сверточной модульной операции на некоторое количество бит. Следуя этим рассуждениям, необходимо уменьшать соотношение между размером поля в битах и размером идентификатора, равным k битам. В частности, можно сделать это соотношение равным 3*α, где α является степенью полинома. Если принимают α=3, и существует полином f(x,y)= ∑ i j α = 3 α i j x i y j ( mod q ) и его оценивают при x=R, R имеет длину [ log q ] 2 * α + 1 бит, то получают часть полинома g(y)= ∑ i α = 3 b j y j ( mod q ) . Каждый коэффициент b_j вычисляют, как b_j= ∑ i = 0 α = 3 α i j R i ( 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 = n 2 * α + 1 без потери общности. Значения [C₀, C₁₀..., C_i0,... C_α0, C₁₁..., C_j1,...C_α1) содержат подэлементы SKGE объекта N1 и зависят от коэффициентов исходной части полинома, как:

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

Каждый из этих подэлементов SKGE объекта N1 зависит от α+1 коэффициентов исходного корневого двумерного полинома. На фиг. 5 изображают 4 коэффициента исходно