Общая алгебраическая схема распределения криптографических ключей и её криптоанализ | Прикладная дискретная математика. 2017. № 37. DOI: 10.17223/20710410/37/4

Показано, что многие известные схемы алгебраического открытого распределения криптографических ключей, использующие двусторонние умножения, являются частными случаями общей схемы такого вида. В большинстве случаев схемы строятся на платформах, которые являются подмножествами линейных пространств. К ним уже неоднократно применялся метод линейного разложения, разработанный первым автором. Метод позволяет вычислять распределяемые ключи без определения секретных параметров схемы, не решая лежащих в основе схем трудно разрешимых алгоритмических проблем. В работе показано, что данный метод применим к общей схеме, то есть является в определённом смысле универсальным. Общая схема выглядит следующим образом. Пусть G - алгебраическая система, на которой определена ассоциативная операция умножения, например группа, выбранная в качестве платформы. Предположим, что G является подмножеством конечномерного линейного пространства. Сначала задаётся открытое множество элементов g1,...,gk G G. Затем корреспонденты, Алиса и Боб, последовательно публикуют элементы вида a,b(f) для a,b G G, где p_a,b(f) = afb, f G G и f - заданный или предварительно построенный элемент. Распределённый ключ имеет вид K = ра_ьь_г (Ра_г__ьь_г_1 (... (Pai'bi (gi)...)) = am _ 1 ...a1gib1 ...bi _ 1b. Предположим, Алиса выбирает параметры a, b из конечно порождённой подгруппы A группы G, Боб выбирает аналогичные параметры из конечно порождённой подгруппы B группы G, с помощью которых они конструируют преобразования вида р_а,ь, использованные в схеме. Тогда при некоторых естественных предположениях относительно G, A и B показывается, что любой злоумышленник может эффективно вычислить распределяемый ключ K без вычисления использованных в схеме преобразований.