Linearly recurrent sequences and LFSRs

Wildon's Weblog 2019-09-17

Part B of my Cipher Systems course is on stream ciphers. Modern stream ciphers, such as Trivium, are typically constructed by judiciously introducing non-linearity into a long-period linear stream cipher. The linear case is therefore still important.

By one mathematical definition, a Linear Feedback Shift Register (LFSR) is a function $F : \mathbb{F}_2^\ell \rightarrow \mathbb{F}_2^\ell$ of the form

$(x_0,x_1,\ldots, x_{\ell-2}, x_{\ell-1}) \mapsto \bigl(x_1,x_2,\ldots, x_{\ell-1},f(x_0,x_1,\ldots, x_{\ell-1})\bigr)$

where the feedback function $f$ is linear. If

$f(x_0,x_1,\ldots, x_{\ell-1}) = \sum_{t \in T} x_{\ell -t}$

then we say that $f$ has taps $T$ and that $\ell$ is the width of $F$ . The keystream generated by $F$ for a key $(k_0,\ldots,k_{\ell-1}) \in \mathbb{F}_2^\ell$ is the sequence $k_0,\ldots, k_{\ell-1},k_{\ell}, k_{\ell+1}, \ldots$ , where each $k_s$ for $s \ge \ell$ is defined recursively by

$k_s = f(k_{s-\ell}, \ldots, k_{s-1}) = \sum_{t \in T} k_{s-t}.$

Equivalently, for $s \ge \ell$ ,

$F\bigl( k_{s-\ell}, \ldots, k_{s-2}, k_{s-1} \bigr) = (k_{s-\ell+1}, \ldots, k_{s-1}, k_s) \quad(\star).$

The equation $(\star)$ is close to the hardware implementation of an LFSR: fill $\ell$ registers with the key $k_0k_1\ldots k_{\ell-1}$ and then repeatedly step by putting the sum of the bits $k_{\ell-t}$ for each $t \in T$ into the rightmost register, shifting the other registers to the left. (In hardware, these bits would be ‘tapped’ by physical wires.) This interpretation makes it clear that an LFSR of width $\ell$ is invertible if and only if it taps the bit about to leave the register for good: that is $\ell$ must be a tap.

The period of an invertible LFSR $F$ is the least $P \in \mathbb{N}$ such that $F^P = F$ . One way to find $P$ uses that in the canonical basis of $\mathbb{F}_2^\ell$ , the matrix (acting on column vectors) representing $F$ is the companion matrix of the polynomial $X^\ell + \sum_{t \in T}X^{\ell - t}$ . Thus $F^m = F$ if and only if $X^\ell + \sum_{t \in T}X^{\ell -t}$ divides $x^m + 1$ . This may seem concise written here, but in practice it takes well over a lecture to remind students of matrices, find the matrix representing $F$ and determine its minimal polynomial. All this adds up to a substantial diversion from cryptography; I fear it lost most students in my Cipher Systems course.

Instead, this year I’m going to give up on linear algebra and use the theory of linearly recurrent sequences and infinite power series. My plan is to subsume all or the required ring-theory into the following definition.

Definition. A polynomial $f(X)$ annihilates a power series $K(X)$ if $f(X)K(X)$ is a polynomial.

For example, the LFSR of width $4$ with taps $\{3,4\}$ generates the keystream ${\bf 0001}00110101111{\bf 0001} \ldots$ of period $15$ . The corresponding power series is

$\begin{aligned}(X^3 + X^6 + &X^7 + X^9 + X^{11} + X^{12} + X^{13} + X^{14})(1+X^{15} + \cdots ) \\ &= \displaystyle \frac{X^3 + X^6 + X^7 + X^9 + X^{11} + X^{12} + X^{13} + X^{14}}{1+X^{15}}.\end{aligned}$

Clearly the power series is annihilated by $1+X^{15}$ . But since $k_s = k_{s-3} + k_{s-4}$ for $s \ge 4$ , it is also annihilated by $1+X^3+X^4$ . Correspondingly,

$X^3 + X^6 + X^7 + X^9 + X^{11} + X^{12} + X^{13} + X^{14} + \cdots = \frac{X^3}{1+X^3+X^4}.$

More generally, the keystream generated by an LFSR with taps $T$ is annihilated by the feedback polynomial $f_T(X) = 1 + \sum_{t \in T} X^t$ . Indeed, the coefficient of $X^s$ in the product is $k_s + \sum_{t \in T} k_{s-t} = 0$ , and so $f_T(X)K(X)$ is a polynomial of degree at most $\ell-1$ . Hence the period of $F$ is the minimum $m \in \mathbb{N}$ such that $X^m + 1$ is divisible by $1 + \sum_{t \in T} X^t$ . (This is equivalent to the condition found before by taking reciprocal polynomials.)

One quickly gets further non-trivial results.

Keystream of maximum period

Given $h(X) = h_0 + h_1X + \cdots + h_{\ell-1}X^{\ell-1}$ , we claim that the equation $K(X) = h(X)/f_T(X)$ defines a corresponding keystream. To avoid the need to define inverses in the ring of power series, let’s agree to interpret this equation as equivalent to

$(1+\sum_{t \in T}X^t)(k_0 + k_1X + \cdots + k_{\ell-1}X^{\ell-1}) = h(X)$ .

In turn, this is equivalent to the linear equations

$h_s = k_s + \sum_{t \in T : t \le s} k_{s-t}$

for $s \in \{0,1,\ldots, \ell-1\}$ ; clearly these have a unique solution. In particular, there is a keystream such that $K(x) = 1/f_T(X)$ . (This holds even if the LFSR is not invertible.) It’s obvious that $K(x)$ is annihilated only by the multiples of $f_T(X)$ . In the invertible case we have seen that $f_T(X)$ divides $X^m + 1$ if and only if $m$ is a multiple of the period $P$ of the LFSR. Therefore there is a keystream of period $P$ .

(For comparison, using the linear algebra method, one argues that the matrix representing an LFSR is cyclic and that, as is clear from the left-shift in the definition, the corresponding $\mathbb{F}_2[x]$ -module is generated by $(0,\ldots,0,1)$ . The period of the keystream for $(0,\ldots, 0,1)$ is therefore the period of $F$ . Again this is an argument that becomes far more long-winded when enough detail is included to make it accessible to students.)

Sum of two keystreams

Suppose, in any attempt to increase the linear complexity, we add the keystream ${\bf 001}0111{\bf 001} \ldots$ of the LFSR of width $3$ with taps $\{2,3\}$ to the keystream with period $15$ in the example above. The new keystream has period $105$ and is annihilated by

$(1+X^3+X^4)(1+X^2+X^3) = 1+X^2+X^4+X^5+X^7.$

It is therefore a keystream of the LFSR with taps $\{2,4,5,7\}$ . I plan to get students to find these taps by the slow method of solving the linear equations $(\star)$ , and then, I hope, impress them with how much faster things are with a bit more algebra.

(Incidentally one can have endless fun with the two competing conventions for taps. While less standard, this example shows that our choice in which $k_s = \sum_{t \in T}k_{s-t}$ is a natural fit for the annihilator method. It is also clearly best for the Berlekamp—Massey algorithm.)

Length of all keystreams

One computer demonstration that I think worked quite well last year used a Mathematica notebook to compute the lengths of all keystreams for all invertible LFSRs of width $\ell \le 5$ . I then showed that the keystreams of maximum possible period $2^{\ell}-1$ came from the LFSRs whose minimal polynomial is primitive. Of course most, quite reasonably, didn’t know what ‘primitive’ meant, but they could see Mathematica did, and that there was some underlying pattern related to the factorization of the minimal polynomial.

Since the matrix representing an LFSR with taps $T$ in the canonical basis of $\mathbb{F}_2^\ell$ is the companion matrix of $X^\ell + \sum_{t \in T}X^{\ell -t}$ , the corresponding $\mathbb{F}_2[X]$ -module is

$\mathbb{F}_2[X]/\langle X^\ell + \sum_{t \in T} X_{\ell - t}\rangle.$

Switching to the reciprocal polynomial, the lengths of the keystreams are the orbit sizes of $X$ in its action on $\mathbb{F}_2[X]/\langle f_T(X) \rangle$ . When $f_T(X)$ is irreducible and primitive, we get a single non-zero orbit. The general case is quite intricate, and stated in Theorem 6.33 in Lidl and Niederreiter Finite fields.

For this retelling, we need the following function. Given $r \in \mathbb{N}$ with $2^{m-1} < r \le 2^m$ , let $b(r) = m$ . Thus the sequence $b(r)$ starts

$0, 1, 2, 2, 3, 3, 3, 3, 4, \ldots$

and $b(r)$ is the number of bits in the binary form of $r-1$ .

In the next two results, let $g(X) \in \mathbb{F}_2[X]$ be an irreducible polynomial of degree $d$ and let $t$ be the order of $X$ in the finite field $\mathbb{F}_2[X]/g(X)$ .

Proposition. Let $r \ge 2$ . The orbits of $X$ on $\mathbb{F}_2[X]/g(X)^r$ not contained in the unique maximal ideal $g(X)\mathbb{F}_2[X]/g(X)^r$ have size $2^{b(r)}t$ and there are $\bigl(2^{rd} - 2^{(r-1)d}\bigr)/ 2^{b(r)} t$ of them.

Proof. Let $J$ be the complement of the maximal ideal. By hypothesis, $X^t + 1$ is divisible by $g(X)$ . Since $t$ is odd,

$X^{2^m t} + 1 = (X^t+1)^{2^r}$

is divisible by $g(X)^r$ if and only if $2^m \ge r$ . Therefore $X$ has order $2^{b(r)} t$ in its action on $J$ . Since $r \ge 2$ , the elements of $J$ are invertible. Hence if $p(X) \in J$ then $p(X)X^m = p(X)$ mod $g(X)^r$ if and only if $X^m = 1$ mod $g(X)^r$ . It follows that all the orbits of $X$ on $J$ have size $2^{b(r)}t$ . Since $J$ has size $2^{dr} - 2^{d(r-1)}$ , the number of orbits is as claimed. $\Box$

Theorem. The non-zero orbits of $X$ on $\mathbb{F}_2[X]/g(X)^e$ have sizes $2^b t$ for $b \in \mathbb{N}_0$ . If $2^b \le e$ then the number of orbits of size $2^b t$ is

$\displaystyle \frac{2^{2^b d} - 2^{2^{b-1}d}}{2^b t}.$

The number of orbits of size $2^{b(e)} t$ is

$\displaystyle \frac{2^{e d} - 2^{2^{b(e)-1}}d}{2^{b(e)} t}.$

Proof. Let $b \in \mathbb{N}$ . Suppose that $2^b \le e$ . For each $r$ such that $2^{b-1} < r \le 2^{b}$ we have $b(r) = b$ and the count of orbits of size $2^b t$ in the previous proposition telescopes as required. A similar telescoping works to count the orbits of size $2^{b(e)} t$ . Finally we count the zero orbit $\{0\}$ and $(2^d-1)/t$ orbits of size $t$ , which together form the minimal ideal $g(X)^{d-1} \mathbb{F}_2[X]/g(X)^d$ isomorphic to the finite field $\mathbb{F}_2[X]/g(X)$ . $\Box$

For example, take $g(X) = (1+X+X^2)^5$ . Then $b(e) = 3$ , $t = 3$ and the orbits of $X$ have sizes $1, 3$ ; $6^2$ ; $12^{20}$ ; $24^{32}$ , where the semicolons indicate the split according to $b \in \mathbb{N}$ used in the theorem, and the exponents indicate multiplicities. These orbit sizes form the multiset $\{1,3,6^2, 12^{20}, 24^{32} \}$ .

Just for the next corollary, we define the product of two multisets to be the multiset obtained by multiplying the elements pairwise, respecting multiplicities. For example

$\{1,3,6^2\} \times \{1,7\} = \{1,3,6^2,7,21,42^2\}.$

Corollary. Let $F$ be an invertible LFSR with taps $T$ . Let $f_T(X) = g_1^{e_1} \ldots g_c^{e_c}$ be the irreducible factorization of its feedback polynomial. Then the multiset of orbit sizes of $F$ is the product of the multisets of orbit sizes for each factor $g_i^{e_i}$ , as given by the previous theorem.

Proof. This is routine from the Chinese Remainder Theorem. $\Box$