This article is cited in
2 papers
Mathematical Methods of Cryptography
Cryptanalysis of $2$-cascade finite automata generator with functional key
I. V. Borovkova,
I. A. Pankratova,
E. V. Semenova National Research Tomsk State University, Tomsk, Russia
Abstract:
A cryptographic generator under consideration is a serial connection
$G= A_1\cdot A_2$ of two finite state machines (finite automata)
$A_1 = (\mathbb{F}_2^n,\mathbb{F}_2, g_1, f_1)$ (it is autonomous) and $A_2 = (\mathbb{F}_2,\mathbb{F}_2^n,\mathbb{F}_2, g_2, f_2)$.
The key of the generator is the function
$f_1$ and possibly the initial states
$x(1),y(1)$ of the automata
$A_1,A_2$. The cryptanalysis problem for
$G$ is the following: given an output sequence
$\gamma = z(1)z(2) \ldots z(l)$, find the generator's key. Two algorithms for analysis of
$A_2$ are presented, they allow to find a preimage
$u(1)\ldots u(l)$ of
$\gamma$ in general case and in the case when
$A_2$ is the Moore automaton with the transition function
$g_2(u, y) = \neg ug^\delta(y) + ug^\tau(y)$ for some
$g:\mathbb{F}_2^m\rightarrow\mathbb{F}_2^m$ and
$\delta,\tau\in\mathbb{N}$. This preimage is an input to
$A_2$ and an output from
$A_1$. The values
$u(t)$ equal the values
$f_1(x(t))$ where
$x(t)$ is the state of
$A_1$ at a time
$t$,
$t=1,2, \ldots, l$.
If the initial state
$x(1)$ and a function class
$C_1$ containing
$f_1$ are known, then
$f_1$ can be determined by its specifying in the class
$C_1$.
Keywords:
finite automaton, cryptographic generator, $(\delta, \tau)$-step generator, cryptanalysis, DSS method.
UDC:
519.7
DOI:
10.17223/20710410/42/3