V.M. Fomichev, N.V. Fomichev

The main characteristic of cryptographic methods is security of implemented cryptograpic systems. Practical security of cryptosystem is estimated with respect to wide range of well known analysis methods. In some cases these methods are based on solving of equations systems to determine key elements. This paper is devoted to determination of linear subsystems in non-linear equations system. This non-linear system describes gamma of clock-controlled shift registers. Complexity of linear systems solvig can be not high. Highly topical problems of cryptographic analysis of some non-linear systems are considered: - determination of linear subsystems if exist, - proof of linear subsystems absence. Following results are achived: 1. Theorem 1 is proved for ?- steps - generator based on LSR-1 (linear shift register) of length n with uniformly distrubuted boolean filter function f(x) and generating LSR-2 of length m: «Exponent of linearity of substitution, which generates group of generator, is equal to 2п-1; order of generator-s linear subgroup is , where =2n-1(+)+f(0,?,0)(-)-.» 2. Theorem 2 is proved for alternating step generators based on controlling LSR-1 of length n and generating LSR-2 of length m and LSR-3 of length r: «Exponent of linearity of substitution, which generates group of generator, is equal to 2п-1; order of generator-s linear subgroup is ». These results mean for generators described in theorem 1 and theorem 2 following: equations of gamma generating are linear if and only if their numbers are multiple of 2n-1. 3. It-s shown for (,)-selfdecimation generators based on LSR of length n, that any equation of gamma generating is non-linear if n>3 and =2, where (,2n-1)=1. Consequently, linearization method using searching of linear subsystems is ineffective in relation to described generators of (,)-selfdecimation, ?- steps - and generators with alternating step, if length of period of controlling gamma exceeds length of known gamma.