RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive

Prikl. Diskr. Mat., 2018 Number 42, Pages 48–56 (Mi pdm641)

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



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024