Geodesic
Cryptanalysis of $2$-cascade finite automata generator with functional key
Prikladnaâ diskretnaâ matematika, no. 4 (2018), pp. 48-56.

Voir la notice de l'article provenant de la source Math-Net.Ru

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, DSS method.
Mots-clés : cryptanalysis 
@article{PDM_2018_4_a3,
     author = {I. V. Borovkova and I. A. Pankratova and E. V. Semenova},
     title = {Cryptanalysis of $2$-cascade finite automata generator with functional key},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {48--56},
     publisher = {mathdoc},
     number = {4},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2018_4_a3/}
}
TY  - JOUR
AU  - I. V. Borovkova
AU  - I. A. Pankratova
AU  - E. V. Semenova
TI  - Cryptanalysis of $2$-cascade finite automata generator with functional key
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2018
SP  - 48
EP  - 56
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2018_4_a3/
LA  - ru
ID  - PDM_2018_4_a3
ER  - 
%0 Journal Article
%A I. V. Borovkova
%A I. A. Pankratova
%A E. V. Semenova
%T Cryptanalysis of $2$-cascade finite automata generator with functional key
%J Prikladnaâ diskretnaâ matematika
%D 2018
%P 48-56
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2018_4_a3/
%G ru
%F PDM_2018_4_a3
I. V. Borovkova; I. A. Pankratova; E. V. Semenova. Cryptanalysis of $2$-cascade finite automata generator with functional key. Prikladnaâ diskretnaâ matematika, no. 4 (2018), pp. 48-56. http://geodesic.mathdoc.fr/item/PDM_2018_4_a3/

[1] Agibalov G. P., “Cryptautomata with functional keys”, Prikladnaya Diskretnaya Matematika, 2017, no. 36, 59–72

[2] Agibalov G. P., Pankratova I. A., “About 2-cascade finite automata cryptographic generators and their cryptanalysis”, Prikladnaya Diskretnaya Matematika, 2017, no. 35, 38–47 | MR

[3] Agibalov G. P., Pankratova I. A., “To cryptanalysis of 2-cascade finite automata cryptographic generators”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2016, no. 9, 41–43

[4] Toropov N. R., “Programming language LYaPAS”, Prikladnaya Diskretnaya Matematika, 2009, no. 2(4), 9–25 (in Russian)

[5] Agibalov G. P., Lipskiy V. B., Pankratova I. A., “Cryptographic extension and its implementation for Russian programming language”, Prikladnaya Diskretnaya Matematika, 2013, no. 3(21), 93–104 (in Russian)

[6] Agibalov G. P., “Some completions of partial Boolean function”, Trudy SPhTI, 1970, no. 49, 12–19 (in Russian)

[7] Agibalov G. P., Sungurova O. G., “Cryptanalysis of a finite-state keystream generator with an output function as a key”, Vestnik TSU. Prilozhenie, 2006, no. 17, 104–108 (in Russian)

[8] Fomichev V. M., Methods of Discrete Mathematics in Cryptology, DIALOG-MEPhI Publ., M., 2010, 424 pp. (in Russian)