2
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

3
$\begingroup$

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):

enter image description here

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.