Способ распределения симметричных ключей между узлами вычислительной сети с системой квантового распределения ключей Российский патент 2022 года по МПК H04L9/08 

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

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

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

Вычислительная сеть с системой квантового распределения ключей (далее - сеть КРК), представляет из себя совокупность узлов, соединенных между собой как квантовыми, так и классическими каналами. Под квантовыми каналами обычно подразумевают среду передачи одиночных фотонов. Такая среда не допускает повторителей и усилителей, в ней можно использовать только специальные маршрутизаторы, например, оптические маршрутизаторы (Бутусов М.М., Галкин С.Л., Оробинский С.П. Волоконная оптика и приборостроение. Л.: Машиностроение, 1987, 258 стр.). Под классическим каналом обычно подразумевают обычный цифровой телекоммуникационный канал. Между двумя узлами сети, которые соединены квантовым каналом, обязательно должен быть классический канал. При этом наличие классического канала не означает наличие квантового канала.

Между узлами сети, которые соединены как квантовым, так и классическим каналом, может быть сформирована одинаковая последовательность из нулей и единиц, ее также называют квантовым ключом. Известны различные способы формирования такой последовательности изложены (Кронберг Д.А., Ожигов Ю.И., Чернявский А.Ю. Квантовая криптография, М., Макс Пресс, 2011, 112 с.; доступна по адресу http://sqi.cs.msu.ru/store/storage/ss8dw5n_quantum_cryptography.pdf). Все они основаны на том, что передающий узел кодирует нули и единицы состоянием фотонов, а принимающий узел регистрирует эти фотоны, получая некоторую информацию о них. После этого узлы обмениваются служебной информацией, раскрывая часть информации о переданных фотонах. Затем информация подвергается обработке, в результате чего и появляется квантовый ключ. Служебная информация передается по классическому каналу, а фотоны - по квантовому. При этом информация, переданная по служебному каналу, должна быть аутентичной - чаще всего это условие обеспечивается криптографическими методами.

Передача одиночных фотонов имеет ограничение по расстоянию. Предельная дальность зависит от многих факторов, таких, как мощность однофотонного излучателя, характеристики среды распространения и т.д. (ETSI, White Paper No. 8, Quantum Safe Cryptography and Security An introduction, benefits, enablers and challenges, June 2015, ISBN No. 979-10-92620-03-0). Таким образом, квантовый канал имеет ограничение на максимальную длину. Это означат, что в достаточно протяженных сетях не все узлы могут быть связаны квантовым каналом. На классические каналы такие ограничения не распространяются, так как в этих каналах разрешено использование повторителей и усилителей.

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

Известен способ распределения ключа между узлами сети КРК (патент РФ № 2697696, приоритет от 18.01.2019 г.). Способ применим для совокупность последовательно соединенных узлов сети КРК. Пусть все узлы будут пронумерованы от 1 до N, N ≥ 3. Тогда квантовым и классическим каналом связаны 1-й и 2-й узлы, 2-й и 3-й и т.д., наконец (N-1)-й связан с N-м. Других связей в сети нет. Будем называть такую топологию сети цепью.

Обозначим значение функции зашифрования битовой строки ключом K_i как E_i (K_i, m_i), где i=1, …, N - 1. Конкретный вид функций E_i не фиксируется. Процесс выработки общего ключа между 1-ми N-м узлами сети происходит следующим образом.

Все узлы сети вырабатывают квантовые ключи в соответствии со своими связями. То есть ключ K₁ вырабатывается между 1-ми 2-м узлами, ключ K₂ - между 2-м и 3-м и т.д., наконец, ключ K_N-1 вырабатывается между (N-1)-m и N-m узлами. Длины ключей определяются исходя из алгоритмов, в которых эти ключи будут использоваться.

1-й узел

• формирует случайную битовую строку γ, которая впоследствии станет общим ключом между 1-ми N-м узлами;

• добавляет к γ служебные данные, в результате чего формирует битовую строку m_l, зашифровывает m₁ при помощи ключа K₁: с₁=Е₁(K₁,m₁), пересылает с₁ на 2-й узел.

Очередной узел под номером i, i=2, …, N - 1

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

• зашифровывает m_i при помощи ключа K_i : c_i = E_i(K_i, m_i),

• пересылает q на (i+1)-й узел.

Узел с номером N расшифровывает битовую строку c_N-1, используя ключ K_N-1, получает ключ K_N-2, (N - 2)-ю служебную информацию и битовую строку c_N-2. Далее, последовательно расшифровывает битовую строку c_j, используя ключ K_j и j-ю служебную информацию, j=N - 2, …, 1. В результате, на N-м узле появляется битовая строка γ, которая используется в качестве общего ключа между 1-ми N-м узлами.

Известный способ обладает рядом недостатков:

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

• длина передаваемых сообщений последовательно возрастает в процессе передачи от узла к узлу, что приводит к увеличению нагрузки на ключи защиты K_i, i=1, …, N - 1;

• процесс выработки общего ключа между 1-ми N-м узлами организован так, что в N-й узле сети известны все ключи K₁, …, K_N, значит, для того чтобы дополнительно выработать общий ключ между 1-ми (N-1)-m узлами так, чтобы он был неизвестен в узле с номером N, необходимо распределить новые ключи K₁, …, K_N-1, что влечет дополнительные временные и вычислительные затраты;

• в случае успешного проведения атаки на квантовое оборудование, общий ключ между 1-ми N-м узлами может быть скомпрометирован (V. Makarov et al., "Effects of detector efficiency mismatch on security of quantum cryptosystems", Phys. Rev. A, 2006, 74(2), 022313. erratum ibid. 2008, 78, 019905).

Известен также способ распределения ключей между узлами сети КРК (опубликованная заявка США № 2019/0260581, приоритет от 03.05.2019 г.). В этом способе рассматривается квантовая сеть, разделенная на четыре логических уровня. На 1-м логическом уровне сети располагается центральный контроллер, управляющий всей сетью и формирующий инструкции, по которым узлы 3-го уровня распределяют общие ключи; 2-й логический уровень соответствует уровню устройств-потребителей ключей; 3-й логический уровень сети отвечает за распределение ключей между узлами сети своего уровня, согласно инструкциям, получаемым от центрального контроллера; 4-й логический уровень сети отвечает за выработку квантовых ключей на квантовых каналах. Узлам 2-го уровня однозначно соответствуют узлы 3-го уровня, которым, в свою очередь, однозначно соответствуют узлы 4-го уровня. Центральный контроллер связан со всеми узлами 2-го и 3-го уровней; каждый узел 2-го уровня связан с узлом 3-го уровня, который ему соответствует; каждый узел 3-го уровня связан с узлом 4-го уровня, который ему соответствует.

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

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

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

• всем узлам 3-го уровня, которые входят в построенный маршрут, центральный контроллер рассылает необходимые инструкции;

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

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

Известный способ принят за прототип.

Тем не менее известный способ обладает рядом недостатков:

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

• в способе не описаны конкретные алгоритмы передачи ключей;

• в случае успешного проведения атаки на квантовое оборудование, общий ключ между целевыми узлами может быть скомпрометирован (V. Makarov et al., "Effects of detector efficiency mismatch on security of quantum cryptosystems", Phys. Rev. A, 2006, 74(2), 022313. erratum ibid. 2008, 78, 019905);

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

Раскрытие изобретения

Техническим результатом является

1) повышение защищенности передаваемой информации,

2) расширение эксплуатационных возможностей.

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

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

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

при этом узлы системы КРК соединены квантовыми каналами связи;

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

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

• ставят в соответствие каждому классическому каналу неотрицательное вещественное число, которое зависит от характеристик канала;

• ставят в соответствие каждому квантовому каналу неотрицательное вещественное число, которое зависит от характеристик канала;

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

• на основе топологии сети строят графы Q=(V, E_q) и С=(V, Е_с1), выполняя следующие действия:

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

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

- формируют множество ребер E_q графа Q по следующему правилу: каждому квантовому каналу сопоставляют ребро графа Q; весом ребра устанавливают соответствующее квантовому каналу неотрицательное вещественное число;

- формируют множество ребер Е_с1 графа С по следующему правилу: каждому классическому каналу сопоставляют ребро графа С; весом ребра устанавливают соответствующее классическому каналу неотрицательное вещественное число;

• строят граф G, выполняя следующие шаги:

- множеством вершин графа G выбирают множество вершин V;

- множеством ребер графа G выбирают множество ребер графа С;

- для каждого ребра графа G:

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

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

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

• вычисляют в графе G кратчайший путь между вершинами v_x и v_y;

• из кратчайшего пути в графе G получают совместный кратчайший путь в графах Q=(V, E_q) и С=(V, Е_с1) по следующим правилам:

- путь в графе С идентичен кратчайшему пути графа G;

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

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

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

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

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

- выбирают функции, реализующие внутренние и внешние ключевые контейнеры:

внутренний ключевой контейнер реализуют при помощи таких функций Wrap_cl и Unwrap_cl, что

значения функций Wrap_cl и Unwrap_cl вычислимы за полиномиальное время от длины входных значений;

входными значениями Wrap_cl являются: KM - криптографические ключи, data - битовая строка произвольной длины;

выходным значением Wrap_cl является битовая строка exp_data;

входными значениями Unwrap_cl являются: KM - криптографические ключи, exp_data - битовая строка произвольной длины;

выходным значением Unwrap_cl является: в случае несоответствия входной битовой строки exp_data криптографическим ключам KM - сообщение об ошибке, иначе - битовая строка data', для которой верно равенство exp_data=Wrap _cl(KM, data');

для любой битовой строки data выполняется равенство data=Unwrap_cl(KM, Wrap_cl(KM, data));

не зная KM, вычислительно сложно подобрать такое значение exp_data, чтобы хотя бы для какого-нибудь значения data' выполнялось равенство data'=Unwrap_cl(KM, exp_data);

не зная KM, по известной битовой строке exp_data: exp_data=Wrap_cl(KM, data) вычислительно сложно получить значение data;

внешний ключевой контейнер реализуют при помощи функций Wrap_q и Unwrap_q с такими же свойствами, что и функции Wrap_cl и Unwrap_cl;

- нумеруют узлы квантового маршрута в порядке их следования от узла х к узлу у, при этом узел х является первым узлом, а узел у - n-м узлом;

- нумеруют узлы классического маршрута в порядке их следования от узла х к узлу у, при этом узел х является первым узлом, а узел у - m-м узлом;

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

- нумеруют ключи, соответствующие классическим каналам, где

- устанавливают два счетчика i=1 и у=1;

- вырабатывают ключи, соответствующие квантовым каналам, на каналах квантового маршрута;

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

- на узле х выполняют следующие действия

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

вычисляют значение

вычисляют значение

- значение пересылают второму узлу квантового маршрута;

- выполняют следующие действия до тех пор, пока j<n - 1:

если (j+1)-й узел квантового маршрута принадлежит и классическому маршруту, то на узле выполняют следующие действия:

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

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

вычисляют значение

вычисляют значение

увеличивают значение счетчика i на единицу;

если (у+1)-й узел квантового маршрута не принадлежит классическому маршруту, то выполняют следующие действия:

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

вычисляют значение

вычисляют значение

значение пересылают (j+2)-му узлу квантового маршрута;

увеличивают значение счетчика j на единицу;

- получив значение на узле у выполняют следующие действия:

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

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

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

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

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

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

Введем ряд обозначений.

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

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

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

2. Узлы и каналы в последовательности чередуются.

3. Канал может стоять между двумя узлами в последовательности только в том случае, если он соединяет эти два узла.

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

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

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

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

Атрибутом ребра будем называть дополнительную информацию, связанную с этим ребром.

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

Квантовой сети можно сопоставить два взвешенных графа Q=(V_q, E_q) и С=(V_cl, G_cl), где V_q и V_cl - множества вершин, a E_q и Е_с1 - множества ребер, по следующим правилам:

1. Каждому узлу квантовой сети сопоставляется по одной вершине в каждом графе, таким образом формируется множество вершин обоих графов Других вершин в графах нет. Так как вершины обоих графов совпадают, то мы не будем делать различий между ними и обозначим множество вершин обоих графов V={v₁, …, v_n}.

2. Каждому квантовому каналу сопоставляется ребро графа Q таким образом, что если узлы, которые соответствуют вершинам v_i и v_j, соединены квантовым каналом, то в графе Q есть ребро (v_i, v_j) ∈ E_q. Других ребер в графе Q нет.

3. Каждому классическому каналу сопоставляется ребро графа С таким образом, что если узлы, которые соответствуют вершинам v_i и v_j, соединены классическим каналом, то в графе С есть ребро {v_i, v_j) ∈ Е_с1. Других ребер в графе С нет.

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

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

В терминах теории графов маршруту между двумя узлами соответствует путь в графе между двумя вершинами. Путь в графе С соответствует классическому маршруту; путь в графе Q соответствует квантовому маршруту. Совместным путем от вершины v_x к вершине v_y будем называть совокупность квантового и классического пути, каждый из которых начинается в v_x и заканчивается в v_y, а множество вершин, входящих в классический путь, является подмножеством вершин, входящих в квантовый путь. Вес пути определяется как значение метрики маршрута, который соответствует этому пути. Оптимальному маршруту соответствует кратчайший путь в данной метрике. Если последняя вершина одного пути является началом другого пути, то эти два пути можно естественным образом объединить в один путь.

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

На вход алгоритму поиска кратчайшего совместного пути поступают два графа Q=(V, E_q) и С=(V, Е_с1) и две вершины v_x и v_y.

Выполнение алгоритма предполагает следующую последовательность действий.

1. На основе графов Q и С осуществляется построение нового взвешенного графа G, для чего:

a. в качестве множества вершин графа G берется множество вершин V.

b. в качестве множества ребер графа G берется множество ребер графа С. Вес любого ребра (v_i, v_j) в графе G вычисляется как сумма веса соответствующего ребра (v_i, v_j) из графа С и веса кратчайшего пути в графе Q между вершинами v_i и v_j. Кроме того, атрибутом каждого ребра (v_i, v_j) графа G становится кратчайший путь между вершинами v_i и v_j в графе Q; для построения кратчайшего пути в графе Q используется любой из алгоритмов построения кратчайшего пути между парой вершин (Т. Кормен, Ч. Лейзерсон, Р. Ривест.«Алгоритмы. Построение и анализ». МЦНМО. - 2001. ISBN 5-900916-37-5 (с. 479)), например, алгоритм Дейкстры (Т. Кормен, Ч. Лейзерсон, Р. Ривест. «Алгоритмы. Построение и анализ». МЦНМО. - 2001. ISBN 5-900916-37-5 (с. 489)).

2. Используя любой алгоритм построения кратчайшего пути между парой вершин, строится кратчайший путь между вершинами v_x и v_y во взвешенном графе G.

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

a. путь в графе С идентичен кратчайшему пути графа G, но при этом вес ребер графа С не меняется,

b. путь в графе Q строится как объединение квантовых путей, которые соответствуют атрибутам ребер графа G, при этом квантовые пути располагаются в порядке следования этих ребер в кратчайшем пути графа G.

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

Покажем, что в случае связной квантовой сети описанный способ строит оптимальный совместный маршрут между узлами х и у. Для этого выберем любой оптимальный совместный маршрут между узлами х и у. Сопоставим такому маршруту совместный путь на графах С и Q между вершинами v_x и v_y. Рассмотрим произвольное ребро (v_i, v_j) классической части выбранного совместного пути. Вес квантовой части выбранного совместного пути между вершинами v_i и v_j равен весу кратчайшего пути между этими вершинами в графе Q, поскольку в ином случае выбранный совместный маршрут между узлами х и у являлся бы неоптимальным.

Из построения графа G следует, что ребро (v_i, v_j) содержится в G, при этом вес этого ребра в графе G равен суммарному весу этого ребра в графе С и весу кратчайшего пути в графе Q между вершинами v_i и v_j. Таким образом, рассматривая всю совокупность таких ребер (v_i, v_j), можно заключить, что в графе G имеется путь между вершинами v_x и v_y, вес которого равен весу выбранного совместного пути между узлами v_x и v_y (и, следовательно, значению метрики выбранного оптимального совместного маршрута между узлами х и у). Согласно известному методу (Т. Кормен, Ч. Лейзерсон, Р. Ривест.«Алгоритмы. Построение и анализ». МЦНМО. - 2001, ISBN 5-900916-37-5, с. 479), если между двумя вершинами графа существует путь, то алгоритм построения кратчайшего пути между парой вершин гарантированно строит кратчайший путь между этими вершинами.

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

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

Внутренний ключевой контейнер реализуется при помощи функций Wrap_cl и Unwrap_cl. Входными значениями Wrap_cl являются: KM - криптографические ключи, data - битовая строка произвольной длины; выходным значением Wrap_cl является битовая строка exp_data. Входными значениями Unwrap_cl являются: KM - криптографические ключи, exp_data - битовая строка произвольной длины; выходным значением Unwrap_cl является: в случае несоответствия входной битовой строки exp_data криптографическим ключам KM - сообщение об ошибке, иначе -битовая строка data, для которой верно равенство exp_data=Wrap_cl(KM, data).

Эти функции должны обладать следующими свойствами:

• значения функций Wrap_cl и Unwrap_cl вычисляются за полиномиальное время от длины входных значений;

• для любой битовой строки data выполняется равенство data=Unwrap_cl{KM, Wrap_cl{KM, data));

• не зная KM, вычислительно сложно подобрать такое значение exp_data, чтобы хотя бы для какого-нибудь значения data' выполнялось равенство:

data'=Unwrap_cl(KM, exp_data);

• не зная КМ, по известной битовой строке exp_data:

exp_data=Wrap_cl(KM, data),

вычислительно сложно получить значение data.

Внешний ключевой контейнер реализуется при помощи функций Wrap_q и Unwrap_q с такими же свойствами, что и функции Wrap_cl и Unwrap_cl.

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

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

1. Узлы квантового маршрута нумеруются в порядке их следования от узла х к узлу у, при этом узел х является первым узлом, а узел у - n-м узлом.

2. Узлы классического маршрута нумеруются в порядке их следования от узла х к узлу у, при этом узел х является первым узлом, а узел у - m-м узлом.

3. Каналы классического и квантового маршрута нумеруются в порядке их следования от узла х к узлу у, нумерация начинается с единицы.

4. Нумеруются ключи, соответствующие классическим каналам, где

5. Инициализируются два счетчика i=1 и j=1.

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

7. Нумеруются ключи, соответствующие квантовым каналам, где

8. В узле х выполняются следующие действия:

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

b. вычисляется значение

c. вычисляется значение

9. Значение пересылается второму узлу квантового маршрута.

10. До тех пор, пока j<n - 1, выполняют:

а. если (j+1)-й узел квантового маршрута принадлежит и классическому маршруту, то в узле выполняются следующие действия:

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

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

iii. вычисляется значение

iv. вычисляется значение

v. значение счетчика i увеличивается на единицу.

b. Если (j+1)-й узел квантового маршрута не принадлежит классическому маршруту, то выполняются следующие действия:

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

ii. вычисляется значение

iii. вычисляется значение

c. Значение пересылается (j+2)-му узлу квантового маршрута.

d. Значение счетчика j увеличивается на единицу.

11. Получив значение в узле у выполняются следующие действия:

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

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

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

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

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

На фиг. 1 приведено изображение графа, соответствующего квантовым каналам.

На фиг. 2 приведено изображение графа, соответствующего классическим каналам.

На фиг. 3 приведено изображение графа G.

Осуществление изобретения

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

В качестве модулей обработки информации используются программно-аппаратные комплексы ViPNet Coordinator HW 100 (статья по адресу https://infotecs.ru/upload/iblock/60a/ViPNet_Coordinator_HW100_web_april_2018.pdf). Для реализации квантовых каналов связи используется одномодовое оптоволокно типа SMF-28. Для классических каналов используются Ethernet патчкорды. Все узлы сети пронумерованы от 1 до 6.

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

Значения метрики для квантовых каналов вычисляется следующим образом. Для каждого квантового канала измеряется время, затраченное на выработку первого квантового ключа выработанного в этом канале. Время, измеряется в секундах, обозначим его t₀. Начальное значение метрики для этого канала считается по формуле Последующее уточнение метрики происходит после выработки очередного квантового ключа следующим способом. Обозначим текущее значение метрики m_i, а время выработки очередного квантового ключа, измеренное в секундах, t_i+1, тогда обновленное значение метрики m_n вычисляется по формуле

Описание сети приведено в виде двух матриц смежности, значения ячеек в которых соответствует метрикам каналов (Т. Кормен, Ч. Лейзерсон, Р. Ривест. «Алгоритмы. Построение и анализ». МЦНМО. - 2001, ISBN 5-900916-37-5, с. 436). Первая матрица соответствует квантовым каналам сети, вторая матрица соответствует классическим каналам сети. На пересечении i-й строки и j-го столбца матрицы, где расположены значения метрики для каналов, которые соединяют i-й и j-й узлы; в случае отсутствия канала между узлами используется символ «00».

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

Матрица смежности для классических каналов может быть представлена в виде таблицы (табл. 1).

Графическое представление квантовых каналов изображено в виде графа на фиг. 1.

Матрица смежности для квантовых каналов также может быть представлена в виде таблицы (табл. 2).

Графическое представление классических каналов изображено в виде графа на фиг. 2.

Рассмотрим вариант распределения общего симметричного ключа между узлами 1 и 4. Для этого, согласно описанному способу, сети КРК сопоставляется два графа Q=(V, E_q) и С=(V, Е_с1). В результате получаем

множество вершин V={1,2,3,4,5,6};

множество ребер множество ребер

На основе графов Q=(V, E_q) и С=(V, E_cl) строится новый граф G=(V, Е), который состоит из всех ребер графа С, а вес каждого ребра вычисляется как сумма веса соответствующего ребра графа С и веса кратчайшего пути в графе Q между вершинами, которые это ребро соединяет. Кроме того, атрибутом ребра является кратчайший квантовый путь между вершинами, которое это ребро соединяет. Кратчайший квантовый путь строится по алгоритму Дейкстры (Т. Кормен, Ч. Лейзерсон, Р. Ривест. «Алгоритмы. Построение и анализ». МЦНМО. - 2001. ISBN 5-900916-37-5 (с. 489)). В итоге множество ребер графа G состоит из следующих элементов

Изображение графа G приведено на фиг. 3.

В сформированном графе G строится кратчайший путь между вершинами 1 и 4 по алгоритму Дейкстры. Результатом выполнения алгоритма является путь

Этот путь имеет вес равный 19; проходит через вершины 1,6,5,4; соответствует квантовому маршруту

1, (1,6),6, (5,6), 5, (4,5), 4

и классическому маршруту

1, (1,5),5, (4,5), 4.

Полученный совместный маршрут является оптимальным и имеет значение метрики равное 19.

Распределение общего симметричного ключа K, например длиной 256 бит, между узлами 1 и 4 по совместному маршруту, состоящему из квантового маршрута q_m и классического маршрута cl_m, осуществляется в соответствии с изложенным способом, при этом в качестве алгоритмов Wrap_cl и Wrap_q применяется алгоритм KExp15, описанный в (Р 1323565.1.017-2018. Информационная технология. Криптографическая защита информации. Криптографические алгоритмы, сопутствующие применению алгоритмов блочного шифрования. Москва, Стандартинформ, 2018), а в качестве алгоритмов Unwrap_cl и Unwrap_q применяется алгоритм KImpl5, описанный в (Р 1323565.1.017-2018. Информационная технология. Криптографическая защита информации. Криптографические алгоритмы, сопутствующие применению алгоритмов блочного шифрования. Москва. Стандартинформ 2018). В алгоритмах Wrap_cl и Unwrap_cl используются ключи, соответствующие классическим каналам, в алгоритмах Wrap_q и Unwrap_q используются ключи, соответствующие квантовым каналам. Ключи с пометкой «МАС» используются для имитозащиты; ключи с пометкой «ENC» используются для шифрования; ключи с пометкой «q» соответствуют квантовым ключам; ключи с пометкой «cl» соответствуют классическим ключам. Символ «| |» означает конкатенацию двух битовых строк.

Предполагаем, что в рассматриваемом примере данные не искажаются в процессе передачи.

Тогда выполняются следующие действия.

1. Нумеруются ключи, соответствующие каналам классического маршрута: ключи между узлами 1 и 5 - ключи между узлами 4 и 5 -

2. Вырабатываются квантовые ключи на каналах, входящих в квантовый маршрут: ключи между узлами 1 и 6 - ключи между узлами 5 и 6 - ключи между узлами 4 и 5 -

3. В узле 1:

a. формируется случайная битовая строка K длиной 256 бит,

b. вычисляется значение

c. вычисляется значение

4. Значение пересылается в узел 6.

5. В узле 6:

a. вычисляется значение

b. вычисляется значение

c. вычисляется значение

6. Значение пересылается в узел 5.

7. В узле 5:

a. вычисляется значение

b. вычисляется значение

c. вычисляется значение

d. вычисляется значение

8. Значение пересылается в узел 4.

9. В узле 4:

a. вычисляется значение

b. вычисляется значение

Битовую строку K можно использовать в качестве общего симметричного ключа между узлами 1 и 4.

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

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

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

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

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

при этом узлы системы КРК соединены квантовыми каналами связи;

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

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

способ заключается в том, что:

ставят в соответствие каждому классическому каналу неотрицательное вещественное число, которое зависит от характеристик канала;

ставят в соответствие каждому квантовому каналу неотрицательное вещественное число, которое зависит от характеристик канала;

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

на основе топологии сети строят графы Q=(V, E_q) и С=(V, E_cl), выполняя следующие действия:

формируют множество вершин обоих графов V, для чего каждому узлу сети сопоставляют вершину графа;

выделяют две вершины v_x и v_y, которые соответствуют узлам х и у, между которыми нужно распределить ключ;

формируют множество ребер E_q графа Q по следующему правилу: каждому квантовому каналу сопоставляют ребро графа Q;

весом ребра устанавливают соответствующее квантовому каналу неотрицательное вещественное число;

формируют множество ребер Е_с1 графа С по следующему правилу:

каждому классическому каналу сопоставляют ребро графа С;

весом ребра устанавливают соответствующее классическому каналу неотрицательное вещественное число;

строят граф G, выполняя следующие шаги:

множеством вершин графа G выбирают множество вершин V;

множеством ребер графа G выбирают множество ребер графа С;

для каждого ребра графа G:

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

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

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

вычисляют в графе G кратчайший путь между вершинами v_x и v_y;

из кратчайшего пути в графе G получают совместный кратчайший путь в графах Q=(V, E_q) и С=(V, Е_с1) по следующим правилам:

путь в графе С идентичен кратчайшему пути графа G;

путь в графе Q строят как объединение квантовых путей, которые соответствуют атрибутам ребер графа G, при этом квантовые пути располагают в порядке следования этих ребер в кратчайшем пути графа G;

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

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

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

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

выбирают функции, реализующие внутренние и внешние ключевые контейнеры;

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

входными значениями Wrap_cl являются: КМ - криптографические ключи, data - битовая строка произвольной длины; выходным значением Wrap_cl является битовая строка exp_data;

входными значениями Unwrap_cl являются: КМ - криптографические ключи, exp_data - битовая строка произвольной длины;

выходным значением Unwrap_cl является: в случае несоответствия входной битовой строки exp_data криптографическим ключам КМ - сообщение об ошибке, иначе - битовая строка data', для которой верно равенство exp_data=Wrap_cl(KM, data');

для любой битовой строки data выполняется равенство data=Unwrap _cl(KM,Wrap_cl(KM, data));

не зная KM, вычислительно сложно подобрать такое значение exp_data, чтобы хотя бы для какого-нибудь значения data' выполнялось равенство data'=Unwrap_cl(KM, exp_data);

не зная КМ, по известной битовой строке exp_data: exp_data=Wrap_cl(KM,data) вычислительно сложно получить значение data;

внешний ключевой контейнер реализуют при помощи функций Wrap_q и Unwrap_q с такими же свойствами, что и функции Wrap_cl и Unwrap_cl;

нумеруют узлы квантового маршрута в порядке их следования от узла х к узлу у, при этом узел х является первым узлом, а узел у - n-м узлом;

нумеруют узлы классического маршрута в порядке их следования от узла х к узлу у, при этом узел х является первым узлом, а узел у - m-м узлом;

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

устанавливают два счетчика i=1 и j=1;

вырабатывают ключи, соответствующие квантовым каналам, на каналах квантового маршрута;

нумеруют ключи, соответствующие квантовым каналам, где

на узле х выполняют следующие действия:

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

вычисляют значение

вычисляют значение

значение пересылают второму узлу квантового маршрута;

выполняют следующие действия до тех пор, пока j < n - 1:

если (j+1)-й узел квантового маршрута принадлежит и классическому маршруту, то на узле выполняют следующие действия:

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

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

вычисляют значение

вычисляют значение

увеличивают значение счетчика i на единицу;

если (j+1)-й узел квантового маршрута не принадлежит классическому маршруту, то выполняют следующие действия:

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

вычисляют значение

вычисляют значение

значение пересылают (j+2)-му узлу квантового маршрута;

увеличивают значение счетчика j на единицу;

получив значение на узле у выполняют следующие действия:

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

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

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