Cryptography Reference
In-Depth Information
We may conclude that an RSA key should possess no fewer than 1024 binary
digits if it is to provide a comfortable margin of safety for critical applications.
We may conclude as well, however, that successes in factorization are gradually
approaching this value, and one must keep careful tabs on developments. It
is therefore worthwhile to distinguish different application purposes and for
sensitive applications to consider using 2048 or more binary digits (cf. [Schn],
Chapter 7, and [RegT], Appendix 1.4).
7
With the FLINT/C package we are well
equipped to produce such key lengths. We need not be too concerned that the
expense of factorization decreases in proportion to the speed of new hardware,
since this same hardware allows us to create longer keys as required. The security
of the RSA algorithm can thus always be ensured by keeping sufficiently ahead of
the progress in factorization.
How many such keys are available? Are there enough so that every man,
woman, and child on the planet (and perhaps even their pet cats and dogs) can be
provided one or more RSA keys? To this the prime number theorem provides the
answer, according to which the number of prime numbers less than an integer
x
is
asymptotically approximated by
x/
ln
x
(cf. page 220): Moduli of length 1024 bits
are generated as products of two prime numbers each of length approximately
512 bits. There are about
2
512
/
512
such primes, that is, about
10
151
,eachpairof
which forms a modulus. If we let
N
=10
151
,thenthereare
N
(
N −
1)
/
2
such
pairs, which comes to about
10
300
different moduli for which additionally that
number again can be chosen for secret key components. This overwhelmingly
large number is difficult to grasp, but consider, for example, that the entire visible
universe contains “only” about
10
80
elementary particles (cf. [Saga], Chapter 9).
To put it another way, if every person on Earth were given ten new moduli every
day, then the process could continue for
10
287
years without a modulus being
reused, and to date Earth has existed “only” a few billion years.
Finally, that an arbitrary text can be represented as a positive integer is
obvious: By associating a unique integer to each letter of an alphabet texts can
be interpreted in any number of ways as integers. A common example is the
numerical representation of characters via ASCII code. An ASCII-encoded text
can be turned into a single integer by considering the code value of an individual
character as a digit to base 256. The probability that such a process would result
in an integer
M
for which
gcd(
M, n
)
>
1
, that is, such that
M
contains as a
factor one of the factors
p
,
q
,ofanRSAkey
n
, is vanishingly small. If
M
is too
large for the modulus
n
of an RSA key, that is, larger than
n
1
, then the text can
be divided into blocks whose numerical representations
M
1
,M
2
,M
3
,...
all are
less than
n
. These blocks must then be individually encrypted.
For texts of considerable length this becomes tiresome, and therefore one
seldom uses the RSA algorithm for the encryption of long texts. For this purpose
−
7
It is useful to choose RSA keys of binary length a multiple of 8, in conformity with the
convention that such keys should end at the end of a byte.
