Cryptography and Shift Registers

ABSTRACT

Shift registers are at the heart of cryptography and error-correction. In cryptography they are the main tool for generating long pseudorandom binary sequences which can be used as keys for two communicating parties in symmetric cryptography. Practically all military cryptography makes use of them. Shift registers are also fundamental in signal analysis and frequency hopping, most recently in connection with European GPS codes.

The subject has a chequered history. One of the pioneers was a famous Hollywood star who, in her day, was known as the worlds most beautiful woman and wrote one of the earliest patents on frequency hopping which was developed by the US military. We speak of the Austrian-born Hedwig Maria Eva Kiesler, otherwise known as Hedy Lamarr. The development of spread spectrum technology was first proposed by Lamarr using frequency hopping. She obtained a patent after coming to Hollywood in 1942 and turned it over to the US government as a contribution to the war effort. Shortly after the patent expired in 1959 Sylvania digitize the synchronization to supply secure communication during the Cuban missile crisis.

This paper presents a user-friendly, self-contained and comprehensive discussion of the theory of shift registers. Moreover, we provide several examples (and counterexamples) in support of the theory. In the non-linear case we study the relationship between truth tables and de Bruijn sequences. In the linear case, we use a matrix-theoretic approach to describe the situations when the output is periodic and when it is not periodic. Section three describes additional periodicity properties, using the Cayley-Hamilton theorem and the theory of error-correcting codes.

In Section six, we prove a fundamental result to the effect that, for non-singular shift registers of length k, the entire output is uniquely determined by any 2k consecutive bits of the output sequence. Although the result is part of the folk lore, it is certainly not well understood and there appears to be a lack of any rigorous proof in the literature. An additional bonus of our proof here is that it can be adapted to provide a new algorithm for demonstrating a little-known, and remarkable fact. Namely, we provide the most general method for constructing two quite different shift registers of the same length that produce identical output sequences! A new result concerning such shift registers is also sketched in Section six.

Keywords: