Cryptography Reference
In-Depth Information
The RSA public key cryptosystem is based on the RSA family of trapdoor
permutations as overviewed and discussed in Section 7.2.2. Contrary to many other
public key cryptosystems, RSA yields both an asymmetric encryption system and a
DSS. This means that basically the same set of algorithms can be used to encrypt and
decrypt messages, as well as to digitally sign messages and verify digital signatures
accordingly. The function provided actually depends on the cryptographic key in
use.
•
If the recipient's public key is used to encrypt a plaintext message, then the
RSA public key cryptosystem yields an asymmetric encryption system. In this
case, the recipient's private key must be used to decrypt the ciphertext.
•
If the sender's private key is used to encrypt a plaintext message (or a hash
value thereof), then the RSA key cryptosystem yields a DSS. In this case, the
sender's public key must be used to verify the digital signature.
In this chapter, we only look at the RSA asymmetric encryption system. The
RSA DSS is addressed in Section 15.2.1.
14.2.1.1
Key Generation Algorithm
Before the RSA asymmetric encryption system can be employed, the
Generate
algorithm must be used to generate a public key pair. The algorithm is probabilistic
in nature. It takes as input a security parameter (that represents the bit length of the
RSA modulus), and it generates as output a public key pair. It consists of two steps:
First, the algorithm randomly selects
4
two prime numbers
p
and
q
of roughly
the same size and computes the RSA modulus
n
=
pq
. Given the current
state of the art in integer factorization, a modulus size of 1,024 or 2,024 bits
is appropriate and recommended. This means that both primes must be about
512 or 1,024 bits long.
•
•
Second, the algorithm randomly selects an integer 1
<e<φ
(
n
) with
gcd
(
e, φ
(
n
)) = 1,
5
and computes another integer 1
<d<φ
(
n
) with
4
It is not possible to randomly select large primes (from the set of all prime numbers
P
). Instead,
large integers are randomly chosen and probabilistic primality testing algorithms are then used to
decide whether these integers are prime (see Section 3.2.4.3).
5
Note that
e
must be odd and greater than 2 (it is not possible to set
e
=2, because
φ
(
n
)=
(
p −
1)(
q −
1) is even and
gcd
(
e, φ
(
n
)) = 1 must hold) and that the smallest possible value for
e
is 3. The use of
e
=3should be considered with care, because a corresponding implementation
may be subject to a low exponent attack, as mentioned in Section 14.2.1.4.
