Общая алгебраическая схема распределения криптографических ключей и её криптоанализ

Показано, что многие известные схемы алгебраического открытого распределения криптографических ключей, использующие двусторонние умножения, являются частными случаями общей схемы такого вида. В большинстве случаев схемы строятся на платформах, которые являются подмножествами линейных пространств. К ним уже неоднократно применялся метод линейного разложения, разработанный первым автором. Метод позволяет вычислять распределяемые ключи без определения секретных параметров схемы, не решая лежащих в основе схем трудно разрешимых алгоритмических проблем. В работе показано, что данный метод применим к общей схеме, то есть является в определённом смысле универсальным. Общая схема выглядит следующим образом. Пусть $G$ – алгебраическая система, на которой определена ассоциативная операция умножения, например группа, выбранная в качестве платформы. Предположим, что $G$ является подмножеством конечномерного линейного пространства. Сначала задаётся открытое множество элементов $g_1,\dots,g_k\in G$. Затем корреспонденты, Алиса и Боб, последовательно публикуют элементы вида $\varphi_{a,b}(f)$ для $a,b\in G$, где $\varphi_{a,b}(f)=afb$, $f\in G$ и $f$ – заданный или предварительно построенный элемент. Распределённый ключ имеет вид $K=\varphi_{a_l,b_l}(\varphi_{a_{l-1},b_{l-1}}(\dots (\varphi_{a_1,b_1}(g_i)\dots))=a_la_{l-1}\dots a_1g_ib_1\dots b_{l-1}b_l$. Предположим, Алиса выбирает параметры $a,b$ из конечно порождённой подгруппы $A$ группы $G$, Боб выбирает аналогичные параметры из конечно порождённой подгруппы $B$ группы $G$, с помощью которых они конструируют преобразования вида $\varphi_{a,b}$, использованные в схеме. Тогда при некоторых естественных предположениях относительно $G,A$ и $B$ показывается, что любой злоумышленник может эффективно вычислить распределяемый ключ $K$ без вычисления использованных в схеме преобразований.