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

Prikl. Diskr. Mat. Suppl., 2017 Issue 10, Pages 99–101 (Mi pdma326)

Mathematical Methods of Cryptography

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

V. M. Fomichevabcd, D. M. Kolesovaa

a Financial University under the Government of the Russian Federation, Moscow
b National Engineering Physics Institute "MEPhI", Moscow
c Federal Research Center "Computer Science and Control" of Russian Academy of Sciences, Moscow
d "Security Code", Moscow

Abstract: 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)\}$.

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

UDC: 519.1

DOI: 10.17223/2226308X/10/40



© Steklov Math. Inst. of RAS, 2024