Реализация обобщения алгоритма шифрования Ко-Ли. Часть 1

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

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

Исходный алгоритм Ко-Ли требует наличия в группе двух подмножеств A и B достаточно большой мощности, взаимный коммутант которых равен 1. Е. В. Соколовым было предложено обобщение алгоритма Ко-Ли, описанное в [1], в котором достаточно выполнения некоторого нетривиального тождества w(A1, A2, ..., Ak, Bi, B2, ..., Bi) = 1. На вход этого алгоритма подаются некоммутативная группа G, слово w в алфавите {x1, Х2, ., xk, y1, y2, ., yl}, подмножества A1, A2, ., Ak, B1, B2, ., Bl элементов группы G такие, что для любых элементов a1 е A1, a2 е A2, ..., ak е Ak, b1 e B1, b2 eB2, ..., bi e Bl имеет место равенство w(a1, a2, ..., ak, b1, b2, ..., bl) = 1, а также ключ g, являющийся элементом группы G. Все эти данные являются открытыми. Алгоритм завершается получением элемента группы G, дающего общий секретный ключ.

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

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

Д. С. Лебедева
Продолжение следует