Cryptology IV.3 Feedback Shift Registers and Linear Complexity

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Contents

1. The linear complexity of a bit sequence [PDF]
2. Synthesis of LFSRs [PDF]
3. The BERLEKAMP-MASSEY algorithm [PDF]
   Mathematica program as text and as notebook
   SageMath code is in the PDF file.
4. The BM Algorithm as a Cryptanalytic Tool [PDF]
5. The distribution of linear complexity [PDF]
6. The mean value of the linear complexity [PDF]
7. Linear complexity and TURING complexity (outline) [PDF]
8. Approaches to nonlinearity for FSRs [PDF]
9. Correlation attacks—the Achilles heels of combiners [PDF]
10. Design criteria for nonlinear combiners [PDF]

The complete chapter as PDF file.

Introduction

As we saw in the last chapter LFSRs are cryptographically weak if naively used. Even nonlinear FSRs admit an efficient prediction algorithm via the Noetherian principle undermining their security.

In this chapter we'll look at LFSRs from the opposite direction: Given a bit sequence, how to generate it by an LFSR in an optimal way? The minimal length of such an LFSR—called linear complexity—will turn out to be a useful measure of predictability—even a very good measure except for a few outliers.

As a result of this chapter we note:

Using LFSRs and nonlinear combining functions we can build useful and fast pseudorandom generators, especially in hardware.

Unfortunately[*] there is no satisfying comprehensive theory for the cryptologic security of this type of pseudorandom generators, even less a mathematical proof. Security is assessed by plausible criteria that—as for bitblock ciphers—are related to the nonlinearity of Boolean functions.

[*] Mathematicians would say »fortunately« since unsolved problems are essential for their survival.