Introduction

The need to authenticate both the contents and origin of a message is crucial in any communications network. Consider the following problematic situations in which Alice and Bob face the forger Fred. In each case we suppose that Bob is Alice's banker.

1. (1) Suppose Fred sends Bob a message claiming to come from Alice asking him to transfer $1000 into Fred's account. If Bob has no way of verifying the origin of this message then Alice is in trouble.

2. (2) Suppose Fred intercepts a message from Alice to Bob asking him to transfer $1000 into Carol's account. If Fred can alter the message so that ‘Carol’ is replaced by ‘Fred’ then again there is trouble.

3. (3) Suppose Fred intercepts a message from Alice to Bob asking him to transfer $1000 into Fred's account. Fred stores the message and resends it to Bob whenever he is short of cash!

In each case Fred can succeed if no proper system of message authentication is in place.

Historically the handwritten signature has been the preferred method for authentication of messages. A digital signature is a method for achieving this based on cryptography.

The basic problems

We saw in Chapter 5 that the one-time pad is a cryptosystem that provides perfect secrecy, so why not use it? The obvious reason is that the key needs to be as long as the message and the users need to decide on this secret key in advance using a secure channel.

Having introduced public key cryptography in Chapter 7 one might wonder why anyone would want to use a symmetric cryptosystem. Why not simply use RSA or some other public key cryptosystem and dispense with the need to exchange secret keys once and for all?

The problem with this approach is that symmetric cryptosystems are generally much faster. For example in 1996, DES was around 1000 times faster than RSA. In situations where a large amount of data needs to be encrypted quickly or the users are computationally limited, symmetric cryptosystems still play an important role. A major problem they face is how to agree a common secret key to enable communications to begin.

This basic ‘key exchange problem’ becomes ever more severe as communication networks grow in size and more and more users wish to communicate securely. Indeed while one could imagine. Alice and Bob finding a way to exchange a secret key securely the same may not be true if you have a network with 1000 users.

In search of a definition

Having considered classical symmetric cryptography in the previous chapter we now introduce the modern complexity theoretic approach to cryptographic security.

Recall our two characters Alice and Bob who wish to communicate securely. They would like to use a cryptosystem, in which encryption (by Alice) and decryption (by Bob using his secret key) are computationally easy but the problem of decryption for Eve (who does not know Bob's secret key) should be as computationally intractable as possible.

This complexity theoretic gap between the easy problems faced by Alice and Bob and the hopefully impossible problems faced by Eve is the basis of modern cryptography. In order for such a gap to exist there must be a limit to the computational capabilities of Eve. Moreover it would be unrealistic to suppose that any limits on the computational capabilities of Eve did not also apply to Alice and Bob. This leads to our first assumption:

• Alice, Bob and Eve can only perform probabilistic polynomial time computations.

So for Alice and Bob to be able to encrypt and decrypt easily means that there should be (possibly probabilistic) polynomial time algorithms for both procedures.

But exactly how should we formalise the idea that Eve must face a computationally intractable problem when she tries to decrypt an intercepted cryptogram without Bob's secret key?

Feedback shift register (FSR) sequences have been widely used as synchronization, masking, or scrambling codes and for white noise signals in communication systems, signal sets in CDMA communications, key stream generators in stream cipher cryptosystems, random number generators in many cryptographic primitive algorithms, and testing vectors in hardware design. Golomb's popular book Shift Register Sequences, first published in 1967 and revised in 1982 is a pioneering book that discusses this type of sequences. In this chapter, we introduce this topic and discuss the synthesis and the analysis of periodicity of linear feedback shift register sequences. We give different (though equivalent) definitions and representations for LFSR sequences and point out which are most suitable for either implementation or analysis. This chapter contains seven sections, which are organized as follows. In Section 4.1, we give a general description for feedback shift registers at the gate level for the binary case and as a finite field configuration for the q-ary case. In Sections 4.2–4.4, we introduce the definition of LFSR sequences from the point of view of polynomial rings and discuss their characteristic polynomials, minimal polynomials, and periods. Then, we show the decomposition of LFSR sequences. We provide the matrix representation of LFSR sequences in Section 4.5 as another historic approach and discuss their trace representation for the irreducible case in detail in Section 4.6, which is a more modern approach. (The general case will be treated in Chapter 6.) LFSRs with primitive minimal polynomials are basic building blocks for nonlinear generators.

Randomness of a sequence refers to the unpredictablity of the sequence. Any deterministically generated sequence used in practical applications is not truly random. The best that can be done here is to single out certain properties as being associated with randomness and to accept any sequence that has these properties as random or more properly, a pseudorandom sequence. In this chapter, we will discuss the randomness of sequences whose elements are taken from a finite field. In Section 5.1, we present Golomb's three randomness postulates for binary sequences, namely the balance property, the run property, and the (ideal) two-level autocorrelation property, and the extension of these randomness postulates to nonbinary sequences. M-sequences over a finite field possess many extraordinary randomness properties except for having the lowest possible linear span, which has stimulated researchers to seek nonlinear sequences with similarly such favorable properties for years. In Section 5.2, we show that m-sequences satisfy Golomb's three randomness postulates. In Section 5.3, we introduce the interleaved structures of m-sequences and the subfield decomposition of m-sequences. In Sections 5.4–5.6, we present the shift-and-add property, constant-on-cosets property, and 2-tuple balance property of m-sequences, respectively. The last section is devoted to the classification of binary sequences of period 2n − 1.

Golomb's randomness postulates and randomness criteria

We discussed some general properties of auto- and crosscorrelation in Chapter 1 for sequences whose elements are taken from the real number field or the complex number field.