How is probability theory used in cryptography

reading corner

Introduction to cryptography

Johannes Buchmann
Springer textbook, Springer-Verlag Berlin-Heidelberg-New York 1999, pp.229, 49.90 DM
2nd ext. Ed., Springer-Verlag, Berlin, Heidelberg, New York, 2001, 231 pages, € 27.52
Springer, 2010, 304 pages, 5th edition, 32.99

ISBN: 3-540-66059-3
ISBN: 3-540-41283-2
ISBN: 3-642-11185-8

Then come the Reviews of: H. Meyn (1st ed.), J. Apel(2nd ed.) AndE. Behrends

Review of the 1st edition

The book contains the following sections: Whole Numbers - Congruences and Residual Class Rings - Encryption - Probability and Perfect Security - The DES Algorithm - Prime Number Generation - Public-Key Encryption - Factorization - Discrete Logarithms - Cryptographic Hash Functions - Digital Signatures - Other Groups - Identification - Public key infrastructures.

From the foreword: “In this book, I am addressing readers who want to get to know modern cryptographic techniques and their mathematical foundations, but who do not have the corresponding specialist knowledge of mathematics. My goal is to introduce you to the basic techniques of modern cryptography. Although I require a previous mathematical education, I introduce you to the basics of linear algebra, algebra, number theory and probability theory, insofar as these areas are relevant for the cryptographic processes discussed. "

The author has succeeded in meeting this objective. All the concepts required to understand modern crytopraphic techniques are explained in very clear language and, if possible, illustrated with small examples. Particular emphasis is placed on the description of the underlying ideas. The author restricts himself to the presentation of those mathematical aids, the proof of which does not require more than one printed page. The result is a text that is highly legible.

The exercises (with solutions) are exactly based on the text. In addition to tasks that require a rethinking of the arguments and proofs presented in the text, there are many that ask the reader to try out the techniques presented on moderately large examples with the help of a computer algebra system.

(The LiDIA program library mentioned in the book can be found at http://www.informatik.tu-darmstadt.de/TI/LiDIA/.)

The book has a sufficiently detailed subject index and a bibliography in which, among other things, all important, advanced works on modern cryptography can be found.

Again from the foreword: “It is necessary for the user to be able to assess whether the cryptographic methods used are efficient and secure enough. To do this, they not only have to know how the cryptographic processes work, they also have to understand their mathematical principles. "
This is to the heart of all who want to turn to the practical side of cryptography!

An instructive and inexpensive book.

Review: H. Meyn (Erlangen) from Computeralgebra-Rundbrief, No. 27 - October 2000


Reviews of the 2nd editione

This book from the Springer textbook series, originally published in 1999 and now in its 2nd edition, deals with modern cryptographic procedures with special consideration of the mathematical backgrounds.

The book is divided into 14 chapters, eight of which are devoted to the description and discussion of cryptographic processes and applications based on them, and the remaining six provide introductions to the number-theoretical and algorithmic backgrounds of the processes and the attacks on them.

In the first two chapters (1. whole numbers, 2. congruences and remainder classes) the necessary elementary number theoretic terms and theorems are provided. In addition, there is a brief introduction to the complexity considerations and notations, which are extremely important for the quality assessment of cryptographic procedures and attacks.

Chapter 3 (Encryption) gives an introduction to the problem of cryptography, shows the essential differences between symmetrical and asymmetrical cryptosystems, describes a number of classic symmetrical encryption methods and goes into the various operating modes of block ciphers.

Chapter 4 (Probability and perfect security) provides some terms of the calculus of probability and on this basis formulates the requirements that must be made of a perfectly secure cryptosystem. The generation of (pseudo-) random number sequences, which is an essential prerequisite for the practical implementation of (almost) perfect security, is also discussed. In the fifth chapter (The DES algorithm) the most famous and at the same time most controversial modern symmetrical cryptosystem is described and analyzed.

Before the best-known asymmetric cryptosystems (RSA, Rabin encryption method, Diffie-Hellman key exchange, ElGamal) are presented and discussed in Chapter 7 (Public-Key Encryption), Chapter 6 (Generation of Prime Numbers) provides a series of prime number tests. The fast methods for generating prime numbers based on this play a key role in the implementation of asymmetric cryptosystems. The following two chapters (8th factorization, 9th discrete logarithms) deal with efficient methods for calculating the two one-way functions most frequently used in public key systems. Such methods are important tools for cryptanalysis, which means that they are of decisive importance for the quality assessment of cryptosystems. Asymmetric cryptosystems like ElGamal, whose security is based on the difficulty of calculating discrete logarithms, allow the use of elliptic curves or any finite fields instead of finite prime fields. The mathematical background of these variants is examined in Chapter 12 (Other Groups).

Finally, chapters 10 (cryptographic hash functions), 11 (digital signatures) as well as 13 (identification) and 14 (public key infrastructures) deal with a selection of application problems that can be solved on the basis of cryptographic methods.

Each chapter ends with a series of exercises. A list of the solutions can be found at the end of the book.

The book is aimed primarily at readers who want to understand how cryptographic processes and attacks work. The author does not require any special prior knowledge of the reader, as the necessary mathematical apparatus is developed in the book itself. For those interested in instructions for the efficient implementation of special procedures, it should be noted that the handling of implementation questions would have gone beyond the scope of the book and was therefore not one of Buchmann's main concerns.

From my own experience, I can warmly recommend the book as a textbook for an introductory lecture for students in the main course in theoretical computer science or mathematics in the field of cryptography. It is also ideal for students or academics to familiarize themselves with the subject of cryptography.

Review: Joachim Apel (Leipzig) from Computeralgebra-Rundbrief, No. 30 - March 2002


Soon after its beginnings, cryptography - the science of encryption and decryption - was put on a mathematical basis, and very complex processes have been used for a long time.

The book is written with the aim of introducing the mathematics on which the processes that are important today are based and describing the most important current aspects: RSA, hash functions, digital signatures, zero-knowledge evidence. This claim is fulfilled, there is probably no other book in recent times that offers such a wealth of information with simultaneous mathematical precision.

It is not quite so clear that - as can be read in the foreword - the book can be read without special mathematical knowledge. Strictly speaking, that's certainly true, but it's actually written too compactly for laypeople.

It can be recommended to everyone who has already been introduced to the language of mathematics before reading the book. (E.g. students of mathematics, natural and engineering sciences and computer science; and of course all resilient high school students.)

(Review: Ehrhard Behrends)

 

Details
Category: Reading corner