Использующее общий ключ сетевое устройство и его конфигурирование

Использующее общий ключ сетевое устройство и его конфигурирование

Иллюстрации

Показать все

Реферат

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

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

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

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

УРОВЕНЬ ТЕХНИКИ ИЗОБРЕТЕНИЯ

Статья, написанная SONG GUO и др.: «Основанная на перестановках много-полиномиальная схема для попарного установления ключа в сенсорных сетях (A Permutation-Based Multi-Polynomial Scheme for Pairwisc Key Establishment in Sensor Networks)», COMMUNICATIONS (ICC), международная конференция IEEE (Институт инженеров по электротехнике и радиоэлектронике) 2010 года, IEEE, Пискатауэй, Нью-Джерси, США, 23 мая 2010 года (2010-05-23), страницы 1-5, раскрывает решение предшествующего уровня техники.

Если имеется сеть связи, содержащая множество сетевых устройств, существует проблема установления безопасных соединений между парами таких сетевых устройств. Один из способов осуществления этого описан в работе C. Blundo, A. Dc Santis, A. Herzberg, S. Kuttcn, U. Vaccaro и M. Yung, «Идеально безопасное распределение ключей для динамических конференций (Perfectly-Secure Key distribution for Dynamic Conferences)», Springer, записи лекций по математике, том 740, страницы 471-486, 1993 год (указываемая ссылкой, как 'Blundo').

Предполагается наличие центральной службы, также указываемой как сетевая служба или как доверенная третья сторона (Trusted Third Party,TTP), которая генерирует симметричный двумерный полином f(x,y) с коэффициентами в конечном поле F с p элементами, где p - простое число или степень простого числа. Каждое устройство имеет идентификационный номер в F и обеспечивается материалом локального ключа посредством TTP. Для устройства с идентификатором η, материал локального ключа является коэффициентами полинома f(η,y).

Если устройство η хочет связаться с устройством η’, оно использует свой материал ключа, чтобы сгенерировать ключ K(η,η’)=f(η,η’). Так как f симметричен, генерируется одинаковый ключ.

Проблема этой схемы использования общего ключа возникает, если взломщик знает материал ключа t+1 или более устройств, где t - степень двумерного полинома. Взломщик может восстановить полином f(x,y). В этот момент безопасность системы полностью взломана. При наличии идентификационных номеров любых двух устройств взломщик может восстановить общий ключ этой пары устройств.

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

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

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

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

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

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

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

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

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

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

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

Общий ключ K_AB между парой устройств A и B получается, как сумма по меньшей мере двух (в общем случае m’) подключей , то есть . Каждый подключ сгенерирован из отдельного материала ключа, в котором модульные операции выполняются по модулю публичного модуля N_i. Так как модульные операции смешиваются во время генерирования локального ключа, а также во время генерирования общего ключа, невозможно расширить атаки с использованием шумной полиномиальной интерполяции на эту криптографическую систему. Даже если взломщик получит доступ к N_c b-разрядным ключам, каждый из них получен из двух подключей, каждый подключ, вытекающий из оценивания отдельного материала ключа. Но взломщик не сможет различить подключи, поэтому взломщик не может восстановить два (в общем случае m’) материала ключа атакуемого устройства.

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

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

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

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

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

Особой догадкой изобретателей было то, что публичный модуль не должен быть простым числом. В одном из вариантов осуществления публичный модуль является составным. Кроме того, нет причины, по которой публичный модуль обязан быть числом со 'всеми единичными' разрядами, например числом, которое состоит только из разрядов ‘1’ в своем бинарном представлении. В варианте осуществления публичный модуль не является степенью двойки минус один. В варианте осуществления бинарное представление публичного модуля содержит по меньшей мере один нулевой разряд (не считая ведущие нули, то есть бинарное представление публичного модуля содержит по меньшей мере один нулевой разряд, который младше самого старшего разряда публичного модуля). В варианте осуществления публичный модуль является степенью двойки минус один и составным числом.

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

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

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

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

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

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

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

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

В варианте осуществления способ согласно изобретению может использоваться в качестве криптографического способа для протоколов безопасности, таких как IPSec, (D)TLS, HIP, или ZigBee. В частности, устройство, использующее один из этих протоколов, ассоциируется с идентификатором. Второе устройство, желающее взаимодействовать с первым устройством, может сгенерировать общий парный ключ с первым устройством при наличии его идентификатора, и парный ключ (или ключ, полученный из него посредством, например, функции получения ключа) может использоваться в способе согласно вышеописанным протоколам на основании предварительного общего ключа. В частности, идентификатор устройства, как он определен в данном изобретении, может являться сетевым адресом, таким как короткий адрес ZigBee, IP-адрес или идентификатор хоста. Идентификатор также может являться IEEE адресом устройства или строкой разрядов собственности, связанной с устройством, так, чтобы устройство принимало некоторый материал локального ключа, связанный с IEEE адресом, во время производства.

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

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

В варианте осуществления один или более или все публичные модули N выбираются так, чтобы они удовлетворяли 2^(a+2)b-1≤N≤2^(a+2)b-1, где a представляет степень двумерного полинома, а b представляет длину ключа. Например, в варианте осуществления N=2^(a+2)b-1. Операция по модулю для последнего выбора может быть реализована особенно эффективно.

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

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

Наличие частного модуля, выбранного таким образом, что все из ‘имеющего длину ключа’ количества самых младших разрядов бинарного представления разницы между публичным модулем и частным модулем являются нулевыми разрядами, увеличивает вероятность того, что общий ключ на первом сетевом устройстве из пары сетевых устройств будет близок к общему ключу, полученному на втором сетевом устройстве из пары сетевых устройств; то есть бинарное представление частного модуля содержит такие же разряды в ‘имеющих длину ключа’ самых младших позициях, как и бинарное представление публичного модуля. Например, если длина ключа составляет 64, частный модуль может быть выбран посредством вычитания числа, кратного 2^64, из публичного модуля. В варианте осуществления разница публичного модуля и частного модуля, поделенная на двойку в степени длины ключа, меньше чем двойка в степени длины ключа.

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

Наличие разных частных модулей, и, в частности, множества частных модулей, усложнит анализ для взломщика. Чтобы еще больше увеличить безопасность, возможны дополнительные воздействия на коэффициенты. В варианте осуществления служба, суммирующая множество результирующих одномерных полиномов множества приведений, проверяет, не является ли значение каждого из результирующих коэффициентов либо слишком маленьким, либо слишком большим, например меньше чем минимальное пороговое значение, или больше чем максимальное пороговое значение. Это еще больше увеличивает безопасность, так как в любом из двух случаев взломщик может выявить компоненты множества приведений, если они слишком большие или слишком маленькие. Например, если значение коэффициента, получившееся после сложения, равняется 1, и имеется только два одномерных полинома, тогда взломщик знает, что либо соответствующий коэффициент, связанный с первым полиномом, равен 1, а коэффициент, связанный со вторым полиномом, равен 0, либо наоборот. В частности, служба, генерирующая материал локального ключа для устройства, может проверять, является ли значение каждого из результирующих коэффициентов материала локального ключа по меньшей мере ‘минимальным значением’ или самое большое ‘максимальным значением’. Эта проверка может быть опущена, в частности, если публичный модуль относительно близок к всем частным модулям, и все элементы материала ключа находятся между 0 и N-1. Если TTP может назначать идентификационные номера, она также могла бы назначать устройству другой идентификационный номер, если TTP обнаруживает маленькие или большие коэффициенты.

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

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

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

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

Чтобы сгенерировать общий ключ из имеющих длину ключа разрядов, сетевые устройства сначала применяют дополнительный этап деления. Первое сетевое устройство оценивает материал ключа для идентификационного номера второго сетевого устройства по модулю публичного модуля для каждого набора параметров и суммирует результаты, затем делит на 2^s и приводит по модулю двойки в степени длины ключа. Отметим, что это эквивалентно тому, чтобы сначала применить приведение по модулю 2^(s+длина ключа), затем приведение по публичному модулю, а после этого разделить на 2^s. Здесь, «деление» включает в себя округление вниз.

В варианте осуществления частный модуль генерируется, используя генератор случайных чисел. В варианте осуществления множество частных модулей генерируются так, чтобы они были попарно взаимно простыми. Например, множество частных модулей могут быть сгенерированы итеративно, проверяя, для каждого нового частного модуля, что они все еще попарно взаимно простые, и если нет, отбрасывая последний сгенерированный частный модуль. Вариант осуществления содержит итеративное генерирование потенциального модуля, используя генератор случайных чисел, так, что все имеющие длину ключа (b) последовательные разряды бинарного представления разницы публичного модуля и частного модуля являются нулевыми разрядами, например, самые младшие имеющие длину ключа последовательные разряды, до тех пор пока потенциальный модуль не удовлетворит тесту простоты, используя устройство тестирования простоты, при этом полученный таким образом потенциальный модуль, удовлетворивший тесту простоты, используется в качестве частного модуля. Тест простоты может, например, являться тестом простоты Миллера-Рабина или тестом простоты Соловея-Штрассена.

Симметричный двумерный полином в переменных x и у степени a содержит только одночлены вида xⁱy^j, с i<a, j<a. Более того, коэффициент, соответствующий xⁱy^j совпадает с коэффициентом, соответствующим x^jyⁱ. Это может использоваться, чтобы сократить количество сохраняемых коэффициентов примерно вдвое. Отметим, что используется более слабое определение степени. Мы определяем степень одночлена, как максимальную степень переменных в одночлене. Поэтому степень xⁱy^j равняется max(i,j), где i<a, j<a. Поэтому, например, то, что мы называем полиномом степени 1, имеет общий вид a+bx+cy+dxy (отметим, что, так как рассматриваются только симметричные полиномы, b=c). Отметим, что при желании можно использовать дополнительные ограничения на двумерный полином, включая, например, что используются только одночлены с i+j<a, но это не обязательно.

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

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

В варианте осуществления некоторое количество самых младших разрядов общего ключа, которые удаляются, например, количество удаляемых разрядов может составлять 1, 2 или более, 4 или более, 8 или более, 16 или более, 32 или более, 64 или более. Посредством удаления большего количества самых младших разрядов, шанс наличия ключей, которые не равны, уменьшается; в частности, их можно сокращать до любого желаемого порогового значения. Вероятность того, что общие ключи равны, может быть вычислена посредством следующих математических соотношений, и также может быть определена экспериментально.

Хотя выбор запутывающих чисел может контролироваться, в варианте осуществления диапазон, из которого выбирается запутывающее число, уменьшается для коэффициентов, соответствующих одночленам более высокой степени. В частности, можно потребовать, чтобы , где обозначает запутывающее число для i-го одночлена, i обозначает степень одночлена, соответствующего коэффициенту, a представляет степень двумерного полинома, а b представляет длину ключа. A представляет сетевое устройство, для которого генерируется материал локального ключа. В варианте осуществления запутывающее число генерируется для каждого коэффициента, например, используя вышеприведенную формулу. Разное запутывание может применяться для разных сетевых устройств. Например, даже если имеется 3 или более сетевых устройств, для каждого сетевого устройства могут быть сгенерированы разные запутывающие числа.

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

Количество разрядов в идентификационном номере сетевого устройства обычно выбирается, как меньшее или равное длине ключа. Идентификационный номер может являться строкой разрядов, скажем из 32 или 64, или более разрядов. Длина ключа может составлять 32 или более, 48 или более, 64 или более, 96 или более, 128 или более, 256 или более. Длина ключа может быть выбрана некоторым количеством разрядов более высокого порядка, чтобы снизить соответствующее количество самых младших разрядов определенного общего ключа. С другой стороны, в варианте осуществления длина идентификационного номера выше, чем длина ключа. В этом случае эффект модульных операций может привести к более сильному влиянию на самые младшие разряды имеющих длину ключа разрядов сгенерированного ключа, так, что эти разряды могут не равняться для пары устройств, желающих сгенерировать общий ключ. Наличие более длинного идентификатора может, однако иметь положительный эффект в смысле безопасности, так как большее количество разрядов смешиваются вместе при выполнении соответствующих вычислений.

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