A stream cipher: linear feedback shift registers

Another type of cipher is the following. Suppose that your alphabet is $A=\{0,1,2,...,n-1\}$ and that the message space $M$ is as above. Let $r=(r_1,r_2,...)$ be an infinite sequence of ``random'' elements of $A$. Define the encryption map $E:M\rightarrow E$ by $E(m)=m+r\ ({\rm mod}\ n)$, where addition is componentwise modulo $n$. Since $r$ is a random sequence, any eavesdropper would think the received message is random as well. Define the decryption map $D:M\rightarrow E$ by $E(m)=m-r\ ({\rm mod}\ n)$, where subtraction is componentwise modulo $n$. This is called a one time key pad cipher and $r$ is called the key.

How do we construct a random sequence?

Let us begin with an example. How does the sequence

$$12343577824506956...$$

arise and how do you predict the next term in the sequence? Start with the ``seed'' 1234. To get the $5^{th}$ digit, add the $1^{st}$ and $2^{nd}$ modulo $10$. To get the $6^{th}$ digit, add the $2^{nd}$ and $3^{rd}$ modulo $10$, and so on. In general, if $s_i$ denotes the $i^{th}$ digit then

$$s_{4+i}=s_i+s_{i+1}\ ({\rm mod}\ 10),\ \ \ \ \ \ i>0.$$

In particular, the next term in the series is a $5$ since $6+9=15\equiv 5\ ({\rm mod}\ 10)$. This is a special case of a linear feedback shift register sequence (LFSR).

Definition 1.7.23   A linear feedback shift register sequence modulo $n$ of length $k>0$ is a sequence $s_1,s_2,...$ such that $s_1,...,s_k$ are given and

$$s_{k+i}\equiv a_1s_i+a_2s_{i+1}+...+a_{k}s_{k+i-1}\ ({\rm mod}\ n),\ \ \ \ \ \ i>0,$$ (1.5)

where $a_1,...,a_k$ are given integers. An equation such as this is called a recursion equation of length $k$ modulo $n$.

For security applications, one would like the sequence $\{s_i\}$ to be as ``random looking'' as possible.

S. Golomb [Gol] gives a list of three statistical properties a sequence of numbers ${\bf a}=\{a_n\}_{n=1}^\infty$, $a_n\in \{0,1\}$, should display to be considered ``random''. Define the autocorrelation of ${\bf a}$ to be

$$C(k)=C(k,{\bf a})=\lim_{N\rightarrow \infty} {1\over N}\sum_{n=1}^N (-1)^{a_n+a_{n+k}}.$$

In the case where ${\bf a}$ is periodic with period $P$ then this reduces to

$$C(k)={1\over P}\sum_{n=1}^P (-1)^{a_n+a_{n+k}}.$$

Assume ${\bf a}$ is periodic with period $P$.

balance: $\vert\sum_{n=1}^P(-1)^{a_n}\vert\leq 1$.

low autocorrelation:

$$C(k)= \left\{ \begin{array}{cc} 1,& k=0,\\ \epsilon, & k\not= 0. \end{array}\right.$$

(For sequences satisfying these first two properties, it is known that $\epsilon=-1/P$ must hold.)

proportional runs property: In each period, half the runs have length $1$, one-fourth have length $2$, etc. Moveover, there are as many runs of $1$'s as there are of 0's.

To make the sequence $\{s_i\}$ be as ``random looking'' as possible, we'd like its period to be as long as possible. How do we do that? The answer depends on the theory of polynomials over finite fields, discussed in the next chapter. In order to not keep the reader in suspense and to motivate the material in the next chapter, we present the precise answer in the theorem below.

Theorem 1.7.24   Let $S=\{s_i\}$ be defined by (1.5), where $n=p$ is a prime. The period of $S$ is at most $N=p^k-1$. It's period is exactly $p^k=1$ if and only if the characteristic polynomial of

$$A= \left( \begin{array}{ccccc} 0 & 1 & 0 & \dots & 0\\ 0 & ... ...s & 0 & 1\\ a_0 & a_1 & \dots & & a_{k-1} \end{array}\right),$$

is irreducible and primitive ^1.6 over $\mathbb{F}_p$.

This proof follows from the definition of primitive, and the construction of the finite extension fields of $\mathbb{F}_p$, discussed in the next chapter.

A related result is the following fact.

Theorem 1.7.25   If ${\bf c}=\{c_n\}_{n=1}^\infty$ are the coefficients of $f(x)/g(x)$, where $f,g\in {\bf F}_2[x]$ and $g(x)$ is an irreducible polynomial with $x$ primitive (mod $g(x)$) (i.e., powers of $x$ (mod $g(x)$) yield every element in $({\bf F}_2[x]/g(x){\bf F}_2[x])^\times$). Then ${\bf c}$ is periodic with period $P=2^d-1$ (where $d$ is the degree of $g(x)$) and satisfies Golomb's randomness conditions.

A proof of this may be found in [Gol].