Network Working Group B. Kaliski
Request for Comments: 2437 J. Staddon
Obsoletes: 2313 RSA Laboratories
Category: Informational October 1998
PKCS #1: RSA Cryptography Specifications
Version 2.0
Status of this Memo
This memo provides information for the Internet community. It does
not specify an Internet standard of any kind. Distribution of this
memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (1998). All Rights Reserved.
Table of Contents
1. Introduction.....................................2
1.1 Overview.........................................3
2. Notation.........................................3
3. Key types........................................5
3.1 RSA public key...................................5
3.2 RSA private key..................................5
4. Data conversion primitives.......................6
4.1 I2OSP............................................6
4.2 OS2IP............................................7
5. Cryptographic primitives.........................8
5.1 Encryption and decryption primitives.............8
5.1.1 RSAEP............................................8
5.1.2 RSADP............................................9
5.2 Signature and verification primitives...........10
5.2.1 RSASP1..........................................10
5.2.2 RSAVP1..........................................11
6. Overview of schemes.............................11
7. Encryption schemes..............................12
7.1 RSAES-OAEP......................................13
7.1.1 Encryption operation............................13
7.1.2 Decryption operation............................14
7.2 RSAES-PKCS1-v1_5................................15
7.2.1 Encryption operation............................17
7.2.2 Decryption operation............................17
8. Signature schemes with appendix.................18
8.1 RSASSA-PKCS1-v1_5...............................19
8.1.1 Signature generation operation..................20
Kaliski & Staddon Informational [Page 1]
RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998
8.1.2 Signature verification operation................21
9. Encoding methods................................22
9.1 Encoding methods for encryption.................22
9.1.1 EME-OAEP........................................22
9.1.2 EME-PKCS1-v1_5..................................24
9.2 Encoding methods for signatures with appendix...26
9.2.1 EMSA-PKCS1-v1_5.................................26
10. Auxiliary Functions.............................27
10.1 Hash Functions..................................27
10.2 Mask Generation Functions.......................28
10.2.1 MGF1............................................28
11. ASN.1 syntax....................................29
11.1 Key representation..............................29
11.1.1 Public-key syntax...............................30
11.1.2 Private-key syntax..............................30
11.2 Scheme identification...........................31
11.2.1 Syntax for RSAES-OAEP...........................31
11.2.2 Syntax for RSAES-PKCS1-v1_5.....................32
11.2.3 Syntax for RSASSA-PKCS1-v1_5....................33
12 Patent Statement................................33
12.1 Patent statement for the RSA algorithm..........34
13. Revision history................................35
14. References......................................35
Security Considerations.........................37
Acknowledgements................................37
Authors' Addresses..............................38
Full Copyright Statement........................39
1. Introduction
This memo is the successor to RFC 2313. This document provides
recommendations for the implementation of public-key cryptography
based on the RSA algorithm [18], covering the following aspects:
-cryptographic primitives
-encryption schemes
-signature schemes with appendix
-ASN.1 syntax for representing keys and for identifying the
schemes
The recommendations are intended for general application within
computer and communications systems, and as such include a fair
amount of flexibility. It is expected that application standards
based on these specifications may include additional constraints. The
recommendations are intended to be compatible with draft standards
currently being developed by the ANSI X9F1 [1] and IEEE P1363 working
groups [14]. This document supersedes PKCS #1 version 1.5 [20].
Kaliski & Staddon Informational [Page 2]
RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998
Editor's note. It is expected that subsequent versions of PKCS #1 may
cover other aspects of the RSA algorithm such as key size, key
generation, key validation, and signature schemes with message
recovery.
1.1 Overview
The organization of this document is as follows:
-Section 1 is an introduction.
-Section 2 defines some notation used in this document.
-Section 3 defines the RSA public and private key types.
-Sections 4 and 5 define several primitives, or basic mathematical
operations. Data conversion primitives are in Section 4, and
cryptographic primitives (encryption-decryption,
signature-verification) are in Section 5.
-Section 6, 7 and 8 deal with the encryption and signature schemes
in this document. Section 6 gives an overview. Section 7 defines
an OAEP-based [2] encryption scheme along with the method found
in PKCS #1 v1.5. Section 8 defines a signature scheme with
appendix; the method is identical to that of PKCS #1 v1.5.
-Section 9 defines the encoding methods for the encryption and
signature schemes in Sections 7 and 8.
-Section 10 defines the hash functions and the mask generation
function used in this document.
-Section 11 defines the ASN.1 syntax for the keys defined in
Section 3 and the schemes gives in Sections 7 and 8.
-Section 12 outlines the revision history of PKCS #1.
-Section 13 contains references to other publications and
standards.
2. Notation
(n, e) RSA public key
c ciphertext representative, an integer between 0 and n-1
C ciphertext, an octet string
d private exponent
dP p's exponent, a positive integer such that:
e(dP)\equiv 1 (mod(p-1))
dQ q's exponent, a positive integer such that:
e(dQ)\equiv 1 (mod(q-1))
e public exponent
Kaliski & Staddon Informational [Page 3]
RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998
EM encoded message, an octet string
emLen intended length in octets of an encoded message
H hash value, an output of Hash
Hash hash function
hLen output length in octets of hash function Hash
K RSA private key
k length in octets of the modulus
l intended length of octet string
lcm(.,.) least common multiple of two
nonnegative integers
m message representative, an integer between
0 and n-1
M message, an octet string
MGF mask generation function
n modulus
P encoding parameters, an octet string
p,q prime factors of the modulus
qInv CRT coefficient, a positive integer less
than p such: q(qInv)\equiv 1 (mod p)
s signature representative, an integer
between 0 and n-1
S signature, an octet string
x a nonnegative integer
X an octet string corresponding to x
\xor bitwise exclusive-or of two octet strings
\lambda(n) lcm(p-1, q-1), where n = pq
Kaliski & Staddon Informational [Page 4]
RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998
|| concatenation operator
||.|| octet length operator
3. Key types
Two key types are employed in the primitives and schemes defined in
this document: RSA public key and RSA private key. Together, an RSA
public key and an RSA private key form an RSA key pair.
3.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 odd
primes p and q, and the public exponent e is an integer between 3 and
n-1 satisfying gcd (e, \lambda(n)) = 1, where \lambda(n) = lcm (p-
1,q-1). A recommended syntax for interchanging RSA public keys
between implementations is given in Section 11.1.1; an
implementation's internal representation may differ.
3.2 RSA private key
For the purposes of this document, an RSA private key may have either
of two representations.
1. The first representation consists of the pair (n, d), where the
components have the following meanings:
n, the modulus, a nonnegative integer
d, the private exponent, a nonnegative integer
2. The second representation consists of a quintuple (p, q, dP, dQ,
qInv), where the components have the following meanings:
p, the first factor, a nonnegative integer
q, the second factor, a nonnegative integer
dP, the first factor's exponent, a nonnegative integer
dQ, the second factor's exponent, a nonnegative integer
qInv, the CRT coefficient, a nonnegative integer
In a valid RSA private key with the first representation, the modulus
n is the same as in the corresponding public key and is the product
of two odd primes p and q, and the private exponent d is a positive
Kaliski & Staddon Informational [Page 5]
RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998
integer less than n satisfying:
ed \equiv 1 (mod \lambda(n))
where e is the corresponding public exponent and \lambda(n) is as
defined above.
In a valid RSA private key with the second representation, the two
factors p and q are the prime factors of the modulus n, the exponents
dP and dQ are positive integers less than p and q respectively
satisfying
e(dP)\equiv 1(mod(p-1))
e(dQ)\equiv 1(mod(q-1)),
and the CRT coefficient qInv is a positive integer less than p
satisfying:
q(qInv)\equiv 1 (mod p).
A recommended syntax for interchanging RSA private keys between
implementations, which includes components from both representations,
is given in Section 11.1.2; an implementation's internal
representation may differ.
4. Data conversion primitives
Two data conversion primitives are employed in the schemes defined in
this document:
I2OSP: Integer-to-Octet-String primitive
OS2IP: Octet-String-to-Integer primitive
For the purposes of this document, and consistent with ASN.1 syntax, an
octet string is an ordered sequence of octets (eight-bit bytes). The
sequence is indexed from first (conventionally, leftmost) to last
(rightmost). For purposes of conversion to and from integers, the first
octet is considered the most significant in the following conversion
primitives
4.1 I2OSP
I2OSP converts a nonnegative integer to an octet string of a specified
length.
I2OSP (x, l)
Kaliski & Staddon Informational [Page 6]
RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998
Input:
x nonnegative integer to be converted
l intended length of the resulting octet string
Output:
X corresponding octet string of length l; or
"integer too large"
Steps:
1. If x>=256^l, output "integer too large" and stop.
2. Write the integer x in its unique l-digit representation base 256:
x = x_{l-1}256^{l-1} + x_{l-2}256^{l-2} +... + x_1 256 + x_0
where 0 <= x_i < 256 (note that one or more leading digits will be
zero if x < 256^{l-1}).
3. Let the octet X_i have the value x_{l-i} for 1 <= i <= l. Output
the octet string:
X = X_1 X_2 ... X_l.
4.2 OS2IP
OS2IP converts an octet string to a nonnegative integer.
OS2IP (X)
Input:
X octet string to be converted
Output:
x corresponding nonnegative integer
Steps:
1. Let X_1 X_2 ... X_l be the octets of X from first to last, and
let x{l-i} have value X_i for 1<= i <= l.
2. Let x = x{l-1} 256^{l-1} + x_{l-2} 256^{l-2} +...+ x_1 256 + x_0.
3. Output x.
Kaliski & Staddon Informational [Page 7]
RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998
5. Cryptographic primitives
Cryptographic primitives are basic mathematical operations on which
cryptographic schemes can be built. They are intended for
implementation in hardware or as software modules, and are not
intended to provide security apart from a scheme.
Four types of primitive are specified in this document, organized in
pairs: encryption and decryption; and signature and verification.
The specifications of the primitives assume that certain conditions
are met by the inputs, in particular that public and private keys are
valid.
5.1 Encryption and decryption primitives
An encryption primitive produces a ciphertext representative from a
message representative under the control of a public key, and a
decryption primitive recovers the message representative from the
ciphertext representative under the control of the corresponding
private key.
One pair of encryption and decryption primitives is employed in the
encryption schemes defined in this document and is specified here:
RSAEP/RSADP. RSAEP and RSADP involve the same mathematical operation,
with different keys as input.
The primitives defined here are the same as in the draft IEEE P1363
and are compatible with PKCS #1 v1.5.
The main mathematical operation in each primitive is exponentiation.
5.1.1 RSAEP
RSAEP((n, e), m)
Input:
(n, e) RSA public key
m message representative, an integer between 0 and n-1
Output:
c ciphertext representative, an integer between 0 and n-1;
or "message representative out of range"
Assumptions: public key (n, e) is valid
Steps:
Kaliski & Staddon Informational [Page 8]
RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998
1. If the message representative m is not between 0 and n-1, output
message representative out of range and stop.
2. Let c = m^e mod n.
3. Output c.
5.1.2 RSADP
RSADP (K, c)
Input:
K RSA private key, where K has one of the following forms
-a pair (n, d)
-a quintuple (p, q, dP, dQ, qInv)
c ciphertext representative, an integer between 0 and n-1
Output:
m message representative, an integer between 0 and n-1; or
"ciphertext representative out of range"
Assumptions: private key K is valid
Steps:
1. If the ciphertext representative c is not between 0 and n-1,
output "ciphertext representative out of range" and stop.
2. If the first form (n, d) of K is used:
2.1 Let m = c^d mod n. Else, if the second form (p, q, dP,
dQ, qInv) of K is used:
2.2 Let m_1 = c^dP mod p.
2.3 Let m_2 = c^dQ mod q.
2.4 Let h = qInv ( m_1 - m_2 ) mod p.
2.5 Let m = m_2 + hq.
3. Output m.
Kaliski & Staddon Informational [Page 9]
RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998
5.2 Signature and verification primitives
A signature primitive produces a signature representative from a
message representative under the control of a private key, and a
verification primitive recovers the message representative from the
signature representative under the control of the corresponding
public key. One pair of signature and verification primitives is
employed in the signature schemes defined in this document and is
specified here: RSASP1/RSAVP1.
The primitives defined here are the same as in the draft IEEE P1363
and are compatible with PKCS #1 v1.5.
The main mathematical operation in each primitive is exponentiation,
as in the encryption and decryption primitives of Section 5.1. RSASP1
and RSAVP1 are the same as RSADP and RSAEP except for the names of
their input and output arguments; they are distinguished as they are
intended for different purposes.
5.2.1 RSASP1
RSASP1 (K, m)
Input:
K RSA private key, where K has one of the following
forms:
-a pair (n, d)
-a quintuple (p, q, dP, dQ, qInv)
m message representative, an integer between 0 and n-1
Output:
s signature representative, an integer between 0 and
n-1, or "message representative out of range"
Assumptions:
private key K is valid
Steps:
1. If the message representative m is not between 0 and n-1, output
"message representative out of range" and stop.
2. If the first form (n, d) of K is used:
2.1 Let s = m^d mod n. Else, if the second form (p, q, dP,
dQ, qInv) of K is used:
Kaliski & Staddon Informational [Page 1