- 5
1.2 The RSA algorithm
The RSA algorithm was invented by Ronald L. Rivest, Adi Shamir, and Leonard Adleman in 1977.
The security of the algorithm is based on the hardness of factoring a large composite number and
computing e
th
roots modulo a composite number for a specified odd integer e.
An RSA public key consists of a pair (n, e) of integers, where n is the modulus and e is the public
exponent. The modulus n is a large composite number (a bit length of at least 1024 is the current
recommended size), while the public exponent e is normally a small prime such as 3, 17, or 65537.
In this specification, the modulus is the product of two distinct primes. For a discussion of the case
of three or more prime factors (so-called ‘‘multi-prime’’ RSA), see Appendix A at the end of this
document.
An RSA private key may have one of two different representations. Both representations contain
information about an integer d satisfying
(x
e
)
d
≡ x (mod n)
for all integers x. This means that the private key can be used to solve the equation
x
e
≡ c (mod n)
in x, i.e., compute the e
th
root of c modulo n.
The RSA encryption primitive RSAEP takes as input the public key (n, e) and a positive integer
m < n (a message representative) and returns the integer c = m
e
mod n. The RSA decryption primitive
RSADP takes as input the private key and an integer c < n (a ciphertext representative) to return the
integer m = c
d
mod n, where d is an integer with the above specified properties.
The public key is defined in Section 1.2.1, while the private key is defined in Section 1.2.2. The RSA
primitives are described in detail in Subsections 1.2.3 and 1.2.4; they coincide with the corresponding
primitives in PKCS #1 v2.0 [37], IEEE Std 1363-2000 [25], and the draft ANSI X9.44 [1]. For a
suggested key generation algorithm, see Section 1.5. For the mathematical background of the RSA
algorithm, see Appendix B.
1.2.1 RSA public key
For the purposes of this document, an RSA public key consists of two components:
n the modulus, a nonnegative integer
e the public exponent, a nonnegative integer
In a valid RSA public key, the modulus n is a product of two distinct odd primes p and q, and the
public exponent e is an integer between 3 and n − 1 satisfying GCD(e, p − 1) = GCD(e, q − 1) = 1.
1.2.2 RSA private key
For the purposes of this document, an RSA private key may have either of two representations.
评论0