`
`
`
`
`
`ARCHIVED PUBLICATION
`
`
`
`The attached publication,
`
`FIPS Publication 180-2
`(dated August 1, 2002),
`
`was superseded on February 25, 2004 and is provided here
`only for historical purposes.
`
`
`
`For the most current revision of this publication, see:
`http://csrc.nist.gov/publications/PubsFIPS.html#fips180-4.
`
`
`
`APPLE EXHIBIT 1109
`Page 1 of 76
`
`

`

`
`
`
`
`
`
`
`
`Federal Information
`
`
`Processing Standards Publication 180-2
`
`
`
`2002 August 1
`
`
`
`Announcing the
`
`
`
`SECURE HASH STANDARD
`
`
`
`Federal Information Processing Standards Publications (FIPS PUBS) are issued by the National
`Institute of Standards and Technology (NIST) after approval by the Secretary of Commerce
`pursuant to Section 5131 of the Information Technology Management Reform Act of 1996
`
`(Public Law 104-106), and the Computer Security Act of 1987 (Public Law 100-235).
`
`
`
`1. Name of Standard: Secure Hash Signature Standard (SHS) (FIPS PUB 180-2).
`
`
`
`2. Category of Standard: Computer Security Standard, Cryptography.
`
`
`3. Explanation: This Standard specifies four secure hash algorithms - SHA-1, SHA-256,
`
`SHA-384, and SHA-512 -
`for computing a condensed representation of electronic data
`(message). When a message of any length < 264 bits (for SHA-1 and SHA-256) or < 2128 bits (for
`SHA-384 and SHA-512) is input to an algorithm, the result is an output called a message digest.
`The message digests range in length from 160 to 512 bits, depending on the algorithm. Secure
`hash algorithms are typically used with other cryptographic algorithms, such as digital signature
`
`algorithms and keyed-hash message authentication codes, or in the generation of random
`
`numbers (bits).
`
`
`The four hash algorithms specified in this standard are called secure because, for a given
`algorithm, it is computationally infeasible 1) to find a message that corresponds to a given
`message digest, or 2) to find two different messages that produce the same message digest. Any
`change to a message will, with a very high probability, result in a different message digest. This
`will result in a verification failure when the secure hash algorithm is used with a digital signature
`
`algorithm or a keyed-hash message authentication algorithm.
`
`This standard supersedes FIPS 180-1, adding three algorithms that are capable of producing
`larger message digests. The SHA-1 algorithm specified herein is the same algorithm that was
`specified previously in FIPS 180-1, although some of the notation has been modified to be
`
`consistent with the notation used in the SHA-256, SHA-384, and SHA-512 algorithms.
`
`
`
`4. Approving Authority: Secretary of Commerce.
`
`
`5. Maintenance Agency: U.S. Department of Commerce, National Institute of Standards and
`
`Technology (NIST), Information Technology Laboratory (ITL).
`
`
`APPLE EXHIBIT 1109
`Page 2 of 76
`
`

`

`
`
`
`
`
`
`
`
`
`
` Implementation Schedule: This standard becomes effective on February 1, 2003.
`
` 6. Applicability: This standard is applicable to all Federal departments and agencies for the
`
`protection of sensitive unclassified information that is not subject to section 2315 of Title 10,
`United States Code, or section 3502(2) of Title 44, United States Code. This standard shall be
`implemented whenever a secure hash algorithm is required for Federal applications, including
`use by other cryptographic algorithms and protocols. The adoption and use of this standard is
`available to private and commercial organizations.
`
`
` Specifications : Federal Information Processing Standard (FIPS) 180-2, Secure Hash
` 7.
`
`
` Standard (SHS) (affixed).
`
`
`Implementations: The secure hash algorithms specified herein may be implemented in
`8.
`software, firmware, hardware or any combination thereof. Only algorithm implementations that
`are validated by NIST will be considered as complying with this standard. Information about the
`planned validation program can be obtained at http://csrc.nist.gov/cryptval/ or from the National
`Institute of Standards and Technology, Information Technology Laboratory, Attn: SHS
`
`Validation, 100 Bureau Drive Stop 8930, Gaithersburg, MD 20899-8930.
`
`
` 9.
`
`
`10. Patents : Implementations of the secure hash algorithms in this standard may be covered by
`
`U.S. or foreign patents.
`
`
`11. Export Control: Certain cryptographic devices and technical data regarding them are
`subject to Federal export controls. Exports of cryptographic modules implementing this standard
`and technical data regarding them must comply with these Federal regulations and be licensed by
`the Bureau of Export Administration of the U.S. Department of Commerce. Applicable Federal
`government export controls are specified in Title 15, Code of Federal Regulations (CFR) Part
`
`740.17; Title 15, CFR Part 742; and Title 15, CFR Part 774, Category 5, Part 2.
`
`
`
`12. Qualifications: While it is the intent of this standard to specify general security
`requirements for generating a message digest, conformance to this standard does not assure that a
`particular implementation is secure. The responsible authority in each agency or department
`
`shall assure that an overall implementation provides an acceptable level of security. This
`
`standard will be reviewed every five years in order to assess its adequacy.
`
`
`
`13. Waiver Procedure. Under certain exceptional circumstances, the heads of Federal
`agencies, or their delegates, may approve waivers to Federal Information Processing Standards
`(FIPS). The heads of such agencies may redelegate such authority only to a senior official
`designated pursuant to Section 3506(b) of Title 44, U.S. Code. Waivers shall be granted only
`
`when compliance with this standard would
`
`
`
`
`
`
`
`
`
`a. adversely affect the accomplishment of the mission of an operator of a Federal computer
`
`system or
`
`b. cause a major adverse financial impact on the operator that is not offset by government-
`
`wide savings.
`
`ii
`
`APPLE EXHIBIT 1109
`Page 3 of 76
`
`

`

`
`
`
`
`
`
`Agency heads may act upon a written waiver request containing the information detailed above.
`Agency heads may also act without a written waiver request when they determine that conditions
`for meeting the standard cannot be met. Agency heads may approve waivers only by a written
`decision that explains the basis on which the agency head made the required finding(s). A copy
`of each such decision, with procurement sensitive or classified portions clearly identified, shall
`be sent to: National Institute of Standards and Technology; ATTN: FIPS Waiver Decision,
`Information Technology Laboratory, 100 Bureau Drive, Stop 8900, Gaithersburg, MD 20899­
`8900.
`
`
`In addition, a notice of each waiver granted and each delegation of authority to approve waivers
`shall be sent promptly to the Committee on Government Operations of the House of
`
`Representatives and the Committee on Government Affairs of the Senate and shall be published
`promptly in the Federal Register.
`
`
`When the determination on a waiver applies to the procurement of equipment and/or services, a
`notice of the waiver determination must be published in the Commerce Business Daily as a part
`of the notice of solicitation for offers of an acquisition or, if the waiver determination is made
`after that notice is published, by amendment to such notice.
`
`
`A copy of the waiver, any supporting documents, the document approving the waiver and any
`supporting and accompanying documents, with such deletions as the agency is authorized and
`decides to make under Section 552(b) of Title 5, U.S. Code, shall be part of the procurement
`documentation and retained by the agency.
`
`
`14. Where to Obtain Copies of the Standard: This publication is available electronically by
`
`accessing http://csrc.nist.gov/publications/. A
`list of other available computer security
`
`publications, including ordering information, can be obtained from NIST Publications List 91,
`which is available at the same web site. Alternatively, copies of NIST computer security
`
`publications are available from: National Technical Information Service (NTIS), 5285 Port
`Royal Road, Springfield, VA 22161.
`
`
`
`
`
`
`
` iii
`
`APPLE EXHIBIT 1109
`Page 4 of 76
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
` iv
`
`iv
`
`APPLE EXHIBIT 1109
`Page 5 of 76
`
`APPLE EXHIBIT 1109
`Page 5 of 76
`
`

`

`
`
`
`
`
` 1.
`
`
`
`
`
`
`
`
`
` Federal Information
`
`
` Processing Standards Publication 180-2
`
`
`
`2002 August 1
`
`
`
`Specifications for the
`
`
`SECURE HASH STANDARD
`
`
`
`
`Table Of Contents
`
`
`
` INTRODUCTION ..............................................................................................................................................................3
`
`
`
`
` 2. DEFINITIONS.....................................................................................................................................................................4
`
`
`
`
`4.
`
`
`5.
`
`
`2.1 GLOSSARY OF TERMS AND ACRONYMS.................................................................................................................... 4
`
`
`
`2.2 ALGORITHM PARAMETERS, SYMBOLS, AND TERMS............................................................................................... 4
`
`
`
`2.2.1 Parameters........................................................................................................................................................4
`
`
`
`2.2.2 Symbols..............................................................................................................................................................5
`
`
`
`3. NOTATION AND CONVENTIONS .............................................................................................................................6
`
`
`
`3.1 BIT STRINGS AND INTEGERS.......................................................................................................................................6
`
`
`
`3.2 OPERATIONS ON WORDS.............................................................................................................................................7
`
`
`
`FUNCTIONS AND CONSTANTS .................................................................................................................................9
`
`
`4.1 FUNCTIONS.................................................................................................................................................................... 9
`
`
`
`4.1.1 SHA-1 Functions..............................................................................................................................................9
`
`
`
`4.1.2 SHA-256 Functions.........................................................................................................................................9
`
`
`
`4.1.3 SHA-384 and SHA-512 Functions................................................................................................................9
`
`
`
`4.2 CONSTANTS................................................................................................................................................................. 10
`
`
`
`4.2.1 SHA-1 Constants............................................................................................................................................10
`
`
`
`4.2.2 SHA-256 Constants .......................................................................................................................................10
`
`
`
`4.2.3 SHA-384 and SHA-512 Constants..............................................................................................................10
`
`
`
`PREPROCESSING..........................................................................................................................................................12
`
`
`5.1 PADDING THE MESSAGE ............................................................................................................................................ 12
`
`
`
`5.1.1 SHA-1 and SHA-256......................................................................................................................................12
`
`
`
`5.1.2 SHA-384 and SHA-512.................................................................................................................................12
`
`
`
`5.2 PARSING THE PADDED MESSAGE ............................................................................................................................. 13
`
`
`
`5.2.1 SHA-1 and SHA-256......................................................................................................................................13
`
`
`
`5.2.2 SHA-384 and SHA-512.................................................................................................................................13
`
`
`
`5.3 SETTING THE INITIAL HASH VALUE (H(0)).............................................................................................................. 13
`
`
`
`5.3.1 SHA-1...............................................................................................................................................................13
`
`
`
`5.3.2 SHA-256 ..........................................................................................................................................................13
`
`
`
`5.3.3 SHA-384 ..........................................................................................................................................................14
`
`
`
`5.3.4 SHA-512 ..........................................................................................................................................................14
`
`
`
`SECURE HASH ALGORITHMS ................................................................................................................................15
`
`
`6.1 SHA-1..........................................................................................................................................................................15
`
`
`
`6.1.1 SHA-1 Preprocessing....................................................................................................................................15
`
`
`
`6.1.2 SHA-1 Hash Computation............................................................................................................................15
`
`
`
`6.1.3 Alternate Method for Computing a SHA-1 Message Digest...................................................................17
`
`
`
`
`6.
`
`
`APPLE EXHIBIT 1109
`Page 6 of 76
`
`

`

`
`
`
`
`
`
`
`
`
`
`
` 6.2 SHA-256...................................................................................................................................................................... 18
`
`
` 6.2.1 SHA-256 Preprocessing................................................................................................................................19
`
`
`
` 6.2.2 SHA-256 Hash Computation........................................................................................................................19
`
`
` 6.3 SHA-512...................................................................................................................................................................... 20
`
`
`
` 6.3.1 SHA-512 Preprocessing................................................................................................................................21
`
`
`
` 6.3.2 SHA-512 Hash Computation........................................................................................................................21
`
`
` 6.4 SHA-384...................................................................................................................................................................... 22
`
`
`
`
` APPENDIX A: SHA -1 EXAMPLES ....................................................................................................................................25
`
`
`
`A.1 SHA-1 EXAMPLE (ONE-BLOCK MESSAGE) ........................................................................................................... 25
`
`
`
`A.2 SHA-1 EXAMPLE (MULTI-BLOCK MESSAGE) ....................................................................................................... 27
`
`
`
`A.3 SHA-1 EXAMPLE (LONG MESSAGE) ....................................................................................................................... 32
`
`
`
`
`APPENDIX B: SHA -256 EXAMPLES ................................................................................................................................33
`
`
`
`B.1 SHA-256 EXAMPLE (ONE-BLOCK MESSAGE) ....................................................................................................... 33
`
`
`
`B.2 SHA-256 EXAMPLE (MULTI-BLOCK MESSAGE) ................................................................................................... 35
`
`
`
`B.3 SHA-256 EXAMPLE (LONG MESSAGE)................................................................................................................... 40
`
`
`
`APPENDIX C: SHA -512 EXAMPLES ................................................................................................................................41
`
`
`
`C.1 SHA-512 EXAMPLE (ONE-BLOCK MESSAGE) ....................................................................................................... 41
`
`
`
`C.2 SHA-512 EXAMPLE (MULTI-BLOCK MESSAGE) ................................................................................................... 46
`
`
`
`C.3 SHA-512 EXAMPLE (LONG MESSAGE)................................................................................................................... 55
`
`
`
`APPENDIX D:
`SHA -384 EXAMPLES ..........................................................................................................................56
`
`
`
`
`D.1 SHA-384 EXAMPLE (ONE-BLOCK MESSAGE) ....................................................................................................... 56
`
`
`
`D.2 SHA-384 EXAMPLE (MULTI-BLOCK MESSAGE) ................................................................................................... 61
`
`
`
`D.3 SHA-384 EXAMPLE (LONG MESSAGE)................................................................................................................... 70
`
`
`
`
`APPENDIX E: REFERENCES .............................................................................................................................................71
`
`
`
`
`
`
`
`2
`
`
`APPLE EXHIBIT 1109
`Page 7 of 76
`
`

`

`
`
`
`
`
`
`
`
` INTRODUCTION
` 1.
`
`
`This standard specifies four secure hash algorithms, SHA-11, SHA-256, SHA-384, and SHA­
`512. All four of the algorithms are iterative, one-way hash functions that can process a message
`to produce a condensed representation called a message digest. These algorithms enable the
`determination of a message’s integrity: any change to the message will, with a very high
`
`probability, result in a different message digest. This property is useful in the generation and
`verification of digital signatures and message authentication codes, and in the generation of
`random numbers (bits).
`
`
`Each algorithm can be described in two stages: preprocessing and hash computation.
`
`Preprocessing involves padding a message, parsing the padded message into m-bit blocks, and
`setting initialization values to be used in the hash computation. The hash computation generates
`a message schedule from the padded message and uses that schedule, along with functions,
`constants, and word operations to iteratively generate a series of hash values. The final hash
`value generated by the hash computation is used to determine the message digest.
`
`
`The four algorithms differ most significantly in the number of bits of security that are provided
`for the data being hashed – this is directly related to the message digest length. When a secure
`hash algorithm is used in conjunction with another algorithm, there may be requirements
`
`specified elsewhere that require the use of a secure hash algorithm with a certain number of bits
`of security. For example, if a message is being signed with a digital signature algorithm that
`provides 128 bits of security, then that signature algorithm may require the use of a secure hash
`algorithm that also provides 128 bits of security (e.g., SHA-256).
`
`
`Additionally, the four algorithms differ in terms of the size of the blocks and words of data that
`are used during hashing. Figure 1 presents the basic properties of all four secure hash
`
`algorithms.
`
`
`
`Algorithm Message Size
`Message Digest Size
`Word Size
`Block Size
`(bits)
`(bits)
`(bits)
`(bits)
`< 264
`160
`
`32
`
`512
`
`< 264
`256
`
`32
`
`512
`
`< 2128
`384
`
`64
`
`1024
`
`< 2128
`512
`
`64
`
`1024
`
` Figure 1: Secure Hash Algorithm Properties
`
`
`
`SHA 1 -
`
`SHA 256 -
`
`SHA 384 -
`
`SHA 512 -
`
`
`
`
`
`
`
`
` Security2
` (bits)
`
`
` 80
`
` 128
`
` 192
`
` 256
`
`
`
`
`
`
`
`1 The SHA-1 algorithm specified in this document is identical to the SHA-1 algorithm specified in FIPS 180-1 [180­
`1]. However, this specification, FIPS 180-2, uses ROTLn(X) instead of Sn (X) [180-1] to denote “circular left shift
`by n bits” (i.e., “left rotation by n bits”). This is described in Sec. 3.2. Some other notational changes have been
`
`made in order to be consistent with the specifications for SHA-256, SHA-384, and SHA-512.
`
`2 In this context, “security” refers to the fact that a birthday attack [HAC] on a message digest of size n produces a
`collision with a workfactor of approximately 2n/2.
`
`
`
`
`3
`
`
`APPLE EXHIBIT 1109
`Page 8 of 76
`
`

`

`
`
`
`
`
`
` 2.
`
`
`
` DEFINITIONS
`
`
`
`
`
`
`
`
`
` 2.1 Glossary of Terms and Acronyms
`
`
`Bit
`
`
`Byte
`
`
`FIPS
`
`
`Word
`
`
`A binary digit having a value of 0 or 1.
`
`
`
`A group of eight bits.
`
`
`
`Federal Information Processing Standard.
`
`
`A group of either 32 bits (4 bytes) or 64 bits (8 bytes), depending on the
`
`
`secure hash algorithm.
`
`
`
`
`
` 2.2 Algorithm Parameters, Symbols, and Terms
`
`
`
`
`
` 2.2.1 Parameters
`
`
` The following parameters are used in the secure hash algorithm specifications in this standard.
`
`
`a, b, c, …, h Working variables that are the w-bit words used in the computation of the
`hash values, H(i).
`
`
`
`H (i )
`
`
`
`
`(i )
`H j
`
`
`
`
`
`Kt
`
`
`k
`
`l
`
`
`
`m
`
`
`M
`
`M(i)
`
`
`(i )
`M j
`
`
`The ith hash value. H(0) is the initial hash value; H(N) is the final hash value
`
`
`and is used to determine the message digest.
`
`The jth word of the ith hash value, where H i is the left-most word of hash
`( )
`0
`
`value i.
`
`
`Constant value to be used for iteration t of the hash computation.
`
`
`Number of zeroes appended to a message during the padding step.
`
`
`Length of the message, M, in bits.
`
`Number of bits in a message block, M(i).
`
`
`
`Message to be hashed.
`
`
`Message block i, with a size of m bits.
`
`The jth word of the ith message block, where M 0
`( )
`i is the left-most word of
`
`message block i.
`
`
`
`4
`
`
`APPLE EXHIBIT 1109
`Page 9 of 76
`
`

`

`
`
`
`
`
`
`
`n
`
`
`N
`
`
`T
`
`
`w
`
`
` Wt
`
`
`
`Number of bits to be rotated or shifted when a word is operated upon.
`
`
`
`Number of blocks in the padded message.
`
`
`
`Temporary w-bit word used in the hash computation.
`
`
`
`Number of bits in a word.
`
`
`
`The tth w-bit word of the message schedule.
`
`
`
`
`
`
`2.2.2 Symbols
`The following symbols are used in the secure hash algorithm specifications, and each operates on
`
`w-bit words.
`
`
`
`
`
`
`
`
`
`
`1
`
`v
`
`¯
`
`
`
`
`+
`
`
`<<
`
`
`Bitwise AND operation.
`
`
`Bitwise OR (“inclusive-OR”) operation.
`
`Bitwise XOR (“exclusive-OR”) operation.
`
`
`
`
`Bitwise complement operation.
`
`Addition modulo 2w .
`
`
`
`Left-shift operation, where x << n is obtained by discarding the left-most n
`
`bits of the word x and then padding the result with n zeroes on the right.
`
`Right-shift operation, where x >> n is obtained by discarding the right-
`most n bits of the word x and then padding the result with n zeroes on the
`
`left.
`
`
`
`>>
`
`
`
`5
`
`
`APPLE EXHIBIT 1109
`Page 10 of 76
`
`

`

`
`
`
`
`
`
`
`
`
`
` 3.
`
`
`
` NOTATION AND CONVENTIONS
`
` 3.1 Bit Strings and Integers
`
`
` The following terminology related to bit strings and integers will be used.
`
`
`
`
`
`1. A hex digit is an element of the set {0, 1,…, 9, a,…, f}. A hex digit is the
`representation of a 4-bit string. For example, the hex digit “7” represents the 4-bit
`
`string “0111”, and the hex digit “a” represents the 4-bit string “1010”.
`
`
`
`2. A word is a w-bit string that may be represented as a sequence of hex digits. To
`convert a word to hex digits, each 4-bit string is converted to its hex digit equivalent,
`
`as described in (1) above. For example, the 32-bit string
`
`
`
`
`
`
`
`
`
`
`
`
`1010 0001 0000 0011 1111 1110 0010 0011
`
`
`
`can be expressed as “a103fe23”, and the 64-bit string
`
`
`
`1010 0001 0000 0011 1111 1110 0010 0011
`
`0011 0010 1110 1111 0011 0000 0001 1010
`
`
`
`can be expressed as “a103fe2332ef301a”.
`
`Throughout this specification, the “big-endian” convention is used when expressing
`both 32- and 64-bit words, so that within each word, the most significant bit is stored
`
`in the left-most bit position.
`
`
`3. An integer may be represented as a word or pair of words. A word representation of
`the message length, l , in bits, is required for the padding techniques of Sec. 5.1.
`
`
`An integer between 0 and 232-1 inclusive may be represented as a 32-bit word. The
`
`
`least significant four bits of the integer are represented by the right-most hex digit of
`the word representation. For example, the integer 291 = 28 + 25 + 21 + 20 =
`
`
`256+32+2+1 is represented by the hex word 00000123.
`
`The same holds true for an integer between 0 and 264-1 inclusive, which may be
`
`represented as a 64-bit word.
`
`If Z is an integer, 0 £ Z < 264, then Z = 232X + Y, where 0 £ X < 232 and 0 £ Y < 232.
`
`
`
`
`Since X and Y can be represented as 32-bit words x and y, respectively, the integer Z
`can be represented as the pair of words (x, y). This property is used for SHA-1 and
`
`SHA-256.
`
`
`6
`
`
`APPLE EXHIBIT 1109
`Page 11 of 76
`
`

`

`
`
`
`
`
`
` If Z is an integer, 0 £ Z < 2128, then Z = 264X + Y, where 0 £ X < 264 and 0 £ Y < 264.
`
`
`
`
` Since X and Y can be represented as 64-bit words x and y, respectively, the integer Z
`can be represented as the pair of words (x, y). This property is used for SHA-384 and
`SHA-512.
`
`
`
` 4. For the secure hash algorithms, the size of the message block - m bits - depends on the
`
` algorithm.
`
`
`
`
`
`a) For SHA-1 and SHA-256, each message block has 512 bits, which are
`
`represented as a sequence of sixteen 32-bit words.
`
`
`
`
`
`
`
`b) For SHA-384 and SHA-512, each message block has 1024 bits, which are
`
`represented as a sequence of sixteen 64-bit words.
`
`
`
` 3.2 Operations on Words
`
`
`The following operations are applied to w-bit words in all four secure hash algorithms. SHA-1
`and SHA-256 operate on 32-bit words (w = 32), and SHA-384 and SHA-512 operate on 64-bit
`words (w = 64).
`
`
`
`, ¯
`
`, and
`
`
`
`
`
` (see Sec. 2.2.2).
`
`1. Bitwise logical word operations: 1 , v
`
`
`2. Addition modulo 2w .
`
`
`
`The operation x + y is defined as follows. The words x and y represent integers X and
`Y, where 0 £ X < 2w and 0 £ Y < 2w . For positive integers U and V, let U modV be
`
`
` the remainder upon dividing U by V. Compute
`
`
`
`
`Z = ( X + Y ) mod 2w .
`
`
`Then 0 £ Z < 2w . Convert the integer Z to a word, z, and define z = x + y.
`
`
`
`
`3. The right shift operation SHR n(x), where x is a w-bit word and n is an integer with 0
`
`£ n < w, is defined by
`
`
`
`SHR n(x) = x >> n.
`
`
`
`This operation is used in the SHA-256, SHA-384, and SHA-512 algorithms.
`
`
`
`4. The rotate right (circular right shift) operation ROTR n(x), where x is a w-bit word
`
`and n is an integer with 0 £ n < w, is defined by
`
`
`
`ROTRn(x) = (x >> n) v
`
`
`Thus, ROTR n(x) is equivalent to a circular shift (rotation) of x by n positions to the
`right.
`
`
`
`
` (x << w - n).
`
`
`
`
`
`7
`
`
`
`
`
`
`
`
`APPLE EXHIBIT 1109
`Page 12 of 76
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`This operation is used by the SHA-256, SHA-384, and SHA-512 algorithms.
`
`
`5. The rotate left (circular left shift) operation, ROTL n(x), where x is a w-bit word and n
`
`
`is an integer with 0 £ n < w, is defined by
`
`
`
`
`
`
`
`ROTL n(x) = (x << n) v
`
`Thus, ROTL n(x) is equivalent to a circular shift (rotation) of x by n positions to the
`
` left.
`
`This operation is used only in the SHA-1 algorithm. Note that in Ref. [180-1] this
`operation was referred to as “Sn(X)”; however, the notation has been modified for
`clarity and consistency with the notation used for operations in the other secure hash
`
` algorithms.
`
`
` 6. Note the following equivalence relationships, where w is fixed in each relationship:
`
`
`
`
` (x >> w - n).
`
`ROTL n(x) » ROTR w-n(x)
`
`
`
`ROTRn(x) » ROTL w-n(x).
`
`
`
`
`
`8
`
`
`APPLE EXHIBIT 1109
`Page 13 of 76
`
`

`

`
`
`
`
`
`
`
`
`
`
` 4.
`
`
`
` FUNCTIONS AND CONSTANTS
`
` Functions
` 4.1
`
`
`This section defines the functions that are used by each of the algorithms. Although the SHA­
`256, SHA-384, and SHA-512 algorithms all use similar functions, their descriptions are
`
`separated into sections for SHA-256 (Sec. 4.1.2) and for SHA-384 and SHA-512 (Sec. 4.1.3),
`since the input and output for these functions are words of different sizes. Each of the algorithms
`include Ch(x, y, z) and Maj(x, y, z) functions; the exclusive-OR operation ( ¯
`) in these functions
`may be replaced by a bitwise OR operation (v
` ) and produce identical results.
`
`
`
` 4.1.1 SHA-1 Functions
`
`
`SHA-1 uses a sequence of logical functions, f0, f1,…, f79. Each function ft, where 0 £
`t < 79,
`
`
` operates on three 32-bit words, x, y, and z, and produces a 32-bit word as output. The function ft
`
`(x, y, z) is defined as follows:
`
`
`
`
`
`
`
`
`
`
`
`
`ft (x, y, z) =
`
`
`
`
`
`
`
`
`
`
`
`
`Ch(x, y, z) = (x 1 y) ¯
` ( x 1 z)
`y ¯
`Parity(x, y, z) = x ¯
`
`
`z
`
`
` (x 1 z) ¯
`Maj(x, y, z) = (x 1 y) ¯
`
`0 £
`
`
`
` t £
`
`
`
` 19
`
`20 £
`
`
`t £
`
`
`
` 39
`
` (y 1 z)
`
`
`40 £
`
`t £
`
`
`
` 59
`
`Parity(x, y, z) = x ¯
`
`
`y ¯
`
`
`
`z
`
`60 £
`
`
`t £
`
`
`
` 79.
`
`
`
`
`(4.1)
`
`
`
`
`
`
`4.1.2 SHA-256 Functions
`SHA-256 uses six logical functions, where each function operates on 32-bit words, which are
`
` represented as x, y, and z. The result of each function is a new 32-bit word.
`
`
`
`
`
`
`
`
`Ch( x, y, z) =
`
` Maj( x, y, z) =
`
`
` ( x 1 z)
`( x 1 y) ¯
`
`
`( x 1 y) ¯ ( x 1 z) ¯
`
`( y 1 z)
`
`
`{256}
`(x) = ROTR 2(x)
`
`
`
`0
`{256}
`(x) = ROTR6(x)
`
`
`
`
`1
` x = ROTR7(x)
`
`
`{256} ( )
`
`
`s 0
`
`
` {256} ( ) x = ROTR17(x)
`s 1
`
`
`
`
`¯
`¯
`¯
`¯
`
`
`
`
`
`
`
`
`
` ROTR13(x)
`
`
`
` ROTR11(x)
`
` ROTR18(x)
`
`
` ROTR19(x)
`
`¯
`¯
`¯
`¯
`
`
`
`
`
`
`
`
`
` ROTR22(x)
`
`
` ROTR25(x)
`
`
`
` SHR 3(x)
` SHR 10(x)
`
`
`
` (4.2)
`
` (4.3)
`
`
`
` (4.4)
`
`
` (4.5)
`
` (4.6)
`
` (4.7)
`
`
`
`
`
`
`
`
`4.1.3 SHA-384 and SHA-512 Functions
`SHA-384 and SHA-512 each use six logical functions, where each function operates on 64-bit
`words, which are represented as x, y, and z. The result of each function is a new 64-bit word.
`
`
`
`
`
`9
`
`
`APPLE EXHIBIT 1109
`Page 14 of 76
`
`�
`�
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` Ch( x, y, z) =
`
`
` Maj( x, y, z) =
`
` ( x 1 z)
`( x 1 y) ¯
`
`
`( x 1 y) ¯ ( x 1 z) ¯
`
`( y 1 z)
`
`
`
`
`{512}
`(x) = ROTR28(x)
`
`
`
`0
`{512}
`(x) = ROTR14(x)
`
`
`
`
`1
`
` x = ROTR1(x)
`
`{512}( )
`
`
`s 0
` {512}( ) x = ROTR19(x)
`
`
`
`s 1
`
`
`
`¯
`¯
`¯
`¯
`
`
`
`
`
`
`
`
`
` ROTR34(x)
`
`
` ROTR18(x)
`
`
`
` ROTR8(x)
` ROTR61(x)
`
`
`
`¯
`¯
`¯
`¯
`
`
`
`
`
`
`
`
`
` ROTR39(x)
`
`
` ROTR41(x)
`
`
` SHR 7(x)
`
`
` SHR 6(x)
`
`
`
` (4.8)
`
` (4.9)
`
`
`
` (4.10)
`
`
` (4.11)
`
` (4.12)
`
` (4.13)
`
`
`
` 4.2 Constants
`
`
`
`
`
` 4.2.1 SHA-1 Constants
`
`
` SHA-1 uses a sequence of eighty constant 32-bit words, K0, K1,…, K79, which are given by
`
`
`
`
`
`
`
`
`
`
`
`
`
`5a827999
`
`
`
`
`Kt =
`
`
`
`6ed9eba1
`
`
`8f1bbcdc
`
`
`
`
`ca62c1d6
`
`0 £
`
`t £
`
`
` 19
`
`
`
`20 £
`
`
`40 £
`
`t £
`
`
`t £
`
`
`
` 39
`
`
` 59
`
`60 £
`
`
`t £
`
`
`
` 79.
`
`
`
`
`
`
`(4.14)
`
`
`
`
`4.2.2 SHA-256 Constants
`{256}
`{256}
`{256}
`. These
`SHA-256 uses a sequence of sixty-four constant 32-bit words, K
`, K
`,K, K
`0
`1
`63
`words represent the first thirty-two bits of the fractional parts of the cube roots of the first sixty-
`
`four prime numbers. In hex, these constant words are (from left to right)
`
`
`
` 428a2f98 71374491 b5c0fbcf e9b5dba5 3956c25b 59f111f1 923f82a4 ab1c5ed5
`
` d807aa98 12835b01 243185be 550c7dc3 72be5d74 80deb1fe 9bdc06a7 c19bf174
`
` e49b69c1 efbe4786 0fc19dc6 240ca1cc 2de92c6f 4a7484aa 5cb0a9dc 76f988da
`
` 983e5152 a831c66d b00327c8 bf597fc7 c6e00bf3 d5a79147 06ca6351 14292967
`
` 27b70a85 2e1b2138 4d2c6dfc 53380d13 650a7354 766a0abb 81c2c92e 92722c85
`
` a2bfe8a1 a81a664b c24b8b70 c76c51a3 d192e819 d6990624 f40e3585