Устройства и способ согласования ключей

Изобретение относится к сетевым узлам. Технический результат заключается в повышении безопасности за счет того, что схемы обмена ключами достигают минимального объема связи или требований по полосе пропускания при одновременном обеспечении защищенности от противников с поддержкой классических, а также квантовых вычислений. Первый электронный сетевой узел, сконфигурированный для протокола обмена ключами (KEX), при этом первый сетевой узел выполнен с возможностью получать совместно используемый полином, совместно используемый со вторым сетевым узлом, причем коэффициенты совместно используемого полинома a выбираются по модулю первый математический модуль q, формировать полином (sk_L) закрытых ключей, причем коэффициенты полинома закрытых ключей ограничиваются по абсолютному значению посредством предела (s), формировать полином (pk_L) открытых ключей посредством следующего вычисление полиномиального произведения между совместно используемым полиномом (a) и полиномом (sk_L) закрытых ключей по модулю первый математический модуль (q) и понижающее масштабирование коэффициентов полиномиального произведения до второго математического модуля (p). 3 н. и 10 з.п. ф-лы, 8 ил.

 

Область техники, к которой относится изобретение

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

Уровень техники

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

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

Практические протоколы согласований ключей введены в 1976 году, когда Whitfield Diffie и Martin Hellman ввели понятие криптографии с открытым (общедоступным) ключом. Они предложили систему для согласования ключей между двумя сторонами, которая использует очевидную трудность вычислительных логарифмов по конечному полю GF(q) с q элементами. С использованием системы, два пользователя могут согласовывать симметричный ключ. Симметричный ключ затем может использоваться, скажем, для зашифрованной связи между двумя сторонами.

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

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

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

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

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

Joppe W. Bos и другие, "Post-quantum key exchange for the TLS protocol from the ring learning with errors problem", IACR 2016 год, раскрывает электронный сетевой узел, сконфигурированный для протокола согласования ключей с использованием обучения за счет ошибок.

Andrey Bogdanov и другие, "On the Hardness of Learning with Rounding over Small Modulus", Network and Parallel Computing, Lecture Notes in Computer Science, 2015 год, раскрывает протокол на основе обучения за счет округления.

Chris Peikert и другие, "Lattice Cryptography for the Internet", Network and Parallel Computing, Lecture Notes in Computer Science, 2014 год, раскрывает протокол на основе решеток для аутентифицированного обмена ключами на основе обучения за счет ошибок.

Сущность изобретения

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

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

- интерфейс связи, выполненный с возможностью цифровой связи со вторым сетевым узлом, и

- процессорную схему, выполненную с возможностью:

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

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

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

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

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

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

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

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

Поскольку полином закрытых (конфиденциальных) ключей ограничивается, и полином открытых ключей понижающе масштабируется, объем служебной информации по вычислению и связи при согласовании ключей уменьшается. Кроме того, посредством использования полиномов, скажем, вместо матриц, объем служебной полосы пропускания и служебной информации по вычислению дополнительно уменьшается. Преимущественно, полиномы способствуют дополнительному упрощению протокола. В вариантах осуществления, полиномы, которые используются, выполняются по модулю полином n-ой степени, например, X^n+1, так что они имеют n коэффициентов. Типично, полиномы закрытых ключей имеют идентичное число (n) коэффициентов с совместно используемым полиномом, но это не является обязательным. Например, полиномы закрытых ключей могут иметь более низкую степень или число коэффициентов, чем совместно используемый полином. Они даже могут иметь различное число коэффициентов между первым и вторым узлом. Следует отметить, что даже если число коэффициентов в полиноме закрытых ключей равно числу коэффициентов совместно используемых полиномов, они могут быть более разреженными.

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

Математические модули p и q не должны обязательно быть простым числом и фактически предпочтительно составляют степень 2. Кроме того, гораздо более предпочтительно, если p делит q. Например, в варианте осуществления, первый математический модуль имеет в качестве размера в битах 12 или больше, и/или второй математический модуль имеет в качестве размера в битах 7 или больше.

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

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

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

В варианте осуществления, первый сетевой узел дополнительно выполнен с возможностью:

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

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

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

- отправлять вспомогательные данные во второй сетевой узел.

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

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

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

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

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

Другая опция для того, чтобы преодолевать разность между необработанными ключами, вычисленными в обеих сторонах, заключается в том, чтобы использовать инкапсуляцию ключей. Через инкапсуляции, совместно используемый ключ защищается, и кроме того, небольшие разности между необработанными ключами вызывают небольшую корректируемую разность между деинкапсулированным совместно используемым ключом. Например, чтобы инкапсулировать ключ, можно сначала добавлять дополнительную избыточность. Это, например, может осуществляться посредством преобразования битов в совместно используемом ключе в числа по модулю p, например, посредством преобразования бита 0 в 0 и бита 1 в p/2. Более обширное преобразование использует код с коррекцией ошибок, например, код с повторениями. Другие примеры кодов с коррекцией ошибок включают в себя код Адамара, алгоритм Рида-Соломона, BCH и т.д. После кодирования совместно используемого ключа и добавления избыточности, необработанный ключ суммируется по модулю p с кодированным совместно используемым ключом, чтобы получать инкапсулированный совместно используемый ключ. Вместо суммирования, также могут использоваться другие функции комбинирования, например, вычитание по модулю p.

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

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

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

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

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

Точный размер весового коэффициента Хэмминга, вероятно, не является очень важным. В частности, в крупномасштабных примерах, в которых число коэффициентов больше, хороший вариант выбора вероятно составляет примерное число коэффициентов, деленное на 5 (0,2n). Тем не менее, можно оценивать минимальный весовой коэффициент Хэмминга посредством минимизации h_s (весового коэффициента Хэмминга) при условии, что , составляет, по меньшей мере, скажем, 127, или более предпочтительно, по меньшей мере, 255.

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

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

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

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

Другой аспект изобретения предоставляет способ обеспечения доступности компьютерной программы для загрузки. Этот аспект используется, когда компьютерная программа выгружается, например, в Apple App Store, Google Play Store или Microsoft Windows Store, и когда компьютерная программа доступна для загрузки из такого магазина.

Краткое описание чертежей

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

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

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

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

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

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

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

Фиг. 6a схематично показывает пример варианта осуществления устройства выбора параметров,

Фиг. 6b схематично показывает пример варианта осуществления способа выбора параметров.

Список ссылок с номерами на фиг. 1-2, 5, 6a:

100 - сеть согласования ключей

110 - сетевой узел в форме инициатора

120 - интерфейс связи

130 - модуль обработки совместно используемых полиномов

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

150 - модуль обработки полиномов открытых ключей

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

162 - необработанный ключ

164 - сверочные данные (h)

166 - совместно используемый ключ

210 - сетевой узел в форме ответчика

220 - интерфейс связи

230 - модуль обработки совместно используемых полиномов

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

250 - модуль обработки полиномов открытых ключей

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

262 - необработанный ключ

264 - сверочные данные (h)

266 - совместно используемый ключ

300 - коэффициент полинома необработанных ключей

301 - старшая часть

302 - средняя часть

303 - младшая часть

500 - сеть согласования ключей

510 - сетевой узел в форме инициатора

520 - сетевой узел в форме ответчика

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

564 - кодированный ключ

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

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

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

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

600 - устройство выбора параметров

602 - интерфейс вывода

610 - формирователь наборов параметров

620 - модуль выбора p, q

630 - оптимизатор n, m

640 - оптимизатор

Подробное описание вариантов осуществления

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

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

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

Фиг. 1 схематично показывает пример варианта осуществления сети 100 согласования ключей.

На фиг. 1 показаны два сетевых узла в системе: сетевой узел 110 в форме инициатора и сетевой узел 210 в форме ответчика. В варианте осуществления системы согласования ключей, число узлов может быть большим, даже гораздо большим двух, например, большим 1000 узлов, например, большим 10^6 узлов.

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

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

Узел-инициатор 110 содержит интерфейс 120 связи. Узел-ответчик 210 содержит интерфейс 220 связи. Интерфейсы связи могут быть выполнены с возможностью цифровой связи с другими узлами в системе согласования ключей. Тем не менее, необязательно, что все узлы в системе могут достигаться в любой момент времени.

Интерфейс 120 и 220 связи выполнен с возможностью цифровой связи. Например, интерфейсы связи могут быть выполнены с возможностью обмениваться данными по компьютерной сети. Например, интерфейс связи может быть выполнен с возможностью беспроводной связи, например, Wi-Fi, ZigBee, Bluetooth и т.п., и/или проводной связи, например, Ethernet, USB и т.п. Связь между узлами 110 и 210 также может представлять собой комбинацию проводных и беспроводных соединений. Например, узлы в системе 100, включающей в себя узлы 110 и 120, могут содержать электронное устройство хранения данных, которое содержит идентификатор связи, который уникально идентифицирует узел в системе 100. Например, идентификатор связи может быть включен в цифровые сообщения, которыми обмениваются между узлами 110 и 210, например, чтобы адресовать сообщение. Например, идентификатор связи может представлять собой IP-адрес, MAC-адрес и т.п.

В варианте осуществления, электронный сетевой узел сконфигурирован для протокола обмена ключами (KEX). Протокол заключает в себе обмен сообщениями между узлами 110 и 210 по интерфейсам 120 и 220 связи и выполнение вычислений, например, для данных, принимаемых из другого узла. Выполнение протокола согласования ключей реализуется в процессорной схеме, примеры которой показаны ниже. Фиг. 1 показывает функциональные модули, которые могут представлять собой функциональные модули процессорной схемы. Например, фиг. 1 может использоваться в качестве проекта возможной функциональной организации процессорной схемы. Процессорная схема не показана отдельно от модулей на фиг. 1. Например, функциональные модули, показанные на фиг. 1, также могут полно или частично реализовываться в компьютерных инструкциях, которые сохраняются в сетевых узлах и выполняются посредством микропроцессора сетевого узла.

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

Варианты осуществления изобретений не основываются на доверенной третьей стороне, чтобы предоставлять конфиденциальную связь. Канал связи между интерфейсами 120 и 220 связи не должен обязательно представлять собой защищенный канал. Взломщики могут иметь возможность перехватывать сообщения в канале связи. Несмотря на это, ключ, который согласован между узлами 110 и 210, может быть защищенным. Если канал связи защищается от изменений, степень аутентификации может получаться в такой мере, которая обеспечивается посредством канала. Тем не менее, если канал между интерфейсами 120 и 220 связи не защищается от изменений, KEX-схема не должна достигать аутентификации. Чтобы получать аутентификацию, варианты осуществления могут комбинироваться с любым известным механизмом аутентификации, например, с механизмом неявной аутентификации, например, с использованием сертифицированных открытых ключей, или с механизмом явной аутентификации, например, с использованием цифровых подписей.

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

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

Для n-мерного вектора и распределения X ошибок по Z_q, LWE-распределение по получается посредством выбора вектора a равномерно и случайно из и ошибки e из X и вывода .

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

LWR-проблема представляет собой "дерандомизированную" версию LWE-проблемы, посредством использования округления с математическим модулем "p" вместо вставки ошибок, с тем чтобы скрывать секретную информацию, и затем введения детерминированной ошибки посредством понижающего масштабирования от Z_q (где q является исходным математическим LWE-модулем) до Z_p.

Для n-мерного вектора , LWR-распределение по получается посредством выбора вектора a равномерно и случайно из и вывода .

Здесь, обозначает целое число, ближайшее к x. LWR-проблема поиска задается с точки зрения нахождения секрета s, точно аналогично LWE-проблеме поиска. LWR-проблема принятия решений состоит в том, чтобы отличать распределение от равномерного распределения по с m экземпляров для фиксированного . Показано, что LWR-проблемы поиска и принятия решений являются, по меньшей мере, не менее трудными, чем соответствующие LWE-проблемы, когда m ограничивается таким образом, что является константой (где B является пределом для ошибок в LWE-проблеме).

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

В изобретении, две стороны формируют два полинома, которые являются приблизительно, но не точно равными. Чтобы проводить точное согласование, некоторые сверочные данные отправляются. Схема для осуществления означенного поясняется в заявке на патент идентичного заявителя, с заголовком "REACHING AGREEMENT ON A SECRET VALUE", поданной в EPO 4 ноября 2016 года, с номером заявки 16197277.3; например, способ на страницах 7-10 может использоваться для сверки в вариантах осуществления согласно изобретению. Также могут приспосабливаться разновидности, раскрытые в другом месте в процитированной заявке на патент.

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

1. Функция округления: Для , пусть:

. Тогда:

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

2. Функция перекрестного округления: Для , пусть:

. Тогда:

Интуитивно, извлекает младших битов из старших битов .

3. Сверочная функция :

Для ,

,

где v является ближайшим элементом к w таким образом, что .

Эти три функции могут применяться на основе коэффициентов к полиномам.

Вышеуказанная сверочная функция используется в качестве примера, в данном документе. Как отмечено выше, также могут использоваться способы сверки в вышеуказанной заявке. Фиг. 2 является схематичной иллюстрацией функций округления и перекрестного округления. В качестве примера, фиг. 2 показывает полином 300 необработанных ключей. Коэффициент 300 проиллюстрирован в качестве битовой строки со старшими битами влево и младшими битами вправо. Интуитивно, функция округления, применяемая к коэффициенту, соответствует B битов в старшей части 301, функция перекрестного округления - b_h следующих битов в средней части 302. Младшие могут отбрасываться.

Узел-инициатор 110 содержит модуль 130 обработки совместно используемых полиномов. Узел-ответчик 210 содержит модуль 230 обработки совместно используемых полиномов. Модули 130 и 230 обработки совместно используемых полиномов выполнены с возможностью получать совместно используемый полином (a), который совместно используется двумя узлами. Коэффициенты в совместно используемом полиноме a являются целыми числами, выбранными по модулю первый математический модуль q. Предусмотрено множество способов обеспечивать то, что идентичный полином совместно используется узлами 110 и 210, в частности, с учетом того факта, что полином a не обязательно сохраняется закрытым для узлов 110 и 210.

Например, один из узлов, скажем, узел-инициатор 110, например, в модуле 130 обработки совместно используемых полиномов, может выбирать полином a, например, произвольно с элементами по модулю q. Коэффициенты затем могут отправляться через модули связи в другой узел, например, в модуль 230 обработки совместно используемых полиномов. В этом случае, второй модуль 230 обработки совместно используемых полиномов должен просто принимать полином и сохранять его. Полином a также может выбираться посредством узла-ответчика 210 вместо этого и отправляться в узел-инициатор 110.

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

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

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

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

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

Узел-инициатор 110 содержит модуль 140 обработки полиномов закрытых ключей. Узел-ответчик 210 содержит модуль 240 обработки полиномов закрытых ключей. Модуль 140 обработки полиномов закрытых ключей выполнен с возможностью формировать полином sk_L закрытых ключей. Модуль 240 обработки полиномов закрытых ключей выполнен с возможностью формировать полином sk_R закрытых ключей. Коэффициенты в полиномах закрытых ключей являются целыми числами, ограниченными по абсолютному значению посредством предела s. Например, коэффициент в полиноме закрытых ключей может выбираться между -s и s (пределы включены).

Авторы изобретения обнаружили то, что, неожиданно, выбор небольшого предела обеспечивает двойное преимущество: полиномиальные умножения с полиномами закрытых ключей выполняются быстрее, и расстояние между необработанными ключами, вычисленными в каждой стороне, является меньшим (см. ниже). Второе означает то, что требуется меньше сверочных данных, и/или вероятность сбоя в протоколе, поскольку узлы согласуют различный ключ, является меньшей. Предел s выбирается самое большее как второй математический модуль, например, как меньший или равный второму математическому модулю. Этот выбор является преимущественным, поскольку позднее проводится умножение по модулю p. Можно ограничивать его самое большее (или меньше) половиной второго математического модуля (p/2), если разрешаются коэффициенты со знаком полиномов закрытых ключей.

Предел может составлять ниже второго математического модуля или половины второго математического модуля, и на практике предел типично должен выбираться гораздо меньшим математического модуля. В варианте осуществления, предел s для абсолютного значения коэффициентов полинома (sk_L, sk_R) закрытых ключей равен 2 (s=2). Таким образом, все коэффициенты в полиноме закрытых ключей равны -2, -1, 0, 1 или 2. Чтобы умножать полином a на полином закрытых ключей, требуются только суммирования, вычитания и сдвиги на 1 бит. Такое полиномиальное умножение в силу этого может реализовываться очень эффективно.

С точки зрения реализации, наилучшие результаты достигаются посредством выбора предела равным 1 (s=1). Таким образом, коэффициенты полинома закрытых ключей имеют только значения в -1, 0 и 1. Они также называются "двоичным значениями со знаком". Полиномиальное умножение с полиномом в двоичном значении со знаком заключает в себе только суммирования и вычитания. Модуль умножения для умножения по модулю p или q не требуется. Предел s=1 может быть еще больше ограничен только посредством использования двоичных коэффициентов, например, 0 или 1; тем не менее, в вариантах осуществления, по меньшей мере, некоторые коэффициенты равны 1, -1 и 0.

Другие небольшие числа для s также являются возможными, например, если s=3, разрешенные коэффициенты представляют собой: 0, 1, -1, 2, -2, 3, -3. Процедуры умножения для умножения на эти числа могут содержаться в узлах. Например, +1, -1 могут обрабатываться посредством сумматора/вычитателя, -2, +2 могут обрабатываться посредством сдвига с последующей обработкой посредством сумматора/вычитателя, и +3, -3 могут обрабатываться посредством суммирования/вычитания сдвинутого и несдвинутого числа.

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

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

Число коэффициентов полиномов упоминается вместо их степени, чтобы не допускать сложностей в случае, если коэффициент с наибольшей степенью равен 0. Под n подразумевается число коэффициентов совместно используемого полинома a. Типично, полином закрытых ключей и совместно используемый полином должны иметь идентичное число коэффициентов, но это не является обязательным. В варианте осуществления, полиномы закрытых ключей также имеют n коэффициентов. Все полиномиальные умножения выполняются по модулю полином степени n. С практической точки зрения, полином может представлять собой xⁿ+1, хотя другие полиномы также должны работать. Следует отметить, что набор полиномов формирует кольцо. Это кольцо типично не должно представлять собой поле: как q, так и xⁿ+1 могут быть составными и типично являются составными. Следует отметить, что операции округления, которые поясняются ниже, преобразуют эти кольца в меньшее кольцо способом, несовместимым с кольцевым умножением. Эта намеренное нарушение математической структуры усложняет анализ и повышает безопасность. Число m коэффициентов выбирается достаточно большим для того, чтобы получать достаточное число битов в совместно используемом ключе и получать достаточно высокий уровень безопасности.

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

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

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

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

Другой способ ограничивать весовой коэффициент Хэмминга полиномов закрытых ключей состоит в том, чтобы выбирать коэффициенты полинома (sk_L, sk_R) закрытых ключей из распределения вероятностей. Например, коэффициенты полинома (sk_L, sk_R) закрытых ключей могут выбираться из неравномерного распределения вероятностей, при этом вероятность нулевого коэффициента превышает вероятность ненулевого коэффициента. В варианте осуществления, распределение вероятностей выбирается таким образом, что оно обеспечивает предварительно определенный ожидаемый весовой коэффициент Хэмминга. Например, чтобы выбирать полином с n коэффициентов и ожидаемым весовым коэффициентом h_s Хэмминга, можно выбирать каждый коэффициент в качестве ненулевого с вероятностью h_s/n. Ненулевой коэффициент может выбираться в качестве 1 или -1, например, с равной вероятностью.

Весовой коэффициент Хэмминга в полиномах, который является слишком небольшим, может оказывать влияние на безопасность. Например, для случая двоичного значения со знаком, можно выбирать весовой коэффициент h_s Хэмминга таким образом, что составляет, по меньшей мере, 127, более предпочтительно, по меньшей мере, 255. Причина состоит в том, чтобы приводить к неосуществимости атаки на основе метода прямого опробования посредством цикличного выполнения для полиномов закрытых ключей. В варианте осуществления, весовой коэффициент h_s Хэмминга является максимально возможно небольшим для того, чтобы удовлетворять вышеуказанному пределу. В практических вариантах осуществления, для большего n, можно просто выбирать весовой коэффициент Хэмминга, пропорциональный числу коэффициентов, например, можно задавать , например, с a=0,2. Если обобщить, например, можно отбирать .

Узел-инициатор 110 содержит модуль 150 обработки полиномов открытых ключей. Узел-ответчик 210 содержит полином 250 открытых ключей. Модуль обработки полиномов открытых ключей вычисляет полином открытых ключей из полинома a и полинома sk закрытых ключей.

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

Модуль обработки полиномов открытых ключей вычисляет полином (pk_L, pk_R для инициатора и ответчика, соответственно) открытых ключей посредством вычисления полиномиального произведения между совместно используемым полиномом (a) и полиномом (sk_L или sk_R, соответственно) закрытых ключей по модулю первый математический модуль (q), с получением полиномиального произведения, приведения полинома по модулю полином приведения и понижающего масштабирования результата.

Тем не менее, это промежуточное полиномиальное умножение не раскрывается. Знание совместно используемого полинома a и результата этого полиномиального умножения перед понижающим масштабированием должно раскрывать закрытый ключ, поскольку он может вычисляться посредством отделения полинома a. Этап масштабирования, выполняемый посредством модуля обработки полиномов открытых ключей, блокирует эту опцию. Модуль обработки полиномов открытых ключей понижающе масштабирует коэффициенты полиномиального произведения до второго математического модуля p. Второй математический модуль p меньше первого математического модуля q. Масштабированный коэффициент равен немасштабированному коэффициенту, умноженному на второй математический модуль (p), деленному на первый математический модуль (s) и округленному до ближайшего целого числа. Например, если x является немасштабированным коэффициентом по модулю q в полиномиальном произведении, масштабированный коэффициент может выбираться в качестве , при этом представляет ближайшее целое число. После операции масштабирования, более невозможно просто вычислять закрытый ключ из открытого ключа и полинома a.

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

Умножение полинома a и полинома s закрытых ключей осуществляется по модулю первый математический модуль q. Для этой цели, сетевой узел может содержать модуль модульного приведения для приведения по модулю q. Если коэффициенты в полиноме s закрытых ключей являются небольшими, например, ограниченными посредством 1 или ограниченными посредством предела в 1 по абсолютному значению, модульное приведение может упрощаться; во время полиномиального умножения, каждый раз, когда коэффициент становится больше q или меньше 0, результат возвращается в интервал от 0 до q-1 посредством вычитания или суммирования q.

Как узел-инициатор, так и узел-ответчик отправляют свой полином открытых ключей в другой узел, например, с использованием интерфейсов 120 и 220 связи. Авторы изобретения выявили, по меньшей мере, три преимущества, которые реализованы посредством понижающего масштабирования полиномиального произведения. Во-первых, формирование и явное прибавление шума в полиномиальное произведение не допускаются. Введение шума требует вычисления распределения вероятностей, например, гауссова распределения. Оно имеет относительно большой объем вычислений. Во-вторых, требования по связи уменьшаются. Поскольку второй математический модуль p меньше первого математического модуля q, меньшее число битов требуется для того, чтобы представлять коэффициент полинома открытых ключей, чем полинома закрытых ключей. В-третьих, вычисления, которые заключают в себе полином открытых ключей, являются меньшими, поскольку они заключают в себе меньшие числа. Удивительно, что одна мера одновременно предоставляет три преимущества.

Очень предпочтительно, если второй математический модуль p делит первый математический модуль q. Интересно, что авторы изобретения обнаружили то, что ни первый, ни второй математический модуль не должен обязательно быть простым числом. Фактически, обнаружено, что выбор второго математического модуля (p) и/или первого математического модуля (q) в качестве степени 2 имеет такое преимущество, что открытые и закрытые ключи равномерно распределены. В варианте осуществления, первый и второй математический модуль составляют степени 2.

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

Размеры математических модулей не должны обязательно быть очень большими. Например, в варианте осуществления, второй математический модуль имеет в качестве размера в битах 12 или более, и/или первый математический модуль имеет в качестве размера в битах 8 или более. Большие или меньшие размеры являются возможными в зависимости от требований по обеспечению безопасности. В варианте осуществления, q находится в диапазоне 2¹² и 2¹⁶; p находится в диапазоне 2⁷ и 2⁹ (включительно). Значения p и q могут выбираться большими или меньшими согласно предписанию требований безопасности.

Узел-инициатор 110 содержит модуль 160 обработки совместно используемых ключей. Узел-ответчик 210 содержит модуль 260 обработки совместно используемых ключей. Модули обработки совместно используемых ключей отличаются в том смысле, что они или формируют и передают или принимают и применяют сверочные данные.

Как модуль 160 обработки совместно используемых ключей, так и модуль 260 обработки совместно используемых ключей выполнены с возможностью вычислять необработанный ключ 162, 262 в качестве полиномиального произведения по модулю второй математический модуль (p) между принимаемым открытым ключом другого узла и полиномом закрытых ключей самого сетевого узла, с последующим выполнением приведения по модулю полином приведения. Следует отметить, что если операция масштабирования опущена, то обе стороны должны вычислять идентичный необработанный ключ. Таким образом, идентичные ключи должны получаться в результате без масштабирования, и все вычисления должны проводиться по модулю q. Тем не менее, вследствие масштабирования, оба необработанных ключа не должны обязательно быть идентичными. Вычисление необработанного ключа проводится по модулю p. Сетевые узлы могут содержать модульный модуль для приведения результата умножений по модулю p.

Модуль 260 обработки совместно используемых ключей узла-ответчика 210 выполнен с возможностью получать совместно используемый ключ 266 и сверочные данные 264 из необработанного ключа 262 и отправлять сверочные данные 264 в сетевой узел-инициатор 110. Сверочные данные могут принимать форму одного или более битов в необработанном ключе. Биты, выбранные в качестве сверочных данных, игнорируются в целях формирования ключа.

Модуль 260 обработки совместно используемых ключей выбирает некоторые биты из коэффициентов необработанного ключа, из которых следует формировать ключ. Например, выбранные биты могут конкатенироваться. В варианте осуществления, выбранные биты вводятся в функцию извлечения ключей (KDF), например, в криптографическую хеш-функцию. Пример KDF, например, представлен в CMLA_KDF из CMLA Technical Specification, Version: V1.43-20131218, либо в KDF-функции, заданной в "DRM specification", OMA-TS-DRM-DRM-V2_0_2-20080723-A, Open Mobile Alliance™, Version 2.0.2, section 7.1.2, и т.д. Функция извлечения ключей может применяться к коэффициентам битов ключа в необработанном ключе, например, полученном посредством функции округления, например, после конкатенации, либо из выводов из сверочной функции, например, также после конкатенации.

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

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

Модуль 160 обработки совместно используемых ключей выполнен с возможностью принимать сверочные данные 164 (h) второго сетевого узла и вычислять совместно используемый ключ посредством применения сверочной функции к принимаемым сверочным данным и полиному 162 необработанных ключей. Например, сверочная функция может применяться к каждому из коэффициентов в необработанном ключе 162 и к соответствующей части сверочных данных. Например, если сверочные данные 164 составляют часть необработанного ключа, сформированного посредством модуля-ответчика 210, узел-инициатор может выбирать необработанный ключ, который может получаться посредством узла 210 и является совместимым с принимаемыми сверочными данными, например, имеет идентичные с принимаемыми средние биты. Один способ для означенного состоит в том, чтобы использовать сверочную функцию, заданную выше. Как результат, восстанавливаются идентичные биты с теми, которые узел 210 использует для того, чтобы создавать совместно используемый ключ. Посредством конкатенации битов аналогичным образом или посредством их ввода в идентичную KDF, получается идентичный совместно используемый ключ 166. В варианте осуществления, совместно используемый ключ представляет собой симметричный ключ.

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

Типичные значения для B и b_h равны 1 или 2. В данном документе, B является числом битов ключа, извлеченных в расчете на коэффициент необработанного ключа, и b_h является числом сверочных битов в расчете на коэффициент необработанного ключа. Число (n) коэффициентов выбирается таким образом, что произведение n и B превышает или равно требуемому размеру ключа, например, .

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

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

Ниже описываются дополнительные конкретные преимущественные варианты осуществления. Базовая система, представляющая это изобретение, представляет собой протокол, далее называемый "схемой обмена ключами (KEX)", который может выполняться двумя субъектами или сторон, далее называемых "инициатором" и "ответчиком", чтобы устанавливать совместно используемый секрет между собой, который известен только для них. С этой целью, они используют определенное число общих системных параметров, которые они должны согласовывать до выполнения KEX-схемы, некоторую закрытую информацию, которой обладает каждый из них, далее называемую "их секретными ключами", и некоторую открытую информацию, которой обладает каждый из них, далее называемую "их открытыми ключами". Безопасность KEX-схемы основана на проблеме обучения за счет округления (LWR), безопасность которой основана на проблеме обучения за счет ошибок (LWE), с защитой секретности совместно используемого секрета и секретности секретных ключей инициатора и ответчика.

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

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

Установление: Инициатор и ответчик согласуют следующие положительные целые числа:

i. q, p: так что .

ii. n и . Все полиномиальные умножения выполняются по модулю этот полином приведения.

iii. . Он представляет собой весовой коэффициент Хэмминга полиномов закрытых ключей.

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

v. b_h: Число битов, извлеченных в расчете на коэффициент необработанных ключей двух сторон, при создании сверочных данных.

vi. : Случайный полином, в котором является остаточным кольцом от циклотомического кольца по модулю целое число q.

Предпочтительно, a и являются взаимно простыми.

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

i. Секретный ключ: Полином секретов, например, случайный полином с n коэффициентов и весовым коэффициентом h_s Хэмминга.

ii. Открытый ключ:

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

Обмен ключами: Эта предложенная схема обмена ключами (обмен ключами между инициатором I и ответчиком R) использует округление и полиномы разреженных секретов, содержащие троичные записи, приводя к установлению совместно используемого секрета K между I и R.

KEX-инициатор		KEX-ответчик
Согласует свежий с равноправным узлом, выбирает свежий секретный , таким образом, что и .		Согласует свежий с равноправным узлом, выбирает свежий секретный , таким образом, что и .
.		.
		.
		.
.
, где k является ближайшим элементом к таким образом, что .		.

Для целей реализации, параметр n должен преимущественно составлять степень 2; тем не менее, это не представляет собой проектное требование.

Выбор весового коэффициента Хэмминга не является очень важным, но при условии целевого уровня безопасности в битах S (постквантовый) и 2S (классический). Чтобы обеспечивать то, что исчерпывающий поиск методом прямого опробования секретного ключа, чтобы оценивать его коэффициенты, имеет достаточно высокую рабочую нагрузку, число секретов в векторах секретных ключей (каждый из которых имеет весовой коэффициент h_s Хэмминга) должно удовлетворять следующему:

где является временем выполнения квантового алгоритма поиска Гровера, и является временем выполнения классического алгоритма поиска. Например, S может составлять 128 или 256 и т.д. Следует отметить, что этот предел предназначен для случая, в котором предел для абсолютных значений коэффициентов в полиномах закрытых ключей равен 1. Аналогичный предел может устанавливаться для больших пределов s.

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

Альтернативно, если формирование является детерминированным, то следующее может осуществляться с использованием стандартного защищенного PRF: если имеется h_s ненулевых элементов (или 1 или -1) в векторе n позиций, то PRF-вывод выбирает случайные позиции в столбце наряду со случайным значением в +1 или -1 до тех пор, пока PRF не выбирает h_s ненулевых элементов в различных местоположениях. Например, PRF-вывод может разделяться на блоки из битов, в которых первые битов блока идентифицируют позицию ненулевого элемента, и последний бит блока определяет то, равен элемент 1 или -1. Вектор может использоваться в качестве коэффициентов полинома закрытых ключей.

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

Вычислительная сложность: Поскольку полином секретных ключей является разреженным и имеет коэффициенты в 0, 1 и -1, вычисления по модулю q в нашей схеме являются быстрыми. В частности, умножения, заключающие в себе полиномы с высоким числом коэффициентов (например, во время формирования открытых ключей и необработанных ключей), могут быть высокооптимизированными. Сложность связи: Вследствие использования округления до более низкого математического модуля, есть возможность уменьшать размер каждого коэффициента открытого ключа и необработанного ключа, достигая значительно более низких требований по полосе пропускания. Означенное определяется количественно в двух следующих таблицах, в которых демонстрируются требования по полосе пропускания предложенной схемы (с/без использования округления, соответственно). Варианты осуществления сравниваются с LWE-протоколом, описанным в работе "Frodo: Take off the ring! Practical, Quantum-Secure Key Exchange from LWE", авторов J. Bos, C. Costello, L. Ducas, I. Mironov, M. Naehrig, V. Nikolaenko, A. Raghunathan, D. Stebila.

Полоса пропускания вычисляется как полный размер сообщений обмена ключами, которыми обмениваются (т.е. открытых ключей и сверочных данных), и не включает в себя обмен открытым полиномом a.

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

Ниже приводятся дополнительные варианты осуществления, описывается то, как могут выбираться параметры, и приводятся несколько примеров. Пусть Z_q, для целочисленного , обозначает кольцо частных. задается в качестве кольца целочисленных полиномов по модулю Xⁿ+1. используется для того, чтобы обозначать кольцо целочисленных полиномов по модулю Xⁿ+1, причем каждый коэффициент приводится по модулю q. В случае если X является распределением вероятностей по R, в таком случае обозначает дискретизацию согласно распределению X. Запись означает, что все коэффициенты полинома или вектора a выбираются равномерно и случайно из . представляет дискретное гауссово распределение по Z, параметризованное посредством гауссова параметра и заданное посредством назначения весового коэффициента, пропорционального , для всех целых чисел x. Для целых чисел n, h, где , равномерно и случайно дискретизирует полиномы или векторы, содержащие n компонентов точно с h ненулевых компонентов из распределения либо из . Функции и , используемые при вычислении сверочных данных и сверке конечного совместно используемого ключа, соответственно, являются идентичными функциям, заданным в [1]. (Ссылки приведены ниже).

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

Для сравнения, следует обратиться к алгоритму NewHope [2] и к способу, которым алгоритм NewHope конфигурирует свои параметры [2]. Алгоритм NewHope представляет собой схему обмена ключами на основе LWE в кольце. Тем не менее, алгоритм NewHope использует распределения секретов и шума, которые лучше напоминают исходное гауссово распределение. Таким образом, когда вычисляется открытый ключ , либо когда вычисляется ключ , авторы предлагают использовать теоретико-числовое преобразование. При этом:

и .

Выше, элементы со шляпой представляют векторы после применения NTT. вычисляется непосредственно. Кроме того, на практике, Alice и Bob обмениваются коэффициентами и . NTT означает теоретико-числовое преобразование.

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

- n должен составлять степень двух

- q является простым числом, так что

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

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

Следует отметить, что алгоритм NewHope [2] раскрывает конфигурационные параметры. Тем не менее, отсутствует альтернатива параметрам, предложенным авторами алгоритма NewHope, поскольку n должен составлять степень двух, так что предложенный вариант выбора (n=1024) приводит к возможности реализации на основе NTT в этой настройке. Тем не менее, это представляет собой требование, которое налагается посредством использования NTT, а не посредством аргументов обеспечения безопасности. Наложение вышеуказанного ограничения на форму n приводит к варианту выбора, который больше, чем требуется, для того, чтобы также достигать данного уровня безопасности.

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

Ниже раскрываются варианты осуществления с параметрами (q, p, n), удовлетворяющими следующим условиям:

a) q является максимально возможно небольшим

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

c) n является максимально возможно небольшим при обеспечении того, что в комбинации с выбранным q и оптимальным числом m выборок, предоставленный уровень безопасности составляет, по меньшей мере, λ.

Система вычисляет эти параметры (q, p, n), которые затем применяются Alice и Bob в обмене ключами с использованием небольших секретов.

Анализ безопасности KEX на основе LWE в кольце заключает в себе анализ вероятности успешности взломщика с доступом к алгоритму приведения BKZ-решеток и использование адаптированной версии атаки по принципу решения прямой задачи, чтобы разрешать уникальную SVP-проблему. Эта атака адаптируется взломщиком, чтобы использовать тот факт, что секрет является необычно небольшим и, кроме того, даже возможно разреженным. Эта адаптация осуществляется с использованием масштабирования решеток, чтобы уравнивать дисперсию секрета и компонентов шума в уникальном кратчайшем векторе, которого взломщик выполняет поиск с использованием приведения решеток и вдохновляется посредством технологий, подробно изложенных в [3].

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

Ниже описывается алгоритм для того, чтобы находить наименьшие параметры (q, p, n), которые обеспечивают возможность формирования бита ключа в расчете на коэффициент вектора ключей, для оптимального числа m выборок для того, чтобы достигать данного уровня λ безопасности. В варианте осуществления, этот алгоритм выполняется на сервере либо у Alice или у Bob, которым предоставляется целевой уровень λ безопасности. С учетом уровня безопасности, они вычисляют соответствующие конфигурационные параметры, которые затем подвергаются обмену и используются в протоколе обмена ключами.

Алгоритм 1:

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

Выходные данные: TRUE, если атака по принципу решения прямой задачи на основе приведения решеток [2] на LWR-проблему в кольце успешно выполняется для вышеуказанных параметров; FALSE в противном случае.

Этапы: 1. 2. . . 4. : return TRUE 5. else: return FALSE

Алгоритм 2:

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

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

Этапы: 1. 2. 3. 4. return

Алгоритм 3:

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

Выходные данные: Затраты на выполнение алгоритма приведения BKZ-решеток, чтобы получать приведенный базис для данной идеальной решетки (базиса).

Этапы: 1. 2. 3. 4. 5. 6. 7. 8. // Неопределенный уровень безопасности 9. return

Алгоритм 4:

Входные данные: наименьшее значение большого математического модуля на основе LWR в кольце, для которого должны оцениваться защищенные и функциональные параметры; наибольшее значение большого математического модуля на основе LWR в кольце, для которого должны оцениваться защищенные и функциональные параметры; среднеквадратическое отклонение дискретного гауссова распределения, подходящего для дискретизации LWE-шума (в кольце); максимальная приемлемая вероятность сбоя обмена ключами на основе LWR в кольце; небольшое начальное значение для оценки n; максимальное число LWR-выборок в кольце, которые могут запрашиваться взломщиком; число битов, извлеченных в расчете на полиномиальный компонент для создания конечного ключа согласно способу сверки [1]; число битов, извлеченных в расчете на полиномиальный компонент для создания каждого компонента полинома сверочных данных согласно способу сверки [1]; целевая длина конечного совместно используемого секрета в битах.

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

Этапы: 1. 2. a. i. Нахождение таким образом, что ii. b. i. Нахождение таким образом, что ii. c. : i. Нахождение таким образом, что ii. d. e. i. // Начальное значение n ii. // Булев флаг iii. // Минимальное число LWR-выборок в кольце, доступных для взломщика iv. Выбор в качестве степени 2, удовлетворяющей v. 1. // успешность атаки обозначает либо то, что эта размерность n является слишком небольшой, и соответствующая LWR-проблема в кольце является слишком легкой, либо то, что этот m является достаточно большим, и в силу этого взломщик имеет достаточное число выборок для того, чтобы разрешать проблему. a. // Попытка использования большего значения n, для которого LWR-проблема в кольце оптимистично является защищенной b. // Сброс значения m 2. // Сбой атаки обозначает либо то, что n является слишком большим и LWR-проблема в кольце является слишком трудной, либо то, что m не является достаточно большим, и в силу этого взломщик еще не имеет достаточного числа выборок для того, чтобы разрешать проблему. a. // Взломщик выполняет запрос относительно дополнительных LWR-выборок в кольце и пытается найти решение снова b. // Предел выборок достигнут. Взломщик не может выполнять запрос относительно дополнительных LWR-выборок в кольце. Текущая размерность n является безопасной для всех возможных m. i. // Условие безопасности удовлетворяется, теперь проверка функциональной корректности 1. return // Текущий кортеж параметра является и защищенным и удовлетворяет целевой вероятности сбоя. ii. // Прерывание vi. // Получение защищенных функционально корректных параметров для следующего q

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

Предпочтительно, p должен представлять собой фактор q таким образом, что анализ состояния успешности сверки, который проведен, является корректным (одному из этапов при вычислении условия необходимо это требование). Это условие автоматически удовлетворяется, если (1) удовлетворяется. Безопасность: отношение q/p должно быть достаточно большим, так что дисперсия ошибки округления является почти идентичной дисперсии эквивалентной гауссовой ошибки.

Преимущества KEX на основе небольших секретов с LWR: Поскольку секретные ключи в обмене ключами состоят из небольших компонентов (троичных или двоичных), полиномиальные умножения по модулю (Xⁿ+1) могут выполняться эффективно даже без необходимости операций полиномов в области теоретико-числового преобразования (NTT), к примеру, как осуществляется в [1].

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

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

Полоса пропускания для схемы обмена ключами на основе LWE в кольце по алгоритму Sp-TerRING вычисляется следующим образом:

Параметр b_h представляет число битов, извлеченных в расчете на компонент полинома необработанных ключей Bob для создания каждого компонента полинома r сверочных данных, и рассматривается в качестве 2 для всех вышеуказанных обменов ключами и уровней безопасности, на основе улучшенного механизма сверки вследствие [1].

При сравнении нашего подхода с параметрами алгоритма NewHope, рассматриваются следующие случаи.

Без ограничений на n, но для идентичного q с алгоритмом NewHope, производительность увеличивается для разреженных троичных секретов в LWR в кольце.

Таблица 1. Наибольшие размерности проблемы LWR в кольце подвержены атаке по принципу решения прямой задачи с использованием BKZ с размером b блока таким образом, что затраты на выполнение BKZ-b составляют, по меньшей мере, 2¹²⁸, и вероятность сбоя согласования ключей составляют самое большее 2-⁶⁰. Полином шума дискретизируется из дискретного гауссова распределения среднеквадратического отклонения . Весовой коэффициент Хэмминга полиномов секретов в LWR в кольце по алгоритму Sp-TerRING составляет 0,2n. Вычисляется полоса пропускания, включающая в себя сверочные данные, вычисленные на основе [1].

Уровень безопасности	Длина ключа	q	n, (LWR в кольце по алгоритму Sp-TerRING)	Полоса пропускания (алгоритм NewHope)	Полоса пропускания (LWR в кольце по алгоритму Sp-TerRING)	Отношение с алгоритмом NewHope
Классический (b=438)	128 битов	12289	646	3,64 KB	1,6 KB	0,44
Квантовый (b=483)	256 битов	12289	701	3,64 KB	1,77 KB	0,49
Параноидальный (b=617)	256 битов	12289	856,	3,64 KB	2,15 KB	0.6

Тем не менее, следует отметить, что для этого значения q нецелесообразно выполнять сверку ключей, идентичную сверке ключей в [1].

Без наложения ограничений на (n, q), используемые в алгоритме NewHope, производительность увеличивается для разреженных троичных секретов в LWR в кольце.

Таблица 2. Наибольшие размерности проблемы LWR в кольце подвержены атаке по принципу решения прямой задачи с использованием BKZ с размером b блока таким образом, что затраты на выполнение BKZ-b составляют, по меньшей мере, 2¹²⁸, и вероятность сбоя согласования ключей составляют самое большее 2-⁶⁰. Весовой коэффициент Хэмминга полиномов секретов в LWR в кольце по алгоритму Sp-TerRING составляет 0,2n. Вычисляется полоса пропускания, включающая в себя сверочные данные, вычисленные на основе [1].

Уровень безопасности	Длина ключа	q	p		n, (LWR в кольце по алгоритму Sp-TerRING)	Полоса пропускания (алгоритм NewHope)	Полоса пропускания (LWR в кольце по алгоритму Sp-TerRING)	Отношение с алгоритмом NewHope
Классический (b=438)	128 битов			2	551,	3,64 KB	1,1 KB	0,30
Квантовый (b=483)	256 битов			2	601,	3,64 KB	1,24 KB	0,37
Параноидальный (b=617)	256 битов			3	736,	3,64 KB	1,53KB	0,42

Следует отметить, что используется значение q, равное степени двух, так что можно применять способ сверки ключей в [1]. Следует отметить, что используется значение p, равное степени двух, с тем чтобы повышать производительность.

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

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

Полоса пропускания для схемы обмена ключами на основе LWR в кольце по алгоритму Sp-TerRING вычисляется следующим образом:

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

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

1. L. Tolhuizen, O. Garcia Morchon, R. Rietman, "Reaching agreement on the secret value", First filing, Phillips reference 2016P01227EP, 4 ноября 2016 года. Подана в Европейское патентное ведомство с номером заявки 16197277.3

2. E. Alkim, L. Ducas, T. Poeppelmann, P. Schwabe, "Post-quantum key-exchange - the new hope", Cryptology ePrint Archive, Report 2015/1092, https://eprint.iacr.org/2015/1092.pdf.

3. S. Bai, S. D. Galbraith "Lattice Decoding Attacks on Binary LWE", Cryptology ePrint Archive, Report 2013/839, https://eprint.iacr.org/2013/839.pdf.

Фиг. 6a схематично показывает пример варианта осуществления устройства 600 выбора параметров. Аналогично устройствам 110, 210, 510, 520, устройство 600 также может содержать процессорную схему и электронное запоминающее устройство, причем упомянутое запоминающее устройство сохраняет машинный код, выполняемый посредством процессорной схемы. Упомянутый машинный код конфигурирует устройство, например, реализует соответствующий способ. Альтернативные варианты осуществления могут реализовывать всю или часть функциональности в аппаратных средствах либо в гибридной схеме из аппаратных средств и программного обеспечения. Ниже задаются модули устройства 600; они могут рассматриваться в качестве модуля, который может реализовываться в программном обеспечении/аппаратных средствах и т.д. Устройство 600 выполнено с возможностью выбора параметров для использования в сетевом узле. В частности, параметры p, q и n, но также и другие параметры могут быть оптимизированы, например, h или B и т.д. Устройство 600 может использоваться проектировщиком криптографических протоколов, но устройство 600 также может использоваться в качестве части процедуры установления связи до выполнения одного или более протоколов согласования ключей, к примеру, как описано в данном документе.

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

Устройство 600 содержит формирователь 610 наборов параметров. Формирователь 610 наборов параметров выполнен с возможностью формировать несколько возможных наборов параметров. Например, наборы параметров включают в себя, по меньшей мере, первый математический модуль (q), второй математический модуль (p) и число (n) коэффициентов совместно используемого полинома (a). Формирователь 610 наборов параметров содержит модуль 620 выбора p, q, выполненный с возможностью формировать несколько пар первого математического модуля (q) и второго математического модуля (p). Например, модуль 620 выбора p, q может работать на основе нескольких возможных значений q и выбирать p согласно фиксированному пределу, например, как задано выше. Во втором случае, известный уровень шума вводится в операцию масштабирования. Тем не менее, это не является обязательным. Как p, так и q могут варьироваться независимо друг от друга. Проверки безопасности вариантов выбора затем должны отфильтровывать плохие комбинации p и q. Значения для p и q могут выбираться таким образом, что они являются практичными, например, как степень двух и в обоснованных пределах, например, между 7 и 16 битами и т.п.

Например, в варианте осуществления, q варьируется между (включительно) 2⁸ и 2¹⁶, p может варьироваться независимо от q; например, p может варьироваться между (включительно) 2⁴ и 2¹²; p также может выбираться как можно больше согласно пределу . Это должно обеспечивать то, что вводится шум, как указано посредством σ. Например, σ может выбираться в качестве или , или между ними. Больший уровень шума является хорошим для безопасности, поскольку меньший объем информации может извлекаться из данных, которыми обмениваются между узлами. С другой стороны, более высокий уровень шума увеличивает вероятность сбоя.

Устройство 600 дополнительно содержит оптимизатор 630 n, m. Оптимизатор 630 n, m выполнен с возможностью выполнять поиск безопасного числа (n) коэффициентов для данной пары математических модулей. Выбор безопасного n не является простым, поскольку он зависит от числа m сообщений, которые должен учитывать взломщик. Если взломщик учитывает только небольшое число сообщений, например, передаваемую информацию, такую как совместно используемый полином и открытые ключи, меньшее значение n является достаточным. По мере того, как m увеличивается, наименее безопасное значение для n должно увеличиваться. Тем не менее, в какой-то момент, учитывание большего числа сообщений приводит к гораздо большим усилиям от взломщика, при этом дополнительная информация, которую он может извлекать из дополнительных сообщений, не стоит увеличенной рабочей нагрузки. Другими словами, для любого данного n, p и q, имеется оптимальное число сообщений, которые следует учитывать взломщику.

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

Оптимизатор 630 n, m разрешает эту проблему следующим образом. Он выполнен с возможностью сначала инициализировать число (n) коэффициентов и число (m) выборок, используемых взломщиком (m). Например, n может задаваться равным n_min, скажем, 100, а m - равным m_min, скажем, 0 или 1.

С учетом настройки, оптимизатор 630 n, m определяет то, является набор защищенным или нет. Если он не является защищенным, он увеличивает n; если он является защищенным, он увеличивает m. Процесс завершается, когда m достигает некоторого максимального значения m_max. В этот момент, найдено n, которое является защищенным для всего обоснованного числа m сообщений. При условии, что длинное n является достаточно большим, в конечном счете, система должна быть защищенной. Чтобы не допускать слишком длительного выполнения алгоритма, максимальное значение n также может принудительно активироваться, скажем, 1000 битов или порядка этого.

В этот момент, находится тройное n, p, q, которое является защищенным. Тем не менее, может возникать такая ситуация, что набор имеет слишком низкую вероятность достижения успешного совместно используемого ключа. Далее, устройство 600, например, формирователь 610 наборов параметров верифицирует функциональную корректность набора параметров. Если функциональная корректность не верифицируется (например, слишком низкая вероятность успешности), набор параметров отбрасывается; если функциональная корректность верифицируется, набор параметров может добавляться в список. Поиск может теперь продолжаться для новой пары математических модулей.

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

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

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

Способ 650 содержит формирование 660 нескольких возможных наборов параметров, причем набор параметров включает в себя, по меньшей мере, первый математический модуль q, второй математический модуль p и число n коэффициентов совместно используемого полинома a. Например, формирование набора параметров может осуществляться согласно блок-схеме последовательности операций способа в правой части фиг. 6b.

Формирование 660 может содержать формирование 661 нескольких пар первого математического модуля q и второго математического модуля p. Затем пара математических модулей анализируется на предмет безопасности посредством поиска безопасного числа n коэффициентов для пары. Этот анализ может содержать инициализацию 662 числа m коэффициентов и числа m выборок, используемых взломщиком m.

Затем, на этапе 664 принятия решения определяется то, является возможной или нет атака на набор параметров с данной парой, числом n коэффициентов и числом m выборок.

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

Если атака является невозможной, то алгоритм продолжается на 668 с увеличением числа m выборок.

В обоих случаях, алгоритм возвращается на этап 664 задерживания.

Если число m выборок превышает максимальное число выборок, например, как также может определяться в части 668, то алгоритмы продолжают верифицировать 669 функциональную корректность набора параметров.

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

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

Фиг. 5 схематично показывает пример варианта осуществления сети 500 согласования ключей. Сеть 500 согласования ключей основана, содержит узел-инициатор 510 и узел-ответчик 520. Сеть 500 согласования ключей, узел-инициатор 510 и узел-ответчик 520 основаны на сети 100 согласования ключей, узле-инициаторе 110 и узле-ответчике 120. Сети 500 и 100 могут использовать идентичные или аналогичные базовые кольца, параметры и т.п. Важное различие между сетью 500 и сетью 100 заключается в том, что во второй совместно используемый ключ основан на необработанном ключе, который формирует каждая сторона, но в сети 500 совместно используемый ключ является независимым от него. В нижеприведенном варианте осуществления, предполагается, что совместно используемый ключ формируется посредством узла-ответчика 520, но это не является ограничивающим. Фактически, любой ключ может совместно использоваться с использованием этого механизма. Например, совместно используемый ключ может получаться из дополнительного источника, например, из некоторого другого протокола или из устройства хранения данных и т.д. Например, ключ может объединенно формироваться и т.д.

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

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

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

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

Например, один способ инкапсулировать совместно используемый ключ заключается в следующем. Во-первых, модуль 570 обработки совместно используемых ключей формирует совместно используемый ключ 573 (или иным способом получает ключ, который должен совместно использоваться). Совместно используемый ключ 573 кодируется. Первый способ кодировать совместно используемый ключ состоит в том, чтобы умножать его на половину второго математического модуля p/2. Второй способ состоит в том, чтобы использовать код с коррекцией ошибок.

Результирующий кодированный совместно используемый ключ суммируется с необработанным ключом 262. Например, можно рассматривать совместно используемый ключ 262 в качестве полинома с коэффициентами по модулю p. В этом случае, можно выбирать код с коррекцией ошибок в качестве кода с повторениями по Z_p. На другой стороне, узел 510 содержит модуль 560 совместного использования ключей, выполненный с возможностью вычитать необработанный ключ 162 из принимаемого инкапсулированного ключа 576, чтобы восстанавливать кодированный ключ 564. Он должно отличаться от кодированного ключа 574 вследствие разностей между необработанными ключами 162 и 262. Поскольку результирующий кодированный ключ содержит достаточную информацию, так что исходный кодированный совместно используемый ключ зачастую может реконструироваться. Рассмотрим пример, в котором узел 520 умножает совместно используемый ключ. При этом, узел 510 должен находить значения, близкие к нулю, если исходный кодированный совместно используемый ключ имеет нуль, и значения, близкие к p/2, если исходный кодированный совместно используемый ключ имеет p/2. Декодер на основе жесткого решения в узле 510 может преобразовывать вычитание в ближайшие значения.

Большая гарантия получения идентичного совместно используемого ключа может получаться посредством использования кода с коррекцией ошибок. Например, совместно используемый ключ 573 может кодироваться побитово в код с коррекцией ошибок. Можно также транслировать большие блоки совместно используемого ключа 573 за один раз. Например, можно преобразовывать нулевой бит в совместно используемом ключе 573 в (0, 0, 0) и 1 бит в . В этом случае, совместно используемый ключ 573 составляет примерно 1/3 длины необработанного ключа 262. Незначительные разности в длине могут разрешаться с помощью дополнения. Этот код с повторениями может декодироваться с помощью мажоритарного декодирования. Лучший результат получается посредством суммирования трех значений, соответствующих идентичному биту в совместно используемом ключе. Без ошибок, последний должно быть равным 0 или 3p/2; посредством преобразования в ближайшее значение, получается лучшее декодирование. Скорректированный кодированный совместно используемый ключ может преобразовываться в совместно используемый ключ.

Преимущественно выбирать совместно используемый ключ 573 слишком длинным и впоследствии понижающе хешировать его до требуемой длины ключа, например, с использованием KDF. Например, если n равен 1024, можно рассматривать длину в битах совместно используемого ключа 573 в качестве 341 и впоследствии получать 128-битовый ключ из него. Другой подход заключается в том, чтобы сначала преобразовывать необработанный ключ 262 в двоичную строку. Например, извлечение B битов из каждого коэффициента и конкатенация результата. Это имеет такое преимущество, что может использоваться гораздо меньший код.

Ниже приводится возможный вариант осуществления:

KEX-инициатор		KEX-ответчик
Согласует свежий с равноправным узлом, выбирает свежий секретный , таким образом, что и .		Согласует свежий с равноправным узлом, выбирает свежий секретный , таким образом, что и .
.		.
		.
		Кодирование случайного ключа K с помощью кода с коррекцией ошибок, чтобы получать Encoded_K Вычисление K' = Encoded_K+ по модулю p
.
K''=K '- Коррекция ошибок K'' и декодирование для того, чтобы получать K

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

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

Типично, устройства 110, 210, 510, 520, 600 содержат микропроцессор (не показан отдельно на фиг. 1), который выполняет надлежащее программное обеспечение, сохраненное в устройствах 110, 210, 510, 520, 600; например, это программное обеспечение, возможно, загружено и/или сохранено в соответствующем запоминающем устройстве, например, в энергозависимом запоминающем устройстве, к примеру, в RAM, или в энергонезависимом запоминающем устройстве, к примеру, во флэш-памяти (не показана отдельно). Альтернативно, устройства 110, 210, 510, 520, 600 могут, полностью или частично, реализовываться в программируемой логике, например, в качестве программируемой пользователем вентильной полинома (FPGA). Устройства 110, 210, 510, 520, 600 могут реализовываться, полностью или частично, в качестве так называемой специализированной интегральной схемы (ASIC), т.е. интегральной схемы (IC), специально разработанной для конкретного использования. Например, схемы могут реализовываться в CMOS, например, с использованием языка описания аппаратных средств, такого как Verilog, VHDL и т.д.

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

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

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

Способ 400 содержит:

- приспособление (410) цифровой связи между первым сетевым узлом и вторым сетевым узлом,

- получение (420) совместно используемого полинома (a), причем совместно используемый полином совместно используется со вторым сетевым узлом через цифровую связь, причем коэффициенты совместно используемого полинома a выбираются по модулю первый математический модуль q,

- формирование (430) полинома (sk_L) закрытых ключей, причем коэффициенты полинома закрытых ключей ограничиваются по абсолютному значению посредством предела (s),

- формирование (440) полинома (pk_L) открытых ключей посредством следующего:

- вычисление (442) полиномиального произведения между совместно используемым полиномом (a) и полиномом (sk_L) закрытых ключей по модулю первый математический модуль (q), с получением полиномиального произведения, с последующим приведением по модулю полином приведения,

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

- отправка (452) полинома открытых ключей первого сетевого узла во второй сетевой узел,

- прием (454) полинома (pk_R) открытых ключей второго сетевого узла,

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

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

- прием (472) сверочных данных (h) второго сетевого узла,

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

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

- получение (474) совместно используемого ключа и сверочных данных из необработанного ключа,

- отправка (484) сверочных данных в первый сетевой узел.

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

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

Способ согласно изобретению может осуществляться с использованием программного обеспечения, которое содержит инструкции для инструктирования процессорной системе осуществлять способ 400 или 650. Программное обеспечение может включать в себя только этапы, выполняемые посредством конкретного подобъекта системы. Программное обеспечение может сохраняться на подходящем носителе хранения данных, к примеру, на жестком диске, на дискете, в запоминающем устройстве, на оптическом диске и т.д. Программное обеспечение может отправляться в качестве сигнала проводным или беспроводным способом либо с использованием сети передачи данных, например, Интернета. Программное обеспечение может становиться доступным для загрузки и/или для удаленного использования на сервере. Способ согласно изобретению может осуществляться с использованием потока битов, выполненного с возможностью конфигурировать программируемую логику, например, программируемую пользователем вентильную матрицу (FPGA), с тем чтобы осуществлять способ.

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

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

Фиг. 4b показывает схематичное представление процессорной системы 1140 согласно варианту осуществления, например, в качестве первого или второго сетевого узла. Процессорная система содержит одну или более интегральных схем 1110. Архитектура одной или более интегральных схем 1110 схематично показана на фиг. 4b. Схема 1110 содержит модуль 1120 обработки, например, CPU, для выполнения компьютерных программных компонентов, чтобы осуществлять способ согласно варианту осуществления и/или реализовывать его модули или блоки. Схема 1110 содержит запоминающее устройство 1122 для сохранения программного кода, данных и т.д. Часть запоминающего устройства 1122 может быть неперезаписываемой. Схема 1110 может содержать элемент 1126 связи, например, антенну, разъемы либо и то, и другое и т.п. Схема 1110 может содержать специализированную интегральную схему 1124 для выполнения части или всей обработки, заданной в способе. Процессор 1120, запоминающее устройство 1122, специализированная IC 1124 и элемент 1126 связи могут соединяться между собой через межкомпонентное соединение 1130, скажем, шину. Процессорная система 1110 может быть выполнена с возможностью контактной и/или бесконтактной связи, с использованием антенны и/или разъемов, соответственно.

Машиночитаемый носитель 1000 или процессорная система 1140 также могут быть сконфигурированы для способа выбора параметров.

Например, в варианте осуществления, сетевой узел может содержать процессорную схему и запоминающую схему, причем процессор выполнен с возможностью выполнять программное обеспечение, сохраненное в запоминающей схеме. Например, процессорная схема может представлять собой процессор Intel Core i7, ARM Cortex-R8 и т.д. В варианте осуществления, процессорная схема может представлять собой ARM Cortex M0. Запоминающая схема может представлять собой ROM-схему или энергонезависимое запоминающее устройство, например, флэш-память. Запоминающая схема может представлять собой энергозависимое запоминающее устройство, например, запоминающее SRAM-устройство. Во втором случае, устройство верификации может содержать энергонезависимый программный интерфейс, например, жесткий диск, сетевой интерфейс и т.д., выполненный с возможностью предоставления программного обеспечения.

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

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

Раздел 1. Первый электронный сетевой узел (110), сконфигурированный для протокола согласования ключей, причем первый сетевой узел содержит:

- интерфейс (120) связи, выполненный с возможностью цифровой связи со вторым сетевым узлом, и

- процессорную схему, выполненную с возможностью:

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

- формировать полином (sk_L; sk_R) закрытых ключей, причем коэффициенты полинома закрытых ключей ограничиваются по абсолютному значению посредством предела (s),

- формировать полином (pk_L; pk_R) открытых ключей посредством следующего:

- вычисление полиномиального произведения между совместно используемым полиномом (a) и полиномом (sk_L) закрытых ключей по модулю первый математический модуль (q), с получением полиномиального произведения,

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

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

- принимать полином (pk_R; pk_L) открытых ключей второго сетевого узла,

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

Раздел 2. Электронный способ (400) согласования ключей для первого электронного сетевого узла (110), при этом способ содержит:

- приспособление (410) цифровой связи между первым сетевым узлом и вторым сетевым узлом,

- получение (420) совместно используемого полинома (a), причем совместно используемый полином совместно используется со вторым сетевым узлом через цифровую связь, причем коэффициенты совместно используемого полинома a выбираются по модулю первый математический модуль q,

- формирование (430) полинома (sk_L) закрытых ключей, причем коэффициенты полинома закрытых ключей ограничиваются по абсолютному значению посредством предела (s),

- формирование (440) полинома (pk_L) открытых ключей посредством следующего:

- вычисление (442) полиномиального произведения между совместно используемым полиномом (a) и полиномом (sk_L) закрытых ключей по модулю первый математический модуль (q), с получением полиномиального произведения,

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

- отправка (452) полинома открытых ключей первого сетевого узла во второй сетевой узел,

- прием (454) полинома (pk_R) открытых ключей второго сетевого узла,

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

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

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

1. Первый электронный сетевой узел (110), сконфигурированный для протокола согласования ключей, причем первый сетевой узел содержит:

интерфейс (120) связи, выполненный с возможностью цифровой связи со вторым сетевым узлом, и

процессорную схему, выполненную с возможностью:

получать совместно используемый полином (a), причем совместно используемый полином совместно используется со вторым сетевым узлом через интерфейс связи, при этом коэффициенты совместно используемого полинома (a) выбираются по модулю первая абсолютная величина q,

формировать полином (sk_L; sk_R) конфиденциальных ключей, причем коэффициенты полинома конфиденциальных ключей ограничиваются по абсолютному значению пределом (s), при этом предел (s) меньше второй абсолютной величины (p), причем вторая абсолютная величина (p) меньше первой абсолютной величины (q),

формировать полином (pk_L; pk_R) общедоступных ключей посредством следующего:

– вычисление полиномиального произведения между совместно используемым полиномом (a) и полиномом (sk_L) конфиденциальных ключей по модулю первая абсолютная величина (q), с получением полиномиального произведения,

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

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

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

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

принимать сверочные данные (h) второго сетевого узла,

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

при этом первый сетевой узел дополнительно выполнен с возможностью:

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

отправлять сверочные данные во второй сетевой узел.

2. Первый сетевой узел по п.1, при этом первый сетевой узел дополнительно выполнен с возможностью:

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

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

при этом первый сетевой узел дополнительно выполнен с возможностью:

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

отправлять вспомогательные данные во второй сетевой узел.

3. Первый сетевой узел по любому из предшествующих пунктов, в котором предел (s) по абсолютному значению для коэффициентов полинома (sk_L, sk_R) конфиденциальных ключей равен 2 (s=2) или в котором предел равен 1 (s=1), причем второе соответствует двоичному значению со знаком.

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

полином (sk_L) конфиденциальных ключей формируется самое большее с числом (h_s) ненулевых коэффициентов или

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

5. Первый сетевой узел по любому из предшествующих пунктов, при этом первая абсолютная величина (q) делится на вторую абсолютную величину (p).

6. Первый сетевой узел по любому из предшествующих пунктов, при этом вторая абсолютная величина (p) и/или первая абсолютная величина (q) является степенью 2.

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

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

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

10. Первый сетевой узел по любому из предшествующих пунктов, в котором:

первая абсолютная величина (q) имеет в качестве размера в битах 12 или более и/или

вторая абсолютная величина (p) имеет в качестве размера в битах 7 или более.

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

12. Способ (400) согласования электронных ключей для первого электронного сетевого узла (110), при этом способ содержит этапы, на которых:

обеспечивают (410) цифровую связь между первым сетевым узлом и вторым сетевым узлом;

получают (420) совместно используемый полином (a), причем совместно используемый полином совместно используется со вторым сетевым узлом через цифровую связь, при этом коэффициенты совместно используемого полинома a выбираются по модулю первая абсолютная величина q;

формируют (430) полином (sk_L) конфиденциальных ключей, причем коэффициенты полинома конфиденциальных ключей ограничиваются по абсолютному значению пределом (s), при этом предел (s) меньше второй абсолютной величины (p), причем вторая абсолютная величина (p) меньше первой абсолютной величины (q);

формируют (440) полином (pk_L) общедоступных ключей посредством следующих этапов, на которых:

- вычисляют (442) полиномиальное произведение между совместно используемым полиномом (a) и полиномом (sk_L) конфиденциальных ключей по модулю первая абсолютная величина (q), с получением полиномиального произведения,

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

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

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

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

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

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

при этом способ дополнительно содержит этапы, на которых:

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

отправляют вспомогательные данные во второй сетевой узел.

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