Making, Breaking Codes: Introduction to Cryptology [Paperback]

Paul Garrett (Author)

Book Description

ISBN-10: 0130303690 | ISBN-13: 978-0130303691 | Publication Date: August 9, 2001 | Edition: 1

This unique book explains the basic issues of classical and modern cryptography, and provides a self contained essential mathematical background in number theory, abstract algebra, and probability—with surveys of relevant parts of complexity theory and other things. A user-friendly, down-to-earth tone presents concretely motivated introductions to these topics. More detailed chapter topics include simple ciphers; applying ideas from probability; substitutions, transpositions, permutations; modern symmetric ciphers; the integers; prime numbers; powers and roots modulo primes; powers and roots for composite moduli; weakly multiplicative functions; quadratic symbols, quadratic reciprocity; pseudoprimes; groups; sketches of protocols; rings, fields, polynomials; cyclotomic polynomials, primitive roots; pseudo-random number generators; proofs concerning pseudoprimality; factorization attacks finite fields; and elliptic curves. For personnel in computer security, system administration, and information systems.

Editorial Reviews

From the Inside Flap

Preface

This book is an introduction to modern ideas in cryptology and how to employ these ideas. It includes the relevant material on number theory, probability, and abstract algebra, in addition to descriptions of ideas about algorithms and complexity theory. Three somewhat different terms appear in the discussion of secure communications and related matters: cryptography, cryptanalysis, and cryptology. The first, cryptography, refers to writing using various methods to keep the message secret, as well as more modern applications of these methods. By contrast, cryptanalysis is the science of attacking ciphers, finding weaknesses, or possibly proving that there are none. Cryptology covers both, and is the most inclusive term.

In an introduction to cryptography, cryptanalysis, and cryptology that is more than just recreational, several things should be accomplished:

Provide some historical perspective. Specifically, we should see why the classical cipher systems fail by contemporary standards. Survey uses of cryptography. (It is not just for keeping secrets.) Introduce mathematics relevant to classical and modern cryptosystems. Give examples of types of hostile cryptanalytic attacks. Explain that key management and implementation details are fundamental.

Prerequisites here are minimal: the reader need only have the mathematical sophistication associated with having taken calculus and a bit of linear algebra.

We will first selectively review classical cryptology. This refers to the time prior to the 1940s. Some mechanical and primitive electronic devices were automated decryption/encryption and hostile cryptanalytic attacks, especially during 19351945, but these devices were slow, limited in their programmability, and not very portable. Part of the limitation was that they were fundamentally mechanical or electromechanical, rather than being 'software.'

By contemporary standards, the classical ciphers (prior to Enigma) definitively fail. This doesn't mean what one might think, though. It is much more than just the fact that contemporary computers are much better than the tube-based machines of the 1940s. Rather, it is now demanded that 'strong' ciphers be resistant to types of attacks which might have seemed irrelevant in the past.

One interesting idea that pervades both the classical and modern cryptanalysis and underlying mathematics is that of stochastic algorithm or probabilistic algorithm, by contrast to the more traditional and usual deterministic algorithms used in elementary mathematics. The point is that for many purposes there are algorithms that run much faster but with less than 100% chance of success, or, on the other hand, usually run fast, but not always. And this appears to be a fact of life, rather than just an artifact of our ignorance.

It must be noted that the advent of widely available high-speed computing machinery has drastically altered the landscape of cryptology. Simultaneously:

Encryption and (authorized) decryption can be automated, massive computation to perform encryption/decryption is enormously easier, and more elaborate systems become feasible. Storage, transfer, and manipulation of data on computer networks has sharply increased the need for effective encryption and related techniques. Cryptanalytic attacks have become commensurately easier. So issues which might have previously been viewed as of interest mostly to little kids (?) or spies (?) are now of quite general interest.

This is a subject in applied mathematics, since most of the mathematics we do will be motivated by application. The necessary mathematics will include some number theory, linear algebra, abstract algebra, probability theory, complexity theory, and other things. We can't pretend to be doing justice to these subjects, but will only provide an introduction with some concrete motivation. At the same time, we do not assume prior experience with any of these subjects.

There is also not enough space in a single book to pretend to give any sort of complete coverage of either historical developments or current developments in cryptology itself. What is possible is giving some representative and important examples and indicating other directions.

We will not be able to simulate full-scale real-life examples of contemporary issues, especially of cryptanalysis, because we do not have access to the right kind of computing machinery, and the actual simulations would take many hours or days in any case, with enormous memory usage. Ordinary computers can do encryptions and (authorized) decryptions very fast, but real-life attacks on today's cipher systems take days or months of computer time.

So at first we'll discuss some representative 'classical' cryptosystems, and the mathematics on which they are based, or which can be used to understand or break them. This is a good warm-up. Then, a little later, we'll describe a real symmetric encryption system in current use: DES ('Data Encryption Standard'). DES is considerably more complicated than the classical ciphers, and for good reason: much more is required of it. And, partly because of its success, it is not possible to say how to attack it successfully. A little more specifically: the fact that DES reveals very little mathematical structure is all in its favor, since this is what makes it less vulnerable to attack. DES has been the U.S. standard (for symmetric ciphers) since the mid-1970s, and has been used extensively outside the U.S. as well. Extensive analysis over 20 years has not found any fatal weakness in DES, but by now computers are so much faster than in 1976 that a brute-force attack is feasible. In fact, in mid-1998 the Electronic Frontier Foundation (EEF) spent $100,000 to construct a DES-cracker from off-the-shelf parts, which is able to obtain a DES key in about 2 days. Still, triple encryption by DES, reasonably enough called triple DES, seems to be secure for the foreseeable future. Nevertheless, the National Institute of Standards has called for submission of candidates for a new symmetric cipher with 128-bit block size. This contest is still going on now (mod-2000), and the winner will be known as the Advanced Encryption Standard (AES).

There is much more mathematical content in the discussion of the asymmetric ciphers (also called public-key ciphers). We will mostly discuss two sorts: the RSA system (Rivest, Shamir, Adleman), and the E1Gama1 system and its generalizations. RSA is simpler and more popular, but E1Gama1 lends itself better to generalizations such as elliptic carve ciphers. The security of RSA hinges on the apparent difficulty of factoring very large integers into primes. The security of the E1Gama1 system depends upon the difficulty of computing 'logarithms in finite fields.' (What this means exactly will be explained later.) And practical operation of either system depends upon generating a good supply of very large primes, which is an interesting problem in itself. As a further sample of asymmetric cipher, we briefly mention the NTRU cipher, which is newer and mathematically more sophisticated. In contrast to the symmetric systems, the more mathematical nature of the asymmetric systems does seem to make them naturally more vulnerable. There are important and subtle auxiliary mathematical issues in this part.

More specifically, after reviewing classical issues, we'll give an introduction to the application of number theory to contemporary cryptology, especially public-key ciphers such as RSA and ElGamal. This will introduce

public-key (asymmetric) ciphers pseudo-random-number generators (pRNGs) protocols

The necessary mathematics will include

results from number theory and abstract algebra primality testing, factorization, and related algorithms informal ideas from complexity theory

We won't do much with complexity theory except to keep rough track of the difficulty with which various computations can be performed, separating 'hard' from 'easy.'

The primality testing and factoring issues are fundamental for almost everything here. Many of the actual algorithms can be described in elementary terms, although the explanations for why they work at all usually require more preparation. But even without the explanation it is possible to experiment with these algorithms to get a feeling for their performance and accuracy.

A central underlying issue is the structure of integers-modulo-n, denoted Z/n (explained later), and generalizations of this. Especially we want to understand the differences in the nature of Z/n between for n composite and for n prime.

Randomization plays a very important role in some of the most efficient algorithms. For those of us accustomed to certainty in mathematics, this may be disconcerting, but it seems to be a necessary price to pay in many situations. The immediate goal is to motivate consideration of probabilistic primality tests such as Solovay-Strassen and Miller-Rabin, and prove that they work.

There is much more material here than could fit into a one-semester course, but in good conscience I couldn't have left anything out. A year-long course probably could go straight through and cover nearly everything.

I have used this material several times in a course that does not presume that students know any number theory, abstract algebra, probability, or cryptography. The mathematical topics are interwoven with cryptological applications in a style that is intended to provide adequate motivation for applications-minded people and interesting sidelights for theoretically-minded people. I've tried to make the different chapters maximally independent of each other to allow readers to skip topics that don't appear interesting to them without impairing the intelligibility of subsequent writing. In some cases this required that I repeat some small discussions of technical points because I could not be sure that the reader would have seen the earlier discussion. From a pedagogical viewpoint a modest amount of repetition is probably a good thing anyway.

A one-semester course in number theory could use this text, with the cryptographic and computational parts skipped but left as optional reading. There is more abstract algebra included than here in some traditional number theory courses. When I've taught traditional undergraduate number theory courses I always faced the choice between pretending to do number theory without abstract algebra, requiring abstract algebra as prerequisite, or developing some abstract algebra as motivated by number theory. The latter (somewhat non-traditional) choice has been my choice, but there are few texts that hit that mark. Some parts of the present text are an outgrowth of notes I've written for undergraduate courses in which I coordinated number theory and abstract algebra, using number theory as a tangible entry point to algebra and as a beneficiary of basic results from it. Thus, a one-semester course in number theory could skip over the first six chapters on classical ciphers and probability, and also skip the chapter on the Hill ciphers. The chapter on public-key ciphers could be skipped, but this is one of the chief applications of mathematics to communication.

A short introductory course in cryptography could use this text, with much of the more serious mathematical sections omitted. To make this feasible, I've tried to write about the mathematical aspects in a manner that is intelligible from both relatively elementary and relatively high-level viewpoints. In some cases this means that I've given both an elementary proof of a special case and a more elegant higher-level proof of a more general case. Since this is probably good educational strategy anyway, I don't feel bad about spending the time and space. At the same time, a common limitation of more serious cryptography texts is that the relevant mathematics is given short shrift. A related common limitation is that the reader is assumed to have already reached a high level of mathematical sophistication. By contrast, here I've attempted to require as little as possibly, while still providing appropriate resources for the cryptography student who wants to see how the underlying mathematics works. Thus, a short introductory course in cryptography could simply proceed straight through the text and stop when time ran out. In some sense this is the most natural use of this material.

A course in computational number theory could focus on the algorithms, and soft-pedal the cryptography and the more theoretical mathematical parts. In the classes I've taught from this material I have not assumed that students are able to or want to do computer work of any sort, but of course the material begs for CPU time! My descriptions of the algorithms are intended to be fairly clear, but I've not written out pseudo-code or specific language implementations of the algorithms. One reason for this is that I want students to think about what the algorithms are doing, at least a little, rather than just to execute them. Another reason for not writing out algorithms in a proprietary language is that I am disinclined to implicitly endorse a language and all it entails. And, while I strongly favor students' learning how to write programs, I don't encourage them to study software packages. Still, friendly-interface software packages do provide an easy entry to computing.

In courses for students who have already seen some probability or number theory the corresponding chapters and sections can be skipped. In structuring the text I have incorporated necessary material into the text itself rather than relegating it to appendices. This allows a knowledgeable reader to skip over material while not requiring that everyone else flip back and forth to appendices. Such integration of the material better shows the logical dependencies, too.

I thank the reviewers of the manuscript for their constructive criticism and for their positive responses to some of my non-standard stylistic choices: Professors Irvin Roy Hentzel, Iowa State University; Yangbo Ye, University of Iowa, Iowa City; Joachim Rosenthal, U. of Notre Dame; Daniel Lieman, U. of Missouri, Columbia; Jonathan Hall, Michigan State University. My students in the last few years deserve thanks for tolerating half-baked versions of this text, making helpful suggestions, and finding many errors, hopefully making the reviewers' job less gruesome than it might have been otherwise.

Paul Garrett
University of Minnesota, Minneapolis
[e-mail]
paul.garrett@acm
math.umn/~garrett/

From the Back Cover

This unique book explains the basic issues of classical and modern cryptography, and provides a self contained essential mathematical background in number theory, abstract algebra, and probability—with surveys of relevant parts of complexity theory and other things. A user-friendly, down-to-earth tone presents concretely motivated introductions to these topics. More detailed chapter topics include simple ciphers; applying ideas from probability; substitutions, transpositions, permutations; modern symmetric ciphers; the integers; prime numbers; powers and roots modulo primes; powers and roots for composite moduli; weakly multiplicative functions; quadratic symbols, quadratic reciprocity; pseudoprimes; groups; sketches of protocols; rings, fields, polynomials; cyclotomic polynomials, primitive roots; pseudo-random number generators; proofs concerning pseudoprimality; factorization attacks finite fields; and elliptic curves. For personnel in computer security, system administration, and information systems.

See all Editorial Reviews

Product Details

• Paperback: 483 pages
• Publisher: Prentice Hall; 1 edition (August 9, 2001)
• Language: English
• ISBN-10: 0130303690
• ISBN-13: 978-0130303691
• Product Dimensions: 9.3 x 7 x 1.1 inches
• Shipping Weight: 2.2 pounds (View shipping rates and policies)
• Average Customer Review: 4.3 out of 5 stars  See all reviews (11 customer reviews)
• Amazon Best Sellers Rank: #293,514 in Books (See Top 100 in Books)
  • #60 in Books > Computers & Technology > Programming > Algorithms > Cryptography
  • #90 in Books > Computers & Technology > Microsoft > Word Processing

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

21 of 21 people found the following review helpful:

5.0 out of 5 stars A great book for anyone just starting to learn about codes, August 27, 2000

By A Customer

This review is from: Making, Breaking Codes: Introduction to Cryptology (Paperback)

This book is great for anyone just starting to learn about cryptology. It doesn't expect you to understand large amounts of mathematics, and goes through the necessary mathematics to understand the subject and problems presented. Additionally, this book has an answer key for selected problems (not just a few, but many problems), which makes it great for the person wanting to teach themselves the subject at their own pace. Also, it makes for a good reference for the person already familiar with cryptology. Finally, it is a great book for the experienced mathematician that wants to see modern/abstract algebra applied to a modern day subject.

6 of 6 people found the following review helpful:

4.0 out of 5 stars A good approach, February 23, 2003

By 

L.W.H (Dallas, TX USA) - See all my reviews

This review is from: Making, Breaking Codes: Introduction to Cryptology (Paperback)

This is a math book. It tells you cryptography-related abstract algebra, number theory, etc. The good thing is it doesn't assume you have much math background.

On the other hand, it has a lot of errors. Some are just typos, some not. Personally, I think if a math book has a single math error (wrong lemma, incorrect logic, ...), it is not a qualified math book. Unfortunately, this book has more than one.

The reason I still give it four stars is that I like its approach. Without math, cryptography is not cryptography. If you don't have enough math background, this book really helps you get started. There are simply not many choices on the market of this kind. After reading this, you can go to more rigorous, advanced ones, such as Koblitz's series. An alternative (more rigorous, less abstract algebra) is Bauer's. All Koblitz's and Bauer's are excellent.

2 of 2 people found the following review helpful:

5.0 out of 5 stars Actually 4.6, April 26, 2003

By 

rob (Cedar, MN United States) - See all my reviews

This review is from: Making, Breaking Codes: Introduction to Cryptology (Paperback)

I like the book quite a bit because of the actual down-to-earth language Garrett uses. It is very nice since I'm using it on my own time. There some errors in the book, however. He also selects only about 25% of the questions to anwer in the key. He could show about 50% and give an explanation on how to find the answer. Other than that, there is nothing wrong with the book and those problems shouldn't keep you from buying it.