V.M. Fomichev

In many cryptographic devices shift register is considered to be the basic functional element of sequence generators. Linear shift registers (LSR) over numeric fields that perform linear transformations of n-dimensional space over finite field have gained extensive use. LSR-s allow for convenient software and hardware implementation; with certain design structure they generate linear recurrent sequence (LRS) of the maximum period length and good statistical properties that are close to the properties of ideal random sequences. At the same time LRS does not exhibit non-linear characteristics: in particular, linear complexity of LRS does not exceed its order, which allows to restore the whole LRS from its short fragment by solving a set of linear equations. One of the ways of strengthening non-linear properties of sequences is related to the usage of non-linear shift registers that perform non-linear transformations of n-dimensional space. Many block ciphers are formed on the basis of non-linear registers whose cells contain recorded information blocks in the form of binary words rather than the field elements. The difficulties in developing this direction consist in the fact that studying non-linear registers is much more complicated than studying the linear ones. This article is focused on studying the properties of transformation semi-groups and groups related to shift registers, including non-linear registers. The author demonstrated acyclicity and transitivity of semi-groups and groups of non-autonomous shift registers over the finite aggregate X, which is considered to be a positive property from the point of view of cryptographic systems synthesis. It was proved that the order of group G of any non-autonomous register that shifts n length over the finite aggregate X is not less than nXn; in other words G grows exponentially along with the growth of the length of n register. In particular, for the registers over field X if group G is generated by the affine substitution with the maximum period length, then in this context G is a semidirect product of cyclical group generated by one of the generating permutations and a group of Xn space shifts.