PREFACE xiii material from the text, while others are quite challenging and are introduc- tions to more advanced topics. These problems are meant to supplement the text and to allow students of different levels and interests to explore the material in different ways. Instructors may contact the authors (either directly or through the AMS webpage) to request a complete solution key. Chapter 1 is a brief introduction to the history of cryptography. There is not much mathematics here. The purpose is to provide the exciting historical importance and background of cryptography, introduce the terminology, and describe some of the problems and uses. Chapter 2 deals with classical methods of encryption. For the most part we postpone the attacks and vulnerabilities of these meth- ods for later chapters, concentrating instead on describing popular methods to encrypt and decrypt messages. Many of these methods involve procedures to replace the letters of a message with other letters. The main mathematical tool used here is modular arith- metic. This is a generalization of addition on a clock (if it’s 10 o’clock now, then in five hours it’s 3 o’clock), and this turns out to be a very convenient language for cryptography. The final sec- tion on the Hill cipher requires some basic linear algebra, but this section may safely be skipped or assigned as optional reading. Chapter 3 describes one of the most important encryption methods ever, the Enigma. It was used by the Germans in World War II and thought by them to be unbreakable due to the enormous number of possibilities provided. Fortunately for the Allies, through espionage and small mistakes by some operators, the Enigma was successfully broken. The analysis of the Enigma is a great introduction to some of the basic combinatorial functions and problems. We use these to completely analyze the Enigma’s complexity, and we end with a brief discussion of Ultra, the Allied program that broke the unbreakable code. Chapters 4 and 5 are devoted to attacks on the classical ciphers. The most powerful of these is frequency analysis. We further de- velop the theory of modular arithmetic, generalizing a bit more operations on a clock. We end with a discussion of one-time pads. When used correctly, these offer perfect security however, they re- quire the correspondents to meet and securely exchange a secret. Exchanging a secret via insecure channels is one of the central prob- lems of the subject, and that is the topic of Chapters 7 and 8. In Chapter 6 we begin our study of modern encryption methods. Several mathematical tools are developed, in particular binary ex- pansions (which are similar to the more familiar decimal or base 10 expansions) and recurrence relations (which you may know from the Fibonacci numbers, which satisfy the recursion Fn+2 = Fn+1 +Fn).
Previous Page Next Page