1 2 3 4 5 6 7Network Working Group B. Kaliski 8Request for Comments: 2437 J. Staddon 9Obsoletes: 2313 RSA Laboratories 10Category: Informational October 1998 11 12 13 PKCS #1: RSA Cryptography Specifications 14 Version 2.0 15 16Status of this Memo 17 18 This memo provides information for the Internet community. It does 19 not specify an Internet standard of any kind. Distribution of this 20 memo is unlimited. 21 22Copyright Notice 23 24 Copyright (C) The Internet Society (1998). All Rights Reserved. 25 26Table of Contents 27 28 1. Introduction.....................................2 29 1.1 Overview.........................................3 30 2. Notation.........................................3 31 3. Key types........................................5 32 3.1 RSA public key...................................5 33 3.2 RSA private key..................................5 34 4. Data conversion primitives.......................6 35 4.1 I2OSP............................................6 36 4.2 OS2IP............................................7 37 5. Cryptographic primitives.........................8 38 5.1 Encryption and decryption primitives.............8 39 5.1.1 RSAEP............................................8 40 5.1.2 RSADP............................................9 41 5.2 Signature and verification primitives...........10 42 5.2.1 RSASP1..........................................10 43 5.2.2 RSAVP1..........................................11 44 6. Overview of schemes.............................11 45 7. Encryption schemes..............................12 46 7.1 RSAES-OAEP......................................13 47 7.1.1 Encryption operation............................13 48 7.1.2 Decryption operation............................14 49 7.2 RSAES-PKCS1-v1_5................................15 50 7.2.1 Encryption operation............................17 51 7.2.2 Decryption operation............................17 52 8. Signature schemes with appendix.................18 53 8.1 RSASSA-PKCS1-v1_5...............................19 54 8.1.1 Signature generation operation..................20 55 56 57 58Kaliski & Staddon Informational [Page 1] 59 60RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 61 62 63 8.1.2 Signature verification operation................21 64 9. Encoding methods................................22 65 9.1 Encoding methods for encryption.................22 66 9.1.1 EME-OAEP........................................22 67 9.1.2 EME-PKCS1-v1_5..................................24 68 9.2 Encoding methods for signatures with appendix...26 69 9.2.1 EMSA-PKCS1-v1_5.................................26 70 10. Auxiliary Functions.............................27 71 10.1 Hash Functions..................................27 72 10.2 Mask Generation Functions.......................28 73 10.2.1 MGF1............................................28 74 11. ASN.1 syntax....................................29 75 11.1 Key representation..............................29 76 11.1.1 Public-key syntax...............................30 77 11.1.2 Private-key syntax..............................30 78 11.2 Scheme identification...........................31 79 11.2.1 Syntax for RSAES-OAEP...........................31 80 11.2.2 Syntax for RSAES-PKCS1-v1_5.....................32 81 11.2.3 Syntax for RSASSA-PKCS1-v1_5....................33 82 12 Patent Statement................................33 83 12.1 Patent statement for the RSA algorithm..........34 84 13. Revision history................................35 85 14. References......................................35 86 Security Considerations.........................37 87 Acknowledgements................................37 88 Authors' Addresses..............................38 89 Full Copyright Statement........................39 90 911. Introduction 92 93 This memo is the successor to RFC 2313. This document provides 94 recommendations for the implementation of public-key cryptography 95 based on the RSA algorithm [18], covering the following aspects: 96 97 -cryptographic primitives 98 -encryption schemes 99 -signature schemes with appendix 100 -ASN.1 syntax for representing keys and for identifying the 101 schemes 102 103 The recommendations are intended for general application within 104 computer and communications systems, and as such include a fair 105 amount of flexibility. It is expected that application standards 106 based on these specifications may include additional constraints. The 107 recommendations are intended to be compatible with draft standards 108 currently being developed by the ANSI X9F1 [1] and IEEE P1363 working 109 groups [14]. This document supersedes PKCS #1 version 1.5 [20]. 110 111 112 113 114Kaliski & Staddon Informational [Page 2] 115 116RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 117 118 119 Editor's note. It is expected that subsequent versions of PKCS #1 may 120 cover other aspects of the RSA algorithm such as key size, key 121 generation, key validation, and signature schemes with message 122 recovery. 123 1241.1 Overview 125 126 The organization of this document is as follows: 127 128 -Section 1 is an introduction. 129 -Section 2 defines some notation used in this document. 130 -Section 3 defines the RSA public and private key types. 131 -Sections 4 and 5 define several primitives, or basic mathematical 132 operations. Data conversion primitives are in Section 4, and 133 cryptographic primitives (encryption-decryption, 134 signature-verification) are in Section 5. 135 -Section 6, 7 and 8 deal with the encryption and signature schemes 136 in this document. Section 6 gives an overview. Section 7 defines 137 an OAEP-based [2] encryption scheme along with the method found 138 in PKCS #1 v1.5. Section 8 defines a signature scheme with 139 appendix; the method is identical to that of PKCS #1 v1.5. 140 -Section 9 defines the encoding methods for the encryption and 141 signature schemes in Sections 7 and 8. 142 -Section 10 defines the hash functions and the mask generation 143 function used in this document. 144 -Section 11 defines the ASN.1 syntax for the keys defined in 145 Section 3 and the schemes gives in Sections 7 and 8. 146 -Section 12 outlines the revision history of PKCS #1. 147 -Section 13 contains references to other publications and 148 standards. 149 1502. Notation 151 152 (n, e) RSA public key 153 154 c ciphertext representative, an integer between 0 and n-1 155 156 C ciphertext, an octet string 157 158 d private exponent 159 160 dP p's exponent, a positive integer such that: 161 e(dP)\equiv 1 (mod(p-1)) 162 163 dQ q's exponent, a positive integer such that: 164 e(dQ)\equiv 1 (mod(q-1)) 165 166 e public exponent 167 168 169 170Kaliski & Staddon Informational [Page 3] 171 172RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 173 174 175 EM encoded message, an octet string 176 177 emLen intended length in octets of an encoded message 178 179 H hash value, an output of Hash 180 181 Hash hash function 182 183 hLen output length in octets of hash function Hash 184 185 K RSA private key 186 187 k length in octets of the modulus 188 189 l intended length of octet string 190 191 lcm(.,.) least common multiple of two 192 nonnegative integers 193 194 m message representative, an integer between 195 0 and n-1 196 197 M message, an octet string 198 199 MGF mask generation function 200 201 n modulus 202 203 P encoding parameters, an octet string 204 205 p,q prime factors of the modulus 206 207 qInv CRT coefficient, a positive integer less 208 than p such: q(qInv)\equiv 1 (mod p) 209 210 s signature representative, an integer 211 between 0 and n-1 212 213 S signature, an octet string 214 215 x a nonnegative integer 216 217 X an octet string corresponding to x 218 219 \xor bitwise exclusive-or of two octet strings 220 221 \lambda(n) lcm(p-1, q-1), where n = pq 222 223 224 225 226Kaliski & Staddon Informational [Page 4] 227 228RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 229 230 231 || concatenation operator 232 233 ||.|| octet length operator 234 2353. Key types 236 237 Two key types are employed in the primitives and schemes defined in 238 this document: RSA public key and RSA private key. Together, an RSA 239 public key and an RSA private key form an RSA key pair. 240 2413.1 RSA public key 242 243 For the purposes of this document, an RSA public key consists of two 244 components: 245 246 n, the modulus, a nonnegative integer 247 e, the public exponent, a nonnegative integer 248 249 In a valid RSA public key, the modulus n is a product of two odd 250 primes p and q, and the public exponent e is an integer between 3 and 251 n-1 satisfying gcd (e, \lambda(n)) = 1, where \lambda(n) = lcm (p- 252 1,q-1). A recommended syntax for interchanging RSA public keys 253 between implementations is given in Section 11.1.1; an 254 implementation's internal representation may differ. 255 2563.2 RSA private key 257 258 For the purposes of this document, an RSA private key may have either 259 of two representations. 260 261 1. The first representation consists of the pair (n, d), where the 262 components have the following meanings: 263 264 n, the modulus, a nonnegative integer 265 d, the private exponent, a nonnegative integer 266 267 2. The second representation consists of a quintuple (p, q, dP, dQ, 268 qInv), where the components have the following meanings: 269 270 p, the first factor, a nonnegative integer 271 q, the second factor, a nonnegative integer 272 dP, the first factor's exponent, a nonnegative integer 273 dQ, the second factor's exponent, a nonnegative integer 274 qInv, the CRT coefficient, a nonnegative integer 275 276 In a valid RSA private key with the first representation, the modulus 277 n is the same as in the corresponding public key and is the product 278 of two odd primes p and q, and the private exponent d is a positive 279 280 281 282Kaliski & Staddon Informational [Page 5] 283 284RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 285 286 287 integer less than n satisfying: 288 289 ed \equiv 1 (mod \lambda(n)) 290 291 where e is the corresponding public exponent and \lambda(n) is as 292 defined above. 293 294 In a valid RSA private key with the second representation, the two 295 factors p and q are the prime factors of the modulus n, the exponents 296 dP and dQ are positive integers less than p and q respectively 297 satisfying 298 299 e(dP)\equiv 1(mod(p-1)) 300 e(dQ)\equiv 1(mod(q-1)), 301 302 and the CRT coefficient qInv is a positive integer less than p 303 satisfying: 304 305 q(qInv)\equiv 1 (mod p). 306 307 A recommended syntax for interchanging RSA private keys between 308 implementations, which includes components from both representations, 309 is given in Section 11.1.2; an implementation's internal 310 representation may differ. 311 3124. Data conversion primitives 313 314 Two data conversion primitives are employed in the schemes defined in 315 this document: 316 317 I2OSP: Integer-to-Octet-String primitive 318 OS2IP: Octet-String-to-Integer primitive 319 320 For the purposes of this document, and consistent with ASN.1 syntax, an 321 octet string is an ordered sequence of octets (eight-bit bytes). The 322 sequence is indexed from first (conventionally, leftmost) to last 323 (rightmost). For purposes of conversion to and from integers, the first 324 octet is considered the most significant in the following conversion 325 primitives 326 3274.1 I2OSP 328 329 I2OSP converts a nonnegative integer to an octet string of a specified 330 length. 331 332 I2OSP (x, l) 333 334 335 336 337 338Kaliski & Staddon Informational [Page 6] 339 340RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 341 342 343 Input: 344 x nonnegative integer to be converted 345 l intended length of the resulting octet string 346 347 Output: 348 X corresponding octet string of length l; or 349 "integer too large" 350 351 Steps: 352 353 1. If x>=256^l, output "integer too large" and stop. 354 355 2. Write the integer x in its unique l-digit representation base 256: 356 357 x = x_{l-1}256^{l-1} + x_{l-2}256^{l-2} +... + x_1 256 + x_0 358 359 where 0 <= x_i < 256 (note that one or more leading digits will be 360 zero if x < 256^{l-1}). 361 362 3. Let the octet X_i have the value x_{l-i} for 1 <= i <= l. Output 363 the octet string: 364 365 X = X_1 X_2 ... X_l. 366 3674.2 OS2IP 368 369 OS2IP converts an octet string to a nonnegative integer. 370 371 OS2IP (X) 372 373 Input: 374 X octet string to be converted 375 376 Output: 377 x corresponding nonnegative integer 378 379 Steps: 380 381 1. Let X_1 X_2 ... X_l be the octets of X from first to last, and 382 let x{l-i} have value X_i for 1<= i <= l. 383 384 2. Let x = x{l-1} 256^{l-1} + x_{l-2} 256^{l-2} +...+ x_1 256 + x_0. 385 386 3. Output x. 387 388 389 390 391 392 393 394Kaliski & Staddon Informational [Page 7] 395 396RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 397 398 3995. Cryptographic primitives 400 401 Cryptographic primitives are basic mathematical operations on which 402 cryptographic schemes can be built. They are intended for 403 implementation in hardware or as software modules, and are not 404 intended to provide security apart from a scheme. 405 406 Four types of primitive are specified in this document, organized in 407 pairs: encryption and decryption; and signature and verification. 408 409 The specifications of the primitives assume that certain conditions 410 are met by the inputs, in particular that public and private keys are 411 valid. 412 4135.1 Encryption and decryption primitives 414 415 An encryption primitive produces a ciphertext representative from a 416 message representative under the control of a public key, and a 417 decryption primitive recovers the message representative from the 418 ciphertext representative under the control of the corresponding 419 private key. 420 421 One pair of encryption and decryption primitives is employed in the 422 encryption schemes defined in this document and is specified here: 423 RSAEP/RSADP. RSAEP and RSADP involve the same mathematical operation, 424 with different keys as input. 425 426 The primitives defined here are the same as in the draft IEEE P1363 427 and are compatible with PKCS #1 v1.5. 428 429 The main mathematical operation in each primitive is exponentiation. 430 4315.1.1 RSAEP 432 433 RSAEP((n, e), m) 434 435 Input: 436 (n, e) RSA public key 437 m message representative, an integer between 0 and n-1 438 439 Output: 440 c ciphertext representative, an integer between 0 and n-1; 441 or "message representative out of range" 442 443 Assumptions: public key (n, e) is valid 444 445 Steps: 446 447 448 449 450Kaliski & Staddon Informational [Page 8] 451 452RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 453 454 455 1. If the message representative m is not between 0 and n-1, output 456 message representative out of range and stop. 457 458 2. Let c = m^e mod n. 459 460 3. Output c. 461 4625.1.2 RSADP 463 464 RSADP (K, c) 465 466 Input: 467 468 K RSA private key, where K has one of the following forms 469 -a pair (n, d) 470 -a quintuple (p, q, dP, dQ, qInv) 471 c ciphertext representative, an integer between 0 and n-1 472 473 Output: 474 m message representative, an integer between 0 and n-1; or 475 "ciphertext representative out of range" 476 477 Assumptions: private key K is valid 478 479 Steps: 480 481 1. If the ciphertext representative c is not between 0 and n-1, 482 output "ciphertext representative out of range" and stop. 483 484 2. If the first form (n, d) of K is used: 485 486 2.1 Let m = c^d mod n. Else, if the second form (p, q, dP, 487 dQ, qInv) of K is used: 488 489 2.2 Let m_1 = c^dP mod p. 490 491 2.3 Let m_2 = c^dQ mod q. 492 493 2.4 Let h = qInv ( m_1 - m_2 ) mod p. 494 495 2.5 Let m = m_2 + hq. 496 497 3. Output m. 498 499 500 501 502 503 504 505 506Kaliski & Staddon Informational [Page 9] 507 508RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 509 510 5115.2 Signature and verification primitives 512 513 A signature primitive produces a signature representative from a 514 message representative under the control of a private key, and a 515 verification primitive recovers the message representative from the 516 signature representative under the control of the corresponding 517 public key. One pair of signature and verification primitives is 518 employed in the signature schemes defined in this document and is 519 specified here: RSASP1/RSAVP1. 520 521 The primitives defined here are the same as in the draft IEEE P1363 522 and are compatible with PKCS #1 v1.5. 523 524 The main mathematical operation in each primitive is exponentiation, 525 as in the encryption and decryption primitives of Section 5.1. RSASP1 526 and RSAVP1 are the same as RSADP and RSAEP except for the names of 527 their input and output arguments; they are distinguished as they are 528 intended for different purposes. 529 5305.2.1 RSASP1 531 532 RSASP1 (K, m) 533 534 Input: 535 K RSA private key, where K has one of the following 536 forms: 537 -a pair (n, d) 538 -a quintuple (p, q, dP, dQ, qInv) 539 540 m message representative, an integer between 0 and n-1 541 542 Output: 543 s signature representative, an integer between 0 and 544 n-1, or "message representative out of range" 545 546 Assumptions: 547 private key K is valid 548 549 Steps: 550 551 1. If the message representative m is not between 0 and n-1, output 552 "message representative out of range" and stop. 553 554 2. If the first form (n, d) of K is used: 555 556 2.1 Let s = m^d mod n. Else, if the second form (p, q, dP, 557 dQ, qInv) of K is used: 558 559 560 561 562Kaliski & Staddon Informational [Page 10] 563 564RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 565 566 567 2.2 Let s_1 = m^dP mod p. 568 569 2.3 Let s_2 = m^dQ mod q. 570 571 2.4 Let h = qInv ( s_1 - s_2 ) mod p. 572 573 2.5 Let s = s_2 + hq. 574 575 3. Output S. 576 5775.2.2 RSAVP1 578 579 RSAVP1 ((n, e), s) 580 581 Input: 582 (n, e) RSA public key 583 s signature representative, an integer between 0 and n-1 584 585 Output: 586 m message representative, an integer between 0 and n-1; 587 or "invalid" 588 589 Assumptions: 590 public key (n, e) is valid 591 592 Steps: 593 594 1. If the signature representative s is not between 0 and n-1, output 595 "invalid" and stop. 596 597 2. Let m = s^e mod n. 598 599 3. Output m. 600 6016. Overview of schemes 602 603 A scheme combines cryptographic primitives and other techniques to 604 achieve a particular security goal. Two types of scheme are specified 605 in this document: encryption schemes and signature schemes with 606 appendix. 607 608 The schemes specified in this document are limited in scope in that 609 their operations consist only of steps to process data with a key, 610 and do not include steps for obtaining or validating the key. Thus, 611 in addition to the scheme operations, an application will typically 612 include key management operations by which parties may select public 613 and private keys for a scheme operation. The specific additional 614 operations and other details are outside the scope of this document. 615 616 617 618Kaliski & Staddon Informational [Page 11] 619 620RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 621 622 623 As was the case for the cryptographic primitives (Section 5), the 624 specifications of scheme operations assume that certain conditions 625 are met by the inputs, in particular that public and private keys are 626 valid. The behavior of an implementation is thus unspecified when a 627 key is invalid. The impact of such unspecified behavior depends on 628 the application. Possible means of addressing key validation include 629 explicit key validation by the application; key validation within the 630 public-key infrastructure; and assignment of liability for operations 631 performed with an invalid key to the party who generated the key. 632 6337. Encryption schemes 634 635 An encryption scheme consists of an encryption operation and a 636 decryption operation, where the encryption operation produces a 637 ciphertext from a message with a recipient's public key, and the 638 decryption operation recovers the message from the ciphertext with 639 the recipient's corresponding private key. 640 641 An encryption scheme can be employed in a variety of applications. A 642 typical application is a key establishment protocol, where the 643 message contains key material to be delivered confidentially from one 644 party to another. For instance, PKCS #7 [21] employs such a protocol 645 to deliver a content-encryption key from a sender to a recipient; the 646 encryption schemes defined here would be suitable key-encryption 647 algorithms in that context. 648 649 Two encryption schemes are specified in this document: RSAES-OAEP and 650 RSAES-PKCS1-v1_5. RSAES-OAEP is recommended for new applications; 651 RSAES-PKCS1-v1_5 is included only for compatibility with existing 652 applications, and is not recommended for new applications. 653 654 The encryption schemes given here follow a general model similar to 655 that employed in IEEE P1363, by combining encryption and decryption 656 primitives with an encoding method for encryption. The encryption 657 operations apply a message encoding operation to a message to produce 658 an encoded message, which is then converted to an integer message 659 representative. An encryption primitive is applied to the message 660 representative to produce the ciphertext. Reversing this, the 661 decryption operations apply a decryption primitive to the ciphertext 662 to recover a message representative, which is then converted to an 663 octet string encoded message. A message decoding operation is applied 664 to the encoded message to recover the message and verify the 665 correctness of the decryption. 666 667 668 669 670 671 672 673 674Kaliski & Staddon Informational [Page 12] 675 676RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 677 678 6797.1 RSAES-OAEP 680 681 RSAES-OAEP combines the RSAEP and RSADP primitives (Sections 5.1.1 682 and 5.1.2) with the EME-OAEP encoding method (Section 9.1.1) EME-OAEP 683 is based on the method found in [2]. It is compatible with the IFES 684 scheme defined in the draft P1363 where the encryption and decryption 685 primitives are IFEP-RSA and IFDP-RSA and the message encoding method 686 is EME-OAEP. RSAES-OAEP can operate on messages of length up to k-2- 687 2hLen octets, where hLen is the length of the hash function output 688 for EME-OAEP and k is the length in octets of the recipient's RSA 689 modulus. Assuming that the hash function in EME-OAEP has appropriate 690 properties, and the key size is sufficiently large, RSAEP-OAEP 691 provides "plaintext-aware encryption," meaning that it is 692 computationally infeasible to obtain full or partial information 693 about a message from a ciphertext, and computationally infeasible to 694 generate a valid ciphertext without knowing the corresponding 695 message. Therefore, a chosen-ciphertext attack is ineffective 696 against a plaintext-aware encryption scheme such as RSAES-OAEP. 697 698 Both the encryption and the decryption operations of RSAES-OAEP take 699 the value of the parameter string P as input. In this version of PKCS 700 #1, P is an octet string that is specified explicitly. See Section 701 11.2.1 for the relevant ASN.1 syntax. We briefly note that to receive 702 the full security benefit of RSAES-OAEP, it should not be used in a 703 protocol involving RSAES-PKCS1-v1_5. It is possible that in a 704 protocol on which both encryption schemes are present, an adaptive 705 chosen ciphertext attack such as [4] would be useful. 706 707 Both the encryption and the decryption operations of RSAES-OAEP take 708 the value of the parameter string P as input. In this version of PKCS 709 #1, P is an octet string that is specified explicitly. See Section 710 11.2.1 for the relevant ASN.1 syntax. 711 7127.1.1 Encryption operation 713 714 RSAES-OAEP-ENCRYPT ((n, e), M, P) 715 716 Input: 717 (n, e) recipient's RSA public key 718 719 M message to be encrypted, an octet string of length at 720 most k-2-2hLen, where k is the length in octets of the 721 modulus n and hLen is the length in octets of the hash 722 function output for EME-OAEP 723 724 P encoding parameters, an octet string that may be empty 725 726 727 728 729 730Kaliski & Staddon Informational [Page 13] 731 732RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 733 734 735 Output: 736 C ciphertext, an octet string of length k; or "message too 737 long" 738 739 Assumptions: public key (n, e) is valid 740 741 Steps: 742 743 1. Apply the EME-OAEP encoding operation (Section 9.1.1.2) to the 744 message M and the encoding parameters P to produce an encoded message 745 EM of length k-1 octets: 746 747 EM = EME-OAEP-ENCODE (M, P, k-1) 748 749 If the encoding operation outputs "message too long," then output 750 "message too long" and stop. 751 752 2. Convert the encoded message EM to an integer message 753 representative m: m = OS2IP (EM) 754 755 3. Apply the RSAEP encryption primitive (Section 5.1.1) to the public 756 key (n, e) and the message representative m to produce an integer 757 ciphertext representative c: 758 759 c = RSAEP ((n, e), m) 760 761 4. Convert the ciphertext representative c to a ciphertext C of 762 length k octets: C = I2OSP (c, k) 763 764 5. Output the ciphertext C. 765 7667.1.2 Decryption operation 767 768 RSAES-OAEP-DECRYPT (K, C, P) 769 770 Input: 771 K recipient's RSA private key 772 C ciphertext to be decrypted, an octet string of length 773 k, where k is the length in octets of the modulus n 774 P encoding parameters, an octet string that may be empty 775 776 Output: 777 M message, an octet string of length at most k-2-2hLen, 778 where hLen is the length in octets of the hash 779 function output for EME-OAEP; or "decryption error" 780 781 782 783 784 785 786Kaliski & Staddon Informational [Page 14] 787 788RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 789 790 791 Steps: 792 793 1. If the length of the ciphertext C is not k octets, output 794 "decryption error" and stop. 795 796 2. Convert the ciphertext C to an integer ciphertext representative 797 c: c = OS2IP (C). 798 799 3. Apply the RSADP decryption primitive (Section 5.1.2) to the 800 private key K and the ciphertext representative c to produce an 801 integer message representative m: 802 803 m = RSADP (K, c) 804 805 If RSADP outputs "ciphertext out of range," then output "decryption 806 error" and stop. 807 808 4. Convert the message representative m to an encoded message EM of 809 length k-1 octets: EM = I2OSP (m, k-1) 810 811 If I2OSP outputs "integer too large," then output "decryption error" 812 and stop. 813 814 5. Apply the EME-OAEP decoding operation to the encoded message EM 815 and the encoding parameters P to recover a message M: 816 817 M = EME-OAEP-DECODE (EM, P) 818 819 If the decoding operation outputs "decoding error," then output 820 "decryption error" and stop. 821 822 6. Output the message M. 823 824 Note. It is important that the error messages output in steps 4 and 5 825 be the same, otherwise an adversary may be able to extract useful 826 information from the type of error message received. Error message 827 information is used to mount a chosen-ciphertext attack on PKCS #1 828 v1.5 encrypted messages in [4]. 829 8307.2 RSAES-PKCS1-v1_5 831 832 RSAES-PKCS1-v1_5 combines the RSAEP and RSADP primitives with the 833 EME-PKCS1-v1_5 encoding method. It is the same as the encryption 834 scheme in PKCS #1 v1.5. RSAES-PKCS1-v1_5 can operate on messages of 835 length up to k-11 octets, although care should be taken to avoid 836 certain attacks on low-exponent RSA due to Coppersmith, et al. when 837 long messages are encrypted (see the third bullet in the notes below 838 and [7]). 839 840 841 842Kaliski & Staddon Informational [Page 15] 843 844RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 845 846 847 RSAES-PKCS1-v1_5 does not provide "plaintext aware" encryption. In 848 particular, it is possible to generate valid ciphertexts without 849 knowing the corresponding plaintexts, with a reasonable probability 850 of success. This ability can be exploited in a chosen ciphertext 851 attack as shown in [4]. Therefore, if RSAES-PKCS1-v1_5 is to be used, 852 certain easily implemented countermeasures should be taken to thwart 853 the attack found in [4]. The addition of structure to the data to be 854 encoded, rigorous checking of PKCS #1 v1.5 conformance and other 855 redundancy in decrypted messages, and the consolidation of error 856 messages in a client-server protocol based on PKCS #1 v1.5 can all be 857 effective countermeasures and don't involve changes to a PKCS #1 858 v1.5-based protocol. These and other countermeasures are discussed in 859 [5]. 860 861 Notes. The following passages describe some security recommendations 862 pertaining to the use of RSAES-PKCS1-v1_5. Recommendations from 863 version 1.5 of this document are included as well as new 864 recommendations motivated by cryptanalytic advances made in the 865 intervening years. 866 867 -It is recommended that the pseudorandom octets in EME-PKCS1-v1_5 be 868 generated independently for each encryption process, especially if 869 the same data is input to more than one encryption process. Hastad's 870 results [13] are one motivation for this recommendation. 871 872 -The padding string PS in EME-PKCS1-v1_5 is at least eight octets 873 long, which is a security condition for public-key operations that 874 prevents an attacker from recovering data by trying all possible 875 encryption blocks. 876 877 -The pseudorandom octets can also help thwart an attack due to 878 Coppersmith et al. [7] when the size of the message to be encrypted 879 is kept small. The attack works on low-exponent RSA when similar 880 messages are encrypted with the same public key. More specifically, 881 in one flavor of the attack, when two inputs to RSAEP agree on a 882 large fraction of bits (8/9) and low-exponent RSA (e = 3) is used to 883 encrypt both of them, it may be possible to recover both inputs with 884 the attack. Another flavor of the attack is successful in decrypting 885 a single ciphertext when a large fraction (2/3) of the input to RSAEP 886 is already known. For typical applications, the message to be 887 encrypted is short (e.g., a 128-bit symmetric key) so not enough 888 information will be known or common between two messages to enable 889 the attack. However, if a long message is encrypted, or if part of a 890 message is known, then the attack may be a concern. In any case, the 891 RSAEP-OAEP scheme overcomes the attack. 892 893 894 895 896 897 898Kaliski & Staddon Informational [Page 16] 899 900RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 901 902 9037.2.1 Encryption operation 904 905 RSAES-PKCS1-V1_5-ENCRYPT ((n, e), M) 906 907 Input: 908 (n, e) recipient's RSA public key 909 M message to be encrypted, an octet string of length at 910 most k-11 octets, where k is the length in octets of the 911 modulus n 912 913 Output: 914 C ciphertext, an octet string of length k; or "message too 915 long" 916 917 Steps: 918 919 1. Apply the EME-PKCS1-v1_5 encoding operation (Section 9.1.2.1) to 920 the message M to produce an encoded message EM of length k-1 octets: 921 922 EM = EME-PKCS1-V1_5-ENCODE (M, k-1) 923 924 If the encoding operation outputs "message too long," then output 925 "message too long" and stop. 926 927 2. Convert the encoded message EM to an integer message 928 representative m: m = OS2IP (EM) 929 930 3. Apply the RSAEP encryption primitive (Section 5.1.1) to the public 931 key (n, e) and the message representative m to produce an integer 932 ciphertext representative c: c = RSAEP ((n, e), m) 933 934 4. Convert the ciphertext representative c to a ciphertext C of 935 length k octets: C = I2OSP (c, k) 936 937 5. Output the ciphertext C. 938 9397.2.2 Decryption operation 940 941 RSAES-PKCS1-V1_5-DECRYPT (K, C) 942 943 Input: 944 K recipient's RSA private key 945 C ciphertext to be decrypted, an octet string of length k, 946 where k is the length in octets of the modulus n 947 948 Output: 949 M message, an octet string of length at most k-11; or 950 "decryption error" 951 952 953 954Kaliski & Staddon Informational [Page 17] 955 956RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 957 958 959 Steps: 960 961 1. If the length of the ciphertext C is not k octets, output 962 "decryption error" and stop. 963 964 2. Convert the ciphertext C to an integer ciphertext representative 965 c: c = OS2IP (C). 966 967 3. Apply the RSADP decryption primitive to the private key (n, d) and 968 the ciphertext representative c to produce an integer message 969 representative m: m = RSADP ((n, d), c). 970 971 If RSADP outputs "ciphertext out of range," then output "decryption 972 error" and stop. 973 974 4. Convert the message representative m to an encoded message EM of 975 length k-1 octets: EM = I2OSP (m, k-1) 976 977 If I2OSP outputs "integer too large," then output "decryption error" 978 and stop. 979 980 5. Apply the EME-PKCS1-v1_5 decoding operation to the encoded message 981 EM to recover a message M: M = EME-PKCS1-V1_5-DECODE (EM). 982 983 If the decoding operation outputs "decoding error," then output 984 "decryption error" and stop. 985 986 6. Output the message M. 987 988 Note. It is important that only one type of error message is output 989 by EME-PKCS1-v1_5, as ensured by steps 4 and 5. If this is not done, 990 then an adversary may be able to use information extracted form the 991 type of error message received to mount a chosen-ciphertext attack 992 such as the one found in [4]. 993 9948. Signature schemes with appendix 995 996 A signature scheme with appendix consists of a signature generation 997 operation and a signature verification operation, where the signature 998 generation operation produces a signature from a message with a 999 signer's private key, and the signature verification operation 1000 verifies the signature on the message with the signer's corresponding 1001 public key. To verify a signature constructed with this type of 1002 scheme it is necessary to have the message itself. In this way, 1003 signature schemes with appendix are distinguished from signature 1004 schemes with message recovery, which are not supported in this 1005 document. 1006 1007 1008 1009 1010Kaliski & Staddon Informational [Page 18] 1011 1012RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 1013 1014 1015 A signature scheme with appendix can be employed in a variety of 1016 applications. For instance, X.509 [6] employs such a scheme to 1017 authenticate the content of a certificate; the signature scheme with 1018 appendix defined here would be a suitable signature algorithm in that 1019 context. A related signature scheme could be employed in PKCS #7 1020 [21], although for technical reasons, the current version of PKCS #7 1021 separates a hash function from a signature scheme, which is different 1022 than what is done here. 1023 1024 One signature scheme with appendix is specified in this document: 1025 RSASSA-PKCS1-v1_5. 1026 1027 The signature scheme with appendix given here follows a general model 1028 similar to that employed in IEEE P1363, by combining signature and 1029 verification primitives with an encoding method for signatures. The 1030 signature generation operations apply a message encoding operation to 1031 a message to produce an encoded message, which is then converted to 1032 an integer message representative. A signature primitive is then 1033 applied to the message representative to produce the signature. The 1034 signature verification operations apply a signature verification 1035 primitive to the signature to recover a message representative, which 1036 is then converted to an octet string. The message encoding operation 1037 is again applied to the message, and the result is compared to the 1038 recovered octet string. If there is a match, the signature is 1039 considered valid. (Note that this approach assumes that the signature 1040 and verification primitives have the message-recovery form and the 1041 encoding method is deterministic, as is the case for RSASP1/RSAVP1 1042 and EMSA-PKCS1-v1_5. The signature generation and verification 1043 operations have a different form in P1363 for other primitives and 1044 encoding methods.) 1045 1046 Editor's note. RSA Laboratories is investigating the possibility of 1047 including a scheme based on the PSS encoding methods specified in 1048 [3], which would be recommended for new applications. 1049 10508.1 RSASSA-PKCS1-v1_5 1051 1052 RSASSA-PKCS1-v1_5 combines the RSASP1 and RSAVP1 primitives with the 1053 EME-PKCS1-v1_5 encoding method. It is compatible with the IFSSA 1054 scheme defined in the draft P1363 where the signature and 1055 verification primitives are IFSP-RSA1 and IFVP-RSA1 and the message 1056 encoding method is EMSA-PKCS1-v1_5 (which is not defined in P1363). 1057 The length of messages on which RSASSA-PKCS1-v1_5 can operate is 1058 either unrestricted or constrained by a very large number, depending 1059 on the hash function underlying the message encoding method. 1060 1061 1062 1063 1064 1065 1066Kaliski & Staddon Informational [Page 19] 1067 1068RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 1069 1070 1071 Assuming that the hash function in EMSA-PKCS1-v1_5 has appropriate 1072 properties and the key size is sufficiently large, RSASSA-PKCS1-v1_5 1073 provides secure signatures, meaning that it is computationally 1074 infeasible to generate a signature without knowing the private key, 1075 and computationally infeasible to find a message with a given 1076 signature or two messages with the same signature. Also, in the 1077 encoding method EMSA-PKCS1-v1_5, a hash function identifier is 1078 embedded in the encoding. Because of this feature, an adversary must 1079 invert or find collisions of the particular hash function being used; 1080 attacking a different hash function than the one selected by the 1081 signer is not useful to the adversary. 1082 10838.1.1 Signature generation operation 1084 1085 RSASSA-PKCS1-V1_5-SIGN (K, M) 1086 Input: 1087 K signer's RSA private ke 1088 M message to be signed, an octet string 1089 1090 Output: 1091 S signature, an octet string of length k, where k is the 1092 length in octets of the modulus n; "message too long" or 1093 "modulus too short" 1094 Steps: 1095 1096 1. Apply the EMSA-PKCS1-v1_5 encoding operation (Section 9.2.1) to 1097 the message M to produce an encoded message EM of length k-1 octets: 1098 1099 EM = EMSA-PKCS1-V1_5-ENCODE (M, k-1) 1100 1101 If the encoding operation outputs "message too long," then output 1102 "message too long" and stop. If the encoding operation outputs 1103 "intended encoded message length too short" then output "modulus too 1104 short". 1105 1106 2. Convert the encoded message EM to an integer message 1107 representative m: m = OS2IP (EM) 1108 1109 3. Apply the RSASP1 signature primitive (Section 5.2.1) to the 1110 private key K and the message representative m to produce an integer 1111 signature representative s: s = RSASP1 (K, m) 1112 1113 4. Convert the signature representative s to a signature S of length 1114 k octets: S = I2OSP (s, k) 1115 1116 5. Output the signature S. 1117 1118 1119 1120 1121 1122Kaliski & Staddon Informational [Page 20] 1123 1124RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 1125 1126 11278.1.2 Signature verification operation 1128 1129 RSASSA-PKCS1-V1_5-VERIFY ((n, e), M, S) 1130 1131 Input: 1132 (n, e) signer's RSA public key 1133 M message whose signature is to be verified, an octet string 1134 S signature to be verified, an octet string of length k, 1135 where k is the length in octets of the modulus n 1136 1137 Output: "valid signature," "invalid signature," or "message too 1138 long", or "modulus too short" 1139 1140 Steps: 1141 1142 1. If the length of the signature S is not k octets, output "invalid 1143 signature" and stop. 1144 1145 2. Convert the signature S to an integer signature representative s: 1146 1147 s = OS2IP (S) 1148 1149 3. Apply the RSAVP1 verification primitive (Section 5.2.2) to the 1150 public key (n, e) and the signature representative s to produce an 1151 integer message representative m: 1152 1153 m = RSAVP1 ((n, e), s) If RSAVP1 outputs "invalid" 1154 then output "invalid signature" and stop. 1155 1156 4. Convert the message representative m to an encoded message EM of 1157 length k-1 octets: EM = I2OSP (m, k-1) 1158 1159 If I2OSP outputs "integer too large," then output "invalid signature" 1160 and stop. 1161 1162 5. Apply the EMSA-PKCS1-v1_5 encoding operation (Section 9.2.1) to 1163 the message M to produce a second encoded message EM' of length k-1 1164 octets: 1165 1166 EM' = EMSA-PKCS1-V1_5-ENCODE (M, k-1) 1167 1168 If the encoding operation outputs "message too long," then output 1169 "message too long" and stop. If the encoding operation outputs 1170 "intended encoded message length too short" then output "modulus too 1171 short". 1172 1173 1174 1175 1176 1177 1178Kaliski & Staddon Informational [Page 21] 1179 1180RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 1181 1182 1183 6. Compare the encoded message EM and the second encoded message EM'. 1184 If they are the same, output "valid signature"; otherwise, output 1185 "invalid signature." 1186 11879. Encoding methods 1188 1189 Encoding methods consist of operations that map between octet string 1190 messages and integer message representatives. 1191 1192 Two types of encoding method are considered in this document: 1193 encoding methods for encryption, encoding methods for signatures with 1194 appendix. 1195 11969.1 Encoding methods for encryption 1197 1198 An encoding method for encryption consists of an encoding operation 1199 and a decoding operation. An encoding operation maps a message M to a 1200 message representative EM of a specified length; the decoding 1201 operation maps a message representative EM back to a message. The 1202 encoding and decoding operations are inverses. 1203 1204 The message representative EM will typically have some structure that 1205 can be verified by the decoding operation; the decoding operation 1206 will output "decoding error" if the structure is not present. The 1207 encoding operation may also introduce some randomness, so that 1208 different applications of the encoding operation to the same message 1209 will produce different representatives. 1210 1211 Two encoding methods for encryption are employed in the encryption 1212 schemes and are specified here: EME-OAEP and EME-PKCS1-v1_5. 1213 12149.1.1 EME-OAEP 1215 1216 This encoding method is parameterized by the choice of hash function 1217 and mask generation function. Suggested hash and mask generation 1218 functions are given in Section 10. This encoding method is based on 1219 the method found in [2]. 1220 12219.1.1.1 Encoding operation 1222 1223 EME-OAEP-ENCODE (M, P, emLen) 1224 1225 Options: 1226 Hash hash function (hLen denotes the length in octet of the 1227 hash function output) 1228 MGF mask generation function 1229 1230 1231 1232 1233 1234Kaliski & Staddon Informational [Page 22] 1235 1236RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 1237 1238 1239 Input: 1240 M message to be encoded, an octet string of length at most 1241 emLen-1-2hLen 1242 P encoding parameters, an octet string 1243 emLen intended length in octets of the encoded message, at least 1244 2hLen+1 1245 1246 Output: 1247 EM encoded message, an octet string of length emLen; 1248 "message too long" or "parameter string too long" 1249 1250 Steps: 1251 1252 1. If the length of P is greater than the input limitation for the 1253 hash function (2^61-1 octets for SHA-1) then output "parameter string 1254 too long" and stop. 1255 1256 2. If ||M|| > emLen-2hLen-1 then output "message too long" and stop. 1257 1258 3. Generate an octet string PS consisting of emLen-||M||-2hLen-1 zero 1259 octets. The length of PS may be 0. 1260 1261 4. Let pHash = Hash(P), an octet string of length hLen. 1262 1263 5. Concatenate pHash, PS, the message M, and other padding to form a 1264 data block DB as: DB = pHash || PS || 01 || M 1265 1266 6. Generate a random octet string seed of length hLen. 1267 1268 7. Let dbMask = MGF(seed, emLen-hLen). 1269 1270 8. Let maskedDB = DB \xor dbMask. 1271 1272 9. Let seedMask = MGF(maskedDB, hLen). 1273 1274 10. Let maskedSeed = seed \xor seedMask. 1275 1276 11. Let EM = maskedSeed || maskedDB. 1277 1278 12. Output EM. 1279 12809.1.1.2 Decoding operation EME-OAEP-DECODE (EM, P) 1281 1282 Options: 1283 Hash hash function (hLen denotes the length in octet of the hash 1284 function output) 1285 1286 MGF mask generation function 1287 1288 1289 1290Kaliski & Staddon Informational [Page 23] 1291 1292RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 1293 1294 1295 Input: 1296 1297 EM encoded message, an octet string of length at least 2hLen+1 1298 P encoding parameters, an octet string 1299 1300 Output: 1301 M recovered message, an octet string of length at most 1302 ||EM||-1-2hLen; or "decoding error" 1303 1304 Steps: 1305 1306 1. If the length of P is greater than the input limitation for the 1307 hash function (2^61-1 octets for SHA-1) then output "parameter string 1308 too long" and stop. 1309 1310 2. If ||EM|| < 2hLen+1, then output "decoding error" and stop. 1311 1312 3. Let maskedSeed be the first hLen octets of EM and let maskedDB be 1313 the remaining ||EM|| - hLen octets. 1314 1315 4. Let seedMask = MGF(maskedDB, hLen). 1316 1317 5. Let seed = maskedSeed \xor seedMask. 1318 1319 6. Let dbMask = MGF(seed, ||EM|| - hLen). 1320 1321 7. Let DB = maskedDB \xor dbMask. 1322 1323 8. Let pHash = Hash(P), an octet string of length hLen. 1324 1325 9. Separate DB into an octet string pHash' consisting of the first 1326 hLen octets of DB, a (possibly empty) octet string PS consisting of 1327 consecutive zero octets following pHash', and a message M as: 1328 1329 DB = pHash' || PS || 01 || M 1330 1331 If there is no 01 octet to separate PS from M, output "decoding 1332 error" and stop. 1333 1334 10. If pHash' does not equal pHash, output "decoding error" and stop. 1335 1336 11. Output M. 1337 13389.1.2 EME-PKCS1-v1_5 1339 1340 This encoding method is the same as in PKCS #1 v1.5, Section 8: 1341 Encryption Process. 1342 1343 1344 1345 1346Kaliski & Staddon Informational [Page 24] 1347 1348RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 1349 1350 13519.1.2.1 Encoding operation 1352 1353 EME-PKCS1-V1_5-ENCODE (M, emLen) 1354 1355 Input: 1356 M message to be encoded, an octet string of length at most 1357 emLen-10 1358 emLen intended length in octets of the encoded message 1359 1360 Output: 1361 EM encoded message, an octet string of length emLen; or 1362 "message too long" 1363 1364 Steps: 1365 1366 1. If the length of the message M is greater than emLen - 10 octets, 1367 output "message too long" and stop. 1368 1369 2. Generate an octet string PS of length emLen-||M||-2 consisting of 1370 pseudorandomly generated nonzero octets. The length of PS will be at 1371 least 8 octets. 1372 1373 3. Concatenate PS, the message M, and other padding to form the 1374 encoded message EM as: 1375 1376 EM = 02 || PS || 00 || M 1377 1378 4. Output EM. 1379 13809.1.2.2 Decoding operation 1381 1382 EME-PKCS1-V1_5-DECODE (EM) 1383 1384 Input: 1385 EM encoded message, an octet string of length at least 10 1386 1387 Output: 1388 M recovered message, an octet string of length at most 1389 ||EM||-10; or "decoding error" 1390 1391 Steps: 1392 1393 1. If the length of the encoded message EM is less than 10, output 1394 "decoding error" and stop. 1395 1396 2. Separate the encoded message EM into an octet string PS consisting 1397 of nonzero octets and a message M as: EM = 02 || PS || 00 || M. 1398 1399 1400 1401 1402Kaliski & Staddon Informational [Page 25] 1403 1404RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 1405 1406 1407 If the first octet of EM is not 02, or if there is no 00 octet to 1408 separate PS from M, output "decoding error" and stop. 1409 1410 3. If the length of PS is less than 8 octets, output "decoding error" 1411 and stop. 1412 1413 4. Output M. 1414 14159.2 Encoding methods for signatures with appendix 1416 1417 An encoding method for signatures with appendix, for the purposes of 1418 this document, consists of an encoding operation. An encoding 1419 operation maps a message M to a message representative EM of a 1420 specified length. (In future versions of this document, encoding 1421 methods may be added that also include a decoding operation.) 1422 1423 One encoding method for signatures with appendix is employed in the 1424 encryption schemes and is specified here: EMSA-PKCS1-v1_5. 1425 14269.2.1 EMSA-PKCS1-v1_5 1427 1428 This encoding method only has an encoding operation. 1429 1430 EMSA-PKCS1-v1_5-ENCODE (M, emLen) 1431 1432 Option: 1433 Hash hash function (hLen denotes the length in octet of the hash 1434 function output) 1435 1436 Input: 1437 M message to be encoded 1438 emLen intended length in octets of the encoded message, at least 1439 ||T|| + 10, where T is the DER encoding of a certain value 1440 computed during the encoding operation 1441 1442 Output: 1443 EM encoded message, an octet string of length emLen; or "message 1444 too long" or "intended encoded message length too short" 1445 1446 Steps: 1447 1448 1. Apply the hash function to the message M to produce a hash value 1449 H: 1450 1451 H = Hash(M). 1452 1453 If the hash function outputs "message too long," then output "message 1454 too long". 1455 1456 1457 1458Kaliski & Staddon Informational [Page 26] 1459 1460RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 1461 1462 1463 2. Encode the algorithm ID for the hash function and the hash value 1464 into an ASN.1 value of type DigestInfo (see Section 11) with the 1465 Distinguished Encoding Rules (DER), where the type DigestInfo has the 1466 syntax 1467 1468 DigestInfo::=SEQUENCE{ 1469 digestAlgorithm AlgorithmIdentifier, 1470 digest OCTET STRING } 1471 1472 The first field identifies the hash function and the second contains 1473 the hash value. Let T be the DER encoding. 1474 1475 3. If emLen is less than ||T|| + 10 then output "intended encoded 1476 message length too short". 1477 1478 4. Generate an octet string PS consisting of emLen-||T||-2 octets 1479 with value FF (hexadecimal). The length of PS will be at least 8 1480 octets. 1481 1482 5. Concatenate PS, the DER encoding T, and other padding to form the 1483 encoded message EM as: EM = 01 || PS || 00 || T 1484 1485 6. Output EM. 1486 148710. Auxiliary Functions 1488 1489 This section specifies the hash functions and the mask generation 1490 functions that are mentioned in the encoding methods (Section 9). 1491 149210.1 Hash Functions 1493 1494 Hash functions are used in the operations contained in Sections 7, 8 1495 and 9. Hash functions are deterministic, meaning that the output is 1496 completely determined by the input. Hash functions take octet strings 1497 of variable length, and generate fixed length octet strings. The hash 1498 functions used in the operations contained in Sections 7, 8 and 9 1499 should be collision resistant. This means that it is infeasible to 1500 find two distinct inputs to the hash function that produce the same 1501 output. A collision resistant hash function also has the desirable 1502 property of being one-way; this means that given an output, it is 1503 infeasible to find an input whose hash is the specified output. The 1504 property of collision resistance is especially desirable for RSASSA- 1505 PKCS1-v1_5, as it makes it infeasible to forge signatures. In 1506 addition to the requirements, the hash function should yield a mask 1507 generation function (Section 10.2) with pseudorandom output. 1508 1509 1510 1511 1512 1513 1514Kaliski & Staddon Informational [Page 27] 1515 1516RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 1517 1518 1519 Three hash functions are recommended for the encoding methods in this 1520 document: MD2 [15], MD5 [17], and SHA-1 [16]. For the EME-OAEP 1521 encoding method, only SHA-1 is recommended. For the EMSA-PKCS1-v1_5 1522 encoding method, SHA-1 is recommended for new applications. MD2 and 1523 MD5 are recommended only for compatibility with existing applications 1524 based on PKCS #1 v1.5. 1525 1526 The hash functions themselves are not defined here; readers are 1527 referred to the appropriate references ([15], [17] and [16]). 1528 1529 Note. Version 1.5 of this document also allowed for the use of MD4 in 1530 signature schemes. The cryptanalysis of MD4 has progressed 1531 significantly in the intervening years. For example, Dobbertin [10] 1532 demonstrated how to find collisions for MD4 and that the first two 1533 rounds of MD4 are not one-way [11]. Because of these results and 1534 others (e.g. [9]), MD4 is no longer recommended. There have also been 1535 advances in the cryptanalysis of MD2 and MD5, although not enough to 1536 warrant removal from existing applications. Rogier and Chauvaud [19] 1537 demonstrated how to find collisions in a modified version of MD2. No 1538 one has demonstrated how to find collisions for the full MD5 1539 algorithm, although partial results have been found (e.g. [8]). For 1540 new applications, to address these concerns, SHA-1 is preferred. 1541 154210.2 Mask Generation Functions 1543 1544 A mask generation function takes an octet string of variable length 1545 and a desired output length as input, and outputs an octet string of 1546 the desired length. There may be restrictions on the length of the 1547 input and output octet strings, but such bounds are generally very 1548 large. Mask generation functions are deterministic; the octet string 1549 output is completely determined by the input octet string. The output 1550 of a mask generation function should be pseudorandom, that is, if the 1551 seed to the function is unknown, it should be infeasible to 1552 distinguish the output from a truly random string. The plaintext- 1553 awareness of RSAES-OAEP relies on the random nature of the output of 1554 the mask generation function, which in turn relies on the random 1555 nature of the underlying hash. 1556 1557 One mask generation function is recommended for the encoding methods 1558 in this document, and is defined here: MGF1, which is based on a hash 1559 function. Future versions of this document may define other mask 1560 generation functions. 1561 156210.2.1 MGF1 1563 1564 MGF1 is a Mask Generation Function based on a hash function. 1565 1566 MGF1 (Z, l) 1567 1568 1569 1570Kaliski & Staddon Informational [Page 28] 1571 1572RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 1573 1574 1575 Options: 1576 Hash hash function (hLen denotes the length in octets of the hash 1577 function output) 1578 1579 Input: 1580 Z seed from which mask is generated, an octet string 1581 l intended length in octets of the mask, at most 2^32(hLen) 1582 1583 Output: 1584 mask mask, an octet string of length l; or "mask too long" 1585 1586 Steps: 1587 1588 1.If l > 2^32(hLen), output "mask too long" and stop. 1589 1590 2.Let T be the empty octet string. 1591 1592 3.For counter from 0 to \lceil{l / hLen}\rceil-1, do the following: 1593 1594 a.Convert counter to an octet string C of length 4 with the primitive 1595 I2OSP: C = I2OSP (counter, 4) 1596 1597 b.Concatenate the hash of the seed Z and C to the octet string T: T = 1598 T || Hash (Z || C) 1599 1600 4.Output the leading l octets of T as the octet string mask. 1601 160211. ASN.1 syntax 1603 160411.1 Key representation 1605 1606 This section defines ASN.1 object identifiers for RSA public and 1607 private keys, and defines the types RSAPublicKey and RSAPrivateKey. 1608 The intended application of these definitions includes X.509 1609 certificates, PKCS #8 [22], and PKCS #12 [23]. 1610 1611 The object identifier rsaEncryption identifies RSA public and private 1612 keys as defined in Sections 11.1.1 and 11.1.2. The parameters field 1613 associated with this OID in an AlgorithmIdentifier shall have type 1614 NULL. 1615 1616 rsaEncryption OBJECT IDENTIFIER ::= {pkcs-1 1} 1617 1618 All of the definitions in this section are the same as in PKCS #1 1619 v1.5. 1620 1621 1622 1623 1624 1625 1626Kaliski & Staddon Informational [Page 29] 1627 1628RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 1629 1630 163111.1.1 Public-key syntax 1632 1633 An RSA public key should be represented with the ASN.1 type 1634 RSAPublicKey: 1635 1636 RSAPublicKey::=SEQUENCE{ 1637 modulus INTEGER, -- n 1638 publicExponent INTEGER -- e } 1639 1640 (This type is specified in X.509 and is retained here for 1641 compatibility.) 1642 1643 The fields of type RSAPublicKey have the following meanings: 1644 -modulus is the modulus n. 1645 -publicExponent is the public exponent e. 1646 164711.1.2 Private-key syntax 1648 1649 An RSA private key should be represented with ASN.1 type 1650 RSAPrivateKey: 1651 1652 RSAPrivateKey ::= SEQUENCE { 1653 version Version, 1654 modulus INTEGER, -- n 1655 publicExponent INTEGER, -- e 1656 privateExponent INTEGER, -- d 1657 prime1 INTEGER, -- p 1658 prime2 INTEGER, -- q 1659 exponent1 INTEGER, -- d mod (p-1) 1660 exponent2 INTEGER, -- d mod (q-1) 1661 coefficient INTEGER -- (inverse of q) mod p } 1662 1663 Version ::= INTEGER 1664 1665 The fields of type RSAPrivateKey have the following meanings: 1666 1667 -version is the version number, for compatibility with future 1668 revisions of this document. It shall be 0 for this version of the 1669 document. 1670 -modulus is the modulus n. 1671 -publicExponent is the public exponent e. 1672 -privateExponent is the private exponent d. 1673 -prime1 is the prime factor p of n. 1674 -prime2 is the prime factor q of n. 1675 -exponent1 is d mod (p-1). 1676 -exponent2 is d mod (q-1). 1677 -coefficient is the Chinese Remainder Theorem coefficient q-1 mod p. 1678 1679 1680 1681 1682Kaliski & Staddon Informational [Page 30] 1683 1684RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 1685 1686 168711.2 Scheme identification 1688 1689 This section defines object identifiers for the encryption and 1690 signature schemes. The schemes compatible with PKCS #1 v1.5 have the 1691 same definitions as in PKCS #1 v1.5. The intended application of 1692 these definitions includes X.509 certificates and PKCS #7. 1693 169411.2.1 Syntax for RSAES-OAEP 1695 1696 The object identifier id-RSAES-OAEP identifies the RSAES-OAEP 1697 encryption scheme. 1698 1699 id-RSAES-OAEP OBJECT IDENTIFIER ::= {pkcs-1 7} 1700 1701 The parameters field associated with this OID in an 1702 AlgorithmIdentifier shall have type RSAEP-OAEP-params: 1703 1704 RSAES-OAEP-params ::= SEQUENCE { 1705 hashFunc [0] AlgorithmIdentifier {{oaepDigestAlgorithms}} 1706 DEFAULT sha1Identifier, 1707 maskGenFunc [1] AlgorithmIdentifier {{pkcs1MGFAlgorithms}} 1708 DEFAULT mgf1SHA1Identifier, 1709 pSourceFunc [2] AlgorithmIdentifier 1710 {{pkcs1pSourceAlgorithms}} 1711 DEFAULT pSpecifiedEmptyIdentifier } 1712 1713 The fields of type RSAES-OAEP-params have the following meanings: 1714 1715 -hashFunc identifies the hash function. It shall be an algorithm ID 1716 with an OID in the set oaepDigestAlgorithms, which for this version 1717 shall consist of id-sha1, identifying the SHA-1 hash function. The 1718 parameters field for id-sha1 shall have type NULL. 1719 1720 oaepDigestAlgorithms ALGORITHM-IDENTIFIER ::= { 1721 {NULL IDENTIFIED BY id-sha1} } 1722 1723 id-sha1 OBJECT IDENTIFIER ::= 1724 {iso(1) identified-organization(3) oiw(14) secsig(3) 1725 algorithms(2) 26} 1726 1727 1728 The default hash function is SHA-1: 1729 sha1Identifier ::= AlgorithmIdentifier {id-sha1, NULL} 1730 1731 -maskGenFunc identifies the mask generation function. It shall be an 1732 algorithm ID with an OID in the set pkcs1MGFAlgorithms, which for 1733 this version shall consist of id-mgf1, identifying the MGF1 mask 1734 generation function (see Section 10.2.1). The parameters field for 1735 1736 1737 1738Kaliski & Staddon Informational [Page 31] 1739 1740RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 1741 1742 1743 id-mgf1 shall have type AlgorithmIdentifier, identifying the hash 1744 function on which MGF1 is based, where the OID for the hash function 1745 shall be in the set oaepDigestAlgorithms. 1746 1747 pkcs1MGFAlgorithms ALGORITHM-IDENTIFIER ::= { 1748 {AlgorithmIdentifier {{oaepDigestAlgorithms}} IDENTIFIED 1749 BY id-mgf1} } 1750 1751 id-mgf1 OBJECT IDENTIFIER ::= {pkcs-1 8} 1752 1753 The default mask generation function is MGF1 with SHA-1: 1754 1755 mgf1SHA1Identifier ::= AlgorithmIdentifier { 1756 id-mgf1, sha1Identifier } 1757 1758 -pSourceFunc identifies the source (and possibly the value) of the 1759 encoding parameters P. It shall be an algorithm ID with an OID in the 1760 set pkcs1pSourceAlgorithms, which for this version shall consist of 1761 id-pSpecified, indicating that the encoding parameters are specified 1762 explicitly. The parameters field for id-pSpecified shall have type 1763 OCTET STRING, containing the encoding parameters. 1764 1765 pkcs1pSourceAlgorithms ALGORITHM-IDENTIFIER ::= { 1766 {OCTET STRING IDENTIFIED BY id-pSpecified} } 1767 1768 id-pSpecified OBJECT IDENTIFIER ::= {pkcs-1 9} 1769 1770 The default encoding parameters is an empty string (so that pHash in 1771 EME-OAEP will contain the hash of the empty string): 1772 1773 pSpecifiedEmptyIdentifier ::= AlgorithmIdentifier { 1774 id-pSpecified, OCTET STRING SIZE (0) } 1775 1776 If all of the default values of the fields in RSAES-OAEP-params are 1777 used, then the algorithm identifier will have the following value: 1778 1779 RSAES-OAEP-Default-Identifier ::= AlgorithmIdentifier { 1780 id-RSAES-OAEP, 1781 {sha1Identifier, 1782 mgf1SHA1Identifier, 1783 pSpecifiedEmptyIdentifier } } 1784 178511.2.2 Syntax for RSAES-PKCS1-v1_5 1786 1787 The object identifier rsaEncryption (Section 11.1) identifies the 1788 RSAES-PKCS1-v1_5 encryption scheme. The parameters field associated 1789 with this OID in an AlgorithmIdentifier shall have type NULL. This is 1790 the same as in PKCS #1 v1.5. 1791 1792 1793 1794Kaliski & Staddon Informational [Page 32] 1795 1796RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 1797 1798 1799 RsaEncryption OBJECT IDENTIFIER ::= {PKCS-1 1} 1800 180111.2.3 Syntax for RSASSA-PKCS1-v1_5 1802 1803 The object identifier for RSASSA-PKCS1-v1_5 shall be one of the 1804 following. The choice of OID depends on the choice of hash algorithm: 1805 MD2, MD5 or SHA-1. Note that if either MD2 or MD5 is used then the 1806 OID is just as in PKCS #1 v1.5. For each OID, the parameters field 1807 associated with this OID in an AlgorithmIdentifier shall have type 1808 NULL. 1809 1810 If the hash function to be used is MD2, then the OID should be: 1811 1812 md2WithRSAEncryption ::= {PKCS-1 2} 1813 1814 If the hash function to be used is MD5, then the OID should be: 1815 1816 md5WithRSAEncryption ::= {PKCS-1 4} 1817 1818 If the hash function to be used is SHA-1, then the OID should be: 1819 1820 sha1WithRSAEncryption ::= {pkcs-1 5} 1821 1822 In the digestInfo type mentioned in Section 9.2.1 the OIDS for the 1823 digest algorithm are the following: 1824 1825 id-SHA1 OBJECT IDENTIFIER ::= 1826 {iso(1) identified-organization(3) oiw(14) secsig(3) 1827 algorithms(2) 26 } 1828 1829 md2 OBJECT IDENTIFIER ::= 1830 {iso(1) member-body(2) US(840) rsadsi(113549) 1831 digestAlgorithm(2) 2} 1832 1833 md5 OBJECT IDENTIFIER ::= 1834 {iso(1) member-body(2) US(840) rsadsi(113549) 1835 digestAlgorithm(2) 5} 1836 1837 The parameters field of the digest algorithm has ASN.1 type NULL for 1838 these OIDs. 1839 184012. Patent statement 1841 1842 The Internet Standards Process as defined in RFC 1310 requires a 1843 written statement from the Patent holder that a license will be made 1844 available to applicants under reasonable terms and conditions prior 1845 to approving a specification as a Proposed, Draft or Internet 1846 Standard. 1847 1848 1849 1850Kaliski & Staddon Informational [Page 33] 1851 1852RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 1853 1854 1855 The Internet Society, Internet Architecture Board, Internet 1856 Engineering Steering Group and the Corporation for National Research 1857 Initiatives take no position on the validity or scope of the 1858 following patents and patent applications, nor on the appropriateness 1859 of the terms of the assurance. The Internet Society and other groups 1860 mentioned above have not made any determination as to any other 1861 intellectual property rights which may apply to the practice of this 1862 standard. Any further consideration of these matters is the user's 1863 responsibility. 1864 186512.1 Patent statement for the RSA algorithm 1866 1867 The Massachusetts Institute of Technology has granted RSA Data 1868 Security, Inc., exclusive sub-licensing rights to the following 1869 patent issued in the United States: 1870 1871 Cryptographic Communications System and Method ("RSA"), No. 4,405,829 1872 1873 RSA Data Security, Inc. has provided the following statement with 1874 regard to this patent: 1875 1876 It is RSA's business practice to make licenses to its patents 1877 available on reasonable and nondiscriminatory terms. Accordingly, RSA 1878 is willing, upon request, to grant non-exclusive licenses to such 1879 patent on reasonable and non-discriminatory terms and conditions to 1880 those who respect RSA's intellectual property rights and subject to 1881 RSA's then current royalty rate for the patent licensed. The royalty 1882 rate for the RSA patent is presently set at 2% of the licensee's 1883 selling price for each product covered by the patent. Any requests 1884 for license information may be directed to: 1885 1886 Director of Licensing 1887 RSA Data Security, Inc. 1888 2955 Campus Drive 1889 Suite 400 1890 San Mateo, CA 94403 1891 1892 A license under RSA's patent(s) does not include any rights to know- 1893 how or other technical information or license under other 1894 intellectual property rights. Such license does not extend to any 1895 activities which constitute infringement or inducement thereto. A 1896 licensee must make his own determination as to whether a license is 1897 necessary under patents of others. 1898 1899 1900 1901 1902 1903 1904 1905 1906Kaliski & Staddon Informational [Page 34] 1907 1908RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 1909 1910 191113. Revision history 1912 1913 Versions 1.0-1.3 1914 1915 Versions 1.0-1.3 were distributed to participants in RSA Data 1916 Security, Inc.'s Public-Key Cryptography Standards meetings in 1917 February and March 1991. 1918 1919 1920 Version 1.4 1921 1922 Version 1.4 was part of the June 3, 1991 initial public release of 1923 PKCS. Version 1.4 was published as NIST/OSI Implementors' Workshop 1924 document SEC-SIG-91-18. 1925 1926 1927 Version 1.5 1928 1929 Version 1.5 incorporates several editorial changes, including updates 1930 to the references and the addition of a revision history. The 1931 following substantive changes were made: -Section 10: "MD4 with RSA" 1932 signature and verification processes were added. 1933 1934 -Section 11: md4WithRSAEncryption object identifier was added. 1935 1936 Version 2.0 [DRAFT] 1937 1938 Version 2.0 incorporates major editorial changes in terms of the 1939 document structure, and introduces the RSAEP-OAEP encryption scheme. 1940 This version continues to support the encryption and signature 1941 processes in version 1.5, although the hash algorithm MD4 is no 1942 longer allowed due to cryptanalytic advances in the intervening 1943 years. 1944 194514. References 1946 1947 [1] ANSI, ANSI X9.44: Key Management Using Reversible Public Key 1948 Cryptography for the Financial Services Industry. Work in 1949 Progress. 1950 1951 [2] M. Bellare and P. Rogaway. Optimal Asymmetric Encryption - How to 1952 Encrypt with RSA. In Advances in Cryptology-Eurocrypt '94, pp. 1953 92-111, Springer-Verlag, 1994. 1954 1955 [3] M. Bellare and P. Rogaway. The Exact Security of Digital 1956 Signatures - How to Sign with RSA and Rabin. In Advances in 1957 Cryptology-Eurocrypt '96, pp. 399-416, Springer-Verlag, 1996. 1958 1959 1960 1961 1962Kaliski & Staddon Informational [Page 35] 1963 1964RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 1965 1966 1967 [4] D. Bleichenbacher. Chosen Ciphertext Attacks against Protocols 1968 Based on the RSA Encryption Standard PKCS #1. To appear in 1969 Advances in Cryptology-Crypto '98. 1970 1971 [5] D. Bleichenbacher, B. Kaliski and J. Staddon. Recent Results on 1972 PKCS #1: RSA Encryption Standard. RSA Laboratories' Bulletin, 1973 Number 7, June 24, 1998. 1974 1975 [6] CCITT. Recommendation X.509: The Directory-Authentication 1976 Framework. 1988. 1977 1978 [7] D. Coppersmith, M. Franklin, J. Patarin and M. Reiter. Low- 1979 Exponent RSA with Related Messages. In Advances in Cryptology- 1980 Eurocrypt '96, pp. 1-9, Springer-Verlag, 1996 1981 1982 [8] B. Den Boer and Bosselaers. Collisions for the Compression 1983 Function of MD5. In Advances in Cryptology-Eurocrypt '93, pp 1984 293-304, Springer-Verlag, 1994. 1985 1986 [9] B. den Boer, and A. Bosselaers. An Attack on the Last Two Rounds 1987 of MD4. In Advances in Cryptology-Crypto '91, pp.194-203, 1988 Springer-Verlag, 1992. 1989 1990 [10] H. Dobbertin. Cryptanalysis of MD4. Fast Software Encryption. 1991 Lecture Notes in Computer Science, Springer-Verlag 1996, pp. 1992 55-72. 1993 1994 [11] H. Dobbertin. Cryptanalysis of MD5 Compress. Presented at the 1995 rump session of Eurocrypt `96, May 14, 1996 1996 1997 [12] H. Dobbertin.The First Two Rounds of MD4 are Not One-Way. Fast 1998 Software Encryption. Lecture Notes in Computer Science, 1999 Springer-Verlag 1998, pp. 284-292. 2000 2001 [13] J. Hastad. Solving Simultaneous Modular Equations of Low Degree. 2002 SIAM Journal of Computing, 17, 1988, pp. 336-341. 2003 2004 [14] IEEE. IEEE P1363: Standard Specifications for Public Key 2005 Cryptography. Draft Version 4. 2006 2007 [15] Kaliski, B., "The MD2 Message-Digest Algorithm", RFC 1319, April 2008 1992. 2009 2010 [16] National Institute of Standards and Technology (NIST). FIPS 2011 Publication 180-1: Secure Hash Standard. April 1994. 2012 2013 [17] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April 2014 1992. 2015 2016 2017 2018Kaliski & Staddon Informational [Page 36] 2019 2020RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 2021 2022 2023 [18] R. Rivest, A. Shamir and L. Adleman. A Method for Obtaining 2024 Digital Signatures and Public-Key Cryptosystems. Communications 2025 of the ACM, 21(2), pp. 120-126, February 1978. 2026 2027 [19] N. Rogier and P. Chauvaud. The Compression Function of MD2 is 2028 not Collision Free. Presented at Selected Areas of Cryptography 2029 `95. Carleton University, Ottawa, Canada. May 18-19, 1995. 2030 2031 [20] RSA Laboratories. PKCS #1: RSA Encryption Standard. Version 1.5, 2032 November 1993. 2033 2034 [21] RSA Laboratories. PKCS #7: Cryptographic Message Syntax 2035 Standard. Version 1.5, November 1993. 2036 2037 [22] RSA Laboratories. PKCS #8: Private-Key Information Syntax 2038 Standard. Version 1.2, November 1993. 2039 2040 [23] RSA Laboratories. PKCS #12: Personal Information Exchange Syntax 2041 Standard. Version 1.0, Work in Progress, April 1997. 2042 2043Security Considerations 2044 2045 Security issues are discussed throughout this memo. 2046 2047Acknowledgements 2048 2049 This document is based on a contribution of RSA Laboratories, a 2050 division of RSA Data Security, Inc. Any substantial use of the text 2051 from this document must acknowledge RSA Data Security, Inc. RSA Data 2052 Security, Inc. requests that all material mentioning or referencing 2053 this document identify this as "RSA Data Security, Inc. PKCS #1 2054 v2.0". 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074Kaliski & Staddon Informational [Page 37] 2075 2076RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 2077 2078 2079Authors' Addresses 2080 2081 Burt Kaliski 2082 RSA Laboratories East 2083 20 Crosby Drive 2084 Bedford, MA 01730 2085 2086 Phone: (617) 687-7000 2087 EMail: burt@rsa.com 2088 2089 2090 Jessica Staddon 2091 RSA Laboratories West 2092 2955 Campus Drive 2093 Suite 400 2094 San Mateo, CA 94403 2095 2096 Phone: (650) 295-7600 2097 EMail: jstaddon@rsa.com 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130Kaliski & Staddon Informational [Page 38] 2131 2132RFC 2437 PKCS #1: RSA Cryptography Specifications October 1998 2133 2134 2135Full Copyright Statement 2136 2137 Copyright (C) The Internet Society (1998). All Rights Reserved. 2138 2139 This document and translations of it may be copied and furnished to 2140 others, and derivative works that comment on or otherwise explain it 2141 or assist in its implementation may be prepared, copied, published 2142 and distributed, in whole or in part, without restriction of any 2143 kind, provided that the above copyright notice and this paragraph are 2144 included on all such copies and derivative works. However, this 2145 document itself may not be modified in any way, such as by removing 2146 the copyright notice or references to the Internet Society or other 2147 Internet organizations, except as needed for the purpose of 2148 developing Internet standards in which case the procedures for 2149 copyrights defined in the Internet Standards process must be 2150 followed, or as required to translate it into languages other than 2151 English. 2152 2153 The limited permissions granted above are perpetual and will not be 2154 revoked by the Internet Society or its successors or assigns. 2155 2156 This document and the information contained herein is provided on an 2157 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 2158 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 2159 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 2160 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 2161 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186Kaliski & Staddon Informational [Page 39] 2187 2188