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.