home *** CD-ROM | disk | FTP | other *** search
/ ftp.rsa.com / 2014.05.ftp.rsa.com.tar / ftp.rsa.com / pub / pkcs / ascii / pkcs-1.asc < prev    next >
Text File  |  2014-05-02  |  32KB  |  897 lines
  1. PKCS #1: RSA Encryption Standard
  2.  
  3. An RSA Laboratories Technical Note
  4. Version 1.5
  5. Revised November 1, 1993
  6.  
  7.  
  8. Supersedes June 3, 1991 version, which was also published as
  9. NIST/OSI Implementors' Workshop document SEC-SIG-91-18.
  10. PKCS documents are available by electronic mail
  11. to<pkcs@rsa.com>.  
  12.  
  13. Copyright (C) 1991-1993 RSA Laboratories, a division of RSA
  14. Data Security, Inc. License to copy this document is granted
  15. provided that it is identified as "RSA Data Security, Inc.
  16. Public-Key Cryptography Standards (PKCS)" in all material
  17. mentioning or referencing this document.
  18. 003-903018-150-000-000
  19.  
  20.  
  21. 1. Scope
  22.  
  23. This standard describes a method for encrypting data using
  24. the RSA public-key cryptosystem. Its intended use is in the
  25. construction of digital signatures and digital envelopes, as
  26. described in PKCS #7:
  27.  
  28.      o    For digital signatures, the content to be signed
  29.           is first reduced to a message digest with a
  30.           message-digest algorithm (such as MD5), and then
  31.           an octet string containing the message digest is
  32.           encrypted with the RSA private key of the signer
  33.           of the content. The content and the encrypted
  34.           message digest are represented together according
  35.           to the syntax in PKCS #7 to yield a digital
  36.           signature. This application is compatible with
  37.           Privacy-Enhanced Mail (PEM) methods.
  38.           
  39.      o    For digital envelopes, the content to be enveloped
  40.           is first encrypted under a content-encryption key
  41.           with a content-encryption algorithm (such as DES),
  42.           and then the content-encryption key is encrypted
  43.           with the RSA public keys of the recipients of the
  44.           content. The encrypted content and the encrypted
  45.           content-encryption key are represented together
  46.           according to the syntax in PKCS #7 to yield a
  47.           digital envelope. This application is also
  48.           compatible with PEM methods.
  49.           
  50. The standard also describes a syntax for RSA public keys and
  51. private keys. The public-key syntax would be used in
  52. certificates; the private-key syntax would be used typically
  53. in PKCS #8 private-key information. The public-key syntax is
  54. identical to that in both X.509 and Privacy-Enhanced Mail.
  55. Thus X.509/PEM RSA keys can be used in this standard.
  56.  
  57. The standard also defines three signature algorithms for use
  58. in signing X.509/PEM certificates and certificate-revocation
  59. lists, PKCS #6 extended certificates, and other objects
  60. employing digital signatures such as X.401 message tokens.
  61.  
  62. Details on message-digest and content-encryption algorithms
  63. are outside the scope of this standard, as are details on
  64. sources of the pseudorandom bits required by certain methods
  65. in this standard.
  66.  
  67.  
  68. 2. References
  69.  
  70. FIPS PUB 46-1  National Bureau of Standards. FIPS PUB 46-1:
  71.           Data Encryption Standard. January 1988.
  72.           
  73. PKCS #6   RSA Laboratories. PKCS #6: Extended-Certificate
  74.           Syntax Standard. Version 1.5, November 1993.
  75.           
  76. PKCS #7   RSA Laboratories. PKCS #7: Cryptographic Message
  77.           Syntax Standard. Version 1.5, November 1993.
  78.           
  79. PKCS #8   RSA Laboratories. PKCS #8: Private-Key Information
  80.           Syntax Standard. Version 1.2, November 1993.
  81.           
  82. RFC 1319  B. Kaliski. RFC 1319: The MD2 Message-Digest
  83.           Algorithm. April 1992.
  84.           
  85. RFC 1320  R. Rivest. RFC 1320: The MD4 Message-Digest
  86.           Algorithm. April 1992.
  87.           
  88. RFC 1321  R. Rivest. RFC 1321: The MD5 Message-Digest
  89.           Algorithm. April 1992.
  90.           
  91. RFC 1423  D. Balenson. RFC 1423: Privacy Enhancement for
  92.           Internet Electronic Mail: Part III: Algorithms,
  93.           Modes, and Identifiers. February 1993.
  94.           
  95. X.208     CCITT. Recommendation X.208: Specification of
  96.           Abstract Syntax Notation One (ASN.1). 1988.
  97.           
  98. X.209     CCITT. Recommendation X.209: Specification of
  99.           Basic Encoding Rules for Abstract Syntax Notation
  100.           One (ASN.1). 1988.
  101.           
  102. X.411     CCITT. Recommendation X.411: Message Handling
  103.           Systems: Message Transfer System: Abstract Service
  104.           Definition and Procedures.1988.
  105.           
  106. X.509     CCITT. Recommendation X.509: The Directory--
  107.           Authentication Framework. 1988.
  108.           
  109. [dBB92]   B. den Boer and A. Bosselaers. An attack on the
  110.           last two rounds of MD4. In J. Feigenbaum, editor,
  111.           Advances in Cryptology---CRYPTO '91 Proceedings,
  112.           volume 576 of Lecture Notes in Computer Science,
  113.           pages 194-203. Springer-Verlag, New York, 1992.
  114.           
  115. [dBB93]   B. den Boer  and A. Bosselaers. Collisions for the
  116.           compression function of MD5. Presented at
  117.           EUROCRYPT '93 (Lofthus, Norway, May 24-27, 1993).
  118.           
  119. [DO86]    Y. Desmedt and A.M. Odlyzko. A chosen text attack
  120.           on the RSA cryptosystem and some discrete
  121.           logarithm schemes. In H.C. Williams, editor,
  122.           Advances in Cryptology---CRYPTO '85 Proceedings,
  123.           volume 218 of Lecture Notes in Computer Science,
  124.           pages 516-521. Springer-Verlag, New York, 1986.
  125.           
  126. [Has88]   Johan Hastad. Solving simultaneous modular
  127.           equations. SIAM Journal on Computing,
  128.           17(2):336-341, April 1988.
  129.           
  130. [IM90]    Colin I'Anson and Chris Mitchell. Security defects
  131.           in CCITT Recommendation X.509--The directory
  132.           authentication framework. Computer Communications
  133.           Review, :30-34, April 1990.
  134.           
  135. [Mer90]   R.C. Merkle. Note on MD4. Unpublished manuscript,
  136.           1990.
  137.           
  138. [Mil76]   G.L. Miller. Riemann's hypothesis and tests for
  139.           primality. Journal of Computer and Systems
  140.           Sciences, 13(3):300-307, 1976.
  141.           
  142. [QC82]    J.-J. Quisquater and C. Couvreur. Fast
  143.           decipherment algorithm for RSA public-key
  144.           cryptosystem. Electronics Letters, 18(21):905-907,
  145.           October 1982.
  146.           
  147. [RSA78]   R.L. Rivest, A. Shamir, and L. Adleman. A method
  148.           for obtaining digital signatures and public-key
  149.           cryptosystems. Communications of the ACM,
  150.           21(2):120-126, February 1978.
  151.           
  152.  
  153. 3. Definitions
  154.  
  155. For the purposes of this standard, the following definitions
  156. apply.
  157.  
  158. AlgorithmIdentifier: A type that identifies an algorithm (by
  159. object identifier) and associated parameters. This type is
  160. defined in X.509.
  161.  
  162. ASN.1: Abstract Syntax Notation One, as defined in X.208.
  163.  
  164. BER: Basic Encoding Rules, as defined in X.209.
  165.  
  166. DES: Data Encryption Standard, as defined in FIPS PUB 46-1.
  167.  
  168. MD2: RSA Data Security, Inc.'s MD2 message-digest algorithm,
  169. as defined in RFC 1319.
  170.  
  171. MD4: RSA Data Security, Inc.'s MD4 message-digest algorithm,
  172. as defined in RFC 1320.
  173.  
  174. MD5: RSA Data Security, Inc.'s MD5 message-digest algorithm,
  175. as defined in RFC 1321.
  176.  
  177. modulus: Integer constructed as the product of two primes.
  178.  
  179. PEM: Internet Privacy-Enhanced Mail, as defined in RFC 1423
  180. and related documents.
  181.  
  182. RSA: The RSA public-key cryptosystem, as defined in [RSA78].
  183.  
  184. private key: Modulus and private exponent.
  185.  
  186. public key: Modulus and public exponent.
  187.  
  188.  
  189. 4. Symbols and abbreviations
  190.  
  191. Upper-case italic symbols (e.g., BT) denote octet strings
  192. and bit strings (in the case of the signature S); lower-case
  193. italic symbols (e.g., c) denote integers.
  194.  
  195. ab   hexadecimal octet value  c    exponent
  196. BT   block type               d    private exponent
  197. D    data                     e    public exponent
  198. EB   encryption block         k    length of modulus in
  199.                                      octets
  200. ED   encrypted data           n    modulus
  201. M    message                  p, q  prime factors of modulus
  202. MD   message digest           x    integer encryption block
  203. MD'  comparative message      y    integer encrypted data
  204.        digest
  205. PS   padding string           mod n  modulo n
  206. S    signature                X || Y  concatenation of X, Y
  207.                 ||X||  length in octets of X
  208.  
  209.  
  210. 5. General overview
  211.  
  212. The next six sections specify key generation, key syntax,
  213. the encryption process, the decryption process, signature
  214. algorithms, and object identifiers.
  215.  
  216. Each entity shall generate a pair of keys: a public key and
  217. a private key. The encryption process shall be performed
  218. with one of the keys and the decryption process shall be
  219. performed with the other key. Thus the encryption process
  220. can be either a public-key operation or a private-key
  221. operation, and so can the decryption process. Both processes
  222. transform an octet string to another octet string. The
  223. processes are inverses of each other if one process uses an
  224. entity's public key and the other process uses the same
  225. entity's private key.
  226.  
  227. The encryption and decryption processes can implement either
  228. the classic RSA transformations, or variations with padding.
  229.  
  230.  
  231. 6. Key generation
  232.  
  233. This section describes RSA key generation.
  234.  
  235. Each entity shall select a positive integer e as its public
  236. exponent.
  237.  
  238. Each entity shall privately and randomly select two distinct
  239. odd primes p and q such that (p-1) and e have no common
  240. divisors, and (q-1) and e have no common divisors.
  241.  
  242. The public modulus n shall be the product of the private
  243. prime factors p and q:
  244.  
  245.                           n = pq .
  246.  
  247. The private exponent shall be a positive integer d such that
  248. de-1 is divisible by both p-1 and q-1.
  249.  
  250. The length of the modulus n in octets is the integer k
  251. satisfying
  252.  
  253.                  2^(8(k-1)) <= n < 2^(8k) .
  254.  
  255. The length k of the modulus must be at least 12 octets to
  256. accommodate the block formats in this standard (see Section
  257. 8).
  258.  
  259.  
  260. Notes.
  261.  
  262.      1.   The public exponent may be standardized in
  263.           specific applications. The values 3 and F4 (65537)
  264.           may have some practical advantages, as noted in
  265.           X.509 Annex C.
  266.           
  267.      2.   Some additional conditions on the choice of primes
  268.           may well be taken into account in order to deter
  269.           factorization of the modulus. These security
  270.           conditions fall outside the scope of this
  271.           standard. The lower bound on the length k is to
  272.           accommodate the block formats, not for security.
  273.           
  274.  
  275. 7. Key syntax
  276.  
  277. This section gives the syntax for RSA public and private
  278. keys.
  279.  
  280.  
  281. 7.1 Public-key syntax
  282.  
  283. An RSA public key shall have ASN.1 type RSAPublicKey:
  284.  
  285. RSAPublicKey ::= SEQUENCE {
  286.   modulus INTEGER, -- n
  287.   publicExponent INTEGER -- e }
  288.  
  289. (This type is specified in X.509 and is retained here for
  290. compatibility.)
  291.  
  292. The fields of type RSAPublicKey have the following meanings:
  293.  
  294.      o    modulus is the modulus n.
  295.           
  296.      o    publicExponent is the public exponent e.
  297.           
  298.  
  299. 7.2 Private-key syntax
  300.  
  301. An RSA private key shall have ASN.1 type RSAPrivateKey:
  302.  
  303. RSAPrivateKey ::= SEQUENCE {
  304.   version Version,
  305.   modulus INTEGER, -- n
  306.   publicExponent INTEGER, -- e
  307.   privateExponent INTEGER, -- d
  308.   prime1 INTEGER, -- p
  309.   prime2 INTEGER, -- q
  310.   exponent1 INTEGER, -- d mod (p-1)
  311.   exponent2 INTEGER, -- d mod (q-1)
  312.   coefficient INTEGER -- (inverse of q) mod p }
  313.  
  314. Version ::= INTEGER
  315.  
  316. The fields of type RSAPrivateKey have the following
  317. meanings:
  318.  
  319.      o    version is the version number, for compatibility
  320.           with future revisions of this standard. It shall
  321.           be 0 for this version of the standard.
  322.           
  323.      o    modulus is the modulus n.
  324.           
  325.      o    publicExponent is the public exponent e.
  326.           
  327.      o    privateExponent is the private exponent d.
  328.           
  329.      o    prime1 is the prime factor p of n.
  330.           
  331.      o    prime2 is the prime factor q of n.
  332.           
  333.      o    exponent1 is d mod (p-1).
  334.           
  335.      o    exponent2 is d mod (q-1).
  336.           
  337.      o    coefficient is the Chinese Remainder Theorem
  338.           coefficient q-1 mod p.
  339.           
  340.  
  341. Notes.
  342.  
  343.      1.   An RSA private key logically consists of only the
  344.           modulus n and the private exponent d. The presence
  345.           of the values p, q, d mod (p-1), d mod (p-1), and
  346.           q-1 mod p is intended for efficiency, as
  347.           Quisquater and Couvreur have shown [QC82]. A
  348.           private-key syntax that does not include all the
  349.           extra values can be converted readily to the
  350.           syntax defined here, provided the public key is
  351.           known, according to a result by Miller [Mil76].
  352.           
  353.      2.   The presence of the public exponent e is intended
  354.           to make it straightforward to derive a public key
  355.           from the private key.
  356.           
  357.  
  358. 8. Encryption process
  359.  
  360. This section describes the RSA encryption process.
  361.  
  362. The encryption process consists of four steps: encryption-
  363. block formatting, octet-string-to-integer conversion, RSA
  364. computation, and integer-to-octet-string conversion. The
  365. input to the encryption process shall be an octet string D,
  366. the data; an integer n, the modulus; and an integer c, the
  367. exponent. For a public-key operation, the integer c shall be
  368. an entity's public exponent e; for a private-key operation,
  369. it shall be an entity's private exponent d. The output from
  370. the encryption process shall be an octet string ED, the
  371. encrypted data.
  372.  
  373. The length of the data D shall not be more than k-11 octets,
  374. which is positive since the length k of the modulus is at
  375. least 12 octets. This limitation guarantees that the length
  376. of the padding string PS is at least eight octets, which is
  377. a security condition.
  378.  
  379.  
  380. Notes.
  381.  
  382.      1.   In typical applications of this standard to
  383.           encrypt content-encryption keys and message
  384.           digests, one would have ||D|| <= 30. Thus the
  385.           length of the RSA modulus will need to be at least
  386.           328 bits (41 octets), which is reasonable and
  387.           consistent with security recommendations.
  388.           
  389.      2.   The encryption process does not provide an
  390.           explicit integrity check to facilitate error
  391.           detection should the encrypted data be corrupted
  392.           in transmission. However, the structure of the
  393.           encryption block guarantees that the probability
  394.           that corruption is undetected is less than 2-16,
  395.           which is an upper bound on the probability that a
  396.           random encryption block looks like block type 02.
  397.           
  398.      3.   Application of private-key operations as defined
  399.           here to data other than an octet string containing
  400.           a message digest is not recommended and is subject
  401.           to further study.
  402.           
  403.      4.   This standard may be extended to handle data of
  404.           length more than k-11 octets.
  405.           
  406.  
  407. 8.1 Encryption-block formatting
  408.  
  409. A block type BT, a padding string PS, and the data D shall
  410. be formatted into an octet string EB, the encryption block.
  411.  
  412.               EB = 00 || BT || PS || 00 || D .           (1)
  413.  
  414. The block type BT shall be a single octet indicating the
  415. structure of the encryption block. For this version of the
  416. standard it shall have value 00, 01, or 02. For a private-
  417. key operation, the block type shall be 00 or 01. For a
  418. public-key operation, it shall be 02.
  419.  
  420. The padding string PS shall consist of k-3-||D|| octets. For
  421. block type 00, the octets shall have value 00; for block
  422. type 01, they shall have value FF; and for block type 02,
  423. they shall be pseudorandomly generated and nonzero. This
  424. makes the length of the encryption block EB equal to k.
  425.  
  426.  
  427. Notes.
  428.  
  429.      1.   The leading 00 octet ensures that the encryption
  430.           block, converted to an integer, is less than the
  431.           modulus.
  432.           
  433.      2.   For block type 00, the data D must begin with a
  434.           nonzero octet or have known length so that the
  435.           encryption block can be parsed unambiguously. For
  436.           block types 01 and 02, the encryption block can be
  437.           parsed unambiguously since the padding string PS
  438.           contains no octets with value 00 and the padding
  439.           string is separated from the data D by an octet
  440.           with value 00.
  441.           
  442.      3.   Block type 01 is recommended for private-key
  443.           operations. Block type 01 has the property that
  444.           the encryption block, converted to an integer, is
  445.           guaranteed to be large, which prevents certain
  446.           attacks of the kind proposed by Desmedt and
  447.           Odlyzko [DO86].
  448.           
  449.      4.   Block types 01 and 02 are compatible with PEM RSA
  450.           encryption of content-encryption keys and message
  451.           digests as described in RFC 1423.
  452.           
  453.      5.   For block type 02, it is recommended that the
  454.           pseudorandom octets be generated independently for
  455.           each encryption process, especially if the same
  456.           data is input to more than one encryption process.
  457.           Hastad's results [Has88] motivate this
  458.           recommendation.
  459.           
  460.      6.   For block type 02, the padding string is at least
  461.           eight octets long, which is a security condition
  462.           for public-key operations that prevents an
  463.           attacker from recoving data by trying all possible
  464.           encryption blocks. For simplicity, the minimum
  465.           length is the same for block type 01.
  466.           
  467.      7.   This standard may be extended in the future to
  468.           include other block types.
  469.           
  470.  
  471. 8.2 Octet-string-to-integer conversion
  472.  
  473. The encryption block EB shall be converted to an integer x,
  474. the integer encryption block. Let EB1, ..., EBk be the octets
  475. of EB from first to last. Then the integer x shall satisfy
  476.  
  477.                        k
  478.                  x =  SUM  2^(8(k-i)) EBi .              (2)
  479.                      i = 1
  480.  
  481. In other words, the first octet of EB has the most
  482. significance in the integer and the last octet of EB has the
  483. least significance.
  484.  
  485. Note. The integer encryption block x satisfies 0 <= x <  n
  486. since EB1 = 00 and 2^(8(k-1)) <= n.
  487.  
  488.  
  489. 8.3 RSA computation
  490.  
  491. The integer encryption block x shall be raised to the power
  492. c modulo n to give an integer y, the integer encrypted data.
  493.  
  494.                 y = x^c mod n,  0 <= y < n .
  495.  
  496. This is the classic RSA computation.
  497.  
  498.  
  499. 8.4 Integer-to-octet-string conversion
  500.  
  501. The integer encrypted data y shall be converted to an octet
  502. string ED of length k, the encrypted data. The encrypted
  503. data ED shall satisfy
  504.  
  505.                        k
  506.                  y =  SUM  2^(8(k-i)) EDi .              (3)
  507.                      i = 1
  508.  
  509. where ED1, ..., EDk are the octets of ED from first to last.
  510.  
  511. In other words, the first octet of ED has the most
  512. significance in the integer and the last octet of ED has the
  513. least significance.
  514.  
  515.  
  516. 9. Decryption process
  517.  
  518. This section describes the RSA decryption process.
  519.  
  520. The decryption process consists of four steps: octet-string-
  521. to-integer conversion, RSA computation, integer-to-octet-
  522. string conversion, and encryption-block parsing. The input
  523. to the decryption process shall be an octet string ED, the
  524. encrypted data; an integer n, the modulus; and an integer c,
  525. the exponent. For a public-key operation, the integer c
  526. shall be an entity's public exponent e; for a private-key
  527. operation, it shall be an entity's private exponent d. The
  528. output from the decryption process shall be an octet string
  529. D, the data.
  530.  
  531. It is an error if the length of the encrypted data ED is not
  532. k.
  533.  
  534. For brevity, the decryption process is described in terms of
  535. the encryption process.
  536.  
  537.  
  538. 9.1 Octet-string-to-integer conversion
  539.  
  540. The encrypted data ED shall be converted to an integer y,
  541. the integer encrypted data, according to Equation (3).
  542.  
  543. It is an error if the integer encrypted data y does not
  544. satisfy 0 <= y < n.
  545.  
  546.  
  547. 9.2 RSA computation
  548.  
  549. The integer encrypted data y shall be raised to the power c
  550. modulo n to give an integer x, the integer encryption block.
  551.  
  552.                 x = y^c mod n,  0 <= x < n .
  553.  
  554. This is the classic RSA computation.
  555.  
  556.  
  557. 9.3 Integer-to-octet-string conversion
  558.  
  559. The integer encryption block x shall be converted to an
  560. octet string EB of length k, the encryption block, according
  561. to Equation (2).
  562.  
  563.  
  564. 9.4 Encryption-block parsing
  565.  
  566. The encryption block EB shall be parsed into a block type
  567. BT, a padding string PS, and the data D according to
  568. Equation (1).
  569.  
  570. It is an error if any of the following conditions occurs:
  571.  
  572.      o    The encryption block EB cannot be parsed
  573.           unambiguously (see notes to Section 8.1).
  574.           
  575.      o    The padding string PS consists of fewer than eight
  576.           octets, or is inconsistent with the block type BT.
  577.           
  578.      o    The decryption process is a public-key operation
  579.           and the block type BT is not 00 or 01, or the
  580.           decryption process is a private-key operation and
  581.           the block type is not 02.
  582.           
  583.  
  584. 10. Signature algorithms
  585.  
  586. This section defines three signature algorithms based on the
  587. RSA encryption process described in Sections 8 and 9. The
  588. intended use of the signature algorithms is in signing
  589. X.509/PEM certificates and certificate-revocation lists,
  590. PKCS #6 extended certificates, and other objects employing
  591. digital signatures such as X.401 message tokens. The
  592. algorithms are not intended for use in constructing digital
  593. signatures in PKCS #7. The first signature algorithm
  594. (informally, "MD2 with RSA") combines the MD2 message-digest
  595. algorithm with RSA, the second (informally, "MD4 with RSA")
  596. combines the MD4 message-digest algorithm with RSA, and the
  597. third (informally, "MD5 with RSA") combines the MD5 message-
  598. digest algorithm with RSA.
  599.  
  600. This section describes the signature process and the
  601. verification process for the two algorithms. The "selected"
  602. message-digest algorithm shall be either MD2 or MD5,
  603. depending on the signature algorithm. The signature process
  604. shall be performed with an entity's private key and the
  605. verification process shall be performed with an entity's
  606. public key. The signature process transforms an octet string
  607. (the message) to a bit string (the signature); the
  608. verification process determines whether a bit string (the
  609. signature) is the signature of an octet string (the
  610. message).
  611.  
  612. Note. The only difference between the signature algorithms
  613. defined here and one of the the methods by which signatures
  614. (encrypted message digests) are constructed in PKCS #7 is
  615. that signatures here are represented here as bit strings,
  616. for consistency with the X.509 SIGNED macro. In PKCS #7
  617. encrypted message digests are octet strings.
  618.  
  619.  
  620. 10.1 Signature process
  621.  
  622. The signature process consists of four steps: message
  623. digesting, data encoding, RSA encryption, and octet-string-
  624. to-bit-string conversion. The input to the signature process
  625. shall be an octet string M, the message; and a signer's
  626. private key. The output from the signature process shall be
  627. a bit string S, the signature.
  628.  
  629.  
  630. 10.1.1 Message digesting
  631.  
  632. The message M shall be digested with the selected message-
  633. digest algorithm to give an octet string MD, the message
  634. digest.
  635.  
  636.  
  637. 10.1.2 Data encoding
  638.  
  639. The message digest MD and a message-digest algorithm
  640. identifier shall be combined into an ASN.1 value of type
  641. DigestInfo, described below, which shall be BER-encoded to
  642. give an octet string D, the data.
  643.  
  644. DigestInfo ::= SEQUENCE {
  645.   digestAlgorithm DigestAlgorithmIdentifier,
  646.   digest Digest }
  647.  
  648. DigestAlgorithmIdentifier ::= AlgorithmIdentifier
  649.  
  650. Digest ::= OCTET STRING
  651.  
  652. The fields of type DigestInfo have the following meanings:
  653.  
  654.      o    digestAlgorithm identifies the message-digest
  655.           algorithm (and any associated parameters). For
  656.           this application, it should identify the selected
  657.           message-digest algorithm, MD2, MD4 or MD5. For
  658.           reference, the relevant object identifiers are the
  659.           following:
  660.           
  661. md2 OBJECT IDENTIFIER ::=
  662.   { iso(1) member-body(2) US(840) rsadsi(113549)
  663.       digestAlgorithm(2) 2 }
  664. md4 OBJECT IDENTIFIER ::=
  665.   { iso(1) member-body(2) US(840) rsadsi(113549)
  666.       digestAlgorithm(2) 4 }
  667. md5 OBJECT IDENTIFIER ::=
  668.   { iso(1) member-body(2) US(840) rsadsi(113549)
  669.       digestAlgorithm(2) 5 }
  670.  
  671.           For these object identifiers, the parameters field
  672.           of the digestAlgorithm value should be NULL.
  673.           
  674.      o    digest is the result of the message-digesting
  675.           process, i.e., the message digest MD.
  676.           
  677.  
  678. Notes.
  679.  
  680.      1.   A message-digest algorithm identifier is included
  681.           in the DigestInfo value to limit the damage
  682.           resulting from the compromise of one message-
  683.           digest algorithm. For instance, suppose an
  684.           adversary were able to find messages with a given
  685.           MD2 message digest. That adversary might try to
  686.           forge a signature on a message by finding an
  687.           innocuous-looking message with the same MD2
  688.           message digest, and coercing a signer to sign the
  689.           innocuous-looking message. This attack would
  690.           succeed only if the signer used MD2. If the
  691.           DigestInfo value contained only the message
  692.           digest, however, an adversary could attack signers
  693.           that use any message digest.
  694.           
  695.      2.   Although it may be claimed that the use of a
  696.           SEQUENCE type violates the literal statement in
  697.           the X.509 SIGNED and SIGNATURE macros that a
  698.           signature is an ENCRYPTED OCTET STRING (as opposed
  699.           to ENCRYPTED SEQUENCE), such a literal
  700.           interpretation need not be required, as I'Anson
  701.           and Mitchell point out [IM90].
  702.           
  703.      3.   No reason is known that MD4 would not be
  704.           sufficient for very high security digital
  705.           signature schemes, but because MD4 was designed to
  706.           be exceptionally fast, it is "at the edge" in
  707.           terms of risking successful cryptanalytic attack.
  708.           A message-digest algorithm can be considered
  709.           "broken" if someone can find a collision: two
  710.           messages with the same digest. While collisions
  711.           have been found in variants of MD4 with only two
  712.           digesting "rounds" [Mer90][dBB92], none have been
  713.           found in MD4 itself, which has three rounds. After
  714.           further critical review, it may be appropriate to
  715.           consider MD4 for very high security applications.
  716.           
  717.           MD5, which has four rounds and is proportionally
  718.           slower than MD4, is recommended until the
  719.           completion of MD4's review. The reported
  720.           "pseudocollisions" in MD5's internal compression
  721.           function [dBB93] do not appear to have any
  722.           practical impact on  MD5's security.
  723.           
  724.           MD2, the slowest of the three, has the most
  725.           conservative design. No attacks on MD2 have been
  726.           published.
  727.           
  728.  
  729. 10.1.3 RSA encryption
  730.  
  731. The data D shall be encrypted with the signer's RSA private
  732. key as described in Section 7 to give an octet string ED,
  733. the encrypted data. The block type shall be 01. (See Section
  734. 8.1.)
  735.  
  736.  
  737. 10.1.4 Octet-string-to-bit-string conversion
  738.  
  739. The encrypted data ED shall be converted into a bit string
  740. S, the signature. Specifically, the most significant bit of
  741. the first octet of the encrypted data shall become the first
  742. bit of the signature, and so on through the least
  743. significant bit of the last octet of the encrypted data,
  744. which shall become the last bit of the signature.
  745.  
  746. Note. The length in bits of the signature S is a multiple of
  747. eight.
  748.  
  749.  
  750. 10.2 Verification process
  751.  
  752. The verification process for both signature algorithms
  753. consists of four steps: bit-string-to-octet-string
  754. conversion, RSA decryption, data decoding, and message
  755. digesting and comparison. The input to the verification
  756. process shall be an octet string M, the message; a signer's
  757. public key; and a bit string S, the signature. The output
  758. from the verification process shall be an indication of
  759. success or failure.
  760.  
  761.  
  762. 10.2.1 Bit-string-to-octet-string conversion
  763.  
  764. The signature S shall be converted into an octet string ED,
  765. the encrypted data. Specifically, assuming that the length
  766. in bits of the signature S is a multiple of eight, the first
  767. bit of the signature shall become the most significant bit
  768. of the first octet of the encrypted data, and so on through
  769. the last bit of the signature, which shall become the least
  770. significant bit of the last octet of the encrypted data.
  771.  
  772. It is an error if the length in bits of the signature S is
  773. not a multiple of eight.
  774.  
  775.  
  776. 10.2.2 RSA decryption
  777.  
  778. The encrypted data ED shall be decrypted with the signer's
  779. RSA public key as described in Section 8 to give an octet
  780. string D, the data.
  781.  
  782. It is an error if the block type recovered in the decryption
  783. process is not 01. (See Section 9.4.)
  784.  
  785.  
  786. 10.2.3 Data decoding
  787.  
  788. The data D shall be BER-decoded to give an ASN.1 value of
  789. type DigestInfo, which shall be separated into a message
  790. digest MD and a message-digest algorithm identifier. The
  791. message-digest algorithm identifier shall determine the
  792. "selected" message-digest algorithm for the next step.
  793.  
  794. It is an error if the message-digest algorithm identifier
  795. does not identify the MD2, MD4 or MD5 message-digest
  796. algorithm.
  797.  
  798.  
  799. 10.2.4 Message digesting and comparison
  800.  
  801. The message M shall be digested with the selected message-
  802. digest algorithm to give an octet string MD', the
  803. comparative message digest. The verification process shall
  804. succeed if the comparative message digest MD' is the same as
  805. the message digest MD, and the verification process shall
  806. fail otherwise.
  807.  
  808.  
  809. 11. Object identifiers
  810.  
  811. This standard defines five object identifiers: pkcs-1,
  812. rsaEncryption, md2WithRSAEncryption, md4WithRSAEncryption,
  813. and md5WithRSAEncryption.
  814.  
  815. The object identifier pkcs-1 identifies this standard.
  816.  
  817. pkcs-1 OBJECT IDENTIFIER ::=
  818.  
  819.   { iso(1) member-body(2) US(840) rsadsi(113549)
  820.       pkcs(1) 1 }
  821.  
  822. The object identifier rsaEncryption identifies RSA public
  823. and private keys as defined in Section 7 and the RSA
  824. encryption and decryption processes defined in Sections 8
  825. and 9.
  826.  
  827. rsaEncryption OBJECT IDENTIFIER ::= { pkcs-1 1 }
  828.  
  829. The rsaEncryption object identifier is intended to be used
  830. in the algorithm field of a value of type
  831. AlgorithmIdentifier. The parameters field of that type,
  832. which has the algorithm-specific syntax ANY DEFINED BY
  833. algorithm, would have ASN.1 type NULL for this algorithm.
  834.  
  835. The object identifiers md2WithRSAEncryption,
  836. md4WithRSAEncryption, md5WithRSAEncryption, identify,
  837. respectively, the "MD2 with RSA," "MD4 with RSA," and "MD5
  838. with RSA" signature and verification processes defined in
  839. Section 10.
  840.  
  841. md2WithRSAEncryption OBJECT IDENTIFIER ::= { pkcs-1 2 }
  842. md4WithRSAEncryption OBJECT IDENTIFIER ::= { pkcs-1 3 }
  843. md5WithRSAEncryption OBJECT IDENTIFIER ::= { pkcs-1 4 }
  844.  
  845. These object identifiers are intended to be used in the
  846. algorithm field of a value of type AlgorithmIdentifier. The
  847. parameters field of that type, which has the algorithm-
  848. specific syntax ANY DEFINED BY algorithm, would have ASN.1
  849. type NULL for these algorithms.
  850.  
  851. Note. X.509's object identifier rsa also identifies RSA
  852. public keys as defined in Section 7, but does not identify
  853. private keys, and identifies different encryption and
  854. decryption processes. It is expected that some applications
  855. will identify public keys by rsa. Such public keys are
  856. compatible with this standard; an rsaEncryption process
  857. under an rsa public key is the same as the rsaEncryption
  858. process under an rsaEncryption public key.
  859.  
  860.  
  861. Revision history
  862.  
  863.  
  864. Versions 1.0-1.3
  865.  
  866. Versions 1.0-1.3 were distributed to participants in RSA
  867. Data Security, Inc.'s Public-Key Cryptography Standards
  868. meetings in February and March 1991.
  869.  
  870.  
  871. Version 1.4
  872.  
  873. Version 1.4 is part of the June 3, 1991 initial public
  874. release of PKCS. Version 1.4 was published as NIST/OSI
  875. Implementors' Workshop document SEC-SIG-91-18.
  876.  
  877.  
  878. Version 1.5
  879.  
  880. Version 1.5 incorporates several editorial changes,
  881. including updates to the references and the addition of a
  882. revision history. The following substantive changes were
  883. made:
  884.  
  885.      o    Section 10: "MD4 with RSA" signature and
  886.           verification processes are added.
  887.           
  888.      o    Section 11: md4WithRSAEncryption object identifier
  889.           is added.
  890.           
  891.  
  892. Author's address
  893.  
  894. RSA Laboratories              (415) 595-7703
  895. 100 Marine Parkway            (415) 595-4126 (fax)
  896. Redwood City, CA  94065  USA  pkcs-editor@rsa.com
  897.