To cryptanalysis of 2-cascade finite automata cryptographic generators.pdf Рассматриваемый здесь криптографический генератор (будем обозначать его G) представляет собой последовательное соединение двух абстрактных конечных автоматов над полем F2 -управляющего и управляемого. Первый является некоторым автономным автоматом A1 = (Fn, F2, gi, /i) с множеством состояний Fn, n > 1, выходным алфавитом F2, с функцией переходов g1 : Fn - Fn и функцией выходов /1 : Fn - F2, а второй - некоторым неавтономным автоматом A2 = (F2,Fm,F2,g2,/2) с входным и выходным алфавитами F2, с множеством состояний Fm, m > 1, с функцией выходов /2 : F2 x Fm - F2 и функцией переходов g2 : F2 x Fm - Fm, для которой существуют отображение g : Fm - Fm и различные целые неотрицательные числа 8 и т, такие, что для всех u G F2 и y G Fm если u = 0, то g2(u,y) = gs(y), и если u = 1, то g2(u,y) = gT(y^ т.е. g2(u,y) = -ugS(y) + ugT(y^ где, как обычно, g0(y) = y и gr(y) = g(gr-1(y)). Таким образом, генератор G - это конечный автономный автомат G = Ai• A2 = (FnxFm, F2, h, /), где h : FnxFm - FnxFm и h(x,y) = (gi(x),g2(/i(x),y)), /(x, y) = /2(/1 (x), y), x G Fn, y G Fm. Все функции в определении G, как видим, булевы, причём функции gi и g2,g - векторные размерности n и m соответственно. Генератор G функционирует в дискретном времени t = 1, 2,..., в каждый момент t которого его автомат A1, находясь в состоянии x(t) = x1 (t)x2(t).. .xn(t) G Fn, выдаёт выходной управляющий символ u(t) = /1(x(t)) и переходит в следующее состояние x(t + 1) = g1(x(t)), а автомат A2 в этот момент, находясь в состоянии y(t) = y1(t)y2(t) ...ym(t) G Fm, принимает от A1 символ u(t), выдаёт свой выходной символ v(t) = /2(u(t),y(t)) и переходит в следующее состояние y(t + 1) = g2(u(t),y(t)). Значением z(t) на выходе генератора G в момент t является значение v(t) на выходе автомата A2 в этот момент. Предполагается, что значение любой функции в генераторе G на любом наборе значений её аргументов вычисляется за полиномиальное время от числа последних. Можно показать, что в частном случае, когда функции g1 и g являются функциями переходов некоторых регистров сдвига с линейной обратной связью и длиной n и m соответственно и /2(u, y1, y2,... ,ym) = y1, генератор G функционально эквивалентен генератору (8, т)-шагов [1]. Функционирование генератора G во времени описывается формально следующей системой векторных булевых уравнений с переменными x(t), y(t), u(t), t = 1, 2,...: 'u(t) = f1(x(t)), x(t + 1) = g1 (x(t)), x(1) = x1 (1)x2(1) .. .x„(1); < z(t) = f2(u(t),y(t)), y(t + 1) = -u(t)g5 (y(t)) + u(t)gT (y(t)), y(1)= У1(1)У2(1) ...ym(1); t ^ 1. k. Здесь подсистема E1 из первого, второго и третьего уравнений описывает работу управляющего автомата A1, подсистема E2 из четвёртого, пятого и шестого уравнений - работу управляемого автомата A2. Ключом генератора G теоретически может быть любое непустое подмножество множества {x(1), y(1), f1, g1, f2, g2, g, т}. Требование стойкости криптографического генератора накладывает определённые ограничения на применяемые в нём булевы функции. Кроме того, не любую булеву функцию можно задать практически. В этой связи предполагается, что каждая функция в генераторе принадлежит некоторому классу, и этот класс, в том числе для функции в составе ключа, общеизвестен. При известном ключе и заданных других параметрах генератора уравнения данной системы позволяют однозначно вычислить порождаемую генератором выходную последовательность z(1)z(2)... Задача криптоанализа произвольного генератора G заключается в определении его ключа в известном классе по заданному конечному отрезку 7 = z(1)z(2) ... z(/) последовательности, порождаемой им на этом ключе. В такой постановке задача возникает в криптоанализе поточного шифра, использующего данный генератор, атакой на шифр с известным или выбираемым открытым текстом. Её решение может быть получено как решение конечной подсистемы S^ указанной системы уравнений с t = 1, 2,...,/. В случае неединственности решения системы S^ обычно рекомендуется задаться более длинным отрезком 7. Решение системы S^ может быть найдено атакой грубой силы, или исчерпывающим поиском, т. е. перебором возможных ключей с вычислением при каждом выбранном ключе k начального отрезка 7' длины / порождаемой последовательности и сравнением его с отрезком 7. В случае 7' = 7 ключ k принимается за ответ задачи. Сложность этой атаки определяется размером ключевого пространства. Так, если ключом генератора служит его начальное состояние, то сложность атаки равна 2n+m. Если же ключом является какая-либо из функций генератора, то сложность атаки равна мощности класса этой функции. В данной работе показано, что в генераторе G с линейным автоматом A2 ключ y(1) вскрывается с полиномиальной сложностью решением системы линейных уравнений, а ключ (x(1), y(1)) -линеаризационной атакой сложности не более 2n. Предложен метод, позволяющий в произвольном генераторе G с известными g, т и f2 вычислить по 7 отрезок управляющей последовательности a = u(1)u(2) ...u(/ - 1) на выходе A1 и тем самым открыть две возможности для криптоанализа такого G: 1) вычислить его ключ (x(1),y(1)) атакой «встреча посредине» со сложностью 2m; 2) свести задачу криптоанализа G к криптоанализу автомата A1 -найти его ключ по а. Сложность метода полиномиальная, если y(1) не входит в ключ, и не превосходит 2m в противном случае. Ключ x(1) автомата A1 находится решением его системы уравнений E1, а вскрытие ключа f1 в A1, в свою очередь, сводится к доопределению частичной булевой функции со значениями u(t) на состояниях x(t) для t = 1, 2,..., / - 1 до функции в классе функции f1 . Аналогично, к доопределению частичной булевой функции со значениями z(t) на парах (u(t), y(t)) для t = 1, 2,... , / до функции в классе функции f2 сводится вскрытие ключа f2 произвольного генератора G. Осуществление подобного доопределения демонстрируется на классе, состоящем из всех булевых функций от большого числа переменных с малым количеством существенных аргументов из них.

Скачать электронную версию публикации