Cryptography Reference
In-Depth Information
Chapter 6
Algorithmic Number Theory for Cryptography
and Cryptanalysis: Primality, Factoring
and Discrete Logarithms
In the preceding 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 men-
tioned, in particular, the integer factorization problem, which was briefly discussed in
we will study public-key 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 impor-
tance 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. Therefore, before going on to discuss public-
key cryptographic schemes, we are going to dedicate this chapter to the aspects of
algorithmic number theory which are most relevant to these schemes.
6.1 Large Primes and How to Find Them
We have seen that prime numbers play an important role in some cryptographic
constructions like the Blum-Blum-Shub generator. We will see later on that prime
numbers are also crucial for many other schemes and protocols used in public-key
cryptography, the usual requirements for these primes being that they should be large
(such as, for example, the 1024-bit primes we have used in some of our examples)
and that they should be randomly chosen among the primes of suitable size. How to
do this is far from obvious and a key aspect which will make this task possible is
that, in some sense that will be made precise later on, primes are 'abundant', which
makes them easy to find but difficult to guess.
