Cryptography Reference
In-Depth Information
cards, e.g., for banking applications, which are only equipped with a small micro-
processor. Here, digital signing is often needed, which involves the secret key
d
.By
applying the CRT for signature computation, the smart card is four times as fast.
For example, if a regular 1024-bit RSA exponentiation takes 3 sec, using the CRT
reduces that time to 0.75 sec. This acceleration might make the difference between a
product with high customer acceptance (0.75 sec) and a product with a delay that is
not acceptable for many applications (3 sec). This example is a good demonstration
how basic number theory can have direct impact in the real world.
7.6 Finding Large Primes
There is one important practical aspect of RSA which we have not discussed yet:
generating the primes
p
and
q
in Step 1 of the key generation. Since their product
is the RSA modulus
n
=
p
q
, the two primes should have about half the bit length
of
n
. For instance, if we want to set up RSA with a modulus of length
ยท
=
1024,
p
and
q
should have a bit length of about 512 bit. The general approach is
to generate integers at random which are then checked for primality, as depicted in
Fig. 7.2, where RNG stands for random number generator. The RNG should be non
predictable because if an attacker can compute or guess one of the two primes, RSA
can be broken easily as we will see later in this chapter.
log
2
n
Fig. 7.2
Principal approach to generating primes for RSA
In order to make this approach work, we have to answer two questions:
1. How many random integers do we have to test before we have a prime? (If the
likelihood of a prime is too small, it might take too long.)
2. How fast can we check whether a random integer is prime? (Again, if the test is
too slow, the approach is impractical.)
It turns out that both steps are reasonably fast, as is discussed in the following.
7.6.1 How Common Are Primes?
Now we'll answer the question whether the likelihood that a randomly picked inte-
ger
p
is a prime is sufficiently high. We know from looking at the first few positive
