Modern cryptography. Volume 1. A classical introduction to informational and mathematical principle (Q2122572)

The present book is a textbook of theoretical cryptography suitable for senior students in mathematics, compulsory for cryptography and science, and engineering postgraduates. It deals with information theory, the statistical characteristics of cryptosystems, and the computational complexity of cryptographic algorithms, and discusses several important public-key cryptosystems. It emphasises the mathematical principles behind various cryptographic and authentication schemes. The book contains seven chapters. The first chapter presents some preliminary knowledge. Basic facts about maps are recalled, and the computational complexity of an algorithm that receives as input integers is introduced. Furthermore, Jensen inequality and the Stirling formula are presented. Finally, the \(n\)-fold Bernoulli experiment, Chebyshev inequality, and stochastic process are discussed. The second chapter is devoted to code theory. Its goal is to give an introduction of the theory of error-correcting codes. It includes Hamming distance, Lee distance, linear codes, some typical good codes, and Mac Williams and Shannon theorems. The third chapter presents Shannon's theory. The information space, the entropy, the redundancy, the Markov space, and the source coding theorem are discussed. Furthermore, the optimal code theory is investigated and several examples of compressing codes are given. Finally, Shannon's channel coding theorem is proved. Cryptography is the topic of the fourth chapter. It gives an introduction to Shannon's ideas and results in cryptography, and in public key cryptography. First, it deals with the statistical characteristic of cryptosystems, fully confidential systems, and ideal security systems. Further, the message authentication systems and the forgery and substitute attacks are discussed. Moreover, some classical encryption algorithms and the public-key cryptosystems RSA, ElGamal scheme, and knapsack scheme are described. In the fifth chapter, the primality tests, which are necessary for the construction of a wide class of public key cryptosystems, are presented. The Fermat and Euler tests are described and the Monte Carlo method is introduced. Furthermore, the factor basis method and the continuous fraction method are given. The important topic of elliptic curves is introduced in the sixth chapter. The basic theory is presented and some classical public key cryptosystems based on elliptic curves are discussed. Finally, the elliptic curve factorisation method is described. The last chapter contains classical results on lattices and their applications in public-key cryptography. It gives an introduction to the geometry of numbers and discusses the basic properties of lattices. Furthermore, it studies the reduced bases and the LLL algorithm and presents approximation algorithms for the shortest vector problem and the closest vector problem. Finally, the GGH/HNF cryptosystem, the NTRU cryptosystem, the McEliece/Niederreiter cryptosystem, and the Ajtai/Dwork cryptosystem are presented.