ANALYTICAL EXPRESSION OF THE PROBABILITY OF ADJACENT SIGNS’COINCIDENCE OF THE OUTPUT SEQUENCE OF A COMBINATION KEYSTREAM GENERATOR BASED ON SHIFT REGISTERS MOVING WITH IDLE

A theorem that establishes an explicit expression of the probability of two adjacent signs’ coincidence of the output sequence of an arbitrary combination keystream generator based on linear shift registers, each of which is either idle or shifts by one step in each clock cycle is proved. The obtained result allows us to calculate this probability directly from the known laws of the linear shift registers’ motion and the Walsh–Hadamard transform of the combination function. Keywords: stream cipher, combinational gamma generator with non-uniform motion, correlation attack, Walsh–Hadamard transform, A5/1, Alpha1.