On the properties of a finite-state generator

A. O. Bakharev ; R. O. Zapanov ; S. E. Zinchenko ; I. A. Pankratova ; E. S. Prudnikov

Prikladnaâ diskretnaâ matematika, no. 4 (2024), pp. 78-85.

Résumé

The periodic properties of a two-stage finite-state generator $G=A_1\cdot A_2$ are studied, where $A_1=(\mathbb{F}_2^n,\mathbb{F}_2, g_1, f_1)$ (it is autonomous), $A_2 = (\mathbb{F}_2,\mathbb{F}_2^m,\mathbb{F}_2,g_2,f_2)$, $n,m\geq 1$. Some necessary conditions for such a generator with the maximum period of $2^{n+m}$ have been formulated, namely: 1) the output sequence of $A_1$ is purely periodic and the period length is $2^n$; 2) the substitution $G_u$ transforming any initial state $y(1)$ of the automaton $A_2$ into the state $y(2^n+1)$ is a full-cycle substitution; 3) the function $f_1$ has an odd weight; 4) the substitutions $g(0,\cdot)$ and $g(1,\cdot)$ have different parities. Some sufficient conditions have been also formulated, for example, in addition to conditions 1–4, the function $g_2(u,y)$ must be injective in $u$ and the weight of the function $f_2$ must be odd. Two methods for constructing a generator having maximum period have been proposed. It has been proved that, for any binary sequence whose period is a power of two, there exists a generator that produces it.

Détail

Keywords: finite state machine, cryptographic generator, cryptoautomaton, sequence period.

Bibliographie

[1] Agibalov G. P., “Cryptautomata with functional keys”, Prikladnaya Diskretnaya Matematika, 2017, no. 36, 59–72 (In Russian) | Zbl

[2] Watanabe D., Furuya S., Yoshida H., et al., “A new keystream generator MUGI”, LNCS, 2365, 2002, 179–194 | Zbl

[3] Joux A. and Muller F., “Loosening the KNOT”, LNCS, 2887, 2003, 87–99 | Zbl

[4] Zakrevskiy A. D., “The method for messages automatic encryption”, Prikladnaya Diskretnaya Matematika, 2009, no. 2(4), 127–137 (In Russian) | MR | Zbl

[5] Tao R., Finite Automata and Application to Cryptography, TSINGHUA University Press, 2009, 406 pp. | MR

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

[7] Borovkova I. V., Pankratova I. A., and Semenova E. V., “Cryptanalysis of 2-cascade finite automata generator with functional key”, Prikladnaya Diskretnaya Matematika, 2018, no. 42, 48–56 (In Russian) | MR | Zbl

[8] Obukhov P. K. and Pankratova I. A., “Periodic properties of a finite automaton generator”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2023, no. 16, 141–143 (In Russian)

[9] Kostrikin A. I., Introduction to Algebra, Textbook for Universities, v. 1, Fundamentals of Algebra, Fizmatlit Publ., M., 2000, 272 pp. (In Russian)

[10] Fomichev V. M., Methods of Discrete Mathematics in Cryptology, Dialog-MIFI Publ., M., 2010, 424 pp. (In Russian)

[11] Idrisova V. A., Tokareva N. N., Gorodilova A. A., et al., “Mathematical problems and solutions of the Ninth International Olympiad in Cryptography NSUCRYPTO”, Prikladnaya Diskretnaya Matematika, 2023, no. 62, 29–54 | MR

[12] https://nsucrypto.nsu.ru/

[13] Prudnikov E. S., “Finite-state generators with maximal period”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2024, no. 17, 152–154 (In Russian)