О двухкаскадных конечно-автоматных криптографических генераторах и методах их криптоанализа | Прикладная дискретная математика. 2017. № 35. DOI: 10.17223/20710410/35/4

Рассматривается криптографический генератор G = A · A2, представляющий собой последовательное соединение двух абстрактных конечных автоматов A1 и A2 над полем F2 с множествами состояний F^, n > 1, и F™, m > 1, соответственно, с выходным алфавитом F2 и с функциями выходов f1(x) и f2(u,y) из некоторых классов булевых функций от n и m + 1 переменных соответственно. Автомат A1 автономный с произвольной функцией переходов g1(x), автомат A2 неавтономный с входным алфавитом F₂ и функцией переходов g₂(u, y), в которой g₂(0, y) = д(y) и g2(1,y) = д(y) для некоторых различных нетрицательных целых 5 и т и отображения g : Fm ^ F™. В каждый момент времени t = 1,2,... автомат A1 из состояния x(t) переходит в состояние x(t + 1) = g1(x(t)) и вырабатывает выходной символ u(t) = /1(x(t)), автомат A2 из состояния y(t) переходит в состояние y(t + 1) = g₂(u(t),y(t)) и вырабатывает выходной символ z(t) = f₂(u(t),y(t)), который и является выходным символом генератора G. Ключом генератора может быть любой непустой набор элементов из ряда x(1),y(1), f₁,g₁, f₂,g₂,g,5,T. Задача криптоанализа генератора G состоит в определении его ключа по заданному конечному отрезку y = z(1)z(2) ...z(l) его выходной последовательности. Показано, что в генераторе G с линейным автоматом A2 ключ y(1) вскрывается с полиномиальной сложностью решением системы линейных уравнений, а ключ (x(1),y(1)) -линеаризационной атакой сложности не более 2. Предложен метод, позволяющий в произвольном генераторе G с известными функциями g₂ и f₂ вычислить по y отрезок управляющей последовательности в = u(1)u(2) ...u(l) на выходе A1 и тем самым открыть две возможности для криптоанализа такого G: 1) найти его ключ (x(1),y(1)) атакой «встреча посредине» со сложностью 2 и 2) свести задачу криптоанализа G к криптоанализу автомата A1 - найти ключ последнего по в. Сложность метода полиномиальная, если y(1) не входит в ключ, и не превосходит 2 в противном случае. Если ключом в A1 служит функция f, то его вскрытие, в свою очередь, сводится к доопределению частичной булевой функции со значениями u(t) на состояниях x(t) для t = 1, 2,...,l до функции в классе функции f₁ . Аналогично, к доопределению частичной булевой функции со значениями z(t) на парах (u(t),y(t)) для t = 1, 2,...,l до функции в классе функции f сводится вскрытие ключа произвольного генератора G с ключом f2. Сообщается об известных авторам алгоритмах доопределения частичной булевой функции от сколь угодно большого набора переменных до функции из класса полностью определённых булевых функций, существенно зависящих от малого или ограниченного количества переменных из этого набора.