Протоколы инкапсуляции ключей

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

 

ОБЛАСТЬ ТЕХНИКИ

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

УРОВЕНЬ ТЕХНИКИ

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

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

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

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

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

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

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

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

Цитируемая литература:

RLWE: «On Ideal Lattices and Learning with Errors Over Rings», by Vadim Lyubashevsky, Chris Peikert, and Oded Regev,

RLWR: «Pseudorandom Functions and Lattices», by Abhishek Banerjee, Chris Peikert, and Alon Rosen,

LWE: «On Lattices, Learning with Errors, Random Linear Codes, and Cryptography», by Oded Regev.

LWR: «Pseudorandom Functions and Lattices», by Abhishek Banerjee, Chris Peikert, and Alon Rosen,

Hila5: «HILA5: On Reliability, Reconciliation, and Error Correction for Ring-LWE Encryption», by Markku-Juhani O. Saarinen

Round2: «Round2: KEM and PKE based on GLWR», by Hayo Baan, Sauvik Bhattacharya, Oscar Garcia-Morchon, Ronald Rietman, Ludo Tolhuizen, Jose-Luis Torre-Arce, and Zhenfei Zhang

Эта литература включена в настоящий документ путем ссылки.

РАСКРЫТИЕ СУЩНОСТИ ИЗОБРЕТЕНИЯ

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

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

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

- формирования второго закрытого ключа, кодового слова в соответствии с кодом с исправлением ошибок и формирования второго открытого ключа из второго закрытого ключа,

- формирования второго необработанного общего ключа из первого открытого ключа и второго закрытого ключа,

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

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

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

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

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

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

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

- формирования первого необработанного общего ключа из второго открытого ключа и первого закрытого ключа,

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

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

- применения функции исправления ошибок к почти кодовому слову с получением кодового слова.

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

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

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

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

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

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

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

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

Первое и второе криптографические устройства могут быть электронными устройствами. Например, они могут быть компьютерами. Они могут быть мобильными электронными устройствами, например мобильным телефоном, смарт-картой. Первое и второе криптографические устройства могут быть потребительской электроникой, например телеприставкой, телевизором.

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

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

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

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

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

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

на Фиг. 1 схематически показан пример протокола KEX,

на Фиг. 2 схематически показан пример протокола KEM,

на Фиг. 3 схематически показан пример протокола KEM,

на Фиг. 4 схематически показан пример протокола KEM,

На Фиг. 5a схематически показан пример варианта реализации протокола шифрования с открытым ключом (PKE),

на Фиг. 5b схематически показан пример варианта реализации протокола KEM,

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

На Фиг. 7a схематически показан пример варианта реализации устройства 100 первой стороны,

На Фиг. 7b схематически показан пример варианта реализации устройства 200 второй стороны,

На Фиг. 7c схематически показан пример варианта реализации криптографической системы 101.

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

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

на Фиг. 9 схематически показан пример формирования секрета в соответствии с вариантом реализации,

на Фиг. 10 схематически показан пример криптографической системы в соответствии с вариантом реализации,

на Фиг. 11a схематически показан пример криптографического способа в соответствии с вариантом реализации,

на Фиг. 11b схематически показан пример криптографического способа в соответствии с вариантом реализации.

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

Список ссылочных позиций:

10 - первая сторона

20 - вторая сторона

100 - устройство первой стороны

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

191 - компьютерная сеть

192 - интерфейс хранилища

194 - процессор

196 - память

200 - устройство второй стороны

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

292 - интерфейс хранилища

294 - процессор

296 - память

300 - первое криптографическое устройство

301 - криптографическая система

302 - депозитарий открытых ключей

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

315 - генератор открытых/закрытых ключей

320 - средство исправления ошибок

325 - блок Диффи-Хеллмана

335 - блок согласования

340 - блок декапсуляции

350 - второе криптографическое устройство

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

360 - получатель открытых ключей

365 - генератор открытых/закрытых ключей

370 - генератор кодовых слов

375 - блок Диффи-Хеллмана

380 - генератор надежных битов

385 - генератор данных согласования

390 - инкапсулятор

1000 - компьютерочитаемый носитель

1010 - выполненная с возможностью записи часть

1020 - компьютерная программа

1110 - интегральная (-ые) схема (-ы)

1120 - блок обработки

1122 - память

1124 - специализированная интегральная схема

1126 - элемент связи

1130 - межсоединение

1140 - процессорная система

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

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

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

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

Мы представляем протокол KEM, который использует KEX-ключ k для инкапсуляции случайного ключа K, определенного второй частью, а также битами четности в K. В вариантах реализации используют KEX для инкапсуляции и функцию надежных битов для снижения вероятности отказа. Поскольку для инкапсуляции используют ключ KEX, можно обмениваться вспомогательными данными, что налагает низкие требования на пропускную способность и снижает вероятность отказа. Благодаря инкапсуляции можно достичь активной защиты. Поскольку биты четности тоже инкапсулируют, то, опять же, можно достичь более хорошей вероятности отказа. В приведенных ниже вариантах реализации мы будем ссылаться на функцию safe_bits, но это может быть любая функция надежных битов.

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

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

При выборе надежных битов делают допущение, что не все биты, заданные размерностью кольца, нужны для ключей. Как правило, размерность лежащих в основе полиномов/матриц намного больше требуемой длины ключа. Например, вторая сторона может выбрать m индексов в , которые, скорее всего, будут согласованы. Эти безопасные коэффициенты могут быть коэффициентами, наиболее близкими к центральным точкам диапазонов коэффициентов, которые отображаются в нулевой бит или в единичный бит; k = 0 и k = 1. Например, в кольце по модулю q коэффициент может быть отображен в 0, если находится в диапазоне , и в 1, если находится в диапазоне находится в диапазоне , или наоборот. Если не находится ни в одном их этих двух диапазонов, он не является надежным битом. Значение определяет, в частности, надежность битов. Например, в этом случае оно может быть выбрано как ; меньшие значения для обеспечивают более высокую надежность, но меньше битов ключа. В данном случае центральными точками могут быть и или их округленные значения.

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

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

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

На Фиг. 1 схематически показан пример протокола KEX. Примером этого протокола являются spKEX или Frodo.

На Фиг. 2 схематически показан пример протокола KEM. Примером этого протокола является CPA-PKE-версия Round2 или NewHope Simple.

На Фиг. 3 схематически показан пример протокола KEM с исправлением ошибок.

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

На фигурах использованы следующие обозначения:

- a представляет главную копию секрета, например, полином в данном кольце (например, как в RLWE или RLWR) или матрицу с элементами в целых числах (например, как в LWE или LWR).

- r и s представляют секреты первой стороны и второй стороны.

- b и u представляют «открытые» общие части ключа первой стороны и второй стороны, показанные как произведение a*r или a*s. Это представление операции фактически означает однонаправленную функцию лежащей в основе задачи. Операция звездочка (*) выводит новый математический объект из двух исходных объектов, вводя при этом некоторый шум. Например, операция звездочка может быть полиномиальным или матричным произведением; например, шум может быть введен путем добавления элементов шума или неявно, например за счет округления. Примеры операции звездочка можно найти в том, что может представлять собой (R)LWE или (R)LWR либо их модульная версия. Например, a*r может означать Round( (A*r (mod q)), p, q), например, как в LWR. Это означает произведение r, являющегося вектором длины n, на квадратную матрицу A размера n×n по модулю q. Затем результат округляют с помощью целых чисел p и q, где p < q путем выполнения p/q (A*r (mod q).

- c представляет шифртекст.

- h представляет вспомогательные данные, содержащие биты согласования.

- parity_bits относится к информации, используемой для исправления ошибок.

- get_reconciliation(k) является функцией, которая возвращает биты согласования из необработанного ключа k.

- reconciliate(k,h) является функцией, которая согласует необработанный ключ k при данных битах согласования h.

- encapsulate(m,k) означает, что сообщение m инкапсулируют с помощью k. Например, если k принадлежит Z_q, то m тоже может быть представлено в Z_q. Если k принадлежит Z_2, то это эквивалентно XOR. Инкапсуляция может быть выполнена покомпонентно следующим образом:

c = k + m*(q/2) (mod q).

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

- decapsulate(c,k) означает, что шифртекст c декапсулируют из k, возвращающего битовую строку.

- obtain_parity_bits(k) означает, что получают некоторые биты четности k. Например, биты четности могут быть сформированы в соответствии с кодом с исправлением ошибок.

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

- safe_bits() возвращает два значения: (i) фактические надежные значения и (ii) позиции битов ключа, которые могут привести к более низкой вероятности отказа, поскольку полученные значения находятся дальше от границ количественного определения. Фактические значения, возвращаемые Safe_bits(), используют позже, например для инкапсуляции. Позициями обмениваются с другой стороной, чтобы она знала, какие позиции нужны.

KEX на Фиг.1 позволяет первой стороне и второй стороне вырабатывать общий ключ. Этот ключ имеет низкую вероятность отказа, поскольку первая сторона и вторая сторона обмениваются некоторыми битами согласования. Проблема KEX (Фиг. 1) состоит в том, что он делает возможным только один этап исправления ошибок, а именно, использование согласования ключа. Другая проблема KEX заключается в том, что ключи определяются только посредством r и s. В результате KEX не может достичь активной защиты для сообщений, которые нужно защитить.

KEM на Фиг. 2 позволяет второй стороне инкапсулировать случайный ключ на свой выбор при данном открытом ключе b первой стороны. Это позволяет достигать активной защиты. Проблема KEM (Фиг. 2) состоит в том, что он имеет только один этап для сокращения ошибок, обычно путем изменения коэффициента сжатия в шифртексте c. Желательно сжимать таким образом, чтобы требования к пропускной способности были ниже, например, если элементы, которые нужно инкапсулировать, принадлежат Z_q, то эти элементы могут быть перемещены в Z_t (где t > q). Однако, если t очень маленькое, вероятность ошибки возрастает.

KEM на Фиг. 3 позволяет второй стороне включать биты четности в ключ, который она хочет инкапсулировать. Таким образом, первая сторона может исправлять ошибки, которые могут возникать. Это снижает вероятность отказа. Отличие KEM с исправлением ошибок (Фиг. 3) состоит в том, что по сравнению с KEX инкапсулированные ключи принадлежат Z_q или Z_t, так что KEM эффективно инкапсулирует фактический ключ, определенный второй стороной. Однако это означает также, что KEM всегда будет иметь больше служебных данных, чем KEX.

Протокол, приведенный на Фиг. 4, представляет собой KEX, который использует ключ KEX вместе с исправлением ошибок. Хорошим свойством этой конструкции является то, что она позволяет добавлять код с исправлением ошибок, который, как в протоколе, показанном на Фиг. 3, снижает вероятность отказа. Поскольку это KEX, он может также использовать функцию safe_bits(), которая возвращает биты общего ключа k*, что приводит к снижению вероятности отказа. Проблемой протокола, приведенного на Фиг. 4, является то, что он не дает возможности активной защиты. Причина в том, что ключ определяется только посредством r и s.

На Фиг. 4 схематически показан вариант реализации протокола KEM, причем функция инкапсуляции может представлять собой, например, c = encapsulate () = (k1 | parity_bits(k1)) XOR (k2). Пример параметров для использования в протоколе, приведенном на Фиг. 4, в котором используют вышеуказанную функцию инкапсуляции:

- k1 имеет длину каппа битов, например 256 битов;

- биты четности составляют, например 121 бит;

- k2 имеет длину мю битов, например 121;

- C имеет длину parity_bits битов, например 121;

- H имеет длину (каппа + parity_bits)b_h битов, например 256 + 121.

На Фиг. 5a схематически показан пример варианта реализации протокола PKE. В протоколе PKE, приведенном на Фиг. 5, используют согласование ключа, исправление ошибок и безопасные биты.

Фиг. 5a ссылается на алгоритмы в приложении A для конкретных примеров реализации. Однако следует отметить, что алгоритмы 1, 2 и 3 описывают конкретный вариант реализации, который может быть реализован частично, например, с использование примитивов, аналогичных примитивам в RLWR. Тем не менее, протокол, показанный на Фиг. 5a, является более общим, поскольку операции a*s, a*r, b*s, u*r представляют многие различные основополагающие криптографические задачи, такие как LWR, MLWR, RLWR, LWE, MLWE или RLWE.

Функцией инкапсуляции может быть например, c = encapsulate () = (K | parity_bits(K)) XOR (k*). При таком выборе можно использовать следующие примеры параметров:

- K имеет длину каппа битов, например 256 битов;

- биты четности составляют, например 121 бит;

- K* имеет длину мю = каппа + parity_bits битов, например 256 + 121;

- c имеет длину мю битов, например 256 + 121;

- H имеет длину (каппа + parity_bits)b_h битов, например 256 + 121.

- Safe_bits: n битов.

В протоколе шифрования с открытым ключом, приведенном на Фиг. 5a, первая сторона 10 может формировать случайный объект a и r, например полином или матрицу. Соответствующий открытый ключ содержит их произведение b, полученное с помощью операции звездочка. Объект a может совместно использоваться двумя сторонами другим способом, но в варианте реализации как a, так и b являются частью открытого ключа. Чтобы зашифровать сообщение m, вторая сторона 20 может сформировать кратковременный закрытый ключ s и из него определить соответствующий открытый ключ, содержащий u. В PKE первая сторона 10 может повторно использовать свой открытый ключ, например a и b. Одни и те же a и b могут быть использованы многими сторонами 20 для шифрования сообщений для первой стороны 10. Следует отметить, что передача общего объекта может быть осуществлена путем передачи затравки, из которой можно сформировать a, например псевдослучайным образом.

Для использования подобного протокола в качестве KEM открытые ключи могут быть сформированы случайным образом на обеих сторонах. Такой протокол показан на Фиг. 5b.

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

Эта схема имеет следующие свойства:

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

- Как и в протоколах, приведенных на Фиг. 1 или Фиг. 4, это KEX, так что для выполнения согласования ключа и снижения вероятности отказа присоединяют биты согласования.

- Как и в протоколах, приведенных на Фиг. 3 и Фиг. 4 это позволяет внедрять биты четности, так что вероятность отказа дополнительно снижается.

- Инкапсуляция происходит в Z_2, поэтому служебные данные для инкапсуляции сведены к минимуму.

Например, достигаются следующие преимущества по сравнению с:

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

- Протоколом на Фиг. 2 в том, что новый протокол позволяет выбирать безопасные биты и исправление ошибок.

- Протоколом на Фиг. 3 в том, что новый протокол позволяет выбирать безопасные биты.

- Протоколом на Фиг. 4 в том, что новый протокол делает возможной активную защиту.

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

Протокол, приведенный на Фиг. 5a может быть применен к сообщениям , но также к ключу K. Например, ключ может быть сформирован на второй стороне. Пример такого применения показан на Фиг. 5b. Вариант реализации, например, показанный ниже на Фиг. 5b, может содержать следующие части:

- 1: Первая сторона получает секретный ключ r, открытый параметр a и общую часть b своего открытого ключа.

- 2: Первая сторона отправляет a и b. Первая сторона может также вместо этого отправлять затравку для получения а.

- 3: Вторая сторона получает свой секретный ключ s, вторая сторона случайным образом получает ключ K, который вторая сторона хочет тоже инкапсулировать. Затем вторая сторона получает общую часть u своего открытого ключа и главный ключ k*. Вторая сторона выполняет функцию безопасных битов на k*, чтобы получить биты в k*, которые являются наиболее подходящими, другими словами, которые, вероятно, приведут к меньшим отказам, поскольку их значения находятся дальше от границ принятия решения. Далее, она применяет функцию get_reconciliation() для получения материала согласования ключа для выбранных безопасных битов. После этого вторая сторона получает биты четности для сформированного K. Биты четности получают с использованием выбранного способа исправления ошибок. Затем вторая сторона переходит к инкапсуляции двоичной строки битов, содержащей (например, состоящей из) ключ K и биты четности с ключом k, поступающим из обмена ключами. В данном случае инкапсуляция означает побитовое применение операции XOR, поскольку элементы ключа принадлежат Z_2. Это шифртекст c.

- 4: Вторая сторона должна отправить первой стороне общую часть u открытого ключа, вспомогательные данные h и шифртекст c. Вторая сторона должна также включить безопасные биты.

- 5: Первая сторона переходит к получению K, сначала получив свой необработанный ключ k'. Затем она согласовывает ключ при имеющихся необработанном ключе, вспомогательных данных и местоположении безопасных битов. С помощью этой информации первая сторона может теперь декапсулировать и получить оценку (K|Parity_bits(K)), к которой она применяет функцию исправления ошибок error_correct() для удаления потенциальных ошибок. Первая сторона получает K.

См. Фиг. 6. Отметим, что с учетом этого стандартного блока можно:

- Задать на его основе indCPA-KEM путем хэширования K. Это можно сделать точно так же, как в Round2.

- Задать на его основе indCCA-KEM путем применения стандартного преобразования, такого как преобразование Фуджисаки-Окамото (Fujisaki-Okamoto, FO). Это идентично тому, что делают в Round2.

На Фиг. 9 схематически показан пример формирования секрета в соответствии с вариантом реализации.

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

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

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

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

Полученный секрет может быть сохранен в памяти. Генератор может выполняться на ЦП компьютера.

Детерминистический способ

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

Секрет s с компонентами будет иметь значений и значений , где для .

Количество ненулевых элементов в s называется и задается как .

Последовательность ненулевых элементов называется и содержит значения .

Кроме того, s будет иметь значений 0, где .

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

Генератор инициализирует вектор размерности нулями.

С учетом значений генератор случайным образом формирует последовательность с ровно разными целыми числами в диапазоне от до . Затем генератор присваивает значения в s в соответствии со значениями в :

значение в позициям вектора в , индексированным первыми значениями в ,

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

…

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

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

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

…

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

Вероятностный способ

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

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

Генератор инициализирует вектор размерности нулями.

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

Вектор обновляют в соответствии со следующим псевдокодом.

Таблица 1. Псевдокод для второго способа

seed = obtain_true_random_seed() R = generate_2_h1_pseudo_random_values(seed); s = 0; // первая часть в наборе P For i = 0 to h1-1 { s[R[i]] = s[R[i]] + 1; } // вторая часть в наборе P For i = 0 to h1-1 { s[R[i+h1]] = s[R[i+h1]] - 1; }

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

В этом третьем варианте реализации

вычисляют векторов , каждый длины с коэффициентами {0,1}, причем каждый вектор ровно с ненулевыми элементами, где p является вероятностью того, что коэффициент равен 1. Для этого можно случайным образом выбрать разных значений в [0, n - 1], которым будет присвоено значение 1.

вычисляют k/2 векторов длины с коэффициентами {0,1}, причем каждый вектор ровно с ненулевыми элементами, где p является вероятностью того, что коэффициент равен 1. Для этого можно случайным образом выбрать разных значений в [0, n - 1], которым будет присвоено значение 1.

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

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

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

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

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

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

. Тогда

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

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

. Тогда

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

3. Функция согласования :

Для ,

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

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

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

На Фиг. 7a схематически показан пример варианта реализации устройства 100 первой стороны. На Фиг. 7b схематически показан пример варианта реализации устройства 200 второй стороны. На Фиг. 7c схематически показан пример варианта реализации криптографической системы 101, содержащей первое устройство 100 и второе устройство 200. Первое устройство 100, второе устройство 200 могут содержать одно или более из интерфейса 192, 292 хранилища, процессора 194, 294 и памяти 196, 296, соответственно.

Первое устройство 100 и второе устройство 200, например, разные устройства системы 101, могут обмениваться данными друг с другом по компьютерной сети 191. Компьютерная сеть может быть интернетом, интрасетью, ЛВС, БЛВС и т.д. Компьютерная сеть 191 может быть Интернетом. Компьютерная сеть может быть полностью или частично проводной и/или полностью или частично беспроводной. Например, компьютерная сеть может содержать соединения Ethernet. Например, компьютерная сеть может содержать беспроводные соединения, такие как Wi-Fi, ZigBee и т.п. Устройства содержат интерфейс соединения, который выполнен с возможностью обмена данными с другими устройствами системы 101 при необходимости. Например, интерфейс соединения может содержать разъем, например, проводной разъем, например, разъем Ethernet, или беспроводной разъем, например, антенну, например, антенну Wi-Fi, 4G или 5G. Например, первое устройство 100 и второе устройство 200 могут содержать интерфейс 130, 230 связи, соответственно. Компьютерная сеть 191 может содержать дополнительные элементы, например, маршрутизатор, концентратор и т.д.

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

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

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

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

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

Как правило, каждое из устройств 100 и 200 содержит микропроцессор, который исполняет надлежащее программное обеспечение на устройствах 100 и 200; например, это программное обеспечение могло быть загружено и/или сохранено в соответствующей памяти, например, энергозависимой памяти, такой как ОЗУ, или энергонезависимой памяти, такой как флэш-память. В альтернативном варианте реализации устройства 100 и 200 полностью или частично реализованы в программируемой логике, например, такой как программируемая пользователем вентильная матрица (FPGA). Устройства 100 и 200 могут быть реализованы, полностью или частично, в виде так называемой специализированной интегральной схемы (ASIC), например, интегральной схемы (ИС), изготовленной на заказ для ее конкретного применения. Например, схемы могут быть реализованы в КМОП, например, с использованием языка описания аппаратных средств, такого как Verilog, VHDL и т.д.

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

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

Схемы могут также представлять собой FPGA, ASIC и т. п.

На Фиг. 10 схематически показан пример криптографической системы 301 в соответствии с вариантом реализации. Система 301 содержит первое криптографическое устройство 300, второе криптографическое устройство 350 и, необязательно, депозитарий 302 открытых ключей. Например, первое устройство 300 и второе устройство 350 на устройстве, таком как первое устройство 100 и/или второе устройство 200.

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

Например, первое и второе устройства могут быть сконфигурированы для протокола выработки общего ключа, например, выполнены с возможностью формирования ключа, как правило, симметричного ключа, который является общим для двух устройств. Тогда общий ключ может быть использован устройствами для защиты обмена данными, например, шифрованного и/или использующего проверку подлинности обмена данными, например, путем использования ключа для шифрования сообщений и/или для вычисления метки проверки подлинности для сообщения. Протокол может быть протоколом шифрования с открытым ключом, например, выполненным с возможностью предоставления другим устройствам, скажем, второму устройству 350, возможности шифрования сообщения (m) так, что конкретное устройство, скажем, первое устройство 300, может расшифровать его. Однако содержимое зашифрованных открытым ключом сообщений не может быть получено другими устройствами, кроме зашифровывающего и расшифровывающего устройства, например, второго устройства 350 и первого устройства 300. В случае шифрования с открытым ключом один и тот же открытый ключ первого устройства, например, одни и те же первый открытый ключ и открытый объект, могут быть использованы множеством вторых устройств для отправки зашифрованных сообщений первому открытому устройству. Даже если два вторых устройства используют один и тот же открытый ключ для шифрования сообщения, они не могут расшифровать обмен данными один другого.

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

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

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

Первый открытый ключ передают с первого устройства 300 на второе устройство 350, например, посредством интерфейсов 305 и 355 связи. Это можно сделать прямым обменом данных или опосредованно, например, через депозитарий 302 открытых ключей. Вместе с первым открытым ключом также может быть передан открытый объект (a), если требуется. Например, открытый объект может быть передан путем отправки затравки, из которой может быть сформирован открытый объект (a).

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

Второе устройство 350 может содержать генератор 365 открытых/закрытых ключей, выполненный с возможностью формирования второго закрытого ключа (s) и формирования первого открытого ключа (u), выводимого из второго закрытого ключа (s). Второй открытый ключ использует тот же самый открытый объект, который использовали при формировании первого открытого ключа. Первый и второй закрытые ключи являются закрытыми для их соответствующих устройств. Они могут совместно использоваться доверенными сторонами, если требуется, например, для резервного копирования, депонирования ключа и т.д. Открытые ключи и открытый объект не обязательно являются секретными для безопасности; тем не менее, один или более из них все же могут быть закрытыми для первого и второго устройства, если требуется. Например, первый открытый ключ может совместно использоваться только со вторым устройством, и наоборот.

Второе устройство 350 содержит генератор 370 кодовых слов. Генератор 370 кодовых слов выполнен с возможностью формирования кодового слова в соответствии с кодом с исправлением ошибок. Код с исправлением ошибок может быть линейным кодом или нелинейным кодом. Например, код с исправлением ошибок может быть кодом БЧХ, кодом Рида-Соломона, кодом Адамара и т.п. Могут быть конкатенированы несколько кодов. Конкатенированные коды являются кодами с исправлением ошибок, которые построены из двух или более менее сложных кодов для достижения хороших рабочих характеристик при разумной сложности. Например, кода Адамара может быть конкатенирован с кодом БЧХ.

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

Кодовое слово может быть использовано различными способами. Например, сообщение, которое должно быть доставлено от второго устройства 350 первому устройству 300, может быть закодировано в относящейся к данным части кодового слова как данные, подлежащие инкапсуляции. Такой способ кодирования подходит, например, для шифрования с открытым ключом. Шифрование с открытым ключом может быть также получено путем шифрования сообщения (m) на втором устройстве 350, например, симметричным ключом, например, формируемым случайным образом для этой цели, и кодирования симметричного ключа шифрования в кодовом слове. Может быть использован дополнительный этап вывода ключа. Например, в кодовом слове может быть закодирован случайный предварительный ключ, а ключ шифрования может быть выведен из предварительного ключа. Например, при выводе может быть использована функция выработки производного ключа (Key Derivation Function, KDF), например хэш-функция. Например, в последнем случае зашифрованное сообщение может быть отправлено от второго устройства первому устройству вместе с требуемыми данными для расшифрования данных, например, со вторым открытым ключом, и другими данными, как описано ниже.

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

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

Второе устройство 350 содержит блок 375 Диффи-Хеллмана. Блок 375 Диффи-Хеллмана выполнен с возможностью формирования второго необработанного общего ключа (k*) из первого открытого ключа (b) и второго закрытого ключа (s). Например, блок 375 Диффи-Хеллмана может быть выполнен с возможностью применения функции Диффи-Хеллмана к первому открытому ключу и второму закрытому ключу. Например, функция Диффи-Хеллмана может быть умножением или возведением в степень в зависимости от лежащего в основе механизма. Второе устройство 350 выполнено с возможностью передачи своего второго открытого ключа первому устройству 300. Первое устройство 300 содержит блок 325 Диффи-Хеллмана. Блок 325 Диффи-Хеллмана выполнен с возможностью формирования первого необработанного общего ключа (k’) из второго открытого ключа (u) и первого закрытого ключа (r), например путем применения той же самой функции Диффи-Хеллмана. К сожалению, для некоторых типов функции Диффи-Хеллмана может случиться так, что первый и второй ключи будут близки друг к другу, хотя и не обязательно идентичны. Практическая вероятность того, что это случится, зависит от лежащей в основе функции Диффи-Хеллмана. Некоторая вероятность разных необработанных ключей может быть допустима в большинстве областей применения, однако, насколько высокой может быть эта вероятность, будет зависеть от области применения. Однако, как правило, предпочтительной будет более низкая вероятность. Необработанный ключ может быть того же математического типа, например, полиномом или матрицей, что и закрытый и открытый ключи.

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

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

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

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

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

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

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

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

Первое устройство 300 выполнено с возможностью приема от второго устройства второго открытого ключа (u), данных согласования (h) и инкапсулированных данных (c) и надежных индексов. Первое устройство 300 содержит блок 335 согласования, выполненный с возможностью применение данных согласования (h) в функции согласования к коэффициентам в первом необработанном общем ключе (k'), указанном надежными индексами (safe_bits), с получением надежных битов (k). Например, коэффициент, указанный как надежный, может быть согласован с использованием битов согласования и затем отобран для получения надежного бита.

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

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

Ниже приведен небольшой, но наглядный пример для надежности и согласования. Пусть и . Запишем коэффициенты в виде пяти битовых последовательностей со старшими значащими битами слева. Например, в варианте реализации второе устройство может отбросить коэффициенты 00000, 00001, 01110, 01111, 10000, 10001, 11110 и 11111, поскольку лишь небольшое сложение с такими коэффициентами или вычитание из них приведет к смене на противоположный старшего значимого бита.

Не отброшены будут коэффициенты 00010, 00011, …, 01101 и 10010, 10011, …, 11101. Коэффициенты в первом списке дадут надежный бит 0, а коэффициенты в последнем списке дадут надежный бит 1. Второй бит этих последовательностей может быть взять в качестве данных согласования. Данные согласования выбранных коэффициентов передают другому устройству, а надежные бит не передают.

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

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

Между надежностью и согласованием существует интересная синергия. Может случиться так, что ближайший измененный коэффициент с правильными данными согласования будет отброшен вторым криптографическим устройством. Ближайший измененный коэффициент с правильными данными согласования и дополнительным ограничением, который не был отброшен вторым криптографическим устройством, может иметь другой надежный бит. Учитывание этого дополнительно повышает эффективность битов согласования. Например, в продолжение вышеприведенного примера, пусть второе устройство получает коэффициент 01100 с данными согласования 0. Ближайшим измененным коэффициентом будет 10000, но ближайшим коэффициентом, который не был отброшен, является 00111. Соответственно, первое устройство восстановит надежный бит 0, а не 1.

На Фиг. 11a схематически показан пример криптографического способа 400 в соответствии с вариантом реализации. Способ 400 выполнен с возможностью совместного использования кодового слова. Способ 400 включает:

- обмен (410) данными с первым криптографическим устройством (10),

- прием (420) первого открытого ключа (b) от первого криптографического устройства,

- формирование (430) второго закрытого ключа (s) и формирование второго открытого ключа (u) из второго закрытого ключа (s),

- формирование (440) кодового слова (K||четность) в соответствии с кодом с исправлением ошибок, и

- формирование (450) второго общего ключа (k*) из первого открытого ключа (b) и второго закрытого ключа (s),

- применение (460) функции надежных битов (shared_bits) ко второму необработанному общему ключу (k*) с получением надежных индексов, указывающих коэффициенты необработанного общего ключа, и надежных битов, выведенных из указанных коэффициентов,

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

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

- передачу (490) второго открытого ключа (u), данных (h) согласования, инкапсулированных данных (c) и надежных индексов первому устройству.

На Фиг. 11b схематически показан пример криптографического способа 500 в соответствии с вариантом реализации. Способ 500 выполнен с возможностью совместного использования кодового слова, при этом способ 500 включает:

- обмен (510) данными со вторым криптографическим устройством (20),

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

- прием (530) от второго устройства второго открытого ключа (u), данных (h) согласования и инкапсулированных данных (c) и надежных индексов,

- формирование (540) первого необработанного общего ключа (k’) из второго открытого ключа (u) и первого закрытого ключа (r),

- применение (550) данных (h) согласования в функции согласования к коэффициентам в первом необработанном общем ключе (k'), указанным надежными индексами (safe_bits), с получением надежных битов (k),

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

- применение (570) функции исправления ошибок к почти кодовому слову с получением кодового слова.

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

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

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

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

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

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

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

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

1. Второе криптографическое устройство (20), содержащее:

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

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

- получения первого открытого ключа (b) для первого криптографического устройства,

- формирования второго закрытого ключа (s), кодового слова в соответствии с кодом с исправлением ошибок и формирования второго открытого ключа (u) из второго закрытого ключа (s),

- формирования второго необработанного общего ключа (k*) из первого открытого ключа (b) и второго закрытого ключа (s),

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

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

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

- передачи второго открытого ключа (u), данных (h) согласования, инкапсулированных данных (c) и надежных индексов первому устройству.

2. Первое криптографическое устройство (10), содержащее:

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

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

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

- приема от второго устройства второго открытого ключа (u), данных (h) согласования и инкапсулированных данных (c) и надежных индексов,

- формирования первого необработанного общего ключа (k’) из второго открытого ключа (u) и первого закрытого ключа (r),

- применения данных (h) согласования в функции согласования к коэффициентам в первом необработанном общем ключе (k’), указанном надежными индексами, с получением надежных битов (k),

- декапсуляции инкапсулированных данных (c) при помощи надежных битов (k) с получением почти кодового слова,

- применения функции исправления ошибок к почти кодовому слову с получением кодового слова.

3. Криптографический способ (400) совместного использования кодового слова, включающий:

- обмен (410) данными с первым криптографическим устройством (10),

- прием (420) первого открытого ключа (b) для первого криптографического устройства,

- формирование (430) второго закрытого ключа (s) и формирование второго открытого ключа (u) из второго закрытого ключа (s),

- формирование (440) кодового слова в соответствии с кодом с исправлением ошибок, и

- формирование (450) второго необработанного общего ключа (k*) из первого открытого ключа (b) и второго закрытого ключа (s),

- применение (460) функции надежных битов ко второму необработанному общему ключу (k*) с получением надежных индексов, указывающих коэффициенты необработанного общего ключа, и надежных битов, выведенных из указанных коэффициентов,

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

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

- передачу (490) второго открытого ключа (u), данных (h) согласования, инкапсулированных данных (c) и надежных индексов первому устройству.

4. Криптографический способ (500) совместного использования кодового слова, включающий:

- обмен (510) данными со вторым криптографическим устройством (20),

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

- прием (530) от второго устройства второго открытого ключа (u), данных (h) согласования и инкапсулированных данных (c) и надежных индексов,

- формирование (540) первого необработанного общего ключа (k’) из второго открытого ключа (u) и первого закрытого ключа (r),

- применение (550) данных (h) согласования в функции согласования к коэффициентам в первом необработанном общем ключе (k'), указанном надежными индексами, с получением надежных битов (k),

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

- применение (570) функции исправления ошибок к почти кодовому слову с получением кодового слова.

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

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

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

ПРИЛОЖЕНИЕ A

Схематические математические описания примеров реализации.

Алгоритмы описывают схему шифрования CPAPKE с открытым ключом, которая является INDCPA-стойкой (неразличимость при атаке подбором открытого текста, Indistinguishability under chosen-plaintext attack). CPAKEM может быть построен из CPAPKE в виде «черного ящика», а механизм CCAKEM защищенной инкапсуляции ключа INDCCA2 может быть построен из CPAPKE, например путем применения преобразования Фуджисаки-Окамото.

CPAPKE использует открытые параметры, которые являются целыми числами n; q; p; bh; κ; μ, и алгоритмы формирования ключа, шифрования и расшифрования. Ds представляет собой распределение, из которого могут быть извлечены коэффициенты секретного ключа, и параметризовано посредством η. Например, если Ds является распределением разреженных троичных векторов, то η представляет вес Хэмминга векторов. fr является детерминистической функцией, которая при данной затравке ρ отбирает свежий секретный ключ из распределения Ds. Действует на полиноме степени не более n. Функция SafeBits выбирает μ≤n коэффициентов, которые приводят к минимальной общей вероятности отказа расшифрования, в соответствии с положительными позициями/индексами, например, в векторе, представляющем μ выбираемых коэффициентов.

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

CCAKEM может быть получен путем применения преобразования Фуджисаки-Окамото на CPAPKE и может использовать хэш-функции H, как определено в CPAKEM, и дополнительно хэш-функцию G из * битов в умноженные на 3 κ битов.

1. Криптографическое устройство (20), содержащее:

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

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

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

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

формирования второго необработанного общего ключа (k*) из первого открытого ключа (b) и второго закрытого ключа (s), при этом

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

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

вывода общего криптографического ключа из по меньшей мере данных (K), закодированных в кодовом слове,

передачи второго открытого ключа (u) и инкапсулированных данных (c) первому устройству.

2. Криптографическое устройство по п. 1, в котором:

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

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

данных для инкапсуляции и битов четности.

3. Криптографическое устройство (10), содержащее:

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

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

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

приема от второго устройства второго открытого ключа (u) и инкапсулированных данных (c),

формирования первого необработанного общего ключа (k’) из второго открытого ключа (u) и первого закрытого ключа (r), при этом:

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

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

применения функции исправления ошибок к почти кодовому слову с получением кодового слова и

вывода общего криптографического ключа из по меньшей мере данных (K), закодированных в кодовом слове.

4. Криптографическое устройство по любому из предыдущих пунктов, сконфигурированное для протокола шифрования с открытым ключом, в котором сообщение (m) зашифровано общим симметричным ключом, выведенным по меньшей мере из данных (K), закодированных в кодовом слове, причем зашифрованное сообщение отправляют вместе со вторым открытым ключом (u) со второго устройства первому устройству.

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

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

7. Криптографическое устройство по любому из пп. 1 или 2 или 4-6 при зависимости от п. 1 или 2, в котором процессор второго устройства выполнен с возможностью

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

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

8. Криптографическое устройство по п. 3 или по любому из пп. 4-6 при зависимости от п. 3, в котором процессор криптографического устройства выполнен с возможностью

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

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

9. Криптографическое устройство по п. 8, в котором:

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

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

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

12. Криптографический способ (400) совместного использования кодового слова, включающий:

обмен (410) данными с первым криптографическим устройством (10),

прием (420) первого открытого ключа (b) для первого криптографического устройства от первого криптографического устройства, причем первый открытый ключ (b) формируют из сформированного кратковременно первого закрытого ключа,

формирование (430) второго закрытого ключа (s) и формирование второго открытого ключа (u) из второго закрытого ключа (s),

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

формирование (450) второго необработанного общего ключа (k*) из первого открытого ключа (b) и второго закрытого ключа (s), при этом

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

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

вывод общего криптографического ключа из по меньшей мере данных (K), закодированных в кодовом слове,

передачу (490) второго открытого ключа (u) и инкапсулированных данных (c) первому устройству.

13. Криптографический способ (500) совместного использования кодового слова, включающий:

обмен (510) данными со вторым криптографическим устройством (20),

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

прием (530) от второго устройства второго открытого ключа (u) и инкапсулированных данных (c),

формирование (540) первого необработанного общего ключа (k’) из второго открытого ключа (u) и первого закрытого ключа (r), при этом

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

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

применение (570) функции исправления ошибок к почти кодовому слову с получением кодового слова и

вывод общего криптографического ключа из по меньшей мере данных (K), закодированных в кодовом слове.

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