The mathematician Claude Shannon first formalized the notion of perfect secrecy and showed that certain cryptosystems realized it. We do not cover all of his theory, but address the part that is directly relevant to our study of cryptography and that relies on math that is within the scope of the text.

In this chapter, we discuss how to tell whether a cryptosystem is perfectly secure. In Chapter 7, we discuss some more ways to use perfect secrecy. It should become clear to the reader why modular arithmetic is used instead of ordinary arithmetic for much of cryptography.

As we will see, perfect secrecy of a cryptosystem and unique decryptability are mathematical cousins. A cryptosystem may be uniquely decryptable and not perfectly secure, or vice versa. However, the math that goes into determining perfect secrecy is very similar to the math that goes into determining unique decryptability.

What does an eavesdropper learn from seeing a cyphertext?

A cryptosystem is perfectly secure if an eavesdropper learns nothing about the plaintext from seeing the cyphertext. To understand what cryptosystems are secure, therefore, we consider what it means to learn something.

For this purpose, we consider a very simple scenario. Alice sends Bob an encrypted message, and Eve intercepts the cyphertext. (For now, we ignore the possibility that Bob may respond using the same cryptosystem and even the same key.) To understand what Eve has learned from seeing the cyphertext, we consider her knowledge of the plaintext before (her a priori knowledge) and after she sees the cyphertext (her a posteriori knowledge).

Outcomes of an experiment

Consider an experiment that depends on chance, and that does not depend on any unknown information. What can we say about the outcome? If we actually carry the experiment out, we can say precisely what happened – but what can we say beforehand? The best description we can hope to give is one that specifies the likelihood of each possible outcome. Such a description is called a probability distribution. Probability theory is a way of reasoning about likelihoods.

Consider the roll of a die – there are six possible outcomes (not including wacky things like “the die rolls right off the table”). We implicitly assume that outcomes of a single experiment are mutually exclusive. That is, only one of the outcomes can occur each time that the experiment is performed.

The possible outcomes are shown in Figure 5.1.

The set of possible outcomes is called the sample space. It is also called the probability space.

Probabilities of outcomes

We describe the relative likelihoods of the six possible outcomes by assigning each outcome a number that represents its probability. If, for example, one outcome is twice as likely to occur as another, we assign the first outcome a probability twice that assigned to the second.

Certain conventions govern the numbers we use as probabilities. It would not make sense for one outcome to be −1 times as likely as another, so we restrict probabilities to be nonnegative numbers. We want probability 0 to correspond to impossibility; an outcome that never occurs would be assigned probability 0. We want probability 1 to correspond to certainty; an outcome that always occurs would be assigned probability 1. In a typical experiment, each outcome's probability is a number bigger than 0 and smaller than 1.

Motivation

One of the difficulties with traditional, symmetric-key cryptosystems is in getting the two parties to both know a secret key without anybody else knowing. This is particularly difficult when the two parties have never met in person and can only communicate via an insecure channel such as the Internet.

One could try to forestall the above difficulty by providing keys to everybody in advance. However, this introduces another difficulty. Suppose that there are a million and one people that want to participate. We can't know in advance who's going to want to communicate private with whom, so we have to provide each person a million keys, one for each of the other people with whom she might want to communicate. I couldn't possibly remember all these keys, so I have to store them on my computer. Suppose Eve has been eavesdropping on my communication and storing all the messages. If she manages to break into my computer and learn my keys, she can decrypt all these messages.

Worse yet, suppose another person comes along and wants to join the crowd. In order that the new person be able to communicate with everyone else, we have to provide a new key to each of the people already in the crowd. How can we transmit these new keys securely to all these people?

Secure block cyphers in the real world

We have seen that the addition cypher is not secure (unless used as a onetime pad). If you stick to one key and use the addition cypher as a block cypher, this cryptosystem is subject to a plaintext–cyphertext attack. Other attacks are effective as well.

There are lots of relatively secure cryptosystems, however. The most famous is DES (Data Encryption Standard). DES came out of an effort in 1970 by the National Bureau of Standards (NBS) to select a standard cryptosystem for use with non-classified data. In 1974, in response to the NBS's public appeal for a cryptosystem, IBM submitted a cryptosystem called Lucifer that they had developed earlier that decade. NBS then went to the National Security Agency (NSA) for help in evaluating the cryptosystem. NSA modified the system somewhat, including a reduction of the key size from the 112 bits used by Lucifer to only 56 bits (a compromise, as NSA had tried to reduce it to 48 bits). The resulting system was then certified by NBS for use. Institutions that needed to communicate privately with the government were expected to use DES (unless the material was classified). In 1979 the American Bankers Association recommended use of DES for encryption. Thus DES achieved very broad use.

Divisibility

We say an integer b evenly divides another integer c if c/b is a whole number. Actually, nobody in mathematics ever says that b “evenly divides” c – people just say b “divides” c. Another way to say the same thing is to say that b is a divisor of c. The divisors of c are the numbers that (evenly) divide c. Finally, one can also say that b is divisible by c.

Examples:

1. • 3 divides 12.

2. • 3 is a divisor of 9.

3. • 40 is not a divisor of 20.

4. • 40 is divisible by 20.

5. • 4 divides 4.

6. • 5 is a divisor of −10.

7. • 12 divides 60.

8. • The positive divisors of 50 are 1, 2, 5, 10, 25, and 50.

Relative primality

Two numbers r and s are relatively prime if there is no integer bigger than 1 that is both a divisor of r and a divisor of s. We also say in this case that r is relatively prime to s. For example, 18 and 8 are not relatively prime because 2 is a divisor of both of them. On the other hand, 9 and 8 are relatively prime because the only divisors common to both of them are 1 and −1. We never count 1 and −1 as common divisors when determining relative primality.

This book is partially based on the material covered in several Cambridge Mathematical Tripos courses: the third-year undergraduate courses Information Theory (which existed and evolved over the last four decades under slightly varied titles) and Coding and Cryptography (a much younger and simplified course avoiding cumbersome technicalities), and a number of more advanced Part III courses (Part III is a Cambridge equivalent to an MSc in Mathematics). The presentation revolves, essentially, around the following core concepts: (a) the entropy of a probability distribution as a measure of ‘uncertainty’ (and the entropy rate of a random process as a measure of ‘variability’ of its sample trajectories), and (b) coding as a means to measure and use redundancy in information generated by the process.

Thus, the contents of this book includes a more or less standard package of information-theoretical material which can be found nowadays in courses taught across the world, mainly at Computer Science and Electrical Engineering Departments and sometimes at Probability and/or Statistics Departments. What makes this book different is, first of all, a wide range of examples (a pattern that we followed from the onset of the series of textbooks Probability and Statistics by Example by the present authors, published by Cambridge University Press). Most of these examples are of a particular level adopted in Cambridge Mathematical Tripos exams. Therefore, our readers can make their own judgement about what level they have reached or want to reach.