idnits 2.17.1 draft-kaliski-pkcs-pkcs1v2-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. ** Expected the document's filename to be given on the first page, but didn't find any == The page length should not exceed 58 lines per page, but there was 1 longer page, the longest (page 2) being 132 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 34 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Abstract section. ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 11 instances of too long lines in the document, the longest one being 7 characters in excess of 72. ** There are 109 instances of lines with control characters in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 1317 has weird spacing: '...Hash hash f...' == Line 1325 has weird spacing: '...mask mask, ...' == Couldn't figure out when the document was first submitted -- there may comments or warnings related to the use of a disclaimer for pre-RFC5378 work that could not be issued because of this. Please check the Legal Provisions document at https://trustee.ietf.org/license-info to determine if you need the pre-RFC5378 disclaimer. -- The document date (September 1998) is 9327 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: '0' is mentioned on line 1423, but not defined -- Looks like a reference, but probably isn't: 'DRAFT' on line 1612 == Unused Reference: '12' is defined on line 1661, but no explicit reference was found in the text ** Obsolete normative reference: RFC 1319 (ref. '15') (Obsoleted by RFC 6149) Summary: 13 errors (**), 0 flaws (~~), 8 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group B. Kaliski and J. Staddon 2 Internet-Draft RSA Laboratories 3 Category: Informational September 1998 5 PKCS #1: RSA Cryptography Specifications 6 Version 2.0 8 Status of this Memo 10 This document is an Internet-Draft. Internet-Drafts are working 11 documents of the Internet Engineering Task Force (IETF), its 12 areas, and its working groups. Note that other groups may also 13 distribute working documents as Internet-Drafts. 15 Internet-Drafts are draft documents valid for a maximum of six 16 months and may be updated, replaced, or obsoleted by other 17 documents at any time. It is inappropriate to use Internet- 18 Drafts as reference material or to cite them other than as 19 "work in progress." 21 To view the entire list of current Internet-Drafts, please check 22 the "1id-abstracts.txt" listing contained in the Internet-Drafts 23 Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net 24 (Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au 25 (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu 26 (US West Coast). 28 This memo provides information for the Internet community. It does not 29 Specify an Internet standard of any kind. Distribution of this memo 30 is unlimited. 32 Copyright Notice 34 Copyright (C) The Internet Society (1998). All Rights Reserved. 36 Table of Contents 37 1. Introduction.....................................2 38 1.1 Overview.........................................2 39 2. Notation.........................................3 40 3. Key types........................................4 41 3.1 RSA public key...................................4 42 3.2 RSA private key..................................4 43 4. Data conversion primitives.......................5 44 4.1 I2OSP............................................6 45 4.2 OS2IP............................................6 46 5. Cryptographic primitives.........................7 47 5.1 Encryption and decryption primitives.............7 48 5.1.1 RSAEP............................................7 49 5.1.2 RSADP............................................8 50 5.2 Signature and verification primitives............8 51 5.2.1 RSASP1...........................................9 52 5.2.2 RSAVP1...........................................9 53 6. Overview of schemes.............................10 54 7. Encryption schemes..............................10 55 7.1 RSAES-OAEP......................................11 56 7.1.1 Encryption operation............................11 57 7.1.2 Decryption operation............................12 58 7.2 RSAES-PKCS1-v1_5................................13 59 7.2.1 Encryption operation............................14 60 7.2.2 Decryption operation............................15 61 8. Signature schemes with appendix.................16 62 8.1 RSASSA-PKCS1-v1_5...............................17 63 8.1.1 Signature generation operation..................17 64 8.1.2 Signature verification operation................18 65 9. Encoding methods................................19 66 9.1 Encoding methods for encryption.................19 67 9.1.1 EME-OAEP........................................19 68 9.1.2 EME-PKCS1-v1_5..................................21 69 9.2 Encoding methods for signatures with appendix...22 70 9.2.1 EMSA-PKCS1-v1_5.................................22 71 10. Auxiliary Functions.............................23 72 10.1 Hash Functions..................................23 73 10.2 Mask Generation Functions.......................24 74 10.2.1 MGF1............................................24 75 11. ASN.1 syntax....................................25 76 11.1 Key representation..............................25 77 11.1.1 Public-key syntax...............................25 78 11.1.2 Private-key syntax..............................26 79 11.2 Scheme identification...........................26 80 11.2.1 Syntax for RSAES-OAEP...........................26 81 11.2.2 Syntax for RSAES-PKCS1-v1_5.....................28 82 11.2.3 Syntax for RSASSA-PKCS1-v1_5....................28 83 12 Patent Statement................................29 84 12.1 Patent statement for the RSA algorithm..........30 85 13. Revision history................................30 86 14. References......................................30 88 1. Introduction 89 This Internet-Draft is proposed as a successor to RFC-2313. This 90 document provides recommendations for the implementation of public- 91 key cryptography based on the RSA algorithm [18], covering the following 92 aspects: 94 -cryptographic primitives 95 -encryption schemes 96 -signature schemes with appendix 97 -ASN.1 syntax for representing keys and for identifying the schemes 99 The recommendations are intended for general application within computer 100 and communications systems, and as such include a fair amount of 101 flexibility. It is expected that application standards based on these 102 specifications may include additional constraints. The recommendations 103 are intended to be compatible with draft standards currently being 104 developed by the ANSI X9F1 [1] and IEEE P1363 working groups [14]. 105 This document supersedes PKCS #1 version 1.5 [20]. 107 Editor's note. It is expected that subsequent versions of PKCS #1 may 108 cover other aspects of the RSA algorithm such as key size, key 109 generation, key validation, and signature schemes with message recovery. 111 1.1 Overview 113 The organization of this document is as follows: 115 -Section 1 is an introduction. 116 -Section 2 defines some notation used in this document. 117 -Section 3 defines the RSA public and private key types. 118 -Sections 4 and 5 define several primitives, or basic mathematical 119 operations. Data conversion primitives are in Section 4, and 120 cryptographic primitives (encryption-decryption, signature-verification) 121 are in Section 5. 122 -Section 6, 7 and 8 deal with the encryption and signature schemes in 123 this document. Section 6 gives an overview. Section 7 defines an OAEP- 124 based [2] encryption scheme along with the method found in PKCS #1 v1.5. 126 Section 8 defines a signature scheme with appendix; the method is 127 identical to that of PKCS #1 v1.5. 128 -Section 9 defines the encoding methods for the encryption and signature 129 schemes in Sections 7 and 8. 130 -Section 10 defines the hash functions and the mask generation function 131 used in this document. 132 -Section 11 defines the ASN.1 syntax for the keys defined in Section 3 133 and the schemes gives in Sections 7 and 8. 134 -Section 12 outlines the revision history of PKCS #1. 135 -Section 13 contains references to other publications and standards. 137 2. Notation 139 (n, e) RSA public key 141 c ciphertext representative, an integer between 0 and n-1 143 C ciphertext, an octet string 145 d private exponent 147 dP p's exponent, a positive integer such that: 148 e(dP)\equiv 1 (mod(p-1)) 150 dQ q's exponent, a positive integer such that: 151 e(dQ)\equiv 1 (mod(q-1)) 153 e public exponent 155 EM encoded message, an octet string 157 emLen intended length in octets of an encoded message 159 H hash value, an output of Hash 161 Hash hash function 163 hLen output length in octets of hash function Hash 165 K RSA private key 167 k length in octets of the modulus 169 l intended length of octet string 171 lcm(.,.) least common multiple of two 172 nonnegative integers 174 m message representative, an integer between 175 0 and n-1 177 M message, an octet string 178 MGF mask generation function 180 n modulus 182 P encoding parameters, an octet string 184 p,q prime factors of the modulus 186 qInv CRT coefficient, a positive integer less 187 than p such: q(qInv)\equiv 1 (mod p) 189 s signature representative, an integer 190 between 0 and n-1 192 S signature, an octet string 194 x a nonnegative integer 196 X an octet string corresponding to x 198 \xor bitwise exclusive-or of two octet strings 200 \lambda(n) lcm(p-1, q-1), where n = pq 202 || concatenation operator 204 ||.|| octet length operator 206 3. Key types 208 Two key types are employed in the primitives and schemes defined in this 209 document: RSA public key and RSA private key. Together, an RSA public 210 key and an RSA private key form an RSA key pair. 212 3.1 RSA public key 214 For the purposes of this document, an RSA public key consists of two 215 components: 217 n, the modulus, a nonnegative integer 218 e, the public exponent, a nonnegative integer 220 In a valid RSA public key, the modulus n is a product of two odd primes 221 p and q, and the public exponent e is an integer between 3 and n-1 222 satisfying gcd (e, \lambda(n)) = 1, where \lambda(n) = lcm (p-1,q-1). 223 A recommended syntax for interchanging RSA public keys between 224 implementations is given in Section 11.1.1; an implementation's internal 225 representation may differ. 227 3.2 RSA private key 229 For the purposes of this document, an RSA private key may have either of 230 two representations. 232 1. The first representation consists of the pair (n, d), where the 233 components have the following meanings: 235 n, the modulus, a nonnegative integer 236 d, the private exponent, a nonnegative integer 238 2. The second representation consists of a quintuple (p, q, dP, dQ, 239 qInv), where the components have the following meanings: 241 p, the first factor, a nonnegative integer 242 q, the second factor, a nonnegative integer 243 dP, the first factor's exponent, a nonnegative integer 244 dQ, the second factor's exponent, a nonnegative integer 245 qInv, the CRT coefficient, a nonnegative integer 247 In a valid RSA private key with the first representation, the modulus n 248 is the same as in the corresponding public key and is the product of two 249 odd primes p and q, and the private exponent d is a positive integer 250 less than n satisfying: 252 ed \equiv 1 (mod \lambda(n)) 254 where e is the corresponding public exponent and \lambda(n) is as 255 defined above. 257 In a valid RSA private key with the second representation, the two 258 factors p and q are the prime factors of the modulus n, the exponents dP 259 and dQ are positive integers less than p and q respectively satisfying 261 e(dP)\equiv 1(mod(p-1)) 262 e(dQ)\equiv 1(mod(q-1)), 264 and the CRT coefficient qInv is a positive integer less than p 265 satisfying: 267 q(qInv)\equiv 1 (mod p). 269 A recommended syntax for interchanging RSA private keys between 270 implementations, which includes components from both representations, is 271 given in Section 11.1.2; an implementation's internal representation may 272 differ. 274 4. Data conversion primitives 276 Two data conversion primitives are employed in the schemes defined in 277 this document: 279 I2OSP: Integer-to-Octet-String primitive 280 OS2IP: Octet-String-to-Integer primitive 282 For the purposes of this document, and consistent with ASN.1 syntax, an 283 octet string is an ordered sequence of octets (eight-bit bytes). The 284 sequence is indexed from first (conventionally, leftmost) to last 285 (rightmost). For purposes of conversion to and from integers, the first 286 octet is considered the most significant in the following conversion 287 primitives 289 4.1 I2OSP 291 I2OSP converts a nonnegative integer to an octet string of a specified 292 length. 294 I2OSP (x, l) 296 Input: 297 x nonnegative integer to be converted 298 l intended length of the resulting octet string 300 Output: 301 X corresponding octet string of length l; or "integer too large" 303 Steps: 305 1. If x>=256^l, output "integer too large" and stop. 307 2. Write the integer x in its unique l-digit representation base 256: 309 x = x_{l-1}256^{l-1} + x_{l-2}256^{l-2} +... + x_1 256 + x_0 311 where 0 <= x_i < 256 (note that one or more leading digits will be zero 312 if x < 256^{l-1}). 314 3. Let the octet X_i have the value x_{l-i} for 1 <= i <= l. Output the 315 octet string: 317 X = X_1 X_2 ... X_l. 319 4.2 OS2IP 321 OS2IP converts an octet string to a nonnegative integer. 323 OS2IP (X) 325 Input: 326 X octet string to be converted 328 Output: 329 x corresponding nonnegative integer 331 Steps: 333 1.Let X_1 X_2 ... X_l be the octets of X from first to last, and let 334 x{l-i} have value X_i for 1<= i <= l. 336 2.Let x = x{l-1} 256^{l-1} + x_{l-2} 256^{l-2} +...+ x_1 256 + x_0. 338 3.Output x. 340 5. Cryptographic primitives 342 Cryptographic primitives are basic mathematical operations on which 343 cryptographic schemes can be built. They are intended for implementation 344 in hardware or as software modules, and are not intended to provide 345 security apart from a scheme. 347 Four types of primitive are specified in this document, organized in 348 pairs: encryption and decryption; and signature and verification. 350 The specifications of the primitives assume that certain conditions are 351 met by the inputs, in particular that public and private keys are valid. 353 5.1 Encryption and decryption primitives 355 An encryption primitive produces a ciphertext representative from a 356 message representative under the control of a public key, and a 357 decryption primitive recovers the message representative from the 358 ciphertext representative under the control of the corresponding private 359 key. 361 One pair of encryption and decryption primitives is employed in the 362 encryption schemes defined in this document and is specified here: 363 RSAEP/RSADP. RSAEP and RSADP involve the same mathematical operation, 364 with different keys as input. 366 The primitives defined here are the same as in the draft IEEE P1363 and 367 are compatible with PKCS #1 v1.5. 369 The main mathematical operation in each primitive is exponentiation. 371 5.1.1 RSAEP 373 RSAEP((n, e), m) 375 Input: 376 (n, e) RSA public key 377 m message representative, an integer between 0 and n-1 379 Output: 380 c ciphertext representative, an integer between 0 and n-1; 381 or "message representative out of range" 383 Assumptions: public key (n, e) is valid 385 Steps: 387 1. If the message representative m is not between 0 and n-1, output 388 message representative out of range and stop. 390 2. Let c = m^e mod n. 391 3. Output c. 393 5.1.2 RSADP 395 RSADP (K, c) 397 Input: 399 K RSA private key, where K has one of the following forms 400 -a pair (n, d) 401 -a quintuple (p, q, dP, dQ, qInv) 402 c ciphertext representative, an integer between 0 and n-1 404 Output: 405 m message representative, an integer between 0 and n-1; or 406 "ciphertext representative out of range" 408 Assumptions: private key K is valid 410 Steps: 412 1. If the ciphertext representative c is not between 0 and n-1, output 413 "ciphertext representative out of range" and stop. 415 2. If the first form (n, d) of K is used: 417 2.1 Let m = c^d mod n. 419 Else, if the second form (p, q, dP, dQ, qInv) of K is used: 421 2.2 Let m_1 = c^dP mod p. 423 2.3 Let m_2 = c^dQ mod q. 425 2.4 Let h = qInv ( m_1 - m_2 ) mod p. 427 2.5 Let m = m_2 + hq. 429 3.Output m. 431 5.2 Signature and verification primitives 433 A signature primitive produces a signature representative from a message 434 representative under the control of a private key, and a verification 435 primitive recovers the message representative from the signature 436 representative under the control of the corresponding public key. One 437 pair of signature and verification primitives is employed in the 438 signature schemes defined in this document and is specified here: 439 RSASP1/RSAVP1. 441 The primitives defined here are the same as in the draft IEEE P1363 and 442 are compatible with PKCS #1 v1.5. 444 The main mathematical operation in each primitive is exponentiation, as 445 in the encryption and decryption primitives of Section 5.1. RSASP1 and 446 RSAVP1 are the same as RSADP and RSAEP except for the names of their 447 input and output arguments; they are distinguished as they are intended 448 for different purposes. 450 5.2.1 RSASP1 452 RSASP1 (K, m) 454 Input: 455 K RSA private key, where K has one of the following 456 forms: 457 -a pair (n, d) 458 -a quintuple (p, q, dP, dQ, qInv) 460 m message representative, an integer between 0 and n-1 462 Output: 463 s signature representative, an integer between 0 and 464 n-1, or "message representative out of range" 466 Assumptions: 467 private key K is valid 469 Steps: 471 1. If the message representative m is not between 0 and n-1, output 472 "message representative out of range" and stop. 474 2. If the first form (n, d) of K is used: 476 2.1 Let s = m^d mod n. 478 Else, if the second form (p, q, dP, dQ, qInv) of K is used: 480 2.2 Let s_1 = m^dP mod p. 482 2.3 Let s_2 = m^dQ mod q. 484 2.4 Let h = qInv ( s_1 - s_2 ) mod p. 486 2.5 Let s = s_2 + hq. 488 3.Output S. 490 5.2.2 RSAVP1 492 RSAVP1 ((n, e), s) 494 Input: 496 (n, e) RSA public key 497 s signature representative, an integer between 0 and n-1 499 Output: 500 m message representative, an integer between 0 and n-1; 501 or "invalid" 503 Assumptions: 504 public key (n, e) is valid 506 Steps: 508 1. If the signature representative s is not between 0 and n-1, output 509 "invalid" and stop. 511 2. Let m = s^e mod n. 513 3. Output m. 515 6. Overview of schemes 517 A scheme combines cryptographic primitives and other techniques to 518 achieve a particular security goal. Two types of scheme are specified in 519 this document: encryption schemes and signature schemes with appendix. 521 The schemes specified in this document are limited in scope in that 522 their operations consist only of steps to process data with a key, and 523 do not include steps for obtaining or validating the key. Thus, in 524 addition to the scheme operations, an application will typically include 525 key management operations by which parties may select public and private 526 keys for a scheme operation. The specific additional operations and 527 other details are outside the scope of this document. 529 As was the case for the cryptographic primitives (Section 5), the 530 specifications of scheme operations assume that certain conditions are 531 met by the inputs, in particular that public and private keys are valid. 532 The behavior of an implementation is thus unspecified when a key is 533 invalid. The impact of such unspecified behavior depends on the 534 application. Possible means of addressing key validation include 535 explicit key validation by the application; key validation within the 536 public-key infrastructure; and assignment of liability for operations 537 performed with an invalid key to the party who generated the key. 539 7. Encryption schemes 541 An encryption scheme consists of an encryption operation and a 542 decryption operation, where the encryption operation produces a 543 ciphertext from a message with a recipient's public key, and the 544 decryption operation recovers the message from the ciphertext with the 545 recipient's corresponding private key. 547 An encryption scheme can be employed in a variety of applications. A 548 typical application is a key establishment protocol, where the message 549 contains key material to be delivered confidentially from one party to 550 another. For instance, PKCS #7 [21] employs such a protocol to deliver a 551 content-encryption key from a sender to a recipient; the encryption 552 schemes defined here would be suitable key-encryption algorithms in that 553 context. 555 Two encryption schemes are specified in this document: RSAES-OAEP and 556 RSAES-PKCS1-v1_5. RSAES-OAEP is recommended for new applications; RSAES- 557 PKCS1-v1_5 is included only for compatibility with existing 558 applications, and is not recommended for new applications. 560 The encryption schemes given here follow a general model similar to that 561 employed in IEEE P1363, by combining encryption and decryption 562 primitives with an encoding method for encryption. The encryption 563 operations apply a message encoding operation to a message to produce an 564 encoded message, which is then converted to an integer message 565 representative. An encryption primitive is applied to the message 566 representative to produce the ciphertext. Reversing this, the decryption 567 operations apply a decryption primitive to the ciphertext to recover a 568 message representative, which is then converted to an octet string 569 encoded message. A message decoding operation is applied to the encoded 570 message to recover the message and verify the correctness of the 571 decryption. 573 7.1 RSAES-OAEP 575 RSAES-OAEP combines the RSAEP and RSADP primitives (Sections 5.1.1 and 576 5.1.2) with the EME-OAEP encoding method (Section 9.1.1) EME-OAEP is 577 based on the method found in [2]. It is compatible with the IFES scheme 578 defined in the draft P1363 where the encryption and decryption 579 primitives are IFEP-RSA and IFDP-RSA and the message encoding method is 580 EME-OAEP. RSAES-OAEP can operate on messages of length up to k-2-2hLen 581 octets, where hLen is the length of the hash function output for EME- 582 OAEP and k is the length in octets of the recipient's RSA modulus. 583 Assuming that the hash function in EME-OAEP has appropriate properties, 584 and the key size is sufficiently large, RSAEP-OAEP provides "plaintext- 585 aware encryption," meaning that it is computationally infeasible to 586 obtain full or partial information about a message from a ciphertext, 587 and computationally infeasible to generate a valid ciphertext without 588 knowing the corresponding message. Therefore, a chosen-ciphertext attack 589 is ineffective against a plaintext-aware encryption scheme such as 590 RSAES-OAEP. 592 Both the encryption and the decryption operations of RSAES-OAEP take the 593 value of the parameter string P as input. In this version of PKCS #1, P 594 is an octet string that is specified explicitly. See Section 11.2.1 for 595 the relevant ASN.1 syntax. We briefly note that to receive the full 596 security benefit of RSAES-OAEP, it should not be used in a protocol 597 involving RSAES-PKCS1-v1_5. It is possible that in a protocol on which 598 both encryption schemes are present, an adaptive chosen ciphertext 599 attack such as [4] would be useful. 601 Both the encryption and the decryption operations of RSAES-OAEP take 602 the value of the parameter string P as input. In this version of 603 PKCS #1, P is an octet string that is specified explicitly. See 604 Section 11.2.1 for the relevant ASN.1 syntax. 606 7.1.1 Encryption operation 608 RSAES-OAEP-ENCRYPT ((n, e), M, P) 610 Input: 611 (n, e) recipient's RSA public key 613 M message to be encrypted, an octet string of length at 614 most k-2-2hLen, where k is the length in octets of the 615 modulus n and hLen is the length in octets of the hash 616 function output for EME-OAEP 618 P encoding parameters, an octet string that may be empty 620 Output: 621 C ciphertext, an octet string of length k; or "message too 622 long" 624 Assumptions: public key (n, e) is valid 626 Steps: 628 1. Apply the EME-OAEP encoding operation (Section 9.1.1.2) to the 629 message M and the encoding parameters P to produce an encoded message EM 630 of length k-1 octets: 632 EM = EME-OAEP-ENCODE (M, P, k-1) 634 If the encoding operation outputs "message too long," then output 635 "message too long" and stop. 636 2. Convert the encoded message EM to an integer message representative 637 m: m = OS2IP (EM) 639 3.Apply the RSAEP encryption primitive (Section 5.1.1) to the public 640 key (n, e) and the message representative m to produce an integer 641 ciphertext representative c: 643 c = RSAEP ((n, e), m) 645 4.Convert the ciphertext representative c to a ciphertext C of length k 646 octets: C = I2OSP (c, k) 648 5.Output the ciphertext C. 650 7.1.2 Decryption operation 652 RSAES-OAEP-DECRYPT (K, C, P) 653 Input: 654 K recipient's RSA private key 655 C ciphertext to be decrypted, an octet string of length 656 k, where k is the length in octets of the modulus n 657 P encoding parameters, an octet string that may be empty 659 Output: 660 M message, an octet string of length at most k-2-2hLen, 661 where hLen is the length in octets of the hash 662 function output for EME-OAEP; or "decryption error" 664 Steps: 666 1. If the length of the ciphertext C is not k octets, output "decryption 667 error" and stop. 669 2. Convert the ciphertext C to an integer ciphertext representative c: 670 c = OS2IP (C). 672 3. Apply the RSADP decryption primitive (Section 5.1.2) to the private 673 key K and the ciphertext representative c to produce an integer message 674 representative m: 676 m = RSADP (K, c) 678 If RSADP outputs "ciphertext out of range," then output "decryption 679 error" and stop. 681 4. Convert the message representative m to an encoded message EM of 682 length k-1 octets: EM = I2OSP (m, k-1) 684 If I2OSP outputs "integer too large," then output "decryption error" and 685 stop. 687 5. Apply the EME-OAEP decoding operation to the encoded message EM and 688 the encoding parameters P to recover a message M: 690 M = EME-OAEP-DECODE (EM, P) 692 If the decoding operation outputs "decoding error," then output 693 "decryption error" and stop. 695 6. Output the message M. 697 Note. It is important that the error messages output in steps 4 and 5 be 698 the same, otherwise an adversary may be able to extract useful 699 information from the type of error message received. Error message 700 information is used to mount a chosen-ciphertext attack on PKCS #1 v1.5 701 encrypted messages in [4]. 703 7.2 RSAES-PKCS1-v1_5 704 RSAES-PKCS1-v1_5 combines the RSAEP and RSADP primitives with the EME- 705 PKCS1-v1_5 encoding method. It is the same as the encryption scheme in 706 PKCS #1 v1.5. RSAES-PKCS1-v1_5 can operate on messages of length up to 707 k-11 octets, although care should be taken to avoid certain attacks on 708 low-exponent RSA due to Coppersmith, et al. when long messages are 709 encrypted (see the third bullet in the notes below and [7]). 711 RSAES-PKCS1-v1_5 does not provide "plaintext aware" encryption. In 712 particular, it is possible to generate valid ciphertexts without knowing 713 the corresponding plaintexts, with a reasonable probability of success. 714 This ability can be exploited in a chosen ciphertext attack as shown in 715 [4]. Therefore, if RSAES-PKCS1-v1_5 is to be used, certain easily 716 implemented countermeasures should be taken to thwart the attack found 717 in [4]. The addition of structure to the data to be encoded, rigorous 718 checking of PKCS #1 v1.5 conformance and other redundancy in decrypted 719 messages, and the consolidation of error messages in a client-server 720 protocol based on PKCS #1 v1.5 can all be effective countermeasures and 721 don't involve changes to a PKCS #1 v1.5-based protocol. These and other 722 countermeasures are discussed in [5]. 724 Notes. The following passages describe some security recommendations 725 pertaining to the use of RSAES-PKCS1-v1_5. Recommendations from version 726 1.5 of this document are included as well as new recommendations 727 motivated by cryptanalytic advances made in the intervening years. 729 -It is recommended that the pseudorandom octets in EME-PKCS1-v1_5 be 730 generated independently for each encryption process, especially if the 731 same data is input to more than one encryption process. Hastad's results 732 [13] are one motivation for this recommendation. 734 -The padding string PS in EME-PKCS1-v1_5 is at least eight octets long, 735 which is a security condition for public-key operations that prevents an 736 attacker from recovering data by trying all possible encryption blocks. 738 -The pseudorandom octets can also help thwart an attack due to 739 Coppersmith et al. [7] when the size of the message to be encrypted is 740 kept small. The attack works on low-exponent RSA when similar messages 741 are encrypted with the same public key. More specifically, in one flavor 742 of the attack, when two inputs to RSAEP agree on a large fraction of 743 bits (8/9) and low-exponent RSA (e = 3) is used to encrypt both of them, 744 it may be possible to recover both inputs with the attack. Another 745 flavor of the attack is successful in decrypting a single ciphertext 746 when a large fraction (2/3) of the input to RSAEP is already known. For 747 typical applications, the message to be encrypted is short (e.g., a 128- 748 bit symmetric key) so not enough information will be known or common 749 between two messages to enable the attack. However, if a long message is 750 encrypted, or if part of a message is known, then the attack may be a 751 concern. In any case, the RSAEP-OAEP scheme overcomes the attack. 753 7.2.1 Encryption operation 755 RSAES-PKCS1-V1_5-ENCRYPT ((n, e), M) 756 Input: 757 (n, e) recipient's RSA public key 758 M message to be encrypted, an octet string of length at 759 most k-11 octets, where k is the length in octets of the 760 modulus n 762 Output: 763 C ciphertext, an octet string of length k; or "message too 764 long" 766 Steps: 768 1. Apply the EME-PKCS1-v1_5 encoding operation (Section 9.1.2.1) to the 769 message M to produce an encoded message EM of length k-1 octets: 771 EM = EME-PKCS1-V1_5-ENCODE (M, k-1) 773 If the encoding operation outputs "message too long," then output 774 "message too long" and stop. 776 2. Convert the encoded message EM to an integer message representative 777 m: m = OS2IP (EM) 779 3. Apply the RSAEP encryption primitive (Section 5.1.1) to the public 780 key (n, e) and the message representative m to produce an integer 781 ciphertext representative c: c = RSAEP ((n, e), m) 783 4. Convert the ciphertext representative c to a ciphertext C of length k 784 octets: C = I2OSP (c, k) 786 5. Output the ciphertext C. 788 7.2.2 Decryption operation 790 RSAES-PKCS1-V1_5-DECRYPT (K, C) 792 Input: 793 K recipient's RSA private key 794 C ciphertext to be decrypted, an octet string of length k, 795 where k is the length in octets of the modulus n 797 Output: 798 M message, an octet string of length at most k-11; or 799 "decryption error" 801 Steps: 803 1. If the length of the ciphertext C is not k octets, output "decryption 804 error" and stop. 806 2. Convert the ciphertext C to an integer ciphertext representative c: 807 c = OS2IP (C). 809 3. Apply the RSADP decryption primitive to the private key (n, d) and 810 the ciphertext representative c to produce an integer message 811 representative m: m = RSADP ((n, d), c). 813 If RSADP outputs "ciphertext out of range," then output "decryption 814 error" and stop. 816 4. Convert the message representative m to an encoded message EM of 817 length k-1 octets: EM = I2OSP (m, k-1) 819 If I2OSP outputs "integer too large," then output "decryption error" and 820 stop. 822 5.Apply the EME-PKCS1-v1_5 decoding operation to the encoded message EM 823 to recover a message M: M = EME-PKCS1-V1_5-DECODE (EM). 825 If the decoding operation outputs "decoding error," then output 826 "decryption error" and stop. 828 6. Output the message M. 830 Note. It is important that only one type of error message is output by 831 EME-PKCS1-v1_5, as ensured by steps 4 and 5. If this is not done, then 832 an adversary may be able to use information extracted form the type of 833 error message received to mount a chosen-ciphertext attack such as the 834 one found in [4]. 836 8. Signature schemes with appendix 838 A signature scheme with appendix consists of a signature generation 839 operation and a signature verification operation, where the signature 840 generation operation produces a signature from a message with a signer's 841 private key, and the signature verification operation verifies the 842 signature on the message with the signer's corresponding public key. 843 To verify a signature constructed with this type of scheme it is 844 necessary to have the message itself. In this way, signature schemes 845 with appendix are distinguished from signature schemes with message 846 recovery, which are not supported in this document. 848 A signature scheme with appendix can be employed in a variety of 849 applications. For instance, X.509 [6] employs such a scheme to 850 authenticate the content of a certificate; the signature scheme with 851 appendix defined here would be a suitable signature algorithm in that 852 context. A related signature scheme could be employed in PKCS #7 [21], 853 although for technical reasons, the current version of PKCS #7 separates 854 a hash function from a signature scheme, which is different than what is 855 done here. 857 One signature scheme with appendix is specified in this document: 858 RSASSA-PKCS1-v1_5. 860 The signature scheme with appendix given here follows a general model 861 similar to that employed in IEEE P1363, by combining signature and 862 verification primitives with an encoding method for signatures. The 863 signature generation operations apply a message encoding operation to a 864 message to produce an encoded message, which is then converted to an 865 integer message representative. A signature primitive is then applied to 866 the message representative to produce the signature. The signature 867 verification operations apply a signature verification primitive to the 868 signature to recover a message representative, which is then converted 869 to an octet string. The message encoding operation is again applied to 870 the message, and the result is compared to the recovered octet string. 871 If there is a match, the signature is considered valid. (Note that this 872 approach assumes that the signature and verification primitives have the 873 message-recovery form and the encoding method is deterministic, as is 874 the case for RSASP1/RSAVP1 and EMSA-PKCS1-v1_5. The signature generation 875 and verification operations have a different form in P1363 for other 876 primitives and encoding methods.) 878 Editor's note. RSA Laboratories is investigating the possibility of 879 including a scheme based on the PSS encoding methods specified in [3], 880 which would be recommended for new applications. 882 8.1 RSASSA-PKCS1-v1_5 884 RSASSA-PKCS1-v1_5 combines the RSASP1 and RSAVP1 primitives with the 885 EME-PKCS1-v1_5 encoding method. It is compatible with the IFSSA scheme 886 defined in the draft P1363 where the signature and verification 887 primitives are IFSP-RSA1 and IFVP-RSA1 and the message encoding method 888 is EMSA-PKCS1-v1_5 (which is not defined in P1363). The length of 889 messages on which RSASSA-PKCS1-v1_5 can operate is either unrestricted 890 or constrained by a very large number, depending on the hash function 891 underlying the message encoding method. 893 Assuming that the hash function in EMSA-PKCS1-v1_5 has appropriate 894 properties and the key size is sufficiently large, RSASSA-PKCS1-v1_5 895 provides secure signatures, meaning that it is computationally 896 infeasible to generate a signature without knowing the private key, and 897 computationally infeasible to find a message with a given signature or 898 two messages with the same signature. Also, in the encoding method EMSA- 899 PKCS1-v1_5, a hash function identifier is embedded in the encoding. 900 Because of this feature, an adversary must invert or find collisions of 901 the particular hash function being used; attacking a different hash 902 function than the one selected by the signer is not useful to the 903 adversary. 905 8.1.1 Signature generation operation 907 RSASSA-PKCS1-V1_5-SIGN (K, M) 908 Input: 909 K signer's RSA private ke 910 M message to be signed, an octet string 912 Output: 913 S signature, an octet string of length k, where k is the 914 length in octets of the modulus n; "message too long" or 915 "modulus too short" 917 Steps: 919 1. Apply the EMSA-PKCS1-v1_5 encoding operation (Section 9.2.1) to the 920 message M to produce an encoded message EM of length k-1 octets: 922 EM = EMSA-PKCS1-V1_5-ENCODE (M, k-1) 924 If the encoding operation outputs "message too long," then output 925 "message too long" and stop. If the encoding operation outputs "intended 926 encoded message length too short" then output "modulus too short". 928 2. Convert the encoded message EM to an integer message representative 929 m: m = OS2IP (EM) 931 3. Apply the RSASP1 signature primitive (Section 5.2.1) to the private 932 key K and the message representative m to produce an integer signature 933 representative s: s = RSASP1 (K, m) 935 4. Convert the signature representative s to a signature S of length k 936 octets: S = I2OSP (s, k) 938 5. Output the signature S. 940 8.1.2 Signature verification operation 942 RSASSA-PKCS1-V1_5-VERIFY ((n, e), M, S) 944 Input: 945 (n, e) signer's RSA public key 946 M message whose signature is to be verified, an octet string 947 S signature to be verified, an octet string of length k, 948 where k is the length in octets of the modulus n 950 Output: "valid signature," "invalid signature," or "message too long", 951 or "modulus too short" 953 Steps: 955 1. If the length of the signature S is not k octets, output "invalid 956 signature" and stop. 958 2. Convert the signature S to an integer signature representative s: 960 s = OS2IP (S) 962 3. Apply the RSAVP1 verification primitive (Section 5.2.2) to the public 963 key (n, e) and the signature representative s to produce an integer 964 message representative m: 966 m = RSAVP1 ((n, e), s) 968 If RSAVP1 outputs "invalid" then output "invalid signature" and stop. 970 4. Convert the message representative m to an encoded message EM of 971 length k-1 octets: EM = I2OSP (m, k-1) 973 If I2OSP outputs "integer too large," then output "invalid signature" 974 and stop. 976 5. Apply the EMSA-PKCS1-v1_5 encoding operation (Section 9.2.1) to the 977 message M to produce a second encoded message EM' of length k-1 octets: 979 EM' = EMSA-PKCS1-V1_5-ENCODE (M, k-1) 981 If the encoding operation outputs "message too long," then output 982 "message too long" and stop. If the encoding operation outputs "intended 983 encoded message length too short" then output "modulus too short". 985 6. Compare the encoded message EM and the second encoded message EM'. If 986 they are the same, output "valid signature"; otherwise, output "invalid 987 signature." 989 9. Encoding methods 991 Encoding methods consist of operations that map between octet string 992 messages and integer message representatives. 994 Two types of encoding method are considered in this document: encoding 995 methods for encryption, encoding methods for signatures with appendix. 997 9.1 Encoding methods for encryption 999 An encoding method for encryption consists of an encoding operation and 1000 a decoding operation. An encoding operation maps a message M to a 1001 message representative EM of a specified length; the decoding operation 1002 maps a message representative EM back to a message. The encoding and 1003 decoding operations are inverses. 1005 The message representative EM will typically have some structure that 1006 can be verified by the decoding operation; the decoding operation will 1007 output "decoding error" if the structure is not present. The encoding 1008 operation may also introduce some randomness, so that different 1009 applications of the encoding operation to the same message will produce 1010 different representatives. 1012 Two encoding methods for encryption are employed in the encryption 1013 schemes and are specified here: EME-OAEP and EME-PKCS1-v1_5. 1015 9.1.1 EME-OAEP 1017 This encoding method is parameterized by the choice of hash function and 1018 mask generation function. Suggested hash and mask generation functions 1019 are given in Section 10. This encoding method is based on the method 1020 found in [2]. 1022 9.1.1.1 Encoding operation 1024 EME-OAEP-ENCODE (M, P, emLen) 1026 Options: 1027 Hash hash function (hLen denotes the length in octet of the 1028 hash function output) 1029 MGF mask generation function 1031 Input: 1032 M message to be encoded, an octet string of length at most 1033 emLen- 1-2hLen 1034 P encoding parameters, an octet string 1035 emLen intended length in octets of the encoded message, at least 1036 2hLen+1 1038 Output: 1039 EM encoded message, an octet string of length emLen; 1040 "message too long" or "parameter string too long" 1042 Steps: 1044 1. If the length of P is greater than the input limitation for 1045 the hash function (2^61-1 octets for SHA-1) then output "parameter 1046 string too long" and stop. 1048 2. If ||M|| > emLen-2hLen-1 then output "message too long" and stop. 1050 3. Generate an octet string PS consisting of emLen-||M||-2hLen-1 zero 1051 octets. The length of PS may be 0. 1053 4. Let pHash = Hash(P), an octet string of length hLen. 1055 5. Concatenate pHash, PS, the message M, and other padding to form a data 1056 block DB as: DB = pHash || PS || 01 || M 1058 6. Generate a random octet string seed of length hLen. 1060 7. Let dbMask = MGF(seed, emLen-hLen). 1062 8. Let maskedDB = DB \xor dbMask. 1064 9. Let seedMask = MGF(maskedDB, hLen). 1066 10. Let maskedSeed = seed \xor seedMask. 1068 11. Let EM = maskedSeed || maskedDB. 1070 12. Output EM. 1072 9.1.1.2 Decoding operation 1073 EME-OAEP-DECODE (EM, P) 1075 Options: 1076 Hash hash function (hLen denotes the length in octet of the hash 1077 function output) 1079 MGF mask generation function 1081 Input: 1083 EM encoded message, an octet string of length at least 2hLen+1 1084 P encoding parameters, an octet string 1086 Output: 1087 M recovered message, an octet string of length at most ||EM||-1- 1088 2hLen; or "decoding error" 1090 Steps: 1092 1. If the length of P is greater than the input limitation for 1093 the hash function (2^61-1 octets for SHA-1) then output "parameter 1094 string too long" and stop. 1096 2. If ||EM|| < 2hLen+1, then output "decoding error" and stop. 1098 3. Let maskedSeed be the first hLen octets of EM and let maskedDB be the 1099 remaining ||EM|| - hLen octets. 1101 4. Let seedMask = MGF(maskedDB, hLen). 1103 5. Let seed = maskedSeed \xor seedMask. 1105 6. Let dbMask = MGF(seed, ||EM|| - hLen). 1107 7. Let DB = maskedDB \xor dbMask. 1109 8. Let pHash = Hash(P), an octet string of length hLen. 1111 9. Separate DB into an octet string pHash' consisting of the first hLen 1112 octets of DB, a (possibly empty) octet string PS consisting of 1113 consecutive zero octets following pHash', and a message M as: 1115 DB = pHash' || PS || 01 || M 1117 If there is no 01 octet to separate PS from M, output "decoding error" 1118 and stop. 1120 10. If pHash' does not equal pHash, output "decoding error" and stop. 1122 11. Output M. 1124 9.1.2 EME-PKCS1-v1_5 1126 This encoding method is the same as in PKCS #1 v1.5, Section 8: 1127 Encryption Process. 1129 9.1.2.1 Encoding operation 1131 EME-PKCS1-V1_5-ENCODE (M, emLen) 1133 Input: 1134 M message to be encoded, an octet string of length at most emLen-10 1135 emLen intended length in octets of the encoded message 1137 Output: 1138 EM encoded message, an octet string of length emLen; or "message too 1139 long" 1141 Steps: 1143 1. If the length of the message M is greater than emLen - 10 octets, 1144 output "message too long" and stop. 1146 2. Generate an octet string PS of length emLen-||M||-2 consisting of 1147 pseudorandomly generated nonzero octets. The length of PS will be at 1148 least 8 octets. 1150 3. Concatenate PS, the message M, and other padding to form the encoded 1151 message EM as: 1153 EM = 02 || PS || 00 || M 1155 4. Output EM. 1157 9.1.2.2 Decoding operation 1159 EME-PKCS1-V1_5-DECODE (EM) 1161 Input: 1162 EM encoded message, an octet string of length at least 10 1164 Output: 1165 M recovered message, an octet string of length at most ||EM||-10; 1166 or "decoding error" 1168 Steps: 1170 1. If the length of the encoded message EM is less than 10, output 1171 "decoding error" and stop. 1173 2. Separate the encoded message EM into an octet string PS consisting of 1174 nonzero octets and a message M as: EM = 02 || PS || 00 || M. 1176 If the first octet of EM is not 02, or if there is no 00 octet to 1177 separate PS from M, output "decoding error" and stop. 1179 3. If the length of PS is less than 8 octets, output "decoding error" and stop. 1181 4. Output M. 1183 9.2 Encoding methods for signatures with appendix 1185 An encoding method for signatures with appendix, for the purposes of 1186 this document, consists of an encoding operation. An encoding operation 1187 maps a message M to a message representative EM of a specified length. 1188 (In future versions of this document, encoding methods may be added that 1189 also include a decoding operation.) 1191 One encoding method for signatures with appendix is employed in the 1192 encryption schemes and is specified here: EMSA-PKCS1-v1_5. 1194 9.2.1 EMSA-PKCS1-v1_5 1196 This encoding method only has an encoding operation. 1198 EMSA-PKCS1-v1_5-ENCODE (M, emLen) 1200 Option: 1201 Hash hash function (hLen denotes the length in octet of the hash 1202 function output) 1204 Input: 1205 M message to be encoded 1206 emLen intended length in octets of the encoded message, at least 1207 ||T|| + 10, where T is the DER encoding of a certain value computed 1208 during the encoding operation 1210 Output: 1211 EM encoded message, an octet string of length emLen; or "message 1212 too long" or "intended encoded message length too short" 1214 Steps: 1216 1. Apply the hash function to the message M to produce a hash value H: 1218 H = Hash(M). 1220 If the hash function outputs "message too long," then output "message 1221 too long". 1223 2. Encode the algorithm ID for the hash function and the hash value into 1224 an ASN.1 value of type DigestInfo (see Section 11) with the 1225 Distinguished Encoding Rules (DER), where the type DigestInfo has the 1226 syntax 1227 DigestInfo::=SEQUENCE{ 1228 digestAlgorithm AlgorithmIdentifier, 1229 digest OCTET STRING } 1231 The first field identifies the hash function and the second contains the 1232 hash value. Let T be the DER encoding. 1234 3. If emLen is less than ||T|| + 10 then output "intended encoded 1235 message length too short". 1237 4. Generate an octet string PS consisting of emLen-||T||-2 octets with 1238 value FF (hexadecimal). The length of PS will be at least 8 octets. 1240 5. Concatenate PS, the DER encoding T, and other padding to form the 1241 encoded message EM as: EM = 01 || PS || 00 || T 1243 6. Output EM. 1245 10. Auxiliary Functions 1247 This section specifies the hash functions and the mask generation 1248 functions that are mentioned in the encoding methods (Section 9). 1250 10.1 Hash Functions 1252 Hash functions are used in the operations contained in Sections 7, 8 and 1253 9. Hash functions are deterministic, meaning that the output is 1254 completely determined by the input. Hash functions take octet strings of 1255 variable length, and generate fixed length octet strings. The hash 1256 functions used in the operations contained in Sections 7, 8 and 9 should 1257 be collision resistant. This means that it is infeasible to find two 1258 distinct inputs to the hash function that produce the same output. A 1259 collision resistant hash function also has the desirable property of 1260 being one-way; this means that given an output, it is infeasible to find 1261 an input whose hash is the specified output. The property of collision 1262 resistance is especially desirable for RSASSA-PKCS1-v1_5, as it makes it 1263 infeasible to forge signatures. In addition to the requirements, the 1264 hash function should yield a mask generation function (Section 10.2) 1265 with pseudorandom output. 1267 Three hash functions are recommended for the encoding methods in this 1268 document: MD2 [15], MD5 [17], and SHA-1 [16]. For the EME-OAEP encoding 1269 method, only SHA-1 is recommended. For the EMSA-PKCS1-v1_5 encoding 1270 method, SHA-1 is recommended for new applications. MD2 and MD5 are 1271 recommended only for compatibility with existing applications based on 1272 PKCS #1 v1.5. 1274 The hash functions themselves are not defined here; readers are referred 1275 to the appropriate references ([15], [17] and [16]). 1277 Note. Version 1.5 of this document also allowed for the use of MD4 in 1278 signature schemes. The cryptanalysis of MD4 has progressed significantly 1279 in the intervening years. For example, Dobbertin [10] demonstrated how 1280 to find collisions for MD4 and that the first two rounds of MD4 are not 1281 one-way [11]. Because of these results and others (e.g. [9]), MD4 is no 1282 longer recommended. There have also been advances in the cryptanalysis 1283 of MD2 and MD5, although not enough to warrant removal from existing 1284 applications. Rogier and Chauvaud [19] demonstrated how to find 1285 collisions in a modified version of MD2. No one has demonstrated how to 1286 find collisions for the full MD5 algorithm, although partial results 1287 have been found (e.g. [8]). For new applications, to address these 1288 concerns, SHA-1 is preferred. 1290 10.2 Mask Generation Functions 1292 A mask generation function takes an octet string of variable length and 1293 a desired output length as input, and outputs an octet string of the 1294 desired length. There may be restrictions on the length of the input and 1295 output octet strings, but such bounds are generally very large. Mask 1296 generation functions are deterministic; the octet string output is 1297 completely determined by the input octet string. The output of a mask 1298 generation function should be pseudorandom, that is, if the seed to the 1299 function is unknown, it should be infeasible to distinguish the output 1300 from a truly random string. The plaintext-awareness of RSAES-OAEP 1301 relies on the random nature of the output of the mask generation 1302 function, which in turn relies on the random nature of the underlying 1303 hash. 1305 One mask generation function is recommended for the encoding methods in 1306 this document, and is defined here: MGF1, which is based on a hash 1307 function. Future versions of this document may define other mask 1308 generation functions. 1310 10.2.1 MGF1 1312 MGF1 is a Mask Generation Function based on a hash function. 1314 MGF1 (Z, l) 1316 Options: 1317 Hash hash function (hLen denotes the length in octets of the hash 1318 function output) 1320 Input: 1321 Z seed from which mask is generated, an octet string 1322 l intended length in octets of the mask, at most 2^32(hLen) 1324 Output: 1325 mask mask, an octet string of length l; or "mask too long" 1327 Steps: 1329 1.If l > 2^32(hLen), output "mask too long" and stop. 1331 2.Let T be the empty octet string. 1333 3.For counter from 0 to \lceil{l / hLen}\rceil-1, do the following: 1335 a.Convert counter to an octet string C of length 4 with the primitive 1336 I2OSP: C = I2OSP (counter, 4) 1338 b.Concatenate the hash of the seed Z and C to the octet string T: 1339 T = T || Hash (Z || C) 1341 4.Output the leading l octets of T as the octet string mask. 1343 11. ASN.1 syntax 1345 11.1 Key representation 1347 This section defines ASN.1 object identifiers for RSA public and private 1348 keys, and defines the types RSAPublicKey and RSAPrivateKey. The intended 1349 application of these definitions includes X.509 certificates, PKCS #8 1350 [22], and PKCS #12 [23]. 1352 The object identifier rsaEncryption identifies RSA public and private 1353 keys as defined in Sections 11.1.1 and 11.1.2. The parameters field 1354 associated with this OID in an AlgorithmIdentifier shall have type NULL. 1356 rsaEncryption OBJECT IDENTIFIER ::= {pkcs-1 1} 1358 All of the definitions in this section are the same as in PKCS #1 v1.5. 1360 11.1.1 Public-key syntax 1362 An RSA public key should be represented with the ASN.1 type 1363 RSAPublicKey: 1365 RSAPublicKey::=SEQUENCE{ 1366 modulus INTEGER, -- n 1367 publicExponent INTEGER -- e } 1369 (This type is specified in X.509 and is retained here for 1370 compatibility.) 1372 The fields of type RSAPublicKey have the following meanings: 1373 -modulus is the modulus n. 1374 -publicExponent is the public exponent e. 1376 11.1.2 Private-key syntax 1378 An RSA private key should be represented with ASN.1 type RSAPrivateKey: 1380 RSAPrivateKey ::= SEQUENCE { 1381 version Version, 1382 modulus INTEGER, -- n 1383 publicExponent INTEGER, -- e 1384 privateExponent INTEGER, -- d 1385 prime1 INTEGER, -- p 1386 prime2 INTEGER, -- q 1387 exponent1 INTEGER, -- d mod (p-1) 1388 exponent2 INTEGER, -- d mod (q-1) 1389 coefficient INTEGER -- (inverse of q) mod p } 1391 Version ::= INTEGER 1393 The fields of type RSAPrivateKey have the following meanings: 1394 -version is the version number, for compatibility with future revisions 1395 of this document. It shall be 0 for this version of the document. 1396 -modulus is the modulus n. 1397 -publicExponent is the public exponent e. 1398 -privateExponent is the private exponent d. 1399 -prime1 is the prime factor p of n. 1400 -prime2 is the prime factor q of n. 1401 -exponent1 is d mod (p-1). 1402 -exponent2 is d mod (q-1). 1403 -coefficient is the Chinese Remainder Theorem coefficient q-1 mod p. 1405 11.2 Scheme identification 1407 This section defines object identifiers for the encryption and signature 1408 schemes. The schemes compatible with PKCS #1 v1.5 have the same 1409 definitions as in PKCS #1 v1.5. The intended application of these 1410 definitions includes X.509 certificates and PKCS #7. 1412 11.2.1 Syntax for RSAES-OAEP 1414 The object identifier id-RSAES-OAEP identifies the RSAES-OAEP encryption 1415 scheme. 1417 id-RSAES-OAEP OBJECT IDENTIFIER ::= {pkcs-1 7} 1419 The parameters field associated with this OID in an AlgorithmIdentifier 1420 shall have type RSAEP-OAEP-params: 1422 RSAES-OAEP-params ::= SEQUENCE { 1423 hashFunc [0] AlgorithmIdentifier {{oaepDigestAlgorithms}} 1424 DEFAULT sha1Identifier, 1425 maskGenFunc [1] AlgorithmIdentifier {{pkcs1MGFAlgorithms}} 1426 DEFAULT mgf1SHA1Identifier, 1427 pSourceFunc [2] AlgorithmIdentifier 1428 {{pkcs1pSourceAlgorithms}} 1429 DEFAULT pSpecifiedEmptyIdentifier } 1431 The fields of type RSAES-OAEP-params have the following meanings: 1433 -hashFunc identifies the hash function. It shall be an algorithm ID with 1434 an OID in the set oaepDigestAlgorithms, which for this version shall 1435 consist of id-sha1, identifying the SHA-1 hash function. The parameters 1436 field for id-sha1 shall have type NULL. 1438 oaepDigestAlgorithms ALGORITHM-IDENTIFIER ::= { 1439 {NULL IDENTIFIED BY id-sha1} } 1441 id-sha1 OBJECT IDENTIFIER ::= 1442 {iso(1) identified-organization(3) oiw(14) secsig(3) 1443 algorithms(2) 26} 1445 The default hash function is SHA-1: 1446 sha1Identifier ::= AlgorithmIdentifier {id-sha1, NULL} 1448 -maskGenFunc identifies the mask generation function. It shall be an 1449 algorithm ID with an OID in the set pkcs1MGFAlgorithms, which for this 1450 version shall consist of id-mgf1, identifying the MGF1 mask generation 1451 function (see Section 10.2.1). The parameters field for id-mgf1 shall 1452 have type AlgorithmIdentifier, identifying the hash function on which 1453 MGF1 is based, where the OID for the hash function shall be in the set 1454 oaepDigestAlgorithms. 1456 pkcs1MGFAlgorithms ALGORITHM-IDENTIFIER ::= { 1457 {AlgorithmIdentifier {{oaepDigestAlgorithms}} IDENTIFIED 1458 BY id-mgf1} } 1460 id-mgf1 OBJECT IDENTIFIER ::= {pkcs-1 8} 1462 The default mask generation function is MGF1 with SHA-1: 1464 mgf1SHA1Identifier ::= AlgorithmIdentifier { 1465 id-mgf1, sha1Identifier } 1467 -pSourceFunc identifies the source (and possibly the value) of the 1468 encoding parameters P. It shall be an algorithm ID with an OID in the 1469 set pkcs1pSourceAlgorithms, which for this version shall consist of id- 1470 pSpecified, indicating that the encoding parameters are specified 1471 explicitly. The parameters field for id-pSpecified shall have type OCTET 1472 STRING, containing the encoding parameters. 1474 pkcs1pSourceAlgorithms ALGORITHM-IDENTIFIER ::= { 1475 {OCTET STRING IDENTIFIED BY id-pSpecified} } 1477 id-pSpecified OBJECT IDENTIFIER ::= {pkcs-1 9} 1479 The default encoding parameters is an empty string (so that pHash in 1480 EME-OAEP will contain the hash of the empty string): 1482 pSpecifiedEmptyIdentifier ::= AlgorithmIdentifier { 1483 id-pSpecified, OCTET STRING SIZE (0) } 1485 If all of the default values of the fields in RSAES-OAEP-params are 1486 used, then the algorithm identifier will have the following value: 1488 RSAES-OAEP-Default-Identifier ::= AlgorithmIdentifier { 1489 id-RSAES-OAEP, 1490 {sha1Identifier, 1491 mgf1SHA1Identifier, 1492 pSpecifiedEmptyIdentifier } } 1494 11.2.2 Syntax for RSAES-PKCS1-v1_5 1496 The object identifier rsaEncryption (Section 11.1) identifies the RSAES- 1497 PKCS1-v1_5 encryption scheme. The parameters field associated with this 1498 OID in an AlgorithmIdentifier shall have type NULL. This is the same as 1499 in PKCS #1 v1.5. 1501 RsaEncryption OBJECT IDENTIFIER ::= {PKCS-1 1} 1503 11.2.3 Syntax for RSASSA-PKCS1-v1_5 1505 The object identifier for RSASSA-PKCS1-v1_5 shall be one of the 1506 following. The choice of OID depends on the choice of hash algorithm: 1507 MD2, MD5 or SHA-1. Note that if either MD2 or MD5 is used then the OID 1508 is just as in PKCS #1 v1.5. For each OID, the parameters field 1509 associated with this OID in an AlgorithmIdentifier shall have type NULL. 1511 If the hash function to be used is MD2, then the OID should be: 1513 md2WithRSAEncryption ::= {PKCS-1 2} 1515 If the hash function to be used is MD5, then the OID should be: 1517 md5WithRSAEncryption ::= {PKCS-1 4} 1519 If the hash function to be used is SHA-1, then the OID should be: 1521 sha1WithRSAEncryption ::= {pkcs-1 5} 1523 In the digestInfo type mentioned in Section 9.2.1 the OIDS for the 1524 digest algorithm are the following: 1526 id-SHA1 OBJECT IDENTIFIER ::= 1527 {iso(1) identified-organization(3) oiw(14) secsig(3) algorithms(2) 26 } 1529 md2 OBJECT IDENTIFIER ::= 1530 {iso(1) member-body(2) US(840) rsadsi(113549) digestAlgorithm(2) 2} 1531 md5 OBJECT IDENTIFIER ::= 1532 {iso(1) member-body(2) US(840) rsadsi(113549) digestAlgorithm(2) 5} 1534 The parameters field of the digest algorithm has ASN.1 type NULL for 1535 these OIDs. 1537 12. Patent statement 1539 The Internet Standards Process as defined in RFC 1310 requires a 1540 written statement from the Patent holder that a license will be made 1541 available to applicants under reasonable terms and conditions prior 1542 to approving a specification as a Proposed, Draft or Internet Stan- 1543 dard. 1545 The Internet Society, Internet Architecture Board, Internet Engineer- 1546 ing Steering Group and the Corporation for National Research Initia- 1547 tives take no position on the validity or scope of the following 1548 patents and patent applications, nor on the appropriateness of the 1549 terms of the assurance. The Internet Society and other groups men- 1550 tioned above have not made any determination as to any other 1551 intellectual property rights which may apply to the practice of this 1552 standard. Any further consideration of these matters is the user's 1553 responsibility. 1555 12.1 Patent statement for the RSA algorithm 1557 The Massachusetts Institute of Technology has granted RSA Data Secu- 1558 rity, Inc., exclusive sub-licensing rights to the following patent 1559 issued in the United States: 1561 Cryptographic Communications System and Method ("RSA"), No. 4,405,829 1563 RSA Data Security, Inc. has provided the following statement with 1564 regard to this patent: 1566 It is RSA's business practice to make licenses to its patents 1567 available on reasonable and nondiscriminatory terms. Accordingly, 1568 RSA is willing, upon request, to grant non-exclusive licenses to 1569 such patent on reasonable and non-discriminatory terms and conditions 1570 to those who respect RSA's intellectual property rights and subject to 1571 RSA's then current royalty rate for the patent licensed. The roy- 1572 alty rate for the RSA patent is presently set at 2% of the 1573 licensee's selling price for each product covered by the patent. 1574 Any requests for license information may be directed to: 1576 Director of Licensing 1577 RSA Data Security, Inc. 1578 2955 Campus Drive 1579 Suite 400 1580 San Mateo, CA 94403 1582 A license under RSA's patent(s) does not include any rights to 1583 know-how or other technical information or license under other 1584 intellectual property rights. Such license does not extend to any 1585 activities which constitute infringement or inducement thereto. A 1586 licensee must make his own determination as to whether a license 1587 is necessary under patents of others. 1589 13. Revision history 1591 Versions 1.0-1.3 1593 Versions 1.0-1.3 were distributed to participants in RSA Data Security, 1594 Inc.'s Public-Key Cryptography Standards meetings in February and March 1595 1991. 1597 Version 1.4 1599 Version 1.4 was part of the June 3, 1991 initial public release of PKCS. 1600 Version 1.4 was published as NIST/OSI Implementors' Workshop document 1601 SEC-SIG-91-18. 1603 Version 1.5 1605 Version 1.5 incorporates several editorial changes, including updates to 1606 the references and the addition of a revision history. The following 1607 substantive changes were made: 1608 -Section 10: "MD4 with RSA" signature and verification processes were 1609 added. 1610 -Section 11: md4WithRSAEncryption object identifier was added. 1612 Version 2.0 [DRAFT] 1614 Version 2.0 incorporates major editorial changes in terms of the 1615 document structure, and introduces the RSAEP-OAEP encryption scheme. 1616 This version continues to support the encryption and signature processes 1617 in version 1.5, although the hash algorithm MD4 is no longer allowed due 1618 to cryptanalytic advances in the intervening years. 1620 14. References 1622 [1] ANSI, ANSI X9.44: Key Management Using Reversible Public Key 1623 Cryptography for the Financial Services Industry. Working Draft. 1625 [2] M. Bellare and P. Rogaway. Optimal Asymmetric Encryption- 1626 How to Encrypt with RSA. In Advances in Cryptology-Eurocrypt '94, 1627 pp. 92-111, Springer-Verlag, 1994. 1629 [3] M. Bellare and P. Rogaway. The Exact Security of Digital Signatures 1630 -How to Sign with RSA and Rabin. In Advances in Cryptology-Eurocrypt 1631 '96, pp. 399-416, Springer-Verlag, 1996. 1633 [4] D. Bleichenbacher. Chosen Ciphertext Attacks against Protocols Based on 1634 the RSA Encryption Standard PKCS #1. To appear in Advances in 1635 Cryptology-Crypto '98. 1637 [5] D. Bleichenbacher, B. Kaliski and J. Staddon. Recent Results on PKCS #1: 1638 RSA Encryption Standard. RSA Laboratories' Bulletin, Number 7, June 24, 1639 1998. 1641 [6] CCITT. Recommendation X.509: The Directory-Authentication Framework. 1642 1988. 1644 [7] D. Coppersmith, M. Franklin, J. Patarin and M. Reiter. Low-Exponent 1645 RSA with Related Messages. In Advances in Cryptology-Eurocrypt '96, 1646 pp. 1-9, Springer-Verlag, 1996 1648 [8] B. Den Boer and Bosselaers. Collisions for the Compression 1649 Function of MD5. In Advances in Cryptology-Eurocrypt '93, pp 293-304, 1650 Springer-Verlag, 1994. 1652 [9] B. den Boer, and A. Bosselaers. An Attack on the Last Two Rounds of MD4. 1653 In Advances in Cryptology-Crypto '91, pp.194-203, Springer-Verlag, 1992. 1655 [10] H. Dobbertin. Cryptanalysis of MD4. Fast Software Encryption. Lecture 1656 Notes in Computer Science, Springer-Verlag 1996, pp. 55-72. 1658 [11] H. Dobbertin. Cryptanalysis of MD5 Compress. Presented at the rump 1659 session of Eurocrypt `96, May 14, 1996 1661 [12] H. Dobbertin.The First Two Rounds of MD4 are Not One-Way. Fast Software 1662 Encryption. Lecture Notes in Computer Science, Springer-Verlag 1998, pp. 1663 284-292. 1665 [13] J. Hastad. Solving Simultaneous Modular Equations of Low Degree. 1666 SIAM Journal of Computing, 17, 1988, pp. 336-341. 1668 [14] IEEE. IEEE P1363: Standard Specifications for Public Key Cryptography. 1669 Draft Version 4. 1671 [15] B. Kaliski. RFC 1319: The MD2 Message-Digest Algorithm. Internet 1672 Activities Board, April 1992. 1674 [16] National Institute of Standards and Technology (NIST). FIPS Publication 1675 180-1: Secure Hash Standard. April 1994. 1677 [17] R. Rivest. RFC 1321: The MD5 Message-Digest Algorithm. Internet 1678 Activities Board, April 1992. 1680 [18] R. Rivest, A. Shamir and L. Adleman. A Method for Obtaining Digital 1681 Signatures and Public-Key Cryptosystems. Communications of the ACM, 1682 21(2), pp. 120-126, February 1978. 1684 [19] N. Rogier and P. Chauvaud. The Compression Function of MD2 is not 1685 Collision Free. Presented at Selected Areas of Cryptography `95. 1686 Carleton University, Ottawa, Canada. May 18-19, 1995. 1688 [20] RSA Laboratories. PKCS #1: RSA Encryption Standard. Version 1.5, 1689 November 1993. 1691 [21] RSA Laboratories. PKCS #7: Cryptographic Message Syntax Standard. 1692 Version 1.5, November 1993. 1694 [22] RSA Laboratories. PKCS #8: Private-Key Information Syntax Standard. 1695 Version 1.2, November 1993. 1697 [23] RSA Laboratories. PKCS #12: Personal Information Exchange Syntax 1698 Standard. Version 1.0, DRAFT, April 1997. 1700 Acknowledgements 1702 This document is based on a contribution of RSA Laboratories, a 1703 division of RSA Data Security, Inc. Any substantial use of the text 1704 from this document must acknowledge RSA Data Security, Inc. RSA Data 1705 Security, Inc. requests that all material mentioning or referencing 1706 this document identify this as "RSA Data Security, Inc. PKCS #1 v2.0". 1708 Authors' Addresses 1710 Burt Kaliski 1711 RSA Laboratories East 1712 20 Crosby Drive 1713 Bedford, MA 01730 1714 Phone: (617) 687-7000 1715 EMail: burt@rsa.com 1717 Jessica Staddon 1718 RSA Laboratories West 1719 2955 Campus Drive 1720 Suite 400 1721 San Mateo, CA 94403 1722 Phone: (650) 295-7600 1723 Email: jstaddon@rsa.com 1725 Full Copyright Statement 1727 Copyright (C) The Internet Society (1998). All Rights Reserved. 1729 This document and translations of it may be copied and furnished to 1730 others, and derivative works that comment on or otherwise explain it 1731 or assist in its implementation may be prepared, copied, published 1732 and distributed, in whole or in part, without restriction of any 1733 kind, provided that the above copyright notice and this paragraph are 1734 included on all such copies and derivative works. However, this 1735 document itself may not be modified in any way, such as by removing 1736 the copyright notice or references to the Internet Society or other 1737 Internet organizations, except as needed for the purpose of 1738 developing Internet standards in which case the procedures for 1739 copyrights defined in the Internet Standards process must be 1740 followed, or as required to translate it into languages other than 1741 English. 1743 The limited permissions granted above are perpetual and will not be 1744 revoked by the Internet Society or its successors or assigns. 1746 This document and the information contained herein is provided on an 1747 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 1748 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 1749 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 1750 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 1751 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.