Probabilistic and statistical methods in cryptology. An introduction by selected topics. (Q1889969): Difference between revisions

This is an introductory text devoted to the stochastic approach to the cryptology. The author selects various results and techniques to cover several important aspects of the standard and contemporary cryptology and cryptanalysis. The first chapter gives a short introduction to classical attacks on polyalphabetic substitution cipher. The second one is devoted to RSA. Besides the basic description of the RSA method and two well-known probabilistic tests for primality (Solovay-Strassen and Rabin), the reader finds here the information about connections between a probabilistic polynomial time algorithm for calculation of the last significant bit of the plaintext from the public key and the ciphertext and a probabilistic polynomial time algorithm for recognition of the whole plaintext from these data. The main ideas of ``timing attacks'' in careless hardware implementations are also outlined. The title of chapter 3 ``Factorization with quantum computers: Shor's algorithm'' describes its contents. Three further chapters of the book are devoted to various aspects of generation of random numbers (physical random number or pseudo--random number generators) and one how to test such generators. One chapter serves as a brief introduction to basic results of information theory. The short chapter ``Algorithmic complexity'' is based on the Turing-Kolmogorov-Chaitin complexity and it is shown here that this type of complexity and the linear complexity are asymptotically the same. One chapter discusses the distribution of the public keys in the Diffie-Hellman system, and it is shown here that if the modulus is a strong prime then the entropy of the key is practically maximum possible. The remaining three chapters address differential cryptanalysis, semantic security and the meet-in-the middle attack. The final short (one and half page) chapter describes the most fundamental idea of the quantum cryptography. The book is worth reading and is written in a clear and lucid style, but the neophyte in the subject could face the problem that some fundamental (though standard) concepts and notions (e.g. from statistics and probability theory) used in the book are not defined here and therefore require a search in additional sources. On the other side, the book provides enough bibliographical information for further reading.