Douglas Stinson - Cryptography, Theory and Practice

Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95

Preface

My objective in writing this book was to produce a general, comprehensive textbook that treats all the essential core areas of cryptography. Although many books and monographs on cryptography have been written in recent years, the majority of them tend to address specialized areas of cryptography. On the other hand, many of the existing general textbooks have become out-of-date due to the rapid expansion of research in cryptography in the past 15 years.

I have taught a graduate level cryptography course at the University of Nebraska-Lincoln to computer science students, but I am aware that cryptography courses are offered at both the undergraduate and graduate levels in mathematics, computer science and electrical engineering departments. Thus, I tried to design the book to be flexible enough to be useful in a wide variety of approaches to the subject.

Of course there are difficulties in trying to appeal to such a wide audience. But basically, I tried to do things in moderation. I have provided a reasonable amount of mathematical background where it is needed. I have attempted to give informal descriptions of the various cryptosystems, along with more precise pseudo-code descriptions, since I feel that the two approaches reinforce each other. As well, there are many examples to illustrate the workings of the algorithms. And in every case I try to explain the mathematical underpinnings; I believe that it is impossible to really understand how a cryptosystem works without understanding the underlying mathematical theory.

The book is organized into three parts. The first part, Chapters 1-3, covers private-key cryptography. Chapters 49 concern the main topics in public-key cryptography. The remaining four chapters provide introductions to four active research areas in cryptography.

The first part consists of the following material: Chapter 1 is a fairly elementary introduction to simple classical cryptosystems. Chapter 2 covers the main elements of Shannons approach to cryptography, including the concept of perfect secrecy and the use of information theory in cryptography. Chapter 3 is a lengthy discussion of the Data Encryption Standard ; it includes a treatment of differential cryptanalysis.

The second part contains the following material: Chapter 4 concerns the RSA Public-key Cryptosystem , together with a considerable amount of background on number-theoretic topics such as primality testing and factoring. Chapter 5 discusses some other public-key systems, the most important being the ElGamal System based on discrete logarithms. Chapter 6 deals with signature schemes, such as the Digital Signature Standard , and includes treatment of special types of signature schemes such as undeniable and fail-stop signature schemes. The subject of Chapter 7 is hash functions. Chapter 8 provides an overview of the numerous approaches to key distribution and key agreement protocols. Finally, Chapter 9 describes identification schemes.

The third part contains chapters on selected research-oriented topics, namely, authentication codes, secret sharing schemes, pseudo-random number generation, and zero-knowledge proofs.

Thus, I have attempted to be quite comprehensive in the core areas of cryptography, as well as to provide some more advanced chapters on specific research areas. Within any given area, however, I try to pick a few representative systems and discuss them in a reasonable amount of depth. Thus my coverage of cryptography is in no way encyclopedic.

Certainly there is much more material in this book than can be covered in one (or even two) semesters. But I hope that it should be possible to base several different types of courses on this book. An introductory course could cover Chapter 1, together with selected sections of Chapters 25. A second or graduate course could cover these chapters in a more complete fashion, as well as material from Chapters 69. Further, I think that any of the chapters would be a suitable basis for a topics course that might delve into specific areas more deeply.

But aside from its primary purpose as a textbook, I hope that researchers and practitioners in cryptography will find it useful in providing an introduction to specific areas with which they might not be familiar. With this in mind, I have tried to provide references to the literature for further reading on many of the topics discussed.

One of the most difficult things about writing this book was deciding how much mathematical background to include. Cryptography is a broad subject, and it requires knowledge of several areas of mathematics, including number theory, groups, rings and fields, linear algebra, probability and information theory. As well, some familiarity with computational complexity, algorithms and NP-completeness theory is useful. I have tried not to assume too much mathematical background, and thus I develop mathematical tools as they are needed, for the most part. But it would certainly be helpful for the reader to have some familiarity with basic linear algebra and modular arithmetic. On the other hand, a more specialized topic, such as the concept of entropy from information theory, is introduced from scratch.

I should also apologize to anyone who does not agree with the phrase Theory and Practice in the title. I admit that the book is more theory than practice. What I mean by this phrase is that I have tried to select the material to be included in the book both on the basis of theoretical interest and practical importance. So, I may include systems that are not of practical use if they are mathematically elegant or illustrate an important concept or technique. But, on the other hand, I do describe the most important systems that are used in practice, e.g., DES and other U. S. cryptographic standards.

I would like to thank the many people who provided encouragement while I wrote this book, pointed out typos and errors, and gave me useful suggestions on material to include and how various topics should be treated. In particular, I would like to convey my thanks to Mustafa Atici, Mihir Bellare, Bob Blakley, Carlo Blundo, Gilles Brassard, Daniel Ducharme, Mike Dvorsky, Luiz Frota-Mattos, David Klarner, Don Kreher, Keith Martin, Vaclav Matyas, Alfred Menezes, Luke O'Connor, William Read, Phil Rogaway, Paul Van Oorschot, Scott Vanstone, Johan van Tilburg, Marc Vauclair and Mike Wiener. Thanks also to Mike Dvorsky for helping me prepare the index.

Douglas R. Stinson

The CRC Press Series on Discrete Mathematics and Its Applications

Discrete mathematics is becoming increasingly applied to computer science, engineering, the physical sciences, the natural sciences, and the social sciences. Moreover, there has also been an explosion of research in discrete mathematics in the past two decades. Both trends have produced a need for many types of information for people who use or study this part of the mathematical sciences. The CRC Press Series on Discrete Mathematics and Its Applications is designed to meet the needs of practitioners, students, and researchers for information in discrete mathematics. The series includes handbooks and other reference books, advanced textbooks, and selected monographs. Among the areas of discrete mathematics addressed by the series are logic, set theory, number theory, combinatorics, discrete probability theory, graph theory, algebra, linear algebra, coding theory, cryptology, discrete optimization, theoretical computer science, algorithmics, and computational geometry.

Kenneth H. Rosen, Series Editor
Distinguished Member of Technical Staff
AT&T Bell Laboratories