Introduction to cryptography. (Vvedenie v kriptografiyu). Izd. 3, ispravl (Q2701797)

The book represents an introductory text surveying basic notions and results of cryptology as well as an outline of some research topics in the area. It is organized as follows. First, prefaces to this edition as well as previous ones are given, outlining the book as the first systematic introductory material to cryptography in Russian language. Then, seven chapters provide background information on the basics of cryptography and some related areas. These chapters were written by different authors and are to a certain extent independent of each other. An Appendix contains a part of Shannon's seminal paper on the theory of secrecy systems translated into Russian language. NEWLINENEWLINENEWLINEChapter 1 provides cryptographic background. Here in a short introduction first the problem of secret communication is stated and basic approaches to its solution (trusted channel, steganography, cryptography) are discussed. Then basic cryptographic notions are introduced, including a discussion on basic types of attacks. Notions like one-way function, one-way trapdoor function, symmetric and asymmetric cryptosystems as well as key exchange protocol, interactive proof system, and zero-knowledge protocols are briefly mentioned as well. NEWLINENEWLINENEWLINEChapter 2 bears the title ``Cryptography and complexity theory''. After an introduction there are four sections dealing with the relations between cryptography and the P = NP? problem, one-way functions, pseudorandom generators and zero-knowledge proofs. A few basic definitions and theorems are given here together with references to seminal works on these topics. NEWLINENEWLINENEWLINEChapter 3 deals with cryptographic protocols. After a brief introduction authentication protocols and signature schemes are introduced and fundamental requirements discussed. The author then presents the notions of untraceability and digital cash followed by ``coin flipping over phone''. The chapter ends with sections devoted to secret sharing protocols, voting schemes, and perfectly secure message transmissions. NEWLINENEWLINENEWLINEChapter 4 is devoted to the basics of algorithmic number theory. RSA is explained here, followed by a section on complexity of some number-theoretic algorithms. Then, primality testing, construction of large primes and factorization problems are outlined and discussed. The chapter ends with a section devoted to discrete logarithms. NEWLINENEWLINENEWLINEChapter 5 introduces the notion of secret sharing schemes. Threshold secret sharing schemes and ideal secret sharing schemes and their relation to matroids are briefly explained. NEWLINENEWLINENEWLINEThe title of Chapter 6 is ``Computer and cryptography''. Here some fundamental practical recommendations for those writing their first encryption/decryption software are outlined and briefly discussed. Also such useful topics as sources of randomness in a computer or considerations on cryptanalysis of a simple cipher are discussed here. NEWLINENEWLINENEWLINEThe content of the last Chapter 7 is closely related to the regular competitions in cryptography and mathematics organized in Russian schools since 1991. The authors devoted the whole chapter to an effort to facilitate the preparation for such competitions. First, an elementary introduction to cryptography is given. Here, examples from well-known writings like those of E. A. Poe, A. C. Doyle, and J. Verne are used to explain principles of substitution and transposition ciphers and their cryptanalysis. The introduction to cryptography ends with a section on polyalphabetic ciphers. Then, a collection of problems used in previous competitions is presented together with their solutions and explanations.