Streams Ciphers - Linear feedback shift register logic behind design

Question

I’m just seeking a better understanding as to the logic behind design of the A5/1 cipher’s keystream generator. Why are the registers degree chosen in such a fashion (19,22 and 23 bits long respectively)? I have heard because they are co-prime but have little understanding how this may influence the system.

The reason I ask this is because I was asked a question today relating to a hypothetical stream cipher key-stream generator with 2 LFSRs, 17 bits and 25 bits in length respectively, with a 40 bit key input. I was needing to explain why these register sizes were chosen over something like a 7 bit and 35 bit register pair or two 21 bit registers but couldn’t find an appropriate line of reasoning.

Answer 1

If you have $k$ sequences $S_i(t)$ with minimal periods $L_i,i=1,\ldots,k,$ then the period of their XOR sum or any other reasonable output combination of the form $$z(t)=f(S_1(t),\ldots,S_k(t))$$ can be made as large as $$\textrm{lcm}(L_1,\ldots,L_k)=\frac{L_1 L_2 \cdots L_k} {\textrm{gcd}(L_1,\ldots,L_k)}.$$

So if each sequence $S_i(t)$ spans a certain state space the sequence $z(t)$ depends nontrivially on the product space of all the sequences. For example if we had periods 2,3 we'd span the state space thus (using indexing of periods from $0$ to $L-1$): $$ \begin{array}{c|cccccc} t~for~S_1 &0 &1 &0 &1 &0 &1\\ t~for~S_1 &0 &1 &2 &0 &1 &2 \\ \hline t~for~z & 0 & 4 & 2 & 3 & 1 & 5\\ \end{array} $$

Note that A5/1 has irregular stuttering/stepping which is used as an additional source of strength. For plainly combining the outputs of LFSRs we have the following (from my notes):