УСТРОЙСТВА И СПОСОБ ОБМЕНА КЛЮЧАМИ
KEY EXCHANGE DEVICES AND METHOD

Область техники, к которой относится изобретение
Изобретение относится к сетевому узлу, к способу согласования ключей и к машиночитаемому носителю.
Уровень техники
В криптографии, протокол согласования ключей представляет собой протокол, за счет которого две или более сторон, которые еще не могут совместно использовать общий ключ, могут согласовывать такой ключ. Предпочтительно, обе стороны могут оказывать влияние на результат, так что ни одна из сторон не может обуславливать выбор ключа. Взломщик, который перехватывает сообщения для всей связи между двумя сторонами, не должен ничего узнавать относительно ключа. При этом, тогда как взломщик, который наблюдает идентичную связь, практически ничего не узнает, непосредственно стороны могут извлекать совместно используемый ключ.
Протоколы согласования ключей являются полезными, например, для защищенной связи, например, чтобы шифровать и/или аутентифицировать сообщения между сторонами.
Практические протоколы согласований ключей введены в 1976 году, когда Whitfield Diffie и Martin Hellman ввели понятие криптографии с общедоступным ключом. Они предложили систему для согласования ключей между двумя сторонами, которая использует очевидную трудность вычислительных логарифмов по конечному полю GF(q) с q элементами. С использованием системы, два пользователя могут согласовывать симметричный ключ. Симметричный ключ затем может использоваться, скажем, для зашифрованной связи между двумя сторонами.
Текущие способы согласования ключей, применимые, когда стороны еще не имеют совместно используемого секрета, такие как способ согласования ключей Диффи–Хеллмана, требуют ресурсоемких математических операций. Например, алгоритм Диффи–Хеллмана требует выполнения операций возведения в степень в конечном поле. Как экспонента, так и размер поля могут быть большими. Это приводит к тому, что протоколы согласования ключей являются менее подходящими для малоресурсных устройств. С другой стороны, протоколы согласования ключей должны быть очень полезными в ресурсоограниченных устройствах. Например, в таких областях применения, как Интернет вещей, произвольно организующиеся беспроводные сети и т.п., согласование ключей может использоваться для того, чтобы защищать линии связи между устройствами. Другой пример представляет собой связь между считывателем и электронным тегом, скажем, считывателем карт и смарт–картой либо считывателем тегов и тегом, например, RFID–тегом или NFC–тегом. Должно быть преимущественным иметь протокол согласования ключей, который налагает меньшую нагрузку, по меньшей мере, на одну из двух сторон, т.е. на электронный тег.
Чтобы упрощать защищенную связь между сторонами, протоколы согласования ключей иногда дополнительно подразделяются на схемы обмена криптографическими ключами (KEX) и инкапсуляции криптографических ключей (KEM). Схемы инкапсуляции криптографических ключей (KEM) используют криптографию с асимметричными шифрами, чтобы устанавливать совместно используемый секрет между двумя сторонами, с использованием общеизвестного (например, общедоступного ключа) и секретно принадлежащего (например, секретного ключа) значения для каждой стороны.
KEX–схемы заключают в себе обмен общедоступными ключами посредством каждой стороны, которые затем независимо используются посредством другой стороны наряду с собственным секретным ключом, чтобы вычислять общий совместно используемый секрет. Известный пример KEX–схемы представляет собой обмен ключами Диффи–Хеллмана, упомянутый выше, безопасность которого основана на решении задачи дискретного логарифма. Интересный признак некоторых KEX–схем заключается в том, что фактический конечный совместно используемый секрет никогда не передается между сторонами, даже в зашифрованной форме, а вычисляется независимо посредством двух сторон на каждом конце. Это приводит к желательному признаку, известному как прямая секретность, который обеспечивает то, что даже компрометация долговременного секретного ключа стороны посредством взломщика в будущем не должна компрометировать секретность зашифрованного сообщения, которым обмениваются в прошлом.
KEM–схемы устанавливают совместно используемый секрет между двумя объектами или сторонами с использованием криптографии с асимметричными шифрами посредством одной стороны, обычно инициатора связи, чтобы шифровать (с использованием общедоступного ключа другой стороны) и передавать совместно используемый секрет другой стороне, известной как ответчик, которая затем может дешифровать его (с использованием своего секретного ключа) и затем использовать его для защищенного обмена данными со стороной инициатора. KEM–схемы не могут достигать прямой секретности, поскольку любой взломщик, который компрометирует секретный ключ стороны для предыдущего сеанса и записывает все сообщения, которыми обмениваются между сторонами в этом сеансе, может восстанавливать совместно используемый секрет для этого конкретного сеанса.
Вследствие роста потребностей в области безопасности в Интернете вещей, схемы обмена ключами должны также достигать высокой эффективности (т.е. минимального объема связи или требований по полосе пропускания) при одновременном обеспечении защищенности от противников с поддержкой классических, а также квантовых вычислений.
Сущность изобретения
Предусмотрен электронный сетевой узел, сконфигурированный для протокола обмена ключами. Сетевой узел называется "первым сетевым узлом", чтобы отличать его от второго сетевого узла, с которым он обменивается данными.
Первый сетевой узел содержит:
– интерфейс связи, выполненный с возможностью осуществления цифровой связи со вторым сетевым узлом, и
– процессорную схему, выполненную с возможностью:
– получать совместно используемую матрицу, причем совместно используемая матрица совместно используется со вторым сетевым узлом через интерфейс связи, причем записи в совместно используемой матрице A выбираются по модулю первая неотрицательная величина q,
– формировать матрицу конфиденциальных ключей, причем записи в матрице конфиденциальных ключей являются целыми числами, ограниченными по абсолютному значению пределом,
– формировать матрицу общедоступных ключей посредством следующего:
– вычисление матричного произведения между совместно используемой матрицей и матрицей конфиденциальных ключей по модулю первая неотрицательная величина, с получением матричного произведения,
– понижающее масштабирование записей в матричном произведении до второй неотрицательной величины, причем масштабированная запись равна немасштабированной записи, умноженной на вторую неотрицательную величину, деленной на первую неотрицательную величину и округленной до ближайшего целого числа, причем вторая неотрицательная величина меньше первой неотрицательной величины, причем предел составляет, самое большее, вторая неотрицательная величина,
– отправка матрицы общедоступных ключей первого сетевого узла во второй сетевой узел,
– прием матрицы общедоступных ключей второго сетевого узла,
– вычисление исходного (чернового) ключа в качестве матричного произведения между принимаемым общедоступным ключом второго узла и матрицей конфиденциальных ключей первого сетевого узла по модулю вторая неотрицательная величина.
Поскольку матрица конфиденциальных ключей ограничивается, и матрица общедоступных ключей понижающе масштабируется, объем служебной информации по вычислению и связи при согласовании ключей уменьшается. С использованием сверочных данных, разность между матрицей исходных ключей, вычисленной в первом и втором сетевом узле, может преодолеваться. Один из узлов вычисляет сверочные данные, а другой использует их. Например, процессорная схема первого сетевого узла может быть выполнена с возможностью:
– приема сверочных данных второго сетевого узла,
– вычисления совместно используемого ключа посредством применения сверочной функции к принимаемым сверочным данным и исходному ключу, или процессорная схема первого сетевого узла может быть выполнена с возможностью:
– получения совместно используемого ключа и сверочных данных из исходного ключа,
– отправки сверочных данных во второй сетевой узел.
Сетевые узлы представляют собой электронные устройства. Например, они могут представлять собой мобильные электронные устройства, такие как мобильный телефон, планшетный компьютер или компьютер на смарт–картах. Сетевой узел может представлять собой абонентскую приставку, компьютер, телевизионный приемник и т.п. Способ согласования ключей, описанный в данном документе, может применяться в широком диапазоне практических вариантов применения. Такие практические варианты применения включают в себя безопасность в Интернете (вещей). Протоколы могут применяться к таким протоколам, как IKE, TLS, SSH и другие. В общем, предложенная схема является постквантовой защищенной как для общих Интернет–примеров использования, так и для ресурсоограниченных окружений. Согласование ключей может использоваться каждый раз, когда защищенная, например, конфиденциальная связь между двумя узлами требуется. Она может выполняться в сенсорной сети, но также, например, защищать финансовые транзакции.
Способ согласно изобретению может реализовываться на компьютере в качестве машинореализуемого способа или в выделенных аппаратных средствах либо в комбинации вышеозначенного. Исполняемый код для способа согласно изобретению может сохраняться на компьютерном программном продукте. Примеры компьютерных программных продуктов включают в себя запоминающие устройства, оптические устройства хранения данных, интегральные схемы, серверы, онлайновое программное обеспечение и т.д. Предпочтительно, компьютерный программный продукт содержит долговременный программный код, сохраненный на машиночитаемом носителе для осуществления способа согласно изобретению, когда упомянутый программный продукт выполняется на компьютере.
В предпочтительном варианте осуществления, компьютерная программа содержит компьютерный программный код, выполненный с возможностью осуществлять все этапы способа согласно изобретению, когда компьютерная программа выполняется на компьютере. Предпочтительно, компьютерная программа осуществляется на машиночитаемом носителе.
Другой аспект изобретения предоставляет способ обеспечения доступности компьютерной программы для загрузки. Этот аспект используется, когда компьютерная программа выгружается, например, в Apple App Store, Google Play Store или Microsoft Windows Store, и когда компьютерная программа доступна для загрузки из такого магазина.
Краткое описание чертежей
В дальнейшем описываются дополнительные подробности, аспекты и варианты осуществления изобретения, только в качестве примера, со ссылкой на чертежи. Элементы на чертежах проиллюстрированы для простоты и ясности и не обязательно нарисованы в масштабе. На чертежах, элементы, которые соответствуют уже описанным элементам, могут иметь идентичные номера ссылок. На чертежах:
Фиг. 1 схематично показывает пример варианта осуществления сети согласования ключей,
Фиг. 2 схематично показывает пример варианта осуществления исходного ключа,
Фиг. 3 схематично показывает пример варианта осуществления способа обмена электронными ключами,
Фиг. 4a схематично показывает машиночитаемый носитель, имеющий записываемую часть, содержащую компьютерную программу согласно варианту осуществления,
Фиг. 4b схематично показывает представление процессорной системы согласно варианту осуществления.
Список ссылок с номерами на фиг. 1–2:
100 – сеть согласования ключей
110 – сетевой узел в форме инициатора
120 – интерфейс связи
130 – модуль обработки совместно используемых матриц
140 – модуль обработки матриц конфиденциальных ключей
150 – модуль обработки матриц общедоступных ключей
160 – модуль обработки совместно используемых ключей
162 – исходный ключ
164 – сверочные данные (h)
166 – совместно используемый ключ
210 – сетевой узел в форме ответчика
220 – интерфейс связи
230 – модуль обработки совместно используемых матриц
240 – модуль обработки матриц конфиденциальных ключей
250 – модуль обработки матриц общедоступных ключей
260 – модуль обработки совместно используемых ключей
262 – исходный ключ
264 – сверочные данные (h)
266 – совместно используемый ключ
300 – исходный ключ
301 – старшая часть
302 – средняя часть
303 – младшая часть
Подробное описание вариантов осуществления
Хотя это изобретение допускает вариант осуществления во многих различных формах, один или более конкретных вариантов осуществления показаны на чертежах и подробно описываются в данном документе с пониманием того, что настоящее раскрытие сущности должно рассматриваться в качестве примера принципов изобретения и не имеет намерение ограничивать изобретение конкретными показанными и описанными вариантами осуществления.
Далее, для понимания, элементы вариантов осуществления описываются при работе. Тем не менее, должно быть очевидным то, что соответствующие элементы выполнены с возможностью осуществлять функции, описанные как выполняемые посредством них.
Дополнительно, изобретение не ограничено вариантами осуществления, и изобретение заключается в каждом новом признаке или в комбинации признаков, описанных в данном документе или изложенных во взаимно различных зависимых пунктах формулы изобретения.
Фиг. 1 схематично показывает пример варианта осуществления сети 100 согласования ключей.
На фиг. 1 показаны два сетевых узла в системе: сетевой узел 110 в форме инициатора и сетевой узел 210 в форме ответчика. В варианте осуществления системы согласования ключей, число узлов может быть большим, даже гораздо большим двух, например, большим 1000 узлов, например, большим 10^6 узлов.
Различие между сетевым узлом в форме инициатора или ответчика заключается в том, как они решают задачи, связанные со сверочными данными. Сетевой узел в форме инициатора принимает сверочные данные и применяет их для того, чтобы получать совместно используемый ключ, тогда как сетевой узел в форме ответчика формирует сверочные данные и отправляет их сетевой узел в форме инициатора. Сетевому узлу в форме ответчика не требуются сверочные данные для того, чтобы получать совместно используемый ключ. Типично, тип в форме инициатора также должен инициировать протокол согласования ключей между двумя сетевыми узлами, поскольку это позволяет сокращать число раундов, выполняемых между двумя сетевыми узлами. Тем не менее, это необязательно; протокол согласования ключей также может инициироваться посредством сетевого узла в форме ответчика.
Кроме того, в варианте осуществления сетевого узла, сетевой узел выполнен с возможностью работать согласно режиму инициатора и согласно режиму ответчика. Например, если сетевой узел инициирует согласование ключей, например, отправляет сообщение в другой сетевой узел, передающий в служебных сигналах начало протокола согласования ключей, то сетевой узел может переключаться на режим инициатора. Если сетевой узел отвечает на согласование ключей, например, принимает сообщение из другого сетевого узла, передающего в служебных сигналах начало протокола согласования ключей, то сетевой узел может переключаться на режим ответчика. Хотя это является удобным на практике, также эта опция не является строго обязательной; например, в системе согласования ключей, некоторые режимы могут быть сконфигурированы только как инициатор, и некоторые могут быть сконфигурированы только как узлы–ответчики. Последствие этого заключается в том, что некоторые узлы не могут согласовывать совместно используемый ключ вместе. Для некоторых сетей, это не должно представлять собой проблему, например, в произвольно организующейся сети или произвольно организующихся беспроводных сетках и т.д., до тех пор, пока достаточно большое количество пар сетевых узлов могут обмениваться данными и согласовывать совместно используемый ключ.
Узел–инициатор 110 содержит интерфейс 120 связи. Узел–ответчик 210 содержит интерфейс 220 связи. Интерфейсы связи могут быть выполнены с возможностью осуществления цифровой связи с другими узлами в системе согласования ключей. Тем не менее, в необязательном порядке, все узлы в системе могут достигаться в любой момент времени.
Интерфейс 120 и 220 связи выполнен с возможностью осуществления цифровой связи. Например, интерфейсы связи могут быть выполнены с возможностью обмениваться данными по компьютерной сети. Например, интерфейс связи может быть выполнен с возможностью осуществления беспроводной связи, например, Wi–Fi, ZigBee, Bluetooth и т.п., и/или проводной связи, например, Ethernet, USB и т.п. Связь между узлами 110 и 210 также может представлять собой комбинацию проводных и беспроводных соединений. Например, узлы в системе 100, включающей в себя узлы 110 и 120, могут содержать электронное устройство хранения данных, которое содержит идентификатор связи, который уникально идентифицирует узел в системе 100. Например, идентификатор связи может быть включен в цифровые сообщения, которыми обмениваются между узлами 110 и 210, например, чтобы адресовать сообщение. Например, идентификатор связи может представлять собой IP–адрес, MAC–адрес и т.п.
Электронный сетевой узел сконфигурирован для протокола обмена ключами (KEX). Протокол заключает в себе обмен сообщениями между узлами 110 и 210 по интерфейсам 120 и 220 связи и выполнение вычислений, например, для данных, принимаемых из другого узла. Выполнение протокола согласования ключей реализуется в процессорной схеме, примеры которой показаны ниже. Фиг. 1 показывает функциональные модули, которые могут представлять собой функциональные модули процессорной схемы. Например, фиг. 1 может использоваться в качестве проекта возможной функциональной организации процессорной схемы. Процессорная схема не показана отдельно от модулей на фиг. 1. Например, функциональные модули, показанные на фиг. 1, также может полно или частично реализовываться в компьютерных инструкциях, которые сохраняются в сетевых узлах и выполняются посредством микропроцессора сетевого узла.
Узел–инициатор 110 и узел–ответчик 210 сконфигурированы для протокола обмена ключами (KEX). KEX–схемы заключают в себе обмен общедоступными данными, зачастую называемые "общедоступными ключами", посредством каждой стороны, которые затем независимо используются посредством другой стороны наряду с конфиденциальными данными, зачастую называемыми "секретными ключами", чтобы вычислять общий совместно используемый секрет. Интересный признак некоторых вариантов осуществления заключается в том, что фактический конечный совместно используемый секрет никогда не передается между сторонами, даже в зашифрованной форме, а вычисляется независимо посредством двух сторон на каждом конце. Это приводит к требуемому признаку, известному как прямая секретность, которая обеспечивает то, что даже компрометация долговременных секретных ключей стороны посредством взломщика в будущем не должна компрометировать секретность зашифрованного сообщения, которым обмениваются в прошлом.
Варианты осуществления изобретений не основываются на доверенной третьей стороне, чтобы предоставлять конфиденциальную связь. Канал связи между интерфейсами 120 и 220 связи не должен обязательно представлять собой защищенный канал. Взломщики могут иметь возможность перехватывать сообщения в канале связи. Несмотря на это, ключ, который согласован между узлами 110 и 210, может быть защищенным. Если канал связи защищается от изменений, степень аутентификации может получаться в такой мере, которая обеспечивается посредством канала. Тем не менее, если канал между интерфейсами 120 и 220 связи не защищается от изменений, KEX–схема не должна достигать аутентификации. Чтобы получать аутентификацию, варианты осуществления могут комбинироваться с любым известным механизмом аутентификации, например, с механизмом неявной аутентификации, например, с использованием сертифицированных общедоступных ключей, или с механизмом явной аутентификации, например, с использованием цифровых подписей.
Известный пример KEX–схемы представляет собой обмен ключами Диффи–Хеллмана, безопасность которого основана на решении задачи дискретного логарифма. В изобретении, задается механизм обмена ключами, трудность которого основана на так называемой задаче обучения за счет округления (LWR). Трудность LWR-задачи может быть основана на предположении трудности так называемой задачи обучения за счет ошибок (LWE), когда число LWE–экземпляров ограничивается. Поскольку трудность по принципу среднего случая LWE-задачи основана на трудности по принципу наихудшего случая определенных связанных задач на основе решеток, которые затруднительно разрешаться для квантового компьютера, эта схема обмена ключами представляет собой постквантовый защищенный протокол согласования ключей.
Задача обучения за счет ошибок (LWE) представляет собой математически трудную задачу и приводит к постквантовым криптографическим схемам вследствие своей предполагаемой трудности даже касательно квантовых компьютеров и хорошо проработанной безопасности. Тем не менее, схемы, возникающие из означенного, типично имеет существенные требования по производительности, относительно сложностей вычислений и связи. Задача обучения за счет ошибок (LWE) может описываться следующим образом:
Для n–мерного вектора  и распределения X ошибок по , LWE–распределение по  получается посредством выбора вектора a равномерно и случайно из  и ошибки e из X и вывода .
LWE-задача поиска состоит в том, чтобы находить  с учетом произвольно большого числа независимых выборок  из . LWE-задача принятия решений, обозначаемая посредством , состоит в том, чтобы отличать распределение  от равномерного распределения по  с непренебрежимо малым преимуществом, для фиксированного .
LWR-задача представляет собой "дерандомизированную" версию LWE-задачи, посредством использования округления с неотрицательной величиной "p" вместо вставки ошибок, с тем чтобы скрывать секретную информацию, и затем введения детерминированной ошибки посредством понижающего масштабирования от  (где q является первоначальной неотрицательной величиной LWE) до .
Для n–мерного вектора , LWR–распределение  по  получается посредством выбора вектора a равномерно и случайно из  и вывода .
Здесь,  обозначает целое число, ближайшее к x. LWR-задача поиска задается с точки зрения нахождения секрета s, точно аналогично LWE-задаче поиска. LWR-задача принятия решений состоит в том, чтобы отличать распределение  от равномерного распределения по  с m экземплярами для фиксированного . Показано, что LWR-задачи поиска и принятия решений являются, по меньшей мере, не менее трудными, чем соответствующие LWE-задачи, когда m ограничивается таким образом, что  является константой (где B является пределом для ошибок в LWE-задаче).
Постквантовые схемы обмена ключами на основе LWE-задачи пользуются повсеместным доверием вследствие хорошо проработанной безопасности LWE-задачи. Тем не менее, отсутствует LWE–схема обмена ключами, которая имеет несущественные требования по производительности, допускающая использование в ресурсоограниченных окружениях. Существующие алгоритмы включают в себя различные операции, которые являются медленными на ресурсоограниченных устройствах, такие как: матричное умножение по модулю q, дискретизация из распределения вероятностей, таких как гауссово распределение, и вычисление или передача матриц с большими записями.
В изобретении, две стороны формируют две матрицы, которые являются приблизительно, но не точно равными. Чтобы проводить точное согласование, отправляются некоторые сверочные данные. Схема для осуществления означенного поясняется в патентной заявке того же самого заявителя, озаглавленной "REACHING AGREEMENT ON A SECRET VALUE", поданной в EPO 4 ноября 2016 года, с номером заявки 16197277.3; например, способ на страницах 7–10 может использоваться для сверки в вариантах осуществления согласно изобретению. Также могут приспосабливаться разновидности, раскрытые в другом месте в процитированной заявке на патент.
В этой заявке используется следующая система обозначений для следующих трех функций:
1. Функция  округления: Для , пусть .
Тогда:
Интуитивно,  извлекает B старших битов , при этом второй компонент представляет собой коэффициент округления, чтобы обеспечивать несмещенные ошибки округления.
2. Функция  перекрестного округления: Для , пусть .
Тогда:
Интуитивно,  извлекает  младших битов из  старших битов .
3. Сверочная функция : Для ,
,
где v является ближайшим элементом в w таким образом, что .
Вышеуказанная сверочная функция используется в качестве примера, в данном документе. Как отмечено выше, также могут использоваться способы сверки в вышеуказанной заявке. Фиг. 2 является схематичной иллюстрацией функций округления и перекрестного округления. В качестве примера, фиг. 2 показан исходный ключ 300. Исходный ключ 300 проиллюстрирован в качестве битовой строки со старшими битами влево и младшими битами вправо. Интуитивно, функция округления, применяемая к исходному ключу, соответствует B битов в старшей части 301, функция перекрестного округления –  следующих битов в средней части 302. Младшие  могут отбрасываться.
Узел–инициатор 110 содержит модуль 130 обработки совместно используемых матриц. Узел–ответчик 210 содержит модуль 230 обработки совместно используемых матриц. Модули 130 и 230 обработки совместно используемых матриц выполнены с возможностью получать совместно используемую матрицу (A), которая совместно используется двумя узлами. Записи в совместно используемой матрице A являются целыми числами, выбранными по модулю первая неотрицательная величина q. Предусмотрено множество способов обеспечивать то, что идентичная матрица совместно используется узлами 110 и 210, в частности, с учетом того факта, что матрица A не обязательно сохраняется конфиденциальной для узлов 110 и 210.
Например, один из узлов, скажем, узел–инициатор 110, например, в модуле 130 обработки совместно используемых матриц, может выбирать матрицу A, например, произвольно с элементами по модулю q. Записи затем могут отправляться через модули связи в другой узел, например, в модуль 230 обработки совместно используемых матриц. В этом случае, второй модуль 230 обработки совместно используемых матриц должен просто принимать матрицу и сохранять ее. Матрица A также может выбираться посредством узла–ответчика 210 вместо этого и отправляться в узел–инициатор 110.
Два узла также могут взаимодействовать в выборе матрицы A. Например, каждый узел может выбирать некоторые записи и отправлять их другой стороне. Например, узлы–инициаторы могут выбирать нечетные записи, а узел–ответчик – четные записи и т.д. Таким образом, ни один из двух узлов не управляет конечной матрицей A. Например, два узла могут выбирать полную матрицу A и передавать ее другой стороне. После этого, две матрицы могут суммироваться по модулю q. Чтобы не допускать предоставления последнему узлу для отправки матрицы преимущества, удостоверение по выбранной матрице сначала может отправляться упомянутым последним узлом.
Интересный способ уменьшать объем служебной информации для отправки полной матрицы A состоит в том, чтобы формировать случайное инициирующее число и отправлять случайное инициирующее число через канал связи в другой узел. После приема инициирующего числа, первый и второй сетевой узел могут использовать его для формирования матрицы A любым из вышеуказанных способов. Идентичное случайное инициирующее число используется для того, чтобы отбирать детерминированный генератор псевдослучайных чисел, который в свою очередь формирует матрицу (A) из вывода генератора псевдослучайных чисел. Как описано выше, каждый узел может отправлять инициирующее число, например, чтобы формировать различные части A, либо два инициирующих числа могут комбинироваться, например, суммироваться или подвергаться операции XOR и т.д., и комбинированное инициирующее число может использоваться для того, чтобы формировать A.
Инициирующие числа, например, могут выбираться из дополнительного генератора случайных чисел, например, генератора истинных случайных чисел. Узлы также могут быть сконфигурированы со списком случайных чисел, например, при изготовлении. В этом случае, узлы выбирают следующее случайное число из списка каждый раз, когда новая матрица A формируется для нового согласования ключей. Если список случайных чисел является исчерпывающим, он может пополняться из надежного источника.
В варианте осуществления, матрица A представляет собой квадратную матрицу с размерностями nxn. Это не является строго необходимым; размерности других элементов протокола могут адаптироваться с возможностью учитывать неквадратную матрицу A. Тем не менее, выбор квадратной матрицы A является самым удобным и предполагается во всем описании.
Узел–инициатор 110 содержит модуль 140 обработки матриц конфиденциальных ключей. Узел–ответчик 210 содержит модуль 240 обработки матриц конфиденциальных ключей. Модуль 140 обработки матриц конфиденциальных ключей выполнен с возможностью формировать матрицу  конфиденциальных ключей; Модуль 240 обработки матриц конфиденциальных ключей выполнен с возможностью формировать матрицу  конфиденциальных ключей. Записи в матрицах конфиденциальных ключей являются целыми числами, ограниченными по абсолютному значению пределом s. Например, запись в матрице конфиденциальных ключей может выбираться между –s и s (пределы включены).
Авторы изобретения обнаружили то, что, неожиданно, выбор небольшого предела обеспечивает двойное преимущество: матричные умножения с матрицей конфиденциальных ключей выполняются быстрее, и расстояние между исходными ключами, вычисленными в каждой стороне, является меньшим (см. ниже). Второе означает то, что требуется меньше сверочных данных, и/или вероятность сбоя в протоколе, поскольку узлы согласуют различный ключ, является меньшей. Предел s выбирается самое большее как вторая неотрицательная величина, например, как меньший или равный второй неотрицательной величине. Этот выбор является преимущественным, поскольку позднее проводится умножение по модулю p. Можно ограничивать его самое большее (или менее чем), половиной второй неотрицательной величины (p/2), если разрешаются записи со знаком в S.
Предел может составлять ниже второй неотрицательной величины или половины второй неотрицательной величины, и на практике предел типично должен выбираться гораздо меньшим неотрицательной величины. В варианте осуществления, предел s на абсолютное значение записей в матрице () конфиденциальных ключей равен 2 (). Таким образом, все записи в матрице конфиденциальных ключей или равны –2, –1, 0, 1 или 2. Чтобы умножать матрицу A на матрицу конфиденциальных ключей, требуются только суммирования, вычитания и сдвиги на 1 бит. Такое матричное умножение в силу этого может реализовываться очень эффективно.
С точки зрения реализации, наилучшие результаты достигаются посредством выбора предела равным 1 (). Таким образом, записи матрицы конфиденциальных ключей имеют только значения в –1, 0 и 1. Она также называется "двоичной строкой со знаком". Матричное умножение с матрицей в двоичной строке со знаком заключает в себе только суммирования и вычитания. Модуль умножения для умножения по модулю p или q не требуется.
Другие небольшие числа для s также являются возможными, например, если s=3, разрешенные записи представляют собой: 0, 1, –1, 2, –2, 3, –3. Процедуры умножения для умножения на эти числа могут содержаться в узлах. Например, +1, –1 могут обрабатываться посредством сумматора/вычитателя, –2, +2 могут обрабатываться посредством сдвига, сопровождаемого посредством сумматора/вычитателя, и +3, –3 могут обрабатываться посредством суммирования/вычитания сдвинутого и несдвинутого числа.
В варианте осуществления, матрица конфиденциальных ключей содержит только записи, которые равны 0, степени двух и, в необязательном порядке, минус степени двух, поскольку на них легко умножать.
В варианте осуществления, матрица конфиденциальных ключей содержит положительные и отрицательные числа. Тем не менее, также можно дополнительно ограничивать матрицу конфиденциальных ключей неотрицательными числами. Например, записи в матрице конфиденциальных ключей могут составлять между 0 и s (пределы включены). Например, посредством выбора , во втором случае можно исключать операции умножения и вычитания.
Размерности матриц конфиденциальных ключей выбираются таким образом, что они могут умножаться на матрицу A. Например, если A составляет nxn, то матрица конфиденциальных ключей узла–инициатора может представлять собой матрицу x; матрица конфиденциальных ключей узла–ответчика может представлять собой матрицу x. Размеры  и  выбираются достаточно большими для того, чтобы получать достаточное число битов в совместно используемом ключе и получать достаточно высокий уровень безопасности.
В дополнение к ограничению размера записей матрицы конфиденциальных ключей, дополнительные преимущества получаются посредством ограничения числа ненулевых элементов. Весовой коэффициент Хэмминга столбца или строки матрицы упоминается в качестве ее числа ненулевых записей.
Авторы изобретения исследовали различные способы ограничивать весовой коэффициент Хэмминга матриц конфиденциальных ключей. В общем, достаточно ограничивать весовой коэффициент Хэмминга для столбцов или для строк, в зависимости от того, матрица конфиденциальных ключей умножается влево или вправо на матрицу A. Например, если матрица конфиденциальных ключей умножается вправо на матрицу A (например, AS), достаточно ограничивать весовой коэффициент Хэмминга в столбцах матрицы конфиденциальных ключей.
Например, верхний предел может выбираться для весового коэффициента Хэмминга столбцов и/или строк матрицы конфиденциальных ключей. Верхний предел может быть идентичным для всех столбцов и/или строк. В варианте осуществления, столбцы и/или строки матрицы () конфиденциальных ключей имеют идентичный фиксированный весовой коэффициент Хэмминга.
Безопасность повышается, если (согласно условиям) матрица конфиденциальных ключей выбирается равномерно случайной из возможных вариантов матриц конфиденциальных ключей, т.е. из матриц, которые удовлетворяют выбранным требованиям, например, в отношении пределов для записей и весовых коэффициентах Хэмминга в столбцах или строках. Например, если желательно принудительно активировать такое условие, что весовой коэффициент Хэмминга каждого столбца равен 50, то преимущественно выбирать матрицу конфиденциальных ключей из набора всех матриц с корректными размерностями, которые имеют весовой коэффициент Хэмминга в 50 для каждого столбца. Известны эффективные алгоритмы для того, чтобы выбирать равномерно случайную битовую строку любого требуемого весового коэффициента Хэмминга.
Другой способ ограничивать весовой коэффициент Хэмминга матриц конфиденциальных ключей состоит в том, чтобы выбирать столбцы и/или строки матрицы () конфиденциальных ключей из распределения вероятностей. Например, записи в матрице () конфиденциальных ключей могут выбираться из неравномерного распределения вероятностей, при этом вероятность нулевой записи превышает вероятность ненулевой записи. В варианте осуществления, распределение вероятностей выбирается таким образом, что оно обеспечивает предварительно определенный ожидаемый весовой коэффициент Хэмминга для столбцов и/или строк. Например, чтобы выбирать столбец длины n и с ожидаемым весовым коэффициентом  Хэмминга, можно выбирать каждую запись в качестве ненулевой с вероятностью . Ненулевая запись может выбираться в качестве 1 или –1, например, с равной вероятностью.
Весовой коэффициент Хэмминга в столбцах или строках, который является слишком небольшим, может оказывать влияние на безопасность. Например, для двоичного случая со знаком, можно выбрать весовой коэффициент  Хэмминга таким образом, что составляет, по меньшей мере, 127, более предпочтительно, по меньшей мере, 255. Причина состоит в том, чтобы приводить к неосуществимости атаки на основе метода прямого опробования посредством цикличного выполнения для матриц конфиденциальных ключей. В варианте осуществления, весовой коэффициент  Хэмминга является максимально возможно небольшим, чтобы удовлетворять вышеуказанному пределу.
Узел–инициатор 110 содержит модуль 150 обработки матриц общедоступных ключей. Узел–ответчик 210 содержит матрицу 250 общедоступных ключей. Модуль обработки матриц общедоступных ключей вычисляет матрицу общедоступных ключей из матрицы A и матрицы S конфиденциальных ключей.
Термины "общедоступный и конфиденциальный" имеют намерение передавать то, что совместно используемый ключ не может получаться только со знанием общедоступной информации либо не без знания некоторой конфиденциальной информации. Тем не менее, отсутствует такое требование, что общедоступная информация активно совместно используется. Например, протокол согласования ключей может выполняться по (предполагаемому) защищенному каналу, что сохраняет общедоступные ключи защищенными от устройств перехвата сообщений. В этом случае, протокол согласования ключей предоставляет дополнительный уровень безопасности в случае, если безопасность канала нарушена.
Модуль обработки матриц общедоступных ключей вычисляет матрицу P общедоступных ключей (, для инициатора и ответчика, соответственно) посредством вычисления матричного произведения между совместно используемой матрицей (A) и матрицей ( или , соответственно) конфиденциальных ключей по модулю первая неотрицательная величина (q), с получением матричного произведения и понижающим масштабированием результата.
Тем не менее, это промежуточное матричное умножение не раскрывается. Знание совместно используемой матрицы A и результата этого матричного умножения должно раскрывать конфиденциальный ключ, поскольку он может вычисляться посредством инверсии матрицы A. Этап масштабирования, выполняемый посредством модуля обработки матриц общедоступных ключей, блокирует эту опцию. Модуль обработки матриц общедоступных ключей понижающе масштабирует записи в матричном произведении до второй неотрицательной величины p. Вторая неотрицательная величина p меньше первой неотрицательной величины q. Масштабированная запись равна немасштабированной записи, умноженной на вторую неотрицательную величину (p), деленной на первую неотрицательную величину (s) и округленной до ближайшего целого числа. Например, если x является немасштабированной записью по модулю q в матричном произведении, масштабированная запись может выбираться в качестве , при этом  представляет ближайшее целое число. После операции масштабирования, более невозможно просто вычислять конфиденциальный ключ из общедоступного ключа и матрицы A.
Записи в матрице общедоступных ключей могут представляться как целые числа в интервале . Записи в матрице конфиденциальных ключей также могут представляться как целые числа в интервале . Имеется преимущество в том, чтобы выбирать записи в интервале , чтобы уменьшать размер целых чисел для последующих умножений. Как указано выше, матрица конфиденциальных ключей также может иметь записи, выбранные в интервале  или даже .
Умножение матрицы A и матрицы S конфиденциальных ключей осуществляется по модулю первая неотрицательная величина q. Для этой цели, сетевой узел может содержать модульный модуль уменьшения для уменьшения по модулю q. Если записи в матрице S конфиденциальных ключей являются небольшими, например, ограниченными посредством 1 или ограниченными посредством предела в 1 по абсолютному значению, модульное уменьшение может упрощаться; во время матричного умножения, каждый раз, когда запись становится больше q или меньше 0, результат возвращается в интервал 0– посредством вычитания или суммирования q.
Как узел–инициатор, так и узел–ответчик отправляют свою матрицу общедоступных ключей в другой узел, например, с использованием интерфейсов 120 и 220 связи. Авторы изобретения выявили, по меньшей мере, три преимущества, которые реализованы посредством понижающего масштабирования матричного произведения. Во–первых, формирование и явное прибавление шума в матричное произведение не допускаются. Введение шума требует вычисления распределения вероятностей, например, гауссова распределения. Они имеют относительно большой объем вычислений. Во–вторых, требования по связи уменьшаются. Поскольку вторая неотрицательная величина p меньше первой неотрицательной величины q, меньшее число битов требуется для того, чтобы представлять запись матрицы общедоступных ключей, чем матрицы конфиденциальных ключей. В–третьих, вычисления, которые заключают в себе матрицу общедоступных ключей, являются меньшими, поскольку они заключают в себе меньшие числа. Удивительно, что одна мера одновременно предоставляет три преимущества.
Очень предпочтительно, если первая неотрицательная величина q делится на вторую неотрицательную величину p. Интересно, что авторы изобретения обнаружили то, что ни первая, ни вторая неотрицательная величина не должен обязательно быть простым числом. Фактически, обнаружено, что выбор второй неотрицательной величины (p) и/или первой неотрицательной величины (q) в качестве степени 2 имеет такое преимущество, что общедоступные и конфиденциальные ключи равномерно распределены. В варианте осуществления, первая и вторая неотрицательная величина являются степенями 2.
В варианте осуществления, дополнительно требуется то, что  в дополнение к неотрицательным величинам p и q, которые являются степенями двух. Это приводит к равномерным совместно используемым ключам, даже если сверочные данные наблюдаются. B является числом битов совместно используемого ключа, извлеченных в расчете на запись исходного ключа.
Размеры неотрицательных величин не должны обязательно быть очень большими. Например, в варианте осуществления, вторая неотрицательная величина имеет в качестве размера в битах 12 или более, и/или первая неотрицательная величина имеет в качестве размера в битах 8 или более. Большие или меньшие размеры являются возможными в зависимости от требований по обеспечению безопасности. В варианте осуществления, q находится в диапазоне 2^12 и 2^15, p находится в диапазоне 2^7 и 2^9 (включительно). Значения p и q могут выбираться большими или меньшими согласно предписанию требований безопасности.
Узел–инициатор 110 содержит модуль 160 обработки совместно используемых ключей. Узел–ответчик 210 содержит модуль 260 обработки совместно используемых ключей. Модули обработки совместно используемых ключей отличаются в том смысле, что они или формируют и передают или принимают и применяют сверочные данные.
Как модуль 160 обработки совместно используемых ключей, так и модуль 260 обработки совместно используемых ключей выполнены с возможностью вычислять исходный ключ 162, 262 в качестве матричного произведения по модулю вторая неотрицательная величина (p) между принимаемым общедоступным ключом другого узла и матрицей конфиденциальных ключей самого сетевого узла. Размерности матриц и матричные умножения выбираются таким образом, что если операция масштабирования должна опускаться, то обе стороны должны вычислять идентичный исходный ключ. Таким образом, идентичные ключи должны получаться в результате без масштабирования, и все вычисления должны проводиться по модулю q. Тем не менее, вследствие масштабирования, оба исходных ключа не должны обязательно быть идентичными. Вычисление исходного ключа проводиться по модулю p. Сетевые узлы могут содержать модульный модуль для уменьшения результата умножений по модулю p.
Модуль 260 обработки совместно используемых ключей узла–ответчика 210 выполнен с возможностью получать совместно используемый ключ 266 и сверочные данные 264 из исходного ключа 262 и отправлять сверочные данные 264 в сетевой узел–инициатор 110. Сверочные данные могут принимать форму одного или более битов в исходном ключе. Биты, выбранные в качестве сверочных данных, игнорируются в целях формирования ключа.
Модуль 260 обработки совместно используемых ключей выбирает некоторые биты из записей исходного ключа, из которых следует формировать ключ. Например, выбранные биты могут конкатенироваться. В варианте осуществления, выбранные биты вводятся в функцию извлечения ключей (KDF), например, в криптографическую хеш–функцию. Пример KDF, например, представлен в CMLA_KDF из CMLA Technical Specification, Version: V1.43–20131218, либо в KDF–функции, заданной в "DRM specification", OMA–TS–DRM–DRM–V2_0_2–20080723–A, Open Mobile Alliance™, Version 2.0.2, section 7.1.2, и т.д. Функция извлечения ключей может применяться к записям битов ключа в исходном ключе, например, полученном посредством функции округления, например, после конкатенации, либо из выводов из сверочной функции, например, также после конкатенации.
Некоторые биты, которые не выбираются в качестве битов ключа, могут выбираться в качестве сверочных данных. В завершение, некоторые биты могут отбрасываться вообще. В варианте осуществления, биты ключа выбираются из MSB–частей записей исходных ключей, сверочные данные выбираются из средних частей записей исходных ключей, младшие части исходного ключа могут отбрасываться. Например, биты ключа могут получаться посредством применения функции округления к записям исходного ключа; сверочные биты могут получаться посредством применения функции перекрестного округления к записям исходного ключа.
Сверочные данные ключей, полученные из исходного ключа посредством модуля 260 обработки совместно используемых ключей, отправляются в узел–инициатор 110.
Модуль 160 обработки совместно используемых ключей выполнен с возможностью принимать сверочные данные 164 (h) второго сетевого узла и вычислять совместно используемый ключ посредством применения сверочной функции к принимаемым сверочным данным и матрице 162 исходных ключей. Например, сверочная функция может применяться к каждой из записей в исходном ключе 162 и к соответствующей части сверочных данных. Например, если сверочные данные 164 являются частью исходного ключа, сформированного посредством модуля–ответчика 210, узел–инициатор может выбирать исходный ключ, который может получаться посредством узла 210, и являются совместимыми с принимаемыми сверочными данными, например, имеют идентичные с принимаемыми средние биты. Один способ для означенного состоит в том, чтобы использовать сверочную функцию, заданную выше. Как результат, восстанавливаются идентичные биты с теми, который узел 210 использует для того, чтобы создавать совместно используемый ключ. Посредством конкатенации битов аналогичным образом или посредством их ввода в идентичную KDF, получается идентичный совместно используемый ключ 166. В варианте осуществления, совместно используемый ключ представляет собой симметричный ключ.
Требуется немного сверочных данных, может быть достаточно только одного бита. Тем не менее, следует отметить, что увеличение числа сверочных битов до 2 битов или более является преимущественным, поскольку оно уменьшает вероятность отказа протокола.
Типичные значения для B и  равны 1 или 2. В данном документе, B является числом битов ключа, извлеченных в расчете на запись исходного ключа, и  является числом сверочных битов в расчете на запись исходного ключа. Размер  и  выбирается таким образом, что  является достаточно большим, например, . Например,  и  могут выбираться приблизительно равными. Чтобы поддерживать небольшим объем служебной информации, можно выбирать их как .
Можно многократно использовать одну из матрицы A и матрицы конфиденциальных ключей для нескольких выполнений протокола согласования ключей (если обе из них являются идентичными, можно получать идентичный совместно используемый ключ). Это должно уменьшать объем служебной информации по связи, в частности, если матрица A многократно используется. Тем не менее, авторы изобретения поняли, что нет необходимости в том, чтобы многократно использовать любую из матрицы A и матрицы конфиденциальных ключей, поскольку аутентификация не соединяется с этими элементами. В предпочтительном варианте осуществления, свежая матрица A и свежий конфиденциальный ключ получаются для каждого нового обмена ключами. Это имеет такое преимущество, что взломщики не имеют опции наблюдать дополнительную информацию посредством наблюдения нескольких выполнений протокола. Кроме того, повышается прямая секретность.
После того, как протокол завершается, и оба узла вычисляют совместно используемый ключ, один из узлов может отправлять сообщение подтверждения правильности ключа в другой узел, чтобы верифицировать то, что они согласуют идентичный ключ. Например, сообщение подтверждения правильности ключа может представлять собой хеш совместно используемого ключа, шифрование фиксированного значения, шифрование случайного значения вместе со случайным значением. Подтверждение правильности ключа также может выполняться с использованием протокола по методу "вызов–ответ". Можно также выбирать опускать подтверждение правильности ключа. Если стороны получают различный совместно используемый ключ, то последующая связь, выполняемая между ними, должна завершаться неудачно. Например, совместно используемый ключ может использоваться для того, чтобы шифровать и/или аутентифицировать дополнительную связь, например, цифровые сообщения. Если они добиваются различного совместно используемого ключа, то дешифрование и/или верификация могут завершаться неудачно.
Ниже описываются дополнительные конкретные преимущественные варианты осуществления. Базовая система, представляющая это изобретение, представляет собой протокол, далее называемый "схемой обмена ключами (KEX)", который может выполняться посредством двух объектов или сторон, далее называемых "инициатором" и "ответчиком", чтобы устанавливать совместно используемый секрет между собой, который известен только для них. С этой целью, они используют определенное число параметров общей системы, которые они должны согласовывать до выполнения KEX–схемы, некоторую конфиденциальную информацию, которой обладает каждый из них, далее называемую "их секретными ключами", и некоторую открытую информацию, которой обладает каждый из них, далее называемую "их открытыми ключами". Безопасность KEX–схемы основана на задаче обучения за счет округления (LWR), безопасность которой основана на задаче обучения за счет ошибок (LWE), с защитой секретности совместно используемого секрета и секретности секретных ключей инициатора и ответчика. В нижеприведенных примерах, матрицы конфиденциальных ключей представляют собой двоичную строку со знаком.
Вариант осуществления KEX–схемы содержит три фазы:
1. Установление:
Инициатор и ответчик согласуют общие значения для следующих системных параметров, которые являются положительными целыми числами:
i. q: Неотрицательная величина LWR-задачи.
ii. n: Размерность LWR-задачи. Он также представляет размерность матрицы , которая является открытым параметром LWR-задачи.
iii. : Весовой коэффициент Хэмминга каждой строки в распределении двоичных строк со знаком (т.е. троичных) таким образом, что .
iv. : Число экземпляров LWR-задачи или выборок, созданных посредством инициатора в ходе работы KEX–протокола.
v. : Число экземпляров LWR-задачи или выборок, созданных посредством ответчика в ходе работы KEX–протокола.
vi. B: Число битов, извлеченных в расчете на коэффициент исходных ключей двух сторон, при создании конечного совместно используемого секрета или ключа.
vii. : Число битов, извлеченных в расчете на коэффициент исходных ключей двух сторон, при создании сверочных данных.
viii. p: неотрицательная величина округления LWR-задачи, целое кратное , удовлетворяющий . Следует отметить, что требование p в качестве степени двух предоставляет возможность быстрых внедрений и более эффективных реализаций.
Кроме того, стороны согласуют общедоступную матрицу.
i. : Свежий экземпляр этой матрицы выбирается для каждого KEX–сеанса.
Выбор общих параметров может интегрироваться в такой протокол, как TLS или IKE, если конкретные параметры преобразуются в данный идентификатор. Например, идентификатор протокола, например, в TLS элемент шифронабора, может использоваться для того, чтобы кодировать общие параметры. Общедоступная матрица также может извлекаться из инициирующего числа, например, посредством хеш–функции. В другом решении, инициатор должен определять некоторые параметры, которые должны отправляться в ответчик.
2. Формирование ключей:
Инициатор создает свежий секретный ключ  посредством дискретизации  раз из распределения , которое представляет распределение равномерных векторов в , которые имеют весовой коэффициент  Хэмминга.
Инициатор создает общедоступный ключ .
Ответчик создает свежий секретный ключ  посредством дискретизации  раз из распределения , которое представляет распределение равномерных векторов в , которые имеют весовой коэффициент  Хэмминга.
Ответчик создает общедоступный ключ .
3. Обмен ключами:
Табл. 1. Обмен ключами между инициатором I и ответчиком R с использованием округления и матриц разреженных секретов, содержащих троичные записи, что приводит к установлению совместно используемого секрета K между I и R. Средний столбец предоставляет пример сообщений, которыми можно обмениваться между инициатором и ответчиком.
KEX–инициатор
KEX–ответчик
Согласует свежий <img file="00000058.jpg" he="7" wi="14" img-content="undefined" img-format="jpg" /> с равноправным узлом, выбирает свежий секретный <img file="00000062.jpg" he="6" wi="47" img-content="undefined" img-format="jpg" />, <img file="00000068.jpg" he="6" wi="12" img-content="undefined" img-format="jpg" /> таким образом, что <img file="00000069.jpg" he="6" wi="9" img-content="undefined" img-format="jpg" />и <img file="00000061.jpg" he="6" wi="5" img-content="undefined" img-format="jpg" />.
Согласует свежий <img file="00000070.jpg" he="7" wi="14" img-content="undefined" img-format="jpg" /> с равноправным узлом, выбирает свежий секретный <img file="00000066.jpg" he="6" wi="49" img-content="undefined" img-format="jpg" />, <img file="00000068.jpg" he="6" wi="12" img-content="undefined" img-format="jpg" /> таким образом, что <img file="00000069.jpg" he="6" wi="9" img-content="undefined" img-format="jpg" />и <img file="00000061.jpg" he="6" wi="5" img-content="undefined" img-format="jpg" />.
<img file="00000065.jpg" he="9" wi="56" img-content="undefined" img-format="jpg" />.
<img file="00000067.jpg" he="9" wi="58" img-content="undefined" img-format="jpg" />.
<img file="00000071.jpg" he="22" wi="60" img-content="undefined" img-format="jpg" />
<img file="00000072.jpg" he="7" wi="53" img-content="undefined" img-format="jpg" />.
<img file="00000073.jpg" he="7" wi="38" img-content="undefined" img-format="jpg" />.
<img file="00000074.jpg" he="18" wi="62" img-content="undefined" img-format="jpg" />
<img file="00000075.jpg" he="7" wi="53" img-content="undefined" img-format="jpg" />.
<img file="00000076.jpg" he="7" wi="43" img-content="undefined" img-format="jpg" />, где <img file="00000077.jpg" he="6" wi="2" img-content="undefined" img-format="jpg" />является ближайшим элементом к <img file="00000078.jpg" he="6" wi="10" img-content="undefined" img-format="jpg" /> таким образом, что <img file="00000079.jpg" he="7" wi="16" img-content="undefined" img-format="jpg" />.
<img file="00000080.jpg" he="7" wi="26" img-content="undefined" img-format="jpg" />.
Авторы изобретения нашли четыре требования, которые могут налагаться на параметры, чтобы повышать безопасность. Они включают в себя следующее.
1. Минимальная длина ключа: Чтобы обеспечивать то, что совместно используемый секрет содержит, по меньшей мере, целевое число битов, параметр  инициатора, параметр  ответчика и системный параметр B должны быть такими, что:
требуемая длина совместно используемого секрета в битах
2. Безопасность касательно атаки методом исчерпывающего поиска секретного ключа: Предполагается целевой уровень безопасности в битах в S (постквантовый) и в 2S (классический). Чтобы обеспечивать то, что исчерпывающий поиск методом прямого опробования секретного ключа, чтобы оценивать ее записи, имеет достаточно высокую рабочую нагрузку, число секретов в векторах секретных ключей (каждый из которых имеет весовой коэффициент  Хэмминга) должно удовлетворять следующему:
,
где  является временем выполнения квантового алгоритма поиска Гровера, и  является временем выполнения классического алгоритма поиска. Например, S может составлять 128 или 256 и т.д. Следует отметить, что этот предел предназначен для случая, в котором предел на абсолютных значениях записей в матрицах конфиденциальных ключей равен 1. Аналогичный предел может устанавливаться для больших пределов s.
3. Вероятность успешности: чтобы обеспечивать то, что вероятность того, что инициатор и ответчик не добиваются идентичного конечного совместно используемого секрета, составляет самое большее , значения для параметров , ,  и константа  должны выбираться таким образом, что:
где
4. Анализ безопасности: Чтобы обеспечивать то, что временная сложность BKZ–алгоритма уменьшения решетки составляет, по меньшей мере,, что гарантирует 128–битовую постквантовую безопасность, LWR–размерность n должна превышать следующий нижний предел, выражаемый с точки зрения корневого эрмитова BKZ–коэффициента δ (параметра BKZ–алгоритма), неотрицательной величины p округления и степени  разреженности:
Корневой эрмитов BKZ–коэффициент δ является индикатором относительно точности BKZ–алгоритма. Например, для классической безопасности, можно предполагать , с размером BKZ–блока=409, для постквантовой криптографии можно предполагать, что , с размером BKZ–блока=450, и для повышенной безопасности в постквантовой криптографии можно предполагать, что , размером BKZ–блока=573.
Выбор матриц конфиденциальных ключей может осуществляться вероятностно. Вероятностное формирование секретных ключей упрощает реализацию. При создании секретного ключа  и , вместо формирования  ненулевых записей для каждого столбца секретных ключей, каждая  запись секретного ключа  в этом варианте осуществления должна создаваться следующим образом:
(i,j)
s
sk=1, с вероятностью = (h/2n)
(i,j)
s
sk=–1, с вероятностью = (h/2n)
(i,j)
s
sk=0, с вероятностью = (1–h/n).
Альтернативно, если формирование является детерминированным, то следующее может осуществляться с использованием стандартного защищенного PRF: если имеется  ненулевых элементов (или 1 или –1) в векторе n позиций, то PRF–вывод выбирает случайные позиции в столбце наряду со случайным значением +1 или –1, до тех пор, пока PRF не выбирает  ненулевых элементов в различных местоположениях. Например, PRF–вывод может разделяться на блоки из  битов, в которых первые  битов блока идентифицируют позицию ненулевого элемента, и последний бит блока определяет то, равен элемент 1 или –1.
Предложенный обмен ключами имеет несколько преимуществ.
Вычислительная сложность: Поскольку матрица секретных ключей является разреженной и имеет записи, 0, 1 и –1, вычисления по модулю q в нашей схеме являются быстрыми. В частности, умножения, заключающие в себе матрицы высокой размерности (например, во время формирования общедоступных ключей и исходных ключей) могут быть высокооптимизированными. Производительность вычислений предложенной схемы обмена ключами количественно определяется в следующей таблице, предоставляющей тактовые CPU–циклы, требуемые в течение фаз схемы обмена ключами при выполнении на процессоре Intel Xeon Quadcore в 3,2 ГГц:
Табл. 2. Производительность вычислений предложенной схемы, показывающей тактовые CPU–циклы, требуемые для формирования ключей и полного обмена ключами, для трех уровней безопасности. Число конечных выбранных битов ключа, т.е. B, показано в столбце 6.
Случай
q
p
n
<img file="00000100.jpg" he="6" wi="4" img-content="undefined" img-format="jpg" />
Длина ключа = <img file="00000101.jpg" he="6" wi="13" img-content="undefined" img-format="jpg" />
<img file="00000102.jpg" he="6" wi="4" img-content="undefined" img-format="jpg" />
Формирование ключей инициатора (SK+PK)
Формирование ключей ответчика (SK+PK)
Полный обмен ключами
I
2048
256
380
49
<img file="00000103.jpg" he="6" wi="21" img-content="undefined" img-format="jpg" /> битов
2
32329015 тактовых CPU–цикла
29923102 тактовых CPU–цикла
62672479 тактовых CPU–цикла
II
4096
1024
510
46
<img file="00000104.jpg" he="6" wi="21" img-content="undefined" img-format="jpg" /> битов
2
37517641 тактовых CPU–цикла
32664199 тактовых CPU–цикла
70736287 тактовых CPU–цикла
III
4096
1024
610
43
<img file="00000104.jpg" he="6" wi="21" img-content="undefined" img-format="jpg" /> битов
2
42209327 тактовых CPU–цикла
34880341 тактовых CPU–цикла
77752022 тактовых CPU–цикла
Случай I может выбираться для средней безопасности, например, для классической безопасности. Случаи II и II могут выбираться для постквантовой безопасности. Случай III является более защищенным, чем случай II.
Сложность связи: Вследствие использования округления до более малой неотрицательной величины, есть возможность уменьшать размер каждой записи общедоступного ключа и исходного ключа, достигая значительно более низких требований по полосе пропускания. Означенное определяется количественно в двух следующих таблицах, в которых демонстрируются требования по полосе пропускания предложенной схемы (с/без использования округления, соответственно). Варианты осуществления сравниваются с LWE–протоколом, описанным в работе "Frodo: Take off the ring! Practical, Quantum–Secure Key Exchange from LWE", авторов J. Bos, C. Costello, L. Ducas, I. Mironov, M. Naehrig, V. Nikolaenko, A. Raghunathan, D. Stebila.
Полоса пропускания вычисляется как полный размер сообщений обмена ключами, которыми обмениваются (т.е. общедоступных ключей и сверочных данных), и не включает в себя обмен общедоступной матрицей A.
h
Табл. 3. Производительность связи предложенной схемы, показывающей улучшения требований по полосе пропускания по сравнению с LWE–схемой обмена ключами предшествующего уровня техники, Frodo. (Число конечных битов ключа B=2, число битов сверочных данных b=2)
Схема
n
<img file="00000105.jpg" he="7" wi="10" img-content="undefined" img-format="jpg" />
<img file="00000106.jpg" he="7" wi="10" img-content="undefined" img-format="jpg" />
Длина ключа = <img file="00000107.jpg" he="7" wi="14" img-content="undefined" img-format="jpg" />
Полоса пропускания (предложение с использованием LWR)
Полоса пропускания (Frodo LWE)
Отношение
I
380
11
8
<img file="00000108.jpg" he="7" wi="26" img-content="undefined" img-format="jpg" /> битов
6,1 Кбайт
14,22 Кбайт
0,43
II
510
12
10
<img file="00000109.jpg" he="7" wi="26" img-content="undefined" img-format="jpg" /> битов
10,22 Кбайт
22,57 Кбайт
0,45
III
610
12
10
<img file="00000109.jpg" he="7" wi="26" img-content="undefined" img-format="jpg" /> битов
12,22 Кбайт
25,93 Кбайт
0,47
Выигрыш по полосе пропускания с использованием LWE и разреженных небольших секретов:
h
Табл. 4. Производительность связи предложенной схемы, когда только разреженные небольшие секреты используются, вместо комбинации с округлением. (Число конечных битов ключа B=2, число битов сверочных данных b=2)
Схема
n
<img file="00000105.jpg" he="7" wi="10" img-content="undefined" img-format="jpg" />
Длина ключа = <img file="00000107.jpg" he="7" wi="14" img-content="undefined" img-format="jpg" />
Полоса пропускания (предложение с использованием LWE)
Полоса пропускания (Frodo LWE)
Отношение
I
540
12
<img file="00000108.jpg" he="7" wi="26" img-content="undefined" img-format="jpg" /> битов
12,98 Кбайт
14,22 Кбайт
0,91
II
715
15
<img file="00000109.jpg" he="7" wi="26" img-content="undefined" img-format="jpg" /> битов
21,47 Кбайт
22,57 Кбайт
0,95
III
855
15
<img file="00000109.jpg" he="7" wi="26" img-content="undefined" img-format="jpg" /> битов
25,67 Кбайт
25,93 Кбайт
0,99
Выигрыши по полосе пропускания для первой таблицы, т.е. для разреженного LWR (округление используется в сочетании с разреженными небольшими секретами) являются более желательными, чем для второй таблицы, т.е. для разреженного LWE (используются только разреженные небольшие секреты) вследствие следующих причин: Минимальное значение размерности n LWR– и LWE-задачи является более высоким в случае разреженного LWE по сравнению с минимальным значением n в случае разреженного LWR. Это обусловлено тем, что это минимальное значение определяется посредством дисперсии гауссова распределения ошибок в разреженном LWE, что налагает более строгий минимальный предел на n, чем в случае разреженного LWR (в котором минимальный предел n управляется посредством отношения ). Полоса пропускания в разреженном LWR управляется посредством , что меньше  (в случае разреженного LWE).
В различных вариантах осуществления, интерфейс связи может выбираться из различных альтернатив. Например, интерфейс связи может представлять собой сетевой интерфейс с локальной или глобальной вычислительной сетью, например, с Интернетом, интерфейс хранения данных с внутренним или внешним устройством хранения данных, клавиатурой и т.д.
Сетевые узлы могут содержать электронное устройство хранения данных, например, чтобы сохранять промежуточные данные, такие как матрица A, матрицы общедоступных и конфиденциальных ключей и совместно используемый ключ и т.д. Устройство хранения данных может реализовываться как электронное запоминающее устройство, скажем, флэш–память, или магнитное запоминающее устройство, скажем, жесткий диск и т.п. Устройство хранения данных может содержать несколько дискретных запоминающих устройств, вместе составляющих устройство хранения данных. Устройство хранения данных также может представлять собой временное запоминающее устройство, скажем, RAM. В случае устройства временного хранения данных, устройство хранения данных может использовать некоторое средство для того, чтобы получать общие параметры перед использованием, например, посредством получения их по необязательному сетевому соединению (не показано отдельно).
Типично, устройства 110 и 210 содержат микропроцессор (не показан отдельно на фиг. 1), который выполняет надлежащее программное обеспечение, сохраненное в устройствах 110 и 210; например, это программное обеспечение, возможно, загружено и/или сохранено в соответствующем запоминающем устройстве, например, в кратковременном запоминающем устройстве, к примеру, в RAM, или в долговременном запоминающем устройстве, к примеру, во флэш–памяти (не показана отдельно). Альтернативно, устройства 110 и 210 могут, полностью или частично, реализовываться в программируемой логике, например, в качестве программируемой пользователем вентильной матрицы (FPGA). Устройства 110 и 210 могут реализовываться, полностью или частично, в качестве так называемой специализированной интегральной схемы (ASIC), т.е. интегральной схемы (IC), специально разработанной для конкретного использования. Например, схемы могут реализовываться в CMOS, например, с использованием языка описания аппаратных средств, такого как Verilog, VHDL и т.д.
В варианте осуществления, сетевой узел содержит интерфейсную схему связи, схему обработки совместно используемых матриц, схему обработки матриц конфиденциальных ключей, схему обработки матриц общедоступных ключей и схему обработки совместно используемых ключей. Схемы реализуют соответствующие модули, описанные в данном документе. Схемы могут представлять собой процессорную схему и схему хранения данных, причем процессорная схема выполняет инструкции, представленные электронно в схемах хранения.
Процессорная схема может реализовываться распределенным способом, например, в качестве нескольких подпроцессорных схем. Устройство хранения данных может быть распределено по нескольким распределенным субустройствам хранения данных. Часть или все запоминающее устройство может представлять собой электронное запоминающее устройство, магнитное запоминающее устройство и т.д. Например, устройство хранения данных может иметь кратковременную и долговременную часть. Часть устройства хранения данных может быть неперезаписываемой. Схемы также могут представлять собой FPGA, ASIC и т.п.
Фиг. 3 схематично показывает пример варианта осуществления способа обмена электронными ключами. Способ может осуществляться посредством первого электронного сетевого узла, такого как узел–инициатор 110 или узел–ответчик 210.
Способ 400 содержит:
– организацию (410) цифровой связи между первым сетевым узлом и вторым сетевым узлом,
– получение (420) совместно используемой матрицы (A), причем совместно используемая матрица совместно используется со вторым сетевым узлом через цифровую связь, причем записи в совместно используемой матрице A выбираются по модулю первая неотрицательная величина q,
– формирование (430) матрицы () конфиденциальных ключей, причем записи в матрице конфиденциальных ключей ограничиваются по абсолютному значению пределом (s),
– формирование (440) матрицы () общедоступных ключей посредством следующего:
– вычисление (442) матричного произведения между совместно используемой матрицей (A) и матрицей () конфиденциальных ключей по модулю первая неотрицательная величина (q), с получением матричного произведения,
– понижающее масштабирование (444) записей в матричном произведении до второй неотрицательной величины (p), причем масштабированная запись равна немасштабированной записи, умноженной на вторую неотрицательную величину (p), деленной на первую неотрицательную величину (q) и округленной до ближайшего целого числа, причем вторая неотрицательная величина (p) меньше первой неотрицательной величины (q), причем предел (s) составляет самое большее вторая неотрицательная величина (p),
– отправка (452) матрицы общедоступных ключей первого сетевого узла во второй сетевой узел,
– прием (454) матрицы () общедоступных ключей второго сетевого узла,
– вычисление (460) исходного ключа в качестве матричного произведения между принимаемым общедоступным ключом второго узла и матрицей конфиденциальных ключей первого сетевого узла по модулю вторая неотрицательная величина (p),
Если первый сетевой узел работает согласно режиму инициатора, то первый сетевой узел выполняет следующие дополнительные элементы:
– прием (472) сверочных данных (h) второго сетевого узла,
– вычисление (482) совместно используемого ключа посредством применения сверочной функции () к принимаемым сверочным данным и исходному ключу.
Если первый сетевой узел работает согласно режиму ответчика, то первый сетевой узел выполняет следующие дополнительные элементы:
– получение (474) совместно используемого ключа и сверочных данных из исходного ключа,
– отправка (484) сверочных данных в первый сетевой узел.
Специалистам в данной области техники должно быть очевидным, что возможно множество различных вариантов осуществления способа. Например, порядок этапов может варьироваться, либо некоторые этапы могут выполняться параллельно. Кроме того, между этапами могут вставляться другие этапы способа. Вставленные этапы могут представлять уточнения способа, к примеру, описанного в данном документе, или могут быть не связаны со способом. Например, данный этап может не заканчиваться полностью до того, как начинается следующий этап.
Способ согласно изобретению может осуществляться с использованием программного обеспечения, которое содержит инструкции для предписания процессорной системе осуществлять способ 400. Программное обеспечение может включать в себя только этапы, выполняемые посредством конкретного подобъекта системы. Программное обеспечение может сохраняться на подходящем носителе хранения данных, к примеру, на жестком диске, на дискете, в запоминающем устройстве, на оптическом диске и т.д. Программное обеспечение может отправляться в качестве сигнала проводным или беспроводным способом либо с использованием сети передачи данных, например, Интернета. Программное обеспечение может становиться доступным для скачивания и/или для удаленного использования на сервере. Способ согласно изобретению может осуществляться с использованием потока битов, выполненного с возможностью конфигурировать программируемую логику, например, программируемую пользователем вентильную матрицу (FPGA), с тем чтобы осуществлять способ.
Следует принимать во внимание, что изобретение также применимо к компьютерным программам, в частности, к компьютерным программам на носителе, приспособленном для осуществления изобретения на практике. Программа может иметь форму исходного кода, объектного кода, кода, промежуточного между исходным и объектным кодом, к примеру, частично компилированную форму, либо любую другую форму, подходящую для использования при реализации способа согласно изобретению. Вариант осуществления, связанный с компьютерным программным продуктом, содержит машиноисполняемые инструкции, соответствующие каждому из этапов обработки, по меньшей мере, одного из изложенных способов. Эти инструкции могут подразделяться на подпрограммы и/или сохраняться в одном или более файлов, которые могут быть связаны статически или динамически. Другой вариант осуществления, связанный с компьютерным программным продуктом, содержит машиноисполняемые инструкции, соответствующие каждому из средств, по меньшей мере, одной из изложенных систем и/или продуктов.
Фиг. 4a показывает машиночитаемый носитель 1000, имеющий записываемую часть 1010, содержащую компьютерную программу 1020, причем компьютерная программа 1020 содержит инструкции для предписания процессорной системе осуществлять способ согласования ключей согласно варианту осуществления. Компьютерная программа 1020 может быть осуществлена на машиночитаемом носителе 1000 в качестве физических меток либо посредством намагничивания машиночитаемого носителя 1000. Тем не менее, также возможен любой другой подходящий вариант осуществления. Кроме того, следует принимать во внимание, что хотя машиночитаемый носитель 1000 показан здесь в качестве оптического диска, машиночитаемый носитель 1000 может представлять собой любой подходящий машиночитаемый носитель, такой как жесткий диск, полупроводниковое запоминающее устройство, флэш–память и т.д., и может быть незаписываемым или записываемым. Компьютерная программа 1020 содержит инструкции для предписания процессорной системе осуществлять упомянутый способ 400 согласования ключей.
Фиг. 4b показывает схематичное представление процессорной системы 1140 согласно варианту осуществления. Процессорная система содержит одну или более интегральных схем 1110. Архитектура одной или более интегральных схем 1110 схематично показана на фиг. 4b. Схема 1110 содержит модуль 1120 обработки, например, CPU, для выполнения компьютерных программных компонентов, чтобы осуществлять способ согласно варианту осуществления и/или реализовывать его модули или блоки. Схема 1110 содержит запоминающее устройство 1122 для сохранения программного кода, данных и т.д. Часть запоминающего устройства 1122 может быть неперезаписываемой. Схема 1110 может содержать элемент 1126 связи, например, антенну, разъемы либо и то, и другое и т.п. Схема 1110 может содержать специализированную интегральную схему 1124 для выполнения части или всей обработки, заданной в способе. Процессор 1120, запоминающее устройство 1122, специализированная IC 1124 и элемент 1126 связи могут соединяться между собой через межкомпонентное соединение 1130, скажем, шину. Процессорная система 1110 может быть выполнена с возможностью осуществления контактной и/или бесконтактной связи, с использованием антенны и/или разъемов, соответственно.
Например, в варианте осуществления, сетевой узел может содержать процессорную схему и запоминающую схему, причем процессор выполнен с возможностью выполнять программное обеспечение, сохраненное в запоминающей схеме. Например, процессорная схема может представлять собой процессор Intel Core i7, ARM Cortex–R8 и т.д. В варианте осуществления, процессорная схема может представлять собой ARM Cortex M0. Запоминающая схема может представлять собой ROM–схему или долговременное запоминающее устройство, например, флэш–память. Запоминающая схема может представлять собой кратковременное запоминающее устройство, например, запоминающее SRAM–устройство. Во втором случае, устройство верификации может содержать долговременный программный интерфейс, например, жесткий диск, сетевой интерфейс и т.д., выполненный с возможностью предоставления программного обеспечения.
Следует отметить, что вышеуказанные варианты осуществления иллюстрируют, а не ограничивают изобретение, и что специалисты в данной области техники должны иметь возможность разрабатывать множество альтернативных вариантов осуществления.
В формуле изобретения, все ссылки с номерами, помещенные в круглые скобки, не должны рассматриваться как ограничивающие формулу изобретения. Использование глагола "содержит" и его спряжений не исключает наличия элементов или этапов, отличных от элементов или этапов, изложенных в формуле изобретения. Упоминание элемента в единственном числе не исключает наличия множества таких элементов. Изобретение может реализовываться посредством аппаратных средств, содержащих несколько отдельных элементов, и посредством надлежащим образом запрограммированного компьютера. В пункте формулы изобретения на устройство, перечисляющем несколько средств, некоторые из этих средств могут быть осуществлены посредством идентичного элемента аппаратных средств. Простой факт того, что определенные меры упомянуты в различных зависимых пунктах формулы изобретения, не означает того, что комбинация этих мер не может использоваться с выгодой.
В формуле изобретения, ссылки в круглых скобках означают ссылки с номерами на чертежах примерных вариантов осуществления либо формулы вариантов осуществления, за счет этого повышая понятность формулы изобретения. Эти ссылки не должны истолковываться как ограничивающиеся формулу изобретения.