AN INTRODUCTION TO CRYPTOGRAPHY

Reviews

"This is a great book! It can be used in many ways: for a university course at one extreme, and as selective light reading for pleasure at the other. The author's enthusiasm carries the reader along clearly and easily, spilling over to scores of fascinating, beautifully written footnotes, which include more than fifty mini-biographies."

"...this book is excellent and highly recommended."

Short Book Reviews, Vol. 21, No. 2, August, 2001

For those who have a copy, here is an online updates page

 

TABLE OF CONTENTS:

BRIEF OVERVIEW:

This book is intended for a one-semester introductory undergraduate course in cryptography. The text has been designed in such a way that the reader with little mathematical background can work through the text, and the reader with a firm mathematical background will encounter sufficient challenging material to sustain interest. Any mathematics required is presented herein in advance of the cryptographic material requiring it. The impetus for the writing of this text arose from this author's involvement in designing an undergraduate course in introductory cryptography for the Mathematics Department at the University of Calgary in 1998. No suitable text for that course was on the market, nor is there one at the time of this writing, hence the incarnation of this one. Essentially, the text is meant for any reader who wants an introduction to the area of cryptography. The core material is self-contained so that the reader may learn the basics of cryptography without having to go to another source. However, in the optional material sections, such as Section Two of Chapter Five, where the number field sieve is studied, the reader will require some knowledge of algebraic number theory such as that given in this author's previous book ALGEBRAIC NUMBER THEORY. Also, for the advanced topics in optional Chapter Six, such as Section One on elliptic curve methods in primality testing, factoring, and cryptosystems, some algebraic background is required, but the basics of elliptic curves are developed in that section for the benefit of the reader.

For the instructor, a course outline is, simply put, the first four chapters (excluding the material in Section Three of Chapter Two on successors and cryptanalysis of DES) as the core material for a basic introduction to the area. Optional material (determined by the pointing hand symbol) may be added at the discretion of the instructor, depending upon the needs and background of the students involved. The material in Section One of Chapter One is a motivator for the material in the text by giving an overview of the history of the subject, beginning with the first rumblings of cryptography in ancient Egypt four millennia ago and ending with our modern day needs and challenges. There is sufficient historical data on various ciphers, such as the Caesar cipher, the Playfair cipher, the German World War I ADFGVX field cipher, and one of Edgar Allan Poe's famous cryptograms, to provide a novel set of challenging exercises at the end of this first section to motivate the reader further. Section Two of Chapter One is similarly a history, this time of factoring and primality testing. This may be seen as a precursor to the core material in Chapter Four and the optional material in Chapter Five. We begin with the notion of a prime defined in Euclid's Elements and proceed through several primality testing and factoring techniques introduced by Fibonacci and developed by Fermat, Euler, and numerous others up to Lucas at the end of the nineteenth century. We continue with Kraitchik, Lehmer and others whose work ushered in the twentieth century, setting the groundwork for algorithms to be developed in the computer age. Section Three of Chapter One develops the basics of computer arithmetic, and sets the stage for Section Four which explores complexity issues.

Section One of Chapter Two is an introduction to modular arithmetic. The language of congruences is developed from the basic definition through Wilson's Theorem, Fermat's Little Theorem, Euler's generalization, the Arithmetic of the Totient, the Chinese Remainder Theorem and its generalization together with numerous illustrations such as the Coconut Problem, the Egg Basket Problem, and the Units of Work problem, culminating in a tool to be used in many of the cryptographic techniques developed in the text --- the Repeated Squaring Method for Modular Exponentiation. Section Two of Chapter Two is devoted to the first of the two symmetric-key cryptosystems to be studied, namely block ciphers. From requisite definitions of the basic concepts such as enciphering and deciphering transformations, we provide detailed discussions, with examples and diagrams, of numerous block ciphers including: affine, substitution, running-key, as well as transposition and permutation ciphers; concluding with a complete, detailed description of the Data Encryption Standard, DES, together with many illustrative figures. Section Three of Chapter Two is optional, containing a discussion of modes of operation and cryptanalysis of blocks ciphers such as DES, and the candidates for the successor of DES, the soon to be Advanced Encryption Standard, AES. We give a complete, detailed, illustrated description of one of the candidates, the Twofish cipher, which is preceded by a discussion of Feistel ciphers of which the latter is an example. Section Four of Chapter Two deals with the other class of symmetric-key ciphers --- stream ciphers. The reader is taken on a journey from the basic definition of a stream cipher through the notions of keystreams, seeds, generators, randomness, one-time pads, synchronous and self-synchronizing ciphers, linear feedback shift registers, and nonlinear combination generators, plus several illustrations and examples.

Chapter Three addresses public-key cryptosystems, beginning in Section One with exponentiation, discrete logarithms, and protocols. In particular, we present the Pohlig-Hellman symmetric key exponentiation cipher, one-way functions, coin flipping via both exponentiation and one-way functions, bit commitment protocols, the Pohlig-Hellman algorithm for computing discrete logarithms, hash functions, message authentication codes, and the Diffie-Hellman key-exchange protocol. The latter motivates the discussion in Section Two where we look at public-key cryptosystems, beginning with the definition of trapdoor one-way functions, which leads to a discussion of the RSA public-key cryptosystem. Then a definition of modular roots and power residues fleshes out our knowledge of congruences sufficiently to describe the Rabin and ElGamal public-key ciphers. Section Three deals with issues surrounding authentication, the need for which is motivated by an illustrated discussion of impersonation attacks on public-key cryptosystems. This leads into a definition of the notions surrounding digital signatures. As illustrations, we present the RSA, Rabin and ElGamal public-key signature schemes. Section Four studies the knapsack problem. Once the basics are set up, we provide a definition of superincreasing sequences, illustrated by the Merkle-Hellman and Chor-Rivest knapsack cryptosystems. Chapter Three concludes with a comparison and a contrasting of symmetric-key and public-key ciphers, with a description of the modern approach using combinations of both types of ciphers for a more secure cryptographic envelope.

Chapter Four deals with primality testing, starting in Section One with an introduction to primitive roots, moving from the definition to a discussion of Gauss's algorithm for computing primitive roots, Artin's conjecture, and the fundamental primitive root theorem. We then engage in a development of the index calculus, leading to Euler's criterion for power residue congruences. Our knowledge of quadratic residues is then advanced by the introduction of the Legendre symbol and its properties, which allows us to prove Gauss's quadratic reciprocity law. Another step up is taken with a definition of the Jacobi symbol and its properties, which we need later in the chapter. Section Two inspects true primality tests including the Lucas-Lehmer test, the Pocklington theorem, Proth's theorem, and Pepin's test. The section concludes with a discussion of complexity of primality testing, including the introduction of the notion of a certificate. Probabilistic primality tests are the topic of Section Three, starting with the definitions of Euler Liars, pseudoprimes, and witnesses. Then we work through and illustrate the Solovay-Strassen probabilistic primality test. Once the concept of strong pseudoprimes, liars, and witnesses are introduced, we are in a position to present the Miller-Rabin-Selfridge strong pseudoprime. The section concludes with a general discussion of Monte Carlo algorithms, of which the latter two algorithms are examples.

Chapter Five on factoring is the first of two optional chapters. Section One involves an illustrated description of three factoring algorithms: Pollard's p-1 method, the Brillhart-Morrison continued fraction algorithm, and the quadratic sieve. A brief history of how the work of Legendre, Euler, Kraitchik and Lehmer led to the development of these algorithms is also provided, as is a discussion of how the notions can be generalized. This motivates the topic of Section Two, which begins with an illustration of how Pollard's original idea for factoring with cubic integers led to the development of the number field sieve. Then a detailed description of the special number field sieve is given (with the factorization of the ninth Fermat number as an illustration) along with a discussion of its complexity in relation to the general number field sieve.

Chapter Six contains advanced topics. The first section introduces elliptic curves from the basic definition and leads the reader through the development of the elliptic curve group structure with several figures to illustrate the geometry in relation to the algebraic development. Once the basics are established, we state (without proof) some deep results needed for the cryptography, including the Nagell-Lutz Theorem, Mazur's theorem, Mordell's theorem, Siegel's theorem, and Hasse's theorem. We then present, and illustrate with worked examples, Lenstra's elliptic curve factoring method as well as the elliptic curve primality test and some generalizations thereof. To prepare for the cryptosystems, we generalize the notion of discrete logs to elliptic curves, and describe both the ElGamal and Menezes-Vanstone public-key elliptic curve cryptosystems. The section concludes with a discussion of the security of elliptic curve ciphers. The next section takes a look at the concept of zero-knowledge proofs in its various formats. We illustrate with the Feige-Fiat-Shamir identification protocol, the cut and choose protocol, and Hamiltonian circuits. The section is concluded with a study of noninteractive zero-knowledge protocols and zero-knowledge proofs of discrete log. Section Three, the last section of the main text of the book, takes us into the realm of quantum cryptography. The basis upon which the latter rests is the Heisenberg uncertainty principle that we discuss at length. We demonstrate how this principle can be used to generate a secret key for a quantum cryptosystem, called quantum key generation. The amazing properties of both quantum computers and quantum cryptography are considered, including the proposals for nuclear magnetic resonance-based quantum computers. The latter are closer to the proposed DNA-based computers, which would be several orders of magnitude faster than the fastest supercomputers known today. To take the reader to the edge of the fantastic, we also look at quantum teleportation and all that implies. The building of a quantum computer (a prototype of which already exists) would have dramatic consequences, not the least of which would be the breaking of public-key cryptography, such has RSA cryptosystems.

Features of This Text

The book is ideal for the student since it offers a wealth of exercises with nearly 300 problems. The more challenging exercises are marked with a star symbol. Also, complete and detailed solutions to all of the odd-numbered exercises are provided at the back of the text. Complete and detailed solutions of the even-numbered exercises are included in a Solutions Manual, which is available from the publisher for the instructor who adopts the text for a course. The exercises marked with two stars are to be considered only by the reader who requires an exceptional challenge, or for the instructor to extract from the solutions manual to present to students as an additional feature.

The text is accessible to anyone from the beginning undergraduate to the research scientist. Appendix A, described below, contains a review of all of the requisite background material. Essentially, the reader can work through the book without any serious impediment or need to seek another source in order to learn the core material.

There are more than 50 biographies of the individuals who helped develop cryptographic concepts. These are given in the footnotes woven throughout the text, to give a human face to the cryptography being presented. A knowledge of the lives of these individuals can only deepen our appreciation of the material at hand. The footnote presentation of their lives allows the reader to have immediate information at will, or to treat them as digressions, and access them later without significantly interfering with the main mathematical text at hand. The footnotes contain not only the bibliographical information cited above, but also historical data of interest, as well as other information which the discerning reader may want to explore at leisure.

There are optional topics, denoted by a pencil symbol, which add additional material for the more advanced reader or the reader requiring more challenging material which goes beyond the basics presented in the core data.

There are more than 80 examples throughout the text to illustrate the concepts presented, as well as in excess of 60 diagrams, figures, and tables.

Appendix A contains fundamental facts for the uninitiated reader or the reader requiring a quick finger-tip reference for a reminder of the underlying background used in the text. We begin with the basic notions surrounding set theory, binary relations and operations, functions, the basic laws of arithmetic, as well as notions surrounding divisibility including the Euclidean algorithm and its generalization, properties of the gcd and lcm, the fundamental theorem of arithmetic, the principle of induction, and properties of the binomial coefficient including the binomial theorem. Then we turn to some basic concepts in matrix theory, the fundamentals surrounding polynomials and polynomial rings (having already introduced the basic notions of groups, rings and fields in Section One of Chapter Two), morphisms of rings, vector spaces, and sequences. We close the appendix with fundamental concepts needed in the text concerning continued fractions.

For ease of search, the reader will find consecutive numbering, namely object N.m is the mth object in Chapter N (or Appendix N), exclusive of footnotes and exercises, which are numbered separately and consecutively unto themselves. Thus, for instance, Diagram 2.76 is the 76th numbered object in Chapter Two; exclusive of footnotes and exercises; Exercise 3.36 is the 36th exercise in Chapter Three; and Footnote 4.9 is the ninth footnote in Chapter Four.

The bibliography contains morethan 200 references for further reading.

The list of symbols is designed so that the reader may determine, at a glance, on which page the first defining occurrence of a desired notation exists, and the symbols are all contained on a single page.

The index has more than 2,400 entries, and has been devised in such a way to ensure that there is maximum ease in getting information from the text.

 Last updated: December 2, 2012