6. Algorithmic Number Theory for Cryptography and Cryptanalysis: Primality, Factoring and Discrete Logarithms

In the previous chapters we have introduced the most important aspects of private-key cryptography and we have noticed that prime numbers underlie many of the constructions and algorithms discussed. Also, computational number-theoretic problems which are presumed to be hard made their appearance and we mentioned, in particular, the integer factorization problem and the discrete logarithm problem. In the coming chapters we will study publickey cryptography and we will see that all these aspects play a relevant role in this setting. In fact, number theory and, in particular, presumedly hard number-theoretic problems such as the ones just mentioned, are of central importance for public-key cryptography because the security of most public-key schemes relies on the hardness of some of these problems. The study of the known algorithms to solve these hard problems can thus be seen as a form of cryptanalysis and, as such, is an indispensable complement to cryptography and a prerequisite for the practical evaluation of the security of public-key schemes in order to establish, for example, the key sizes that should be used. Thus we devote this chapter to the aspects of algorithmic number theory which are most relevant to public-key cryptographic schemes.