|
Network Working Group Request for Comments: 2313 Category: Informational |
B. Kaliski RSA Laboratories East March 1998 |
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 © The Internet Society (1998). All Rights Reserved.
This document describes a method for encrypting data using the RSA public-key cryptosystem.
This document describes a method for encrypting data using the RSA public-key cryptosystem. Its intended use is in the construction of digital signatures and digital envelopes, as described in PKCS #7:
content-encryption key are represented together
according to the syntax in PKCS #7 to yield a
digital envelope. This application is also
compatible with PEM methods.
The document also describes a syntax for RSA public keys and private keys. The public-key syntax would be used in certificates; the private-key syntax would be used typically in PKCS #8 private-key information. The public-key syntax is identical to that in both X.509 and Privacy-Enhanced Mail. Thus X.509/PEM RSA keys can be used in this document.
The document also defines three signature algorithms for use in signing X.509/PEM certificates and certificate-revocation lists, PKCS
#6 extended certificates, and other objects employing digital signatures such as X.401 message tokens.
Details on message-digest and content-encryption algorithms are outside the scope of this document, as are details on sources of the pseudorandom bits required by certain methods in this document.
FIPS PUB 46-1 National Bureau of Standards. FIPS PUB 46-1: Data Encryption Standard. January 1988.
PKCS #6 RSA Laboratories. PKCS #6: Extended-Certificate
Syntax. Version 1.5, November 1993.
PKCS #7 RSA Laboratories. PKCS #7: Cryptographic Message
Syntax. Version 1.5, November 1993.
PKCS #8 RSA Laboratories. PKCS #8: Private-Key Information
Syntax. Version 1.2, November 1993.
RFC 1319 Kaliski, B., "The MD2 Message-Digest
Algorithm," RFC 1319, April 1992.
RFC 1320 Rivest, R., "The MD4 Message-Digest
Algorithm," RFC 1320, April 1992.
RFC 1321 Rivest, R., "The MD5 Message-Digest
Algorithm," RFC 1321, April 1992.
RFC 1423 Balenson, D., "Privacy Enhancement for
Internet Electronic Mail: Part III: Algorithms,
Modes, and Identifiers," RFC 1423, February 1993.
X.208 CCITT. Recommendation X.208: Specification of
Abstract Syntax Notation One (ASN.1). 1988.
[QC82] J.-J. Quisquater and C. Couvreur. Fast
decipherment algorithm for RSA public-key
cryptosystem. Electronics Letters, 18(21):905-907,
October 1982.
[RSA78] R.L. Rivest, A. Shamir, and L. Adleman. A method
for obtaining digital signatures and public-key
cryptosystems. Communications of the ACM,
21(2):120-126, February 1978.
For the purposes of this document, the following definitions apply.
AlgorithmIdentifier: A type that identifies an algorithm (by object identifier) and associated parameters. This type is defined in X.509.
ASN.1: Abstract Syntax Notation One, as defined in X.208.
BER: Basic Encoding Rules, as defined in X.209.
DES: Data Encryption Standard, as defined in FIPS PUB 46-1.
MD2: RSA Data Security, Inc.'s MD2 message-digest algorithm, as defined in RFC 1319.
MD4: RSA Data Security, Inc.'s MD4 message-digest algorithm, as defined in RFC 1320.
MD5: RSA Data Security, Inc.'s MD5 message-digest algorithm, as defined in RFC 1321.
modulus: Integer constructed as the product of two primes.
PEM: Internet Privacy-Enhanced Mail, as defined in RFC 1423 and related documents.
RSA: The RSA public-key cryptosystem, as defined in [RSA78].
private key: Modulus and private exponent.
public key: Modulus and public exponent.
Upper-case symbols (e.g., BT) denote octet strings and bit strings (in the case of the signature S); lower-case symbols (e.g., c) denote integers.
ab hexadecimal octet value c exponent
BT block type d private exponent
D data e public exponent
EB encryption block k length of modulus in
octets
ED encrypted data n modulus
M message p, q prime factors of modulus
MD message digest x integer encryption block
MD' comparative message y integer encrypted data
digest
PS padding string mod n modulo n
S signature X || Y concatenation of X, Y
||X|| length in octets of X
The next six sections specify key generation, key syntax, the encryption process, the decryption process, signature algorithms, and object identifiers.
Each entity shall generate a pair of keys: a public key and a private key. The encryption process shall be performed with one of the keys and the decryption process shall be performed with the other key. Thus the encryption process can be either a public-key operation or a private-key operation, and so can the decryption process. Both processes transform an octet string to another octet string. The processes are inverses of each other if one process uses an entity's public key and the other process uses the same entity's private key.
The encryption and decryption processes can implement either the classic RSA transformations, or variations with padding.
This section describes RSA key generation.
Each entity shall select a positive integer e as its public exponent.
Each entity shall privately and randomly select two distinct odd primes p and q such that (p-1) and e have no common divisors, and (q-1) and e have no common divisors.
The public modulus n shall be the product of the private prime factors p and q:
n = pq .
The private exponent shall be a positive integer d such that de-1 is divisible by both p-1 and q-1.
The length of the modulus n in octets is the integer k satisfying
2^(8(k-1)) <= n < 2^(8k) .
The length k of the modulus must be at least 12 octets to accommodate the block formats in this document (see Section 8).
Notes.
This section gives the syntax for RSA public and private keys.
An RSA public key shall have ASN.1 type RSAPublicKey:
RSAPublicKey ::= SEQUENCE {
modulus INTEGER, -- n
publicExponent INTEGER -- e }
(This type is specified in X.509 and is retained here for compatibility.)
The fields of type RSAPublicKey have the following meanings:
An RSA private key shall have ASN.1 type RSAPrivateKey:
RSAPrivateKey ::= SEQUENCE {
version Version,
modulus INTEGER, -- n
publicExponent INTEGER, -- e
privateExponent INTEGER, -- d
prime1 INTEGER, -- p
prime2 INTEGER, -- q
exponent1 INTEGER, -- d mod (p-1)
exponent2 INTEGER, -- d mod (q-1)
coefficient INTEGER -- (inverse of q) mod p }
Version ::= INTEGER
The fields of type RSAPrivateKey have the following meanings:
Notes.
all the extra values can be converted readily to the syntax defined here, provided the public key is known, according to a result by Miller [Mil76].
This section describes the RSA encryption process.
The encryption process consists of four steps: encryption- block formatting, octet-string-to-integer conversion, RSA computation, and integer-to-octet-string conversion. The input to the encryption process shall be an octet string D, the data; an integer n, the modulus; and an integer c, the exponent. For a public-key operation, the integer c shall be an entity's public exponent e; for a private- key operation, it shall be an entity's private exponent d. The output from the encryption process shall be an octet string ED, the encrypted data.
The length of the data D shall not be more than k-11 octets, which is positive since the length k of the modulus is at least 12 octets. This limitation guarantees that the length of the padding string PS is at least eight octets, which is a security condition.
Notes.
A block type BT, a padding string PS, and the data D shall be formatted into an octet string EB, the encryption block.
EB = 00 || BT || PS || 00 || D . (1)
The block type BT shall be a single octet indicating the structure of the encryption block. For this version of the document it shall have value 00, 01, or 02. For a private- key operation, the block type shall be 00 or 01. For a public-key operation, it shall be 02.
The padding string PS shall consist of k-3-||D|| octets. For block type 00, the octets shall have value 00; for block type 01, they shall have value FF; and for block type 02, they shall be pseudorandomly generated and nonzero. This makes the length of the encryption block EB equal to k.
Notes.
The encryption block EB shall be converted to an integer x, the integer encryption block. Let EB1, ..., EBk be the octets of EB from first to last. Then the integer x shall satisfy
k
x = SUM 2^(8(k-i)) EBi . (2)
i = 1
In other words, the first octet of EB has the most significance in the integer and the last octet of EB has the least significance.
Note. The integer encryption block x satisfies 0 <= x < n since EB1
= 00 and 2^(8(k-1)) <= n.
The integer encryption block x shall be raised to the power c modulo n to give an integer y, the integer encrypted data.
y = x^c mod n, 0 <= y < n .
This is the classic RSA computation.
The integer encrypted data y shall be converted to an octet string ED of length k, the encrypted data. The encrypted data ED shall satisfy
k
y = SUM 2^(8(k-i)) EDi . (3)
i = 1
where ED1, ..., EDk are the octets of ED from first to last.
In other words, the first octet of ED has the most significance in the integer and the last octet of ED has the least significance.
This section describes the RSA decryption process.
The decryption process consists of four steps: octet-string-to- integer conversion, RSA computation, integer-to-octet-string conversion, and encryption-block parsing. The input to the decryption process shall be an octet string ED, the encrypted data; an integer n, the modulus; and an integer c, the exponent. For a public-key operation, the integer c shall be an entity's public exponent e; for a private-key operation, it shall be an entity's private exponent d. The output from the decryption process shall be an octet string D, the data.
It is an error if the length of the encrypted data ED is not k.
For brevity, the decryption process is described in terms of the encryption process.
The encrypted data ED shall be converted to an integer y, the integer encrypted data, according to Equation (3).
It is an error if the integer encrypted data y does not satisfy 0 <= y < n.
The integer encrypted data y shall be raised to the power c modulo n to give an integer x, the integer encryption block.
x = y^c mod n, 0 <= x < n .
This is the classic RSA computation.
The integer encryption block x shall be converted to an octet string EB of length k, the encryption block, according to Equation (2).
The encryption block EB shall be parsed into a block type BT, a padding string PS, and the data D according to Equation (1).
It is an error if any of the following conditions occurs:
This section defines three signature algorithms based on the RSA encryption process described in Sections 8 and 9. The intended use of the signature algorithms is in signing X.509/PEM certificates and certificate-revocation lists, PKCS #6 extended certificates, and other objects employing digital signatures such as X.401 message tokens. The algorithms are not intended for use in constructing digital signatures in PKCS #7. The first signature algorithm (informally, "MD2 with RSA") combines the MD2 message-digest algorithm with RSA, the second (informally, "MD4 with RSA") combines the MD4 message-digest algorithm with RSA, and the third (informally, "MD5 with RSA") combines the MD5 message-digest algorithm with RSA.
This section describes the signature process and the verification process for the two algorithms. The "selected" message-digest algorithm shall be either MD2 or MD5, depending on the signature algorithm. The signature process shall be performed with an entity's private key and the verification process shall be performed with an entity's public key. The signature process transforms an octet string (the message) to a bit string (the signature); the verification process determines whether a bit string (the signature) is the signature of an octet string (the message).
Note. The only difference between the signature algorithms defined here and one of the the methods by which signatures (encrypted message digests) are constructed in PKCS #7 is that signatures here are represented here as bit strings, for consistency with the X.509 SIGNED macro. In PKCS #7 encrypted message digests are octet strings.
The signature process consists of four steps: message digesting, data encoding, RSA encryption, and octet-string-to-bit-string conversion. The input to the signature process shall be an octet string M, the message; and a signer's private key. The output from the signature process shall be a bit string S, the signature.
The message M shall be digested with the selected message- digest algorithm to give an octet string MD, the message digest.
The message digest MD and a message-digest algorithm identifier shall be combined into an ASN.1 value of type DigestInfo, described below, which shall be BER-encoded to give an octet string D, the data.
DigestInfo ::= SEQUENCE {
digestAlgorithm DigestAlgorithmIdentifier,
digest Digest }
DigestAlgorithmIdentifier ::= AlgorithmIdentifier
Digest ::= OCTET STRING
The fields of type DigestInfo have the following meanings:
md2 OBJECT IDENTIFIER ::=
{ iso(1) member-body(2) US(840) rsadsi(113549)
digestAlgorithm(2) 2 } md4 OBJECT IDENTIFIER ::=
{ iso(1) member-body(2) US(840) rsadsi(113549)
digestAlgorithm(2) 4 } md5 OBJECT IDENTIFIER ::=
{ iso(1) member-body(2) US(840) rsadsi(113549)
digestAlgorithm(2) 5 }
For these object identifiers, the parameters field of the digestAlgorithm value should be NULL.
Notes.
[Mer90][dBB92], none have been found in MD4 itself, which has three rounds. After further critical review, it may be appropriate to consider MD4 for very high security applications.
MD5, which has four rounds and is proportionally slower than MD4, is recommended until the completion of MD4's review. The reported "pseudocollisions" in MD5's internal compression function [dBB93] do not appear to have any practical impact on MD5's security.
MD2, the slowest of the three, has the most conservative design. No attacks on MD2 have been published.
The data D shall be encrypted with the signer's RSA private key as described in Section 7 to give an octet string ED, the encrypted data. The block type shall be 01. (See Section 8.1.)
The encrypted data ED shall be converted into a bit string S, the signature. Specifically, the most significant bit of the first octet of the encrypted data shall become the first bit of the signature, and so on through the least significant bit of the last octet of the encrypted data, which shall become the last bit of the signature.
Note. The length in bits of the signature S is a multiple of eight.
The verification process for both signature algorithms consists of four steps: bit-string-to-octet-string conversion, RSA decryption, data decoding, and message digesting and comparison. The input to the verification process shall be an octet string M, the message; a signer's public key; and a bit string S, the signature. The output from the verification process shall be an indication of success or failure.
The signature S shall be converted into an octet string ED, the encrypted data. Specifically, assuming that the length in bits of the signature S is a multiple of eight, the first bit of the signature shall become the most significant bit of the first octet of the
encrypted data, and so on through the last bit of the signature, which shall become the least significant bit of the last octet of the encrypted data.
It is an error if the length in bits of the signature S is not a multiple of eight.
The encrypted data ED shall be decrypted with the signer's RSA public key as described in Section 8 to give an octet string D, the data.
It is an error if the block type recovered in the decryption process is not 01. (See Section 9.4.)
The data D shall be BER-decoded to give an ASN.1 value of type DigestInfo, which shall be separated into a message digest MD and a message-digest algorithm identifier. The message-digest algorithm identifier shall determine the "selected" message-digest algorithm for the next step.
It is an error if the message-digest algorithm identifier does not identify the MD2, MD4 or MD5 message-digest algorithm.
The message M shall be digested with the selected message-digest algorithm to give an octet string MD', the comparative message digest. The verification process shall succeed if the comparative message digest MD' is the same as the message digest MD, and the verification process shall fail otherwise.
This document defines five object identifiers: pkcs-1, rsaEncryption, md2WithRSAEncryption, md4WithRSAEncryption, and md5WithRSAEncryption.
The object identifier pkcs-1 identifies this document.
pkcs-1 OBJECT IDENTIFIER ::=
{ iso(1) member-body(2) US(840) rsadsi(113549)
pkcs(1) 1 }
The object identifier rsaEncryption identifies RSA public and private keys as defined in Section 7 and the RSA encryption and decryption processes defined in Sections 8 and 9.
rsaEncryption OBJECT IDENTIFIER ::= { pkcs-1 1 }
The rsaEncryption object identifier is intended to be used in the algorithm field of a value of type AlgorithmIdentifier. The parameters field of that type, which has the algorithm-specific syntax ANY DEFINED BY algorithm, would have ASN.1 type NULL for this algorithm.
The object identifiers md2WithRSAEncryption, md4WithRSAEncryption, md5WithRSAEncryption, identify, respectively, the "MD2 with RSA," "MD4 with RSA," and "MD5 with RSA" signature and verification processes defined in Section 10.
md2WithRSAEncryption OBJECT IDENTIFIER ::= { pkcs-1 2 }
md4WithRSAEncryption OBJECT IDENTIFIER ::= { pkcs-1 3 }
md5WithRSAEncryption OBJECT IDENTIFIER ::= { pkcs-1 4 }
These object identifiers are intended to be used in the algorithm field of a value of type AlgorithmIdentifier. The parameters field of that type, which has the algorithm-specific syntax ANY DEFINED BY algorithm, would have ASN.1 type NULL for these algorithms.
Note. X.509's object identifier rsa also identifies RSA public keys as defined in Section 7, but does not identify private keys, and identifies different encryption and decryption processes. It is expected that some applications will identify public keys by rsa. Such public keys are compatible with this document; an rsaEncryption process under an rsa public key is the same as the rsaEncryption process under an rsaEncryption public key.
Security issues are discussed throughout this memo.
Versions 1.0-1.3
Versions 1.0-1.3 were distributed to participants in RSA Data Security, Inc.'s Public-Key Cryptography Standards meetings in February and March 1991.
Version 1.4
Version 1.4 is part of the June 3, 1991 initial public release of PKCS. Version 1.4 was published as NIST/OSI Implementors' Workshop document SEC-SIG-91-18.
Version 1.5
Version 1.5 incorporates several editorial changes, including updates to the references and the addition of a revision history. The following substantive changes were made:
Supersedes June 3, 1991 version, which was also published as NIST/OSI Implementors' Workshop document SEC-SIG-91-18.
This document is based on a contribution of RSA Laboratories, a division of RSA Data Security, Inc. Any substantial use of the text from this document must acknowledge RSA Data Security, Inc. RSA Data Security, Inc. requests that all material mentioning or referencing this document identify this as "RSA Data Security, Inc. PKCS #1".
Burt Kaliski
RSA Laboratories East
20 Crosby Drive
Bedford, MA 01730
Phone: (617) 687-7000
EMail: burt@rsa.com
Copyright © The Internet Society (1998). All Rights Reserved.
This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.
The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.