О двухкаскадных конечно-автоматных криптографических генераторах и методах их криптоанализа

Рассматривается криптографический генератор $G=A_1\cdot A_2$, представляющий собой последовательное соединение двух абстрактных конечных автоматов $A_1$ и $A_2$ над полем $\mathbb F_2$ с множествами состояний $\mathbb F_2^n$, $n>1$, и $\mathbb F_2^m$, $m>1$, соответственно, с выходным алфавитом $\mathbb F_2$ и с функциями выходов $f_1(x)$ и $f_2(u,y)$ из некоторых классов булевых функций от $n$ и $m+1$ переменных соответственно. Автомат $A_1$ автономный с произвольной функцией переходов $g_1(x)$, автомат $A_2$ неавтономный с входным алфавитом $\mathbb F_2$ и функцией переходов $g_2(u,y)$, в которой $g_2(0,y)=g^\delta(y)$ и $g_2(1,y)=g^\tau(y)$ для некоторых различных нетрицательных целых $\delta$ и $\tau$ и отображения $g\colon\mathbb F_2^m\to\mathbb F_2^m$. В каждый момент времени $t=1,2,\dots$ автомат $A_1$ из состояния $x(t)$ переходит в состояние $x(t+1)=g_1(x(t))$ и вырабатывает выходной символ $u(t)=f_1(x(t))$, автомат $A_2$ из состояния $y(t)$ переходит в состояние $y(t+1)=g_2(u(t),y(t))$ и вырабатывает выходной символ $z(t)=f_2(u(t), y(t))$, который и является выходным символом генератора $G$. Ключом генератора может быть любой непустой набор элементов из ряда $x(1),y(1),f_1,g_1,f_2,g_2,g,\delta,\tau$. Задача криптоанализа генератора $G$ состоит в определении его ключа по заданному конечному отрезку $\gamma=z(1)z(2)\dots z(l)$ его выходной последовательности. Показано, что в генераторе $G$ с линейным автоматом $A_2$ ключ $y(1)$ вскрывается с полиномиальной сложностью решением системы линейных уравнений, а ключ $(x(1),y(1))$ – линеаризационной атакой сложности не более $2^n$. Предложен метод, позволяющий в произвольном генераторе $G$ с известными функциями $g_2$ и $f_2$ вычислить по $\gamma$ отрезок управляющей последовательности $\beta=u(1)u(2)\dots u(l)$ на выходе $A_1$ и тем самым открыть две возможности для криптоанализа такого $G$: 1) найти его ключ $(x(1),y(1))$ атакой “встреча посредине” со сложностью $2^m$ и 2) свести задачу криптоанализа $G$ к криптоанализу автомата $A_1$ – найти ключ последнего по $\beta$. Сложность метода полиномиальная, если $y(1)$ не входит в ключ, и не превосходит $2^m$ в противном случае. Если ключом в $A_1$ служит функция $f_1$, то его вскрытие, в свою очередь, сводится к доопределению частичной булевой функции со значениями $u(t)$ на состояниях $x(t)$ для $t=1,2,\dots,l$ до функции в классе функции $f_1$. Аналогично, к доопределению частичной булевой функции со значениями $z(t)$ на парах $(u(t),y(t))$ для $t=1,2,\dots,l$ до функции в классе функции $f_2$ сводится вскрытие ключа произвольного генератора $G$ с ключом $f_2$. Сообщается об известных авторам алгоритмах доопределения частичной булевой функции от сколь угодно большого набора переменных до функции из класса полностью определённых булевых функций, существенно зависящих от малого или ограниченного количества переменных из этого набора.