The source code of my MSc project.
Feedback Shift Registers (FSRs) are pseudorandom number generators (PRNGs) that can efficiently generate pseudorandom sequences of bits for various applications. In cryptography they are used as the building blocks for stream ciphers. Linear FSRs (LFSRs) use a linear function and are the most used but due to their linearity they are vulnerable to cryptanalysis. Non-linear FSRs (NLFSRs) use a non-linear function and are proven to be more immune to attacks, however their theory is not fully understood yet. The project covers LFSR implementation and its application in one section. It introduces the Adjacent-AND NLFSR and discusses some of its properties in another section. In the first section a realisation in software of Fibonacci and Galois LFSRs is given and how to transform between them. The following LFSR applications are also provided: Berlekamp-Massey algorithm, system of linear equations and a demonstration of a known-plaintext attack. The Adjacent-AND NLFSR is introduced in the second section of the MSc thesis. Fibonacci NLFSR is implemented for this purpose. Two algorithms that help in the analysis of NLFSRs are devised: a system of linear equations equivalent for the Adjacent-AND NLFSR and a function that generates NLFSRs of the introduced kind. An experimentation follows and the number of NLFSRs, linear and nonlinear complexities are analysed in particular.
The Adjacent-AND NLFSR is a Fibonacci NLFSR such that AND gates are allowed to appear between adjacent cells only and have exactly two inputs. The project attempts to draw a picture on the immunity and vulnerability of this kind NLFSR by analysing, among other things, its linear and nonlinear complexity. This NLFSR is used in actual stream ciphers. For instance Trivium uses three NLFSRs of this type.