Cryptography Reference
In-Depth Information
−
product will have either 2
k
bits or 2
k
1 bits. If we want the modulus to have exactly
2
k
bits we can adopt several approaches, the simplest one being to check the length
of the modulus and to discard it in case it has 2
k
1 bits. Alternatively, once the first
prime
p
is chosen, the second prime may be chosen in the interval of the integers that
produce a 2
k
-bit integer when multiplied by
p
. We will discuss this in more detail
when presenting the implementation below.
Some years ago it was usual to choose the primes in such a way that they satisfied
some additional requirements and these primes were called 'strong primes'. The
rationale was to choose the primes so that the resulting modulus was not vulnerable
to certain factoring algorithms that are successful when the primes have some special
forms. For example, there is a factoring method due to Pollard, called the
p
−
1
method
, that is able to efficiently factor an RSA modulus
n
if one of its prime factors
p
is such that
p
−
1 has only 'small' prime factors. Thus the concept of 'strong prime'
includes the requirement that
p
−
1 has, at least, one large prime factor. However,
this requirement has lost significance in recent years due, on the one hand, to the
discovery of other factoring algorithms such as ECM that are more powerful than the
p
−
1 method and against which taking strong primes does not protect and, on the
other hand, to the realization that the probability that the randomly chosen primes
for an RSA modulus turn out not to be 'strong' is negligible in practice (see [165]
for a detailed discussion of these issues).
Another point that is sometimes raised in relation to RSA keys is that the two
primes should not be too close in order to prevent the factorization of the modulus
by Fermat's method. It is easy to make the key generation algorithm check whether
the primes are close but, again, when the RSA primes are chosen at random, it is
straightforward to see, taking into account the complexity of Fermat's method given
in Proposition 6.3, that the probability of being able to factor the modulus by this
method is negligible. Therefore, we shall be satisfied with just taking two pseudo-
randomly chosen primes.
The only other aspect of the key generation algorithm that deserves discussion is
how to choose the encryption exponent
e
. One possibility is to choose it at random in
Z
φ(
n
)
−
and hence
also to that of
n
) and has a negative effect on encryption speed. Thus choosing
e
small
seems a good choice because then encryption, which in plain RSA is just a modular
exponentiation with exponent
e
, requires fewer multiplications. Because of this, a
very popular choice for some time was
e
but this produces very large exponents (of size close to that of
φ(
n
)
=
3, requiring only two multiplications
∈ Z
φ(
n
)
(in this case
p
and
q
must be
). This
choice, however, lost popularity because of an attack against plain RSA with a small
encryption exponent that we shall later describe. Although this attack is not effective
against more secure variants of RSA, the exponent of choice is currently
e
≡
2
(
mod 3
)
in order to have 3
2
16
=
+
1
=
65537.
The exponent
e
2
16
1 has several advantages. On the one hand, it is prime
(actually a
Fermat prime
, i.e., a prime of the form 2
2
t
=
+
+
1) and hence it is very
likely that it is relatively prime to both
p
1 when primes
p
,
q
are
randomly chosen. More importantly, this value of
e
is very close to a power of 2 and
so modular exponentiation with this exponent is very fast, requiring only 17 modular
−
1 and
q
−
