4
$\begingroup$

In the classic book "Applied Cryptography" (20th anniversary edition) from Bruce Schneier, there is an illustration of a maximal-length LFSR:

32-bit long maximal-length LFSR

According to the book, this LFSR uses the tap sequence from the polynomial $x^{32}+x^7+x^5+x^3+x^2+x+1$ which is maximal-length.

However, most examples I found online (e.g. Wikipedia) increment the numbering of the shift register bits from the input to the output (left to right)—which could just be a different convention—but the taps are also reversed. On this figure that would translate to taps on $\{b_1,b_{26},b_{28},b_{30},b_{31},b_{32}\}$.

I would normally tend to trust a reference book more than random online sources, but I found an alarming number of counterexamples. Are the taps placed correctly on the figure above?

$\endgroup$
6
$\begingroup$

Are the taps placed correctly on the above figure?

No. That's acknowledged in the errata to the second edition, on the section for page 375 (AFAIK the 20th anniversary edition is essentially the second edition with a little extra at the beginning).

My preferred method to determine the hardware implementation for a Fibonacci LFSR from the polynomial:

  • Use a shift register with as many bits as the degree of the polynomial.
  • Number shift register state bits (the output of the internal D gates) from $0$ for the output, to $n-1$; with thus $n$ the input of the shift register.
  • XOR the bits $i$ from $0$ to $n-1$ of the shift register that has their term $x^i$ present in the polynomial¹ ($x^0$ is the term $1$ of the polynomial).
  • For an LFSR in scrambler configuration, additionally XOR the input of the scrambler.
  • Feed the result of the XORs to the input of the shift register.

Depending on convention, the taps shown are for polynomial $x^{32}+x^{31}+x^6+x^4+x^2+x+1$ or it's reflected polynomial $x^{32}+x^{31}+x^{30}+x^{28}+x^{26}+x+1$. These are not primitive², and accordingly, the sequence for the LFSR shown is not maximal-length.

LFSRs and CRCs are an area where there are many errors in literature and implementations, and several justifiable conventions around, especially for Fibonacci LFSRs:

  • There is no universal agreement that the low-order coefficient of the polynomial is on the output of the LFSR. Using the other convention¹ causes a reflection in time of the order of the bits in the generated sequence, for the reflected initial state.
  • The most common convention for an isolated LFSR is that the output of the LFSR is the output of the shift register, so that the first bits to the output match the initial state of the shift register. But the common convention for LFSR-based scramblers is that the output is the input of the shift register, which reduces latency in telecom applications. That offsets the generated sequence.
  • There is no universal agreement on numbering bits of the shift register/initial state from output to input. This is best IMHO since it matches the order in which output bits appear, and people agree on numbering these incrementally with time.
  • There is no agreement on numbering shift register bits starting from 0 (as in the above method) or from 1 (as in the question's figure). The same issue for output bits in the generated sequence, and I've seen the conventions differ.

Lots of theoretical work, high-speed hardware, and software use Galois LFSRs. There's relative agreement that if their $n$-bit polynomial is $P(x)$, then their state $S(x)$ is a polynomial of degree (at most) $n-1$ with state bits numbered from $0$ to $n-1$ according to rank in $S$. The state changes from $S(x)$ to $x^k\,S(x)\bmod P(x)$ after $k$ steps. Good luck for the rest.

Galois LFSRs are easily implemented in hardware and software:

s = (s<<1)^(p&-(s>>(n-1)));   // Galois LFSR, assuming s an unsigned exactly n-bit
s = (s>>1)^(q&-(s&1));        // Galois LFSR, reflected, assuming s at least n-bit

Note: p is the polynomial evaluated without it's high-order term in $\mathbb Z$ for $x=2$. q is the polynomial reflected, then evaluated without it's high-order term in $\mathbb Z$ for $x=2$.

The output sequence of a Fibonacci LFSR with term $1$ present in it's polynomial matches that of a Galois LFSR with the reflected polynomial (using the conventions above), and an appropriate adaptation of the initial state (which depends on conventions about where the output sequence is extracted from).


¹ Another possibility is to XOR the bits $i$ that have their term $x^{(n-i)}$ present. That works only if the term $1=x^0$ is present in the polynomial, which is true for all polynomials used in practice, all irreducible polynomials, and thus all primitive polynomials (which are those generating a maximal-length sequence when starting from a non-zero initial state, and input at $0$ if in scrambler configuration). The sequence generated is generally not the same.

² Proof: every primitive polynomial is irreducible, and $x^{32}+x^{31}+x^6+x^4+x^2+x+1$ is not, since it's divisible by $x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^9+x^4+x^3+1$. A polynomial and its reflection have the same status w.r.t. primitiveness and irreducibility.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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