On characteristics of a three-stage key generator with an alternating step modified with key generator “stop-forward”

V. M. Fomichev ; D. M. Kolesova

Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 99-101

Résumé

The generator $G$ named in the title of the paper consists of five binary linear feedback shift registers (LFSRs) of maximal periods divided into three cascades. The first cascade is a filter generator $X$ based on a LFSR of a length $n$. Each of the second and third cascades consists of two LFSRs $Y,Z$ and $U,V$ of lengths $m,\mu$ and $r,\rho$ respectively. The registers $Y,Z$ are controlled by the output $x$ of the filter generator $X$, the registers $U,V$ – by the sum $y\oplus z$ of the outputs $y,z$ of the registers $Y,Z$ respectively. The control is made in such a way: if a controlling signal is 1, then one of the controlled registers shifts but another does not change its state; otherwise their behaviour is just opposite. The output of the generator $G$ is the sum $u\oplus v$ of the outputs of registers $U,V$. It is shown, that if the numbers $n,m,\mu,r,\rho$ are relatively prime, then the period $t$ of the sequence produced by $G$ equals the product of the (maximal) periods of its registers. In the cyclic group of order $t$ of the generator $G$, there is a linear subgroup of order $(2^r-1)(2^\rho-1)$. Local exponents $i,(p+1)-\exp\Gamma$ of the mixing digraph $\Gamma$ of $G$ are equal to $n+2$ if $i\in\{1,\dots,n\}$, to $\max(m,\mu)+1$ if $i\in\{n+1,\dots,n+m+\mu\}$, and to $\max(r,\rho)$ if $i\in\{n+m+\mu+1,\dots,p+1\}$ where $p=n+m+\mu+r+\rho$. Consequently, for $G$ the length of “free running” is recommended to be at least $\max\{n+2,\max(m,\mu)+1,\max(r,\rho)\}$.

Détail

Keywords: key generator, linear shift register, length of period, mixing properties, local primitivity of mixing digraph.

Bibliographie

[1] Fomichev V. M., Metody diskretnoi matematiki v kriptologii, Dialog-MIFI, M., 2010, 424 pp.

[2] Fomichev V. M., Melnikov D. A., Kriptograficheskie metody zaschity informatsii. Ch. 1. Matematicheskie aspekty, v 2 ch., Izd-vo Yurait, M., 2016, 209 pp.