УСТРОЙСТВО И СПОСОБ СОВМЕСТНОГО ИСПОЛЬЗОВАНИЯ МАТРИЦЫ ДЛЯ ИСПОЛЬЗОВАНИЯ В КРИПТОГРАФИЧЕСКОМ ПРОТОКОЛЕ Российский патент 2022 года по МПК H04L9/08 

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

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

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

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

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

Начальная точка такой криптографии на основе решеток заключается в том, что обе стороны, например, сетевые узлы 110 и 111, имеют доступ к совместно используемой матрице. Эта матрица типично выбирается произвольно и является довольно большой. Совместно используемая матрица имеет множественные записи, и каждая запись имеет значение. Например, совместно используемая матрица может иметь размерности, скажем, 500 раз по 500 или даже больше. В примерных вычислениях, используется квадратная совместно используемая матрица с размерностью 512=2⁹. Записи в совместно используемой матрице типично задаются по модулю математический модуль q, что может составлять, скажем, 2¹⁰. Таким образом, совместно используемая матрица может представлять примерно 2⁹⋅2⁹⋅2¹⁰=2²⁸ битов информации.

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

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

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

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

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

Первый сетевой узел содержит:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Фиг. 1 схематично показывает пример варианта осуществления криптографической системы 100. Криптографическая система 100 содержит множественные сетевые узлы. На фиг. 1 показаны первый сетевой узел 110 и второй сетевой узел 111. По большей части, узлы 110 и 111 имеют идентичную структуру за исключением того, что они имеют взаимосвязь "отправитель/приемник". Сетевые узлы в системе 100 выполнены с возможностью выполнять криптографический протокол на основе совместно используемой матрицы; в частности, первый сетевой узел 110 и второй сетевой узел 111 сконфигурированы для такого криптографического протокола. Предпочтительно свежая совместно используемая матрица используется для каждого выполнения криптографического протокола.

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

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

- формировать матрицу (S_l) закрытых ключей,

- формировать матрицу (P_l) открытых ключей, причем упомянутое формирование содержит по меньшей мере:

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

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

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

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

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

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

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

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

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

Также в этом примере, шум может добавляться, например, в форме масштабирования. Подробный пример протокола шифрования с открытым ключом на основе решеток содержится в статье авторов J. H. Cheon, D. Kim, J. Lee, Y. Song: "Lizard: Cut off the Tail! Practical Post-Quantum Public-Key Encryption from LWE and LWR" (содержится в данном документе по ссылке).

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

Первый и второй сетевой узел содержат интерфейс 120 связи. Интерфейс 120 связи первого сетевого узла 210 выполнен с возможностью цифровой связи со вторым сетевым узлом 211. Типично, интерфейс 120 связи выполнен с возможностью обмениваться данными со многими из других узлов в системе 100.

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

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

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

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

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

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

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

Чтобы уменьшать объем служебной информации при передаче, диспетчер 130 базовых данных может получать совместно используемую последовательность значений в качестве случайного начального числа. Например, первый сетевой узел 110 может содержать детерминированный генератор 160 псевдослучайных чисел. Генератор псевдослучайных чисел может инициализироваться случайным начальным числом и использоваться для того, чтобы вычислять последовательность значений. Начальное число может получаться из разных источников, например, предварительно программируемых, например, во время изготовления, например, приниматься из второго сетевого узла, например, приниматься от доверенной третьей стороны и т.д. Данные выбора также могут формироваться в первом сетевом узле и отправляться во второй сетевой узел.

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

Генератор 160 псевдослучайных чисел может представлять собой генератор с быстрой линейной обратной связью, такой как вихрь Мерсенна. Тем не менее, предпочтительным является криптографически защищенный генератор случайных чисел. Например, генератор 160 псевдослучайных чисел может удовлетворять так называемому тесту следующего бита. Таким образом, с учетом первых k битов случайной последовательности, отсутствует полиномиально-временной алгоритм, который может прогнозировать (k+1)-ый бит с вероятностью успешности, не пренебрежимо мало превышающей 50%. Имеется множество известных криптографически защищенных генераторов случайных чисел, например, блочный шифр, выполняемый в режиме счетчика, например, усовершенствованный стандарт шифрования в режиме счетчика. Защищенный генератор случайных чисел также может получаться посредством выполнения хэш-функции в режиме счетчика, например, SHA-256 и т.д. Вихрь Мерсенна также может защищаться, например, посредством базирования пары криптографических поточных шифров на выводе из вихря Мерсенна. Дополнительные примеры включают в себя генератор Блюма-Блюма-Шуба, генератор Блюма-Микали и т.д.

Сетевой узел 110 содержит модуль 140 формирования матриц. Модуль 140 формирования матриц выполнен с возможностью формировать совместно используемую матрицу (A) в соответствии с данными выбора с заданием упомянутых множественных записей совместно используемой матрицы равными множественным значениям, назначаемым посредством данных выбора. Данные выбора в силу этого описывают преобразование между совместно используемой последовательностью значений и записями в совместно используемой матрице. Данные выбора могут получаться из второго сетевого узла, например, через интерфейс 120 связи. Последовательность значений трансформируется в фактическую совместно используемую матрицу A посредством данных выбора.

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

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

Фиг. 2a схематично показывает пример варианта осуществления данных выбора. Данные выбора идентифицируют местоположения в последовательности 210 значений, показаны значения 221 и 222, которые должны назначаться местоположениям в совместно используемой матрице 230, показаны записи 231 и 232.

Например, данные выбора могут содержать последовательность кортежей, причем каждый кортеж содержит индекс в последовательности значений и индекс в совместно используемой матрице. Например, последовательность значений может индексироваться линейно, например, подсчитываться последовательно, например, с использованием натуральных чисел. Например, совместно используемая матрица также может индексироваться с одним числом, например, нумероваться последовательно, но также может индексироваться посредством координаты X и Y, например, указывающей столбец и строку, соответственно. Данные выбора, например, могут содержать{(4, (2,5)), (7, (3,3)), …,}, чтобы указывать то, что значение с индексом 4 в последовательности значений должно быть размещено в позиции (2,5) совместно используемой матрицы, и т.д. Данные выбора не содержат фактические значения записи в совместно используемой матрице, вместо этого фактические значения совместно используемой матрицы выбираются из последовательности значений. В варианте осуществления, данные выбора могут дополняться данными для изменения. Например, данные для изменения могут содержать данные, которые указывают то, как значения в совместно используемой матрице должны изменяться, например, посредством включения приращения или постепенного уменьшения или включения нового значения. Такие данные для изменения могут применяться посредством модуля 140 формирования также. Данные для изменения считаются менее преимущественными: отправка новых значений требует множества битов, и каждый элемент в данных для изменения оказывает влияние только на один элемент совместно используемой матрицы, и при этом данные выбора могут указываться только с небольшим числом битов, но могут оказывать влияние на большое число записей совместно используемой матрицы. Небольшие постепенные приращения/постепенные уменьшения могут указываться с меньшим числом битов, но они имеют сравнительно маленькое влияние на результирующую решетку и фактически могут исчезать в шуме, добавленном после матричного умножения с совместно используемой матрицей.

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

Например, данные выбора могут содержать перестановку. Назначение затем может работать посредством перестановки последовательности значений согласно перестановке и назначения перестановочной последовательности значений записям совместно используемой матрицы согласно назначению по умолчанию. Например, если перестановка обозначается как биективная функция σ, которая преобразуется из местоположений 1-mn в последовательности значений в записи в матрице A mxn, для некоторого способа по умолчанию нумерации записей в совместно используемой матрице A, например, по строкам или по столбцам и т.д. Данные выбора могут содержать представление перестановки σ, и назначение может работать посредством назначения, индексу i согласно способу по умолчанию индексации A, значения последовательности 210 в местоположении σ(i). Перестановка также может использоваться наоборот, например, значение с индексом i в последовательности может назначаться записи σ(i) в матрице.

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

Фиг. 2b схематично показывает первый пример варианта осуществления данных выбора. Предусмотрены разные способы уменьшать число битов, требуемых для того, чтобы указывать преобразование между последовательностью 210 и матрицей 230, один из которых проиллюстрирован относительно фиг. 2b. В последовательности 210 значений, задаются одна или более первых групп, показаны первые группы 241 и 242. В матрице 230 задаются одна или более вторых групп, показаны вторые группы 251 и 252. Каждой первой группе в последовательности 210 соответствует вторая группа в матрице 230. Преобразование между записями последовательности 210 и записями матрицы 230 может ограничиваться преобразованиями, которые преобразуют элементы первой группы в элементы соответствующей второй группы. Первые и вторые группы могут выбираться произвольно. На фиг. 2b, первые группы выбираются последовательно, но вторые группы выбираются произвольно. Другие варианты выбора являются возможными. Например, вторые группы также могут быть последовательными, например, строки или столбцы и т.д.

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

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

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

Следует отметить, что объем данных для того, чтобы указывать совместно используемую матрицу из базовых данных в последовательности, например, в базовой матрице, может быть гораздо меньше объема данных непосредственно в совместно используемой матрице. Например, рассмотрим фиг. 2c, для квадратной матрицы размерности 512 и по модулю 2048. Только 9 битов необходимы для того, чтобы указывать циклическую перестановку в строке, тогда как 512*12 битов необходимы для того, чтобы указывать данные непосредственно в строке. Таким образом, в этом примере, часть данных выбора, которые указывают то, какие значения в строке базовой матрицы направляются в какое местоположение в совместно используемой матрице, составляет 9 битов, что составляет 9/(512*12)<1/100, размер данных в строке.

Каждый из способов выше допускает формирование большего количества раных совместно используемых матриц из одной последовательности значений. Например, использование системы для того, чтобы поворачивать строки базовой матрицы, требует только параметра поворота для 8 строк, чтобы формировать (2⁹)⁹раных совместно используемых матриц для случайной последовательности 210 значений. Упомянутое число (2⁹)⁹превышает 2⁶⁴, которое может рассматриваться в качестве параметра безопасности. Согласно этому примеру, достаточно отправлять восемь пар (индекс строки, порядок циклической перестановки), приводя всего к 8*(9+9) битов. Если строки, которые должны поворачиваться, предварительно определены, необходимый объем данных еще дополнительно уменьшается на 8*9 битов. Тем не менее, большие числа разных матриц A легко являются возможными с использованием дополнительных параметров в данных выбора, например, большие 2¹²⁸, большие 2²⁵⁶и т.д., с использованием 15 и 29 параметров поворота для 15 и 29 строк или столбцов, соответственно. В варианте осуществления, часть параметров поворота поворачивает строки, тогда как часть параметров поворота поворачивает столбцы. Это имеет такое преимущество, что поворот является одинаково несовместимым с матричными умножениями для обоих узлов, например, в ситуации, в которой один из узлов использует левое умножение, а другой - правое умножение. В еще одном другом варианте осуществления, с квадратными матрицами, поворота осуществляются по (циклическим) диагоналям матрицы.

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

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

Например, пусть первая группа в последовательности значений представляет собой записи, пронумерованные , предполагается, что строка совместно используемой матрицы имеет m элементов. Пусть p представляет собой параметр в данных выбора, который указывает то, что число записей в этой группе поворачивается. Пусть вторая группа представляет собой k-ую строку матрицы. Записи в A пронумерованы по строкам, начиная с нуля. Строки также подсчитаны, начиная с нуля. В этом случае, запись в последовательности может преобразовываться в запись . Вышеуказанное вычисление является линейным в p. Можно обобщать это преобразование таким образом, что i-ый элемент в первой группе j, имеющей элементов, преобразуется в , при этом представляет собой таблицу, например, таблицу поиска. Здесь j работает на основе числа групп. В варианте осуществления, можно рассматривать для всех j. Число групп может быть равно числу строк, но это не является обязательным. Например, можно рассматривать значение по умолчанию, например, 0 для некоторых параметров . Таблицы могут представлять собой строки, например, простое добавление первого индекса строки, как описано выше, но они также могут преобразовывать первую группу в более сложные наборы. В варианте осуществления, преобразуется в нерегулярные структуры. Пример должен представлять собой независимый набор мошеннического графа матрицы (только для квадратных матриц). Фактически, может даже формировать план на латинском квадрате.

Альтернативный способ для того, чтобы представлять данные выбора, представляет собой случайное начальное число. Например, детерминированный генератор 160 псевдослучайных чисел может инициализироваться случайным начальным числом, и получение из вывода детерминированного генератора псевдослучайных чисел индикатора множественных значений в последовательности значений и/или множественных записей совместно используемой матрицы. Любой из вышеуказанных способов представления данных выбора может использоваться вместе с представлением начального числа, поскольку можно формировать данные выбора из вывода генератора случайных чисел. Например, в варианте осуществления, данные выбора могут поворачивать, скажем, строки 1, 5, 13, 27 и 37 базовой матрицы на величину, указываемую в данных выбора. В этом случае, данные выбора могут непосредственно содержать индексы строки или столбца и величины поворота, или данные выбора могут содержать случайное начальное число. Во втором случае, величина поворота может приниматься из вывода генератора 160 случайных чисел.

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

Фиг. 3a схематично показывает пример варианта осуществления криптографической системы 300. Система 300 содержит сервер 310 и множественных клиентов. Показаны клиенты 320.1, 320.2 и 320.3. Может быть предусмотрено гораздо большее число клиентов. Например, сервер 310 может представлять собой компьютер, который доставляет цифровые услуги по цифровой сети клиентам. Например, сервер 310 может представлять собой веб-магазин. Клиенты могут использовать веб-браузер, чтобы просматривать веб-узел, управляемый посредством сервера 310, и заказ из веб-магазина. Связь между сервером и клиентами может шифроваться и/или аутентифицироваться. Например, сервер и клиенты могут выполнять протокол обмена ключами. Система 300 организуется с возможностью уменьшать объем служебной информации, ассоциированный с вычислением множества разных совместно используемых матриц для сервера 310.

Сервер 310 может организовываться в качестве первой сети 110, показанной на фиг. 1, за исключением того, что запоминающее устройство 170 базовых данных сконфигурировано в качестве кэш-памяти, выполненной с возможностью кэшировать последовательность значений (A₁, A₂) вместе с соответствующим идентификатором последовательности, который идентифицирует упомянутую кэшированную последовательность значений. Кэш-память 170 может сохранять множественные последовательности значений с ассоциированным идентификатором последовательности. Например, может быть предусмотрено две или более базовых матриц A₁, A₂ и т.д., но это не является обязательным.

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

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

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

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

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

Первое сообщение 331, отправленное из клиента 320 на сервер 310, содержит запрос сообщения. Оно может содержать дополнительную информацию, такую как идентификатор для клиента 320. В ответ, сервер 310 отправляет второе сообщение 332 в клиент 320. Второе сообщение 332 содержит идентификатор последовательности, например, содержащий дополнительное случайное начальное число. Сервер 310 кэширует соответствующую последовательность значений, например, после ее вычисления в определенный момент из дополнительного случайного начального числа. Последовательность значений может иметь форму базовой матрицы. Сообщение 332 также может содержать данные выбора, сформированные посредством сервера 310. Данные выбора в сообщении 332 могут иметь форму случайного начального числа или нет. Сообщение 332 также может содержать протокольную информацию, сформированную посредством сервера 310, которая является возможной, поскольку сервер 310 в этот момент имеет доступ к совместно используемой матрице. Например, в протоколе обмена ключами, как описано выше, сообщение 332 может содержать открытый ключ, сформированный для этого выполнения обмена ключами. После приема сообщения 332, клиент 320 может извлекать последовательность значений из своей кэш-памяти, либо, если последовательность значений не присутствует в кэш-памяти, формировать последовательность значений из дополнительного случайного начального числа в идентификаторе последовательности. Кроме того, клиент 320 может формировать совместно используемую матрицу из последовательности значений и данных выбора. С использованием сформированной совместно используемой матрицы, клиент 320 может формировать дополнительные значения в протоколе и возвращать их с сообщением 333. Например, если он представляет собой протокол обмена ключами, то сообщение 333 может содержать открытый ключ, сформированный посредством клиента 320 из совместно используемой матрицы и закрытого ключа клиента 320. Сообщение 320 также может содержать зашифрованную информацию, зашифрованную с помощью ключа, полученного из собственного закрытого ключа и открытого ключа, полученного в сообщении 332. Например, зашифрованные данные могут содержать, скажем, номер кредитной карты пользователя клиента 320. Сервер 310, когда он принимает сообщение 333, может использовать открытый ключ и собственную матрицу закрытых ключей, чтобы получать ключ шифрования и дешифровать зашифрованные данные, например, получать номер кредитной карты.

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

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

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

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

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

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

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

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

- Обмениваться начальным числом между инициатором и сервером, чтобы получать перестановку r{1, …, L}; r затем используется для того, чтобы получать открытую матрицу A mxn, используемую в обмене ключами. Верхняя строка A равна (, ее вторая строка равна , ..., и ее нижняя строка равна .

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

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

Вариант 1 осуществления: инициатор публикует значение начального числа в день для всей связи.

Вариант 2 осуществления: инициатор публикует матрицу A в день для всей связи.

Вариант 3 осуществления: инициатор публикует seed_long для длительного периода времени, из которого могут вычисляться начальные числа для более коротких периодов времени, к примеру, начальное число=PRF(seed_long|time).

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

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

Инициатор или ответчик, или третья сторона публикует первое начальное число, используемое для того, чтобы вычислять матрицу A₀ mxn. Инициатор вычисляет второе начальное число' и применяет псевдослучайную функцию (PRF), чтобы получать случайную перестановку r чисел [0, …, mn-1].

Инициатор отправляет начальное число' в ответчик.

Ответчик получает r и перекомпонует записи A₀ согласно перестановке, чтобы получать A.

После того, как инициатор и ответчик получают A, остальная часть протокола выполняется так, как описано выше.

Дальнейшие расширения варианта 4 осуществления:

Формирование открытой последовательности P, например, последовательности значений или базовой матрицы длины . Обмен начальным числом между инициатором и сервером, чтобы получать перестановку r {1.., L}; r затем используется для того, чтобы получать открытую матрицу A mxn, используемую в обмене ключами. Верхняя строка A равна (, ее вторая строка равна , ..., и ее нижняя строка равна .

Не требуется строго то, что r является перестановкой. Достаточно того, что для , справедливо то, что .

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

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

Для большого L, это может быть громоздким, и меньший набор перестановок может быть предпочтительным с точки зрения реализации. Например, рассмотрим . Битовая последовательность сегментируется на m блоков, каждый из которых имеет длину B, и блок i рассматривается как метка для перестановки для записей P. Например, если , перестановка, соответствующая блоку, представляет собой циклический сдвиг на i позиций для некоторого . Если , любая перестановка на n позиций может помечаться B-битовой меткой. Соответствие между метками и перестановками может либо сохраняться явно (для достаточно небольшого n), либо вычисляться с использованием кода Лемера.

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

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

Предусмотрены разные способы, которыми может получаться открытая последовательность P. Например, открытая последовательность, в одном варианте осуществления, может указываться в отраслевом стандарте. В другом варианте осуществления, она формируется посредством сервера S. Клиент C, желающий обмениваться данными с S, принимает P или параметры, например, начальное число и способ для того, чтобы вычислять P из S. Таким образом, сервер использует P для множественных сеансов и клиентов и не должен обязательно повторно вычислять его. В еще одном другом варианте осуществления, P формируется и распределяется доверенной третьей стороной (TTP). Сервер может сохранять P и использовать его для связи с множественными клиентами. Последовательность P может быть допустимой только в течение периода времени, указываемого посредством TTP. В еще одном другом варианте осуществления, имеются множественные TTP, каждая из которых формирует собственную открытую последовательность P_i. Сервер S сохраняет все такие матрицы. Клиент C выбирает последовательности из TTP, которой он фактически доверяет, комбинирует их некоторым предварительно указанным способом и применяет перестановку к этой комбинации. Он отправляет в S индексы выбранных TTP и начальное число таким образом, что S может получать упомянутую перестановку. Посредством комбинирования матриц и перестановки записей, S может находить матрицу, фактически используемую посредством C.

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

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

PRF2: PRF1 должна иметь коллизии, поскольку является относительно небольшим числом. Альтернатива заключается в том, чтобы отслеживать используемые числа и отбрасывать числа, которые уже возникают.

PRF3: другая альтернатива состоит в , где , где p является простым числом, и g является генератором; k должно быть начальным числом, и эта PRF итеративно проходится посредством увеличения .

Применение вышеописанных вариантов осуществления, в конкретном варианте осуществления 4, к другим схемам может заключаться в следующем. Например, для криптографического протокола на основе решеток, описанного в работе "Post-quantum key exchange - the new hope", авторов Erdem Alkim и др., можно модифицировать их схему следующим образом. С учетом вектора a и секретов s и e, в таком случае b вычисляется как . Генерирование в этом случае является менее затратным, поскольку оно содержит только n элементов, но оно по-прежнему может быть затратным для сервера, если он должен вычислять множество векторов из начального числа. Альтернатива заключается в том, чтобы иметь статический p (набор элементов) и вычислять случайный вектор r перестановки. Таким образом, вычисление должно заключаться в следующем: где представляет перестановочную версию согласно r. Поскольку r имеет меньше элементов, чем a, оно может вычисляться с меньшими затратами, чем a.

В схемах шифрования с открытым ключом на основе решеток, открытый ключ, например, LWE, открытый ключ задается посредством пары (b, A). Матрица A может занимать значительное пространство для хранения данных, либо альтернативно, она, возможно, должна формироваться динамически. Альтернатива заключается в том, чтобы иметь набор открытых значений P; и иметь, в качестве открытого ключа, (b, начальное число') таким образом, что начальное число' используется для того, чтобы получать вектор r перестановки, который определяет то, как элементы в P преобразуются в матрицу A, используемую для того, чтобы получать b в качестве b=As+e. Преимущество состоит в том, что потребности в хранении на сервере являются гораздо более низкими, и вычислительные потребности также являются гораздо более низкими.

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

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

- получение (420) последовательности значений для записей совместно используемой матрицы, причем последовательность значений совместно используется со вторым сетевым узлом,

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

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

- применение (450) совместно используемой матрицы в криптографическом протоколе.

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

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

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

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

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

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

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

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

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

Список ссылочных позиций на фиг. 1-3b

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

110 - первый электронный сетевой узел

111 - второй электронный сетевой узел

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

130 - диспетчер базовых данных

140 - модуль формирования матриц

150 - криптографический модуль

152 - модуль матричного умножения

160 - генератор псевдослучайных чисел

170 - запоминающее устройство базовых данных

210 - последовательность значений

221, 222 - значение

230 - совместно используемая матрица

231, 232 - запись в совместно используемой матрице

233 - данные выбора

241, 242 - первая группа

251, 252 - вторая группа

260 - базовая матрица

261-263 - строка

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

310 - сервер

320 - клиент

320.1-320.3

331-333 - передача

Изобретение относится к области криптографии. Технический результат заключается в повышении надежности передачи данных. Технический результат достигается за счет того, что сетевой узел, сконфигурированный для криптографического протокола на основе совместно используемой матрицы, выполнен с возможностью формировать совместно используемую матрицу (A) в соответствии с данными выбора и совместно используемой последовательностью значений, множественные записи совместно используемой матрицы назначаются множественным значениям последовательности данных, назначенным посредством данных выбора. 4 н. 14 з.п. ф-лы, 9 ил.

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

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

- кэш-память, выполненную с возможностью кэшировать последовательность значений (A₁, A₂), при этом множественным записям совместно используемой матрицы назначается значение из последовательности значений, как кэшировано в кэш–памяти,

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

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

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

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

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

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

3. Первый сетевой узел (110) по п. 2, в котором часть данных выбора, которые указывают множественные значения в первой группе для записей во второй группе, имеет размер в битах меньше 1/100 от полного размера в битах значений во второй группе.

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

5. Первый сетевой узел (110) по п. 2, 3 или 4, в котором последовательность значений образует базовую матрицу, причем данные выбора указывают циклическую перестановку по меньшей мере одной строки и/или столбца базовой матрицы посредством указания числа записей, на которое поворачивается упомянутая строка и/или столбец.

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

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

8. Первый сетевой узел (110) по любому из предшествующих пунктов, в котором процессорная схема выполнена с возможностью вычислять матричное произведение между совместно используемой матрицей (A) и закрытым вектором или матрицей (r; S_l) первого сетевого узла в качестве части криптографического протокола.

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

- формировать матрицу (S_l) закрытых ключей,

- формировать матрицу (P_l) открытых ключей, причем упомянутое формирование содержит по меньшей мере:

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

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

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

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

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

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

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

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

11. Первый сетевой узел (110) по любому из предшествующих пунктов, содержащий:

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

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

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

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

12. Первый сетевой узел (110) по п. 11, в котором идентификатор последовательности содержит дополнительное случайное начальное число, получение или совместное использование последовательности значений содержат инициализацию детерминированного генератора псевдослучайных чисел дополнительным случайным начальным числом и получение последовательности значений из вывода инициализированного детерминированного генератора псевдослучайных чисел.

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

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

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

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

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

кэш–память, выполненную с возможностью кэшировать последовательность значений (A₁, A₂), при этом множественным записям совместно используемой матрицы назначается значение из последовательности значений, как кэшировано в кэш-памяти,

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

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

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

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

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

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

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

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

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

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

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

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