Initial release, version 0.0.0.
[gsasl.git] / doc / specification / rfc3174.txt
blobebe515d31265baf9f374acd14881219443799079
7 Network Working Group                                   D. Eastlake, 3rd
8 Request for Comments: 3174                                      Motorola
9 Category: Informational                                         P. Jones
10                                                            Cisco Systems
11                                                           September 2001
14                    US Secure Hash Algorithm 1 (SHA1)
16 Status of this Memo
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.
22 Copyright Notice
24    Copyright (C) The Internet Society (2001).  All Rights Reserved.
26 Abstract
28    The purpose of this document is to make the SHA-1 (Secure Hash
29    Algorithm 1) hash algorithm conveniently available to the Internet
30    community.  The United States of America has adopted the SHA-1 hash
31    algorithm described herein as a Federal Information Processing
32    Standard.  Most of the text herein was taken by the authors from FIPS
33    180-1.  Only the C code implementation is "original".
35 Acknowledgements
37    Most of the text herein was taken from [FIPS 180-1].  Only the C code
38    implementation is "original" but its style is similar to the
39    previously published MD4 and MD5 RFCs [RFCs 1320, 1321].
41    The SHA-1 is based on principles similar to those used by Professor
42    Ronald L. Rivest of MIT when designing the MD4 message digest
43    algorithm [MD4] and is modeled after that algorithm [RFC 1320].
45    Useful comments from the following, which have been incorporated
46    herein, are gratefully acknowledged:
48       Tony Hansen
49       Garrett Wollman
58 Eastlake & Jones             Informational                      [Page 1]
60 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
63 Table of Contents
65    1. Overview of Contents...........................................  2
66    2. Definitions of Bit Strings and Integers........................  3
67    3. Operations on Words............................................  3
68    4. Message Padding................................................  4
69    5. Functions and Constants Used...................................  6
70    6. Computing the Message Digest...................................  6
71    6.1 Method 1......................................................  6
72    6.2 Method 2......................................................  7
73    7. C Code.........................................................  8
74    7.1 .h file.......................................................  8
75    7.2 .c file....................................................... 10
76    7.3 Test Driver................................................... 18
77    8. Security Considerations........................................ 20
78    References........................................................ 21
79    Authors' Addresses................................................ 21
80    Full Copyright Statement.......................................... 22
82 1. Overview of Contents
84    NOTE: The text below is mostly taken from [FIPS 180-1] and assertions
85    therein of the security of SHA-1 are made by the US Government, the
86    author of [FIPS 180-1], and not by the authors of this document.
88    This document specifies a Secure Hash Algorithm, SHA-1, for computing
89    a condensed representation of a message or a data file.  When a
90    message of any length < 2^64 bits is input, the SHA-1 produces a
91    160-bit output called a message digest.  The message digest can then,
92    for example, be input to a signature algorithm which generates or
93    verifies the signature for the message.  Signing the message digest
94    rather than the message often improves the efficiency of the process
95    because the message digest is usually much smaller in size than the
96    message.  The same hash algorithm must be used by the verifier of a
97    digital signature as was used by the creator of the digital
98    signature.  Any change to the message in transit will, with very high
99    probability, result in a different message digest, and the signature
100    will fail to verify.
102    The SHA-1 is called secure because it is computationally infeasible
103    to find a message which corresponds to a given message digest, or to
104    find two different messages which produce the same message digest.
105    Any change to a message in transit will, with very high probability,
106    result in a different message digest, and the signature will fail to
107    verify.
114 Eastlake & Jones             Informational                      [Page 2]
116 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
119    Section 2 below defines the terminology and functions used as
120    building blocks to form SHA-1.
122 2. Definitions of Bit Strings and Integers
124    The following terminology related to bit strings and integers will be
125    used:
127    a. A hex digit is an element of the set {0, 1, ... , 9, A, ... , F}.
128       A hex digit is the representation of a 4-bit string.  Examples:  7
129       = 0111, A = 1010.
131    b. A word equals a 32-bit string which may be represented as a
132       sequence of 8 hex digits.  To convert a word to 8 hex digits each
133       4-bit string is converted to its hex equivalent as described in
134       (a) above.  Example:
136       1010 0001 0000 0011 1111 1110 0010 0011 = A103FE23.
138    c. An integer between 0 and 2^32 - 1 inclusive may be represented as
139       a word.  The least significant four bits of the integer are
140       represented by the right-most hex digit of the word
141       representation.  Example: the integer 291 = 2^8+2^5+2^1+2^0 =
142       256+32+2+1 is represented by the hex word, 00000123.
144       If z is an integer, 0 <= z < 2^64, then z = (2^32)x + y where 0 <=
145       x < 2^32 and 0 <= y < 2^32.  Since x and y can be represented as
146       words X and Y, respectively, z can be represented as the pair of
147       words (X,Y).
149    d. block = 512-bit string.  A block (e.g., B) may be represented as a
150       sequence of 16 words.
152 3. Operations on Words
154    The following logical operators will be applied to words:
156    a. Bitwise logical word operations
158       X AND Y  =  bitwise logical "and" of  X and Y.
160       X OR Y   =  bitwise logical "inclusive-or" of X and Y.
162       X XOR Y  =  bitwise logical "exclusive-or" of X and Y.
164       NOT X    =  bitwise logical "complement" of X.
170 Eastlake & Jones             Informational                      [Page 3]
172 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
175       Example:
177                01101100101110011101001001111011
178          XOR   01100101110000010110100110110111
179                --------------------------------
180            =   00001001011110001011101111001100
182    b. The operation X + Y is defined as follows:  words X and Y
183       represent integers x and y, where 0 <= x < 2^32 and 0 <= y < 2^32.
184       For positive integers n and m, let n mod m be the remainder upon
185       dividing n by m.  Compute
187          z  =  (x + y) mod 2^32.
189       Then 0 <= z < 2^32.  Convert z to a word,  Z, and define Z = X +
190       Y.
192    c. The circular left shift operation S^n(X), where X is a word and n
193       is an integer with 0 <= n < 32, is defined by
195          S^n(X)  =  (X << n) OR (X >> 32-n).
197       In the above, X << n is obtained as follows: discard the left-most
198       n bits of X and then pad the result with n zeroes on the right
199       (the result will still be 32 bits).  X >> n is obtained by
200       discarding the right-most n bits of X and then padding the result
201       with n zeroes on the left.  Thus S^n(X) is equivalent to a
202       circular shift of X by n positions to the left.
204 4. Message Padding
206    SHA-1 is used to compute a message digest for a message or data file
207    that is provided as input.  The message or data file should be
208    considered to be a bit string.  The length of the message is the
209    number of bits in the message (the empty message has length 0).  If
210    the number of bits in a message is a multiple of 8, for compactness
211    we can represent the message in hex.  The purpose of message padding
212    is to make the total length of a padded message a multiple of 512.
213    SHA-1 sequentially processes blocks of 512 bits when computing the
214    message digest.  The following specifies how this padding shall be
215    performed.  As a summary, a "1" followed by m "0"s followed by a 64-
216    bit integer are appended to the end of the message to produce a
217    padded message of length 512 * n.  The 64-bit integer is the length
218    of the original message.  The padded message is then processed by the
219    SHA-1 as n 512-bit blocks.
226 Eastlake & Jones             Informational                      [Page 4]
228 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
231    Suppose a message has length l < 2^64.  Before it is input to the
232    SHA-1, the message is padded on the right as follows:
234    a. "1" is appended.  Example: if the original message is "01010000",
235       this is padded to "010100001".
237    b. "0"s are appended.  The number of "0"s will depend on the original
238       length of the message.  The last 64 bits of the last 512-bit block
239       are reserved
241       for the length l of the original message.
243       Example:  Suppose the original message is the bit string
245          01100001 01100010 01100011 01100100 01100101.
247       After step (a) this gives
249          01100001 01100010 01100011 01100100 01100101 1.
251       Since l = 40, the number of bits in the above is 41 and 407 "0"s
252       are appended, making the total now 448.  This gives (in hex)
254          61626364 65800000 00000000 00000000
255          00000000 00000000 00000000 00000000
256          00000000 00000000 00000000 00000000
257          00000000 00000000.
259    c. Obtain the 2-word representation of l, the number of bits in the
260       original message.  If l < 2^32 then the first word is all zeroes.
261       Append these two words to the padded message.
263       Example: Suppose the original message is as in (b).  Then l = 40
264       (note that l is computed before any padding).  The two-word
265       representation of 40 is hex 00000000 00000028.  Hence the final
266       padded message is hex
268          61626364 65800000 00000000 00000000
269          00000000 00000000 00000000 00000000
270          00000000 00000000 00000000 00000000
271          00000000 00000000 00000000 00000028.
273       The padded message will contain 16 * n words for some n > 0.
274       The padded message is regarded as a sequence of n blocks M(1) ,
275       M(2), first characters (or bits) of the message.
282 Eastlake & Jones             Informational                      [Page 5]
284 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
287 5. Functions and Constants Used
289    A sequence of logical functions f(0), f(1),..., f(79) is used in
290    SHA-1.  Each f(t), 0 <= t <= 79, operates on three 32-bit words B, C,
291    D and produces a 32-bit word as output.  f(t;B,C,D) is defined as
292    follows: for words B, C, D,
294       f(t;B,C,D) = (B AND C) OR ((NOT B) AND D)         ( 0 <= t <= 19)
296       f(t;B,C,D) = B XOR C XOR D                        (20 <= t <= 39)
298       f(t;B,C,D) = (B AND C) OR (B AND D) OR (C AND D)  (40 <= t <= 59)
300       f(t;B,C,D) = B XOR C XOR D                        (60 <= t <= 79).
302    A sequence of constant words K(0), K(1), ... , K(79) is used in the
303    SHA-1.  In hex these are given by
305       K(t) = 5A827999         ( 0 <= t <= 19)
307       K(t) = 6ED9EBA1         (20 <= t <= 39)
309       K(t) = 8F1BBCDC         (40 <= t <= 59)
311       K(t) = CA62C1D6         (60 <= t <= 79).
313 6. Computing the Message Digest
315    The methods given in 6.1 and 6.2 below yield the same message digest.
316    Although using method 2 saves sixty-four 32-bit words of storage, it
317    is likely to lengthen execution time due to the increased complexity
318    of the address computations for the { W[t] } in step (c).  There are
319    other computation methods which give identical results.
321 6.1 Method 1
323    The message digest is computed using the message padded as described
324    in section 4.  The computation is described using two buffers, each
325    consisting of five 32-bit words, and a sequence of eighty 32-bit
326    words.  The words of the first 5-word buffer are labeled A,B,C,D,E.
327    The words of the second 5-word buffer are labeled H0, H1, H2, H3, H4.
328    The words of the 80-word sequence are labeled W(0), W(1),..., W(79).
329    A single word buffer TEMP is also employed.
331    To generate the message digest, the 16-word blocks M(1), M(2),...,
332    M(n) defined in section 4 are processed in order.  The processing of
333    each M(i) involves 80 steps.
338 Eastlake & Jones             Informational                      [Page 6]
340 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
343    Before processing any blocks, the H's are initialized as follows: in
344    hex,
346       H0 = 67452301
348       H1 = EFCDAB89
350       H2 = 98BADCFE
352       H3 = 10325476
354       H4 = C3D2E1F0.
356    Now M(1), M(2), ... , M(n) are processed.  To process M(i), we
357    proceed as follows:
359       a. Divide M(i) into 16 words W(0), W(1), ... , W(15), where W(0)
360          is the left-most word.
362       b. For t = 16 to 79 let
364          W(t) = S^1(W(t-3) XOR W(t-8) XOR W(t-14) XOR W(t-16)).
366       c. Let A = H0, B = H1, C = H2, D = H3, E = H4.
368       d. For t = 0 to 79 do
370          TEMP = S^5(A) + f(t;B,C,D) + E + W(t) + K(t);
372          E = D;  D = C;  C = S^30(B);  B = A; A = TEMP;
374       e. Let H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4
375          + E.
377    After processing M(n), the message digest is the 160-bit string
378    represented by the 5 words
380          H0 H1 H2 H3 H4.
382 6.2 Method 2
384    The method above assumes that the sequence W(0), ... , W(79) is
385    implemented as an array of eighty 32-bit words.  This is efficient
386    from the standpoint of minimization of execution time, since the
387    addresses of W(t-3), ...  ,W(t-16) in step (b) are easily computed.
388    If space is at a premium, an alternative is to regard { W(t) } as a
394 Eastlake & Jones             Informational                      [Page 7]
396 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
399    circular queue, which may be implemented using an array of sixteen
400    32-bit words W[0], ... W[15].  In this case, in hex let
402    MASK = 0000000F.  Then processing of M(i) is as follows:
404       a. Divide M(i) into 16 words W[0], ... , W[15], where W[0] is the
405          left-most word.
407       b. Let A = H0, B = H1, C = H2, D = H3, E = H4.
409       c. For t = 0 to 79 do
411          s = t AND MASK;
413          if (t >= 16) W[s] = S^1(W[(s + 13) AND MASK] XOR W[(s + 8) AND
414          MASK] XOR W[(s + 2) AND MASK] XOR W[s]);
416          TEMP = S^5(A) + f(t;B,C,D) + E + W[s] + K(t);
418          E = D; D = C; C = S^30(B); B = A; A = TEMP;
420       d. Let H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4
421          + E.
423 7. C Code
425    Below is a demonstration implementation of SHA-1 in C.  Section 7.1
426    contains the header file, 7.2 the C code, and 7.3 a test driver.
428 7.1 .h file
431  *  sha1.h
433  *  Description:
434  *      This is the header file for code which implements the Secure
435  *      Hashing Algorithm 1 as defined in FIPS PUB 180-1 published
436  *      April 17, 1995.
438  *      Many of the variable names in this code, especially the
439  *      single character names, were used because those were the names
440  *      used in the publication.
442  *      Please read the file sha1.c for more information.
444  */
450 Eastlake & Jones             Informational                      [Page 8]
452 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
455 #ifndef _SHA1_H_
456 #define _SHA1_H_
458 #include <stdint.h>
460  * If you do not have the ISO standard stdint.h header file, then you
461  * must typdef the following:
462  *    name              meaning
463  *  uint32_t         unsigned 32 bit integer
464  *  uint8_t          unsigned 8 bit integer (i.e., unsigned char)
465  *  int_least16_t    integer of >= 16 bits
467  */
469 #ifndef _SHA_enum_
470 #define _SHA_enum_
471 enum
473     shaSuccess = 0,
474     shaNull,            /* Null pointer parameter */
475     shaInputTooLong,    /* input data too long */
476     shaStateError       /* called Input after Result */
478 #endif
479 #define SHA1HashSize 20
482  *  This structure will hold context information for the SHA-1
483  *  hashing operation
484  */
485 typedef struct SHA1Context
487     uint32_t Intermediate_Hash[SHA1HashSize/4]; /* Message Digest  */
489     uint32_t Length_Low;            /* Message length in bits      */
490     uint32_t Length_High;           /* Message length in bits      */
492                                /* Index into message block array   */
493     int_least16_t Message_Block_Index;
494     uint8_t Message_Block[64];      /* 512-bit message blocks      */
496     int Computed;               /* Is the digest computed?         */
497     int Corrupted;             /* Is the message digest corrupted? */
498 } SHA1Context;
501  *  Function Prototypes
502  */
506 Eastlake & Jones             Informational                      [Page 9]
508 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
511 int SHA1Reset(  SHA1Context *);
512 int SHA1Input(  SHA1Context *,
513                 const uint8_t *,
514                 unsigned int);
515 int SHA1Result( SHA1Context *,
516                 uint8_t Message_Digest[SHA1HashSize]);
518 #endif
520 7.2 .c file
523  *  sha1.c
525  *  Description:
526  *      This file implements the Secure Hashing Algorithm 1 as
527  *      defined in FIPS PUB 180-1 published April 17, 1995.
529  *      The SHA-1, produces a 160-bit message digest for a given
530  *      data stream.  It should take about 2**n steps to find a
531  *      message with the same digest as a given message and
532  *      2**(n/2) to find any two messages with the same digest,
533  *      when n is the digest size in bits.  Therefore, this
534  *      algorithm can serve as a means of providing a
535  *      "fingerprint" for a message.
537  *  Portability Issues:
538  *      SHA-1 is defined in terms of 32-bit "words".  This code
539  *      uses <stdint.h> (included via "sha1.h" to define 32 and 8
540  *      bit unsigned integer types.  If your C compiler does not
541  *      support 32 bit unsigned integers, this code is not
542  *      appropriate.
544  *  Caveats:
545  *      SHA-1 is designed to work with messages less than 2^64 bits
546  *      long.  Although SHA-1 allows a message digest to be generated
547  *      for messages of any number of bits less than 2^64, this
548  *      implementation only works with messages with a length that is
549  *      a multiple of the size of an 8-bit character.
551  */
562 Eastlake & Jones             Informational                     [Page 10]
564 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
567 #include "sha1.h"
570  *  Define the SHA1 circular left shift macro
571  */
572 #define SHA1CircularShift(bits,word) \
573                 (((word) << (bits)) | ((word) >> (32-(bits))))
575 /* Local Function Prototyptes */
576 void SHA1PadMessage(SHA1Context *);
577 void SHA1ProcessMessageBlock(SHA1Context *);
580  *  SHA1Reset
582  *  Description:
583  *      This function will initialize the SHA1Context in preparation
584  *      for computing a new SHA1 message digest.
586  *  Parameters:
587  *      context: [in/out]
588  *          The context to reset.
590  *  Returns:
591  *      sha Error Code.
593  */
594 int SHA1Reset(SHA1Context *context)
596     if (!context)
597     {
598         return shaNull;
599     }
601     context->Length_Low             = 0;
602     context->Length_High            = 0;
603     context->Message_Block_Index    = 0;
605     context->Intermediate_Hash[0]   = 0x67452301;
606     context->Intermediate_Hash[1]   = 0xEFCDAB89;
607     context->Intermediate_Hash[2]   = 0x98BADCFE;
608     context->Intermediate_Hash[3]   = 0x10325476;
609     context->Intermediate_Hash[4]   = 0xC3D2E1F0;
611     context->Computed   = 0;
612     context->Corrupted  = 0;
618 Eastlake & Jones             Informational                     [Page 11]
620 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
623     return shaSuccess;
627  *  SHA1Result
629  *  Description:
630  *      This function will return the 160-bit message digest into the
631  *      Message_Digest array  provided by the caller.
632  *      NOTE: The first octet of hash is stored in the 0th element,
633  *            the last octet of hash in the 19th element.
635  *  Parameters:
636  *      context: [in/out]
637  *          The context to use to calculate the SHA-1 hash.
638  *      Message_Digest: [out]
639  *          Where the digest is returned.
641  *  Returns:
642  *      sha Error Code.
644  */
645 int SHA1Result( SHA1Context *context,
646                 uint8_t Message_Digest[SHA1HashSize])
648     int i;
650     if (!context || !Message_Digest)
651     {
652         return shaNull;
653     }
655     if (context->Corrupted)
656     {
657         return context->Corrupted;
658     }
660     if (!context->Computed)
661     {
662         SHA1PadMessage(context);
663         for(i=0; i<64; ++i)
664         {
665             /* message may be sensitive, clear it out */
666             context->Message_Block[i] = 0;
667         }
668         context->Length_Low = 0;    /* and clear length */
669         context->Length_High = 0;
670         context->Computed = 1;
674 Eastlake & Jones             Informational                     [Page 12]
676 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
679     }
681     for(i = 0; i < SHA1HashSize; ++i)
682     {
683         Message_Digest[i] = context->Intermediate_Hash[i>>2]
684                             >> 8 * ( 3 - ( i & 0x03 ) );
685     }
687     return shaSuccess;
691  *  SHA1Input
693  *  Description:
694  *      This function accepts an array of octets as the next portion
695  *      of the message.
697  *  Parameters:
698  *      context: [in/out]
699  *          The SHA context to update
700  *      message_array: [in]
701  *          An array of characters representing the next portion of
702  *          the message.
703  *      length: [in]
704  *          The length of the message in message_array
706  *  Returns:
707  *      sha Error Code.
709  */
710 int SHA1Input(    SHA1Context    *context,
711                   const uint8_t  *message_array,
712                   unsigned       length)
714     if (!length)
715     {
716         return shaSuccess;
717     }
719     if (!context || !message_array)
720     {
721         return shaNull;
722     }
724     if (context->Computed)
725     {
726         context->Corrupted = shaStateError;
730 Eastlake & Jones             Informational                     [Page 13]
732 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
735         return shaStateError;
736     }
738     if (context->Corrupted)
739     {
740          return context->Corrupted;
741     }
742     while(length-- && !context->Corrupted)
743     {
744     context->Message_Block[context->Message_Block_Index++] =
745                     (*message_array & 0xFF);
747     context->Length_Low += 8;
748     if (context->Length_Low == 0)
749     {
750         context->Length_High++;
751         if (context->Length_High == 0)
752         {
753             /* Message is too long */
754             context->Corrupted = 1;
755         }
756     }
758     if (context->Message_Block_Index == 64)
759     {
760         SHA1ProcessMessageBlock(context);
761     }
763     message_array++;
764     }
766     return shaSuccess;
770  *  SHA1ProcessMessageBlock
772  *  Description:
773  *      This function will process the next 512 bits of the message
774  *      stored in the Message_Block array.
776  *  Parameters:
777  *      None.
779  *  Returns:
780  *      Nothing.
782  *  Comments:
786 Eastlake & Jones             Informational                     [Page 14]
788 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
791  *      Many of the variable names in this code, especially the
792  *      single character names, were used because those were the
793  *      names used in the publication.
796  */
797 void SHA1ProcessMessageBlock(SHA1Context *context)
799     const uint32_t K[] =    {       /* Constants defined in SHA-1   */
800                             0x5A827999,
801                             0x6ED9EBA1,
802                             0x8F1BBCDC,
803                             0xCA62C1D6
804                             };
805     int           t;                 /* Loop counter                */
806     uint32_t      temp;              /* Temporary word value        */
807     uint32_t      W[80];             /* Word sequence               */
808     uint32_t      A, B, C, D, E;     /* Word buffers                */
810     /*
811      *  Initialize the first 16 words in the array W
812      */
813     for(t = 0; t < 16; t++)
814     {
815         W[t] = context->Message_Block[t * 4] << 24;
816         W[t] |= context->Message_Block[t * 4 + 1] << 16;
817         W[t] |= context->Message_Block[t * 4 + 2] << 8;
818         W[t] |= context->Message_Block[t * 4 + 3];
819     }
821     for(t = 16; t < 80; t++)
822     {
823        W[t] = SHA1CircularShift(1,W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]);
824     }
826     A = context->Intermediate_Hash[0];
827     B = context->Intermediate_Hash[1];
828     C = context->Intermediate_Hash[2];
829     D = context->Intermediate_Hash[3];
830     E = context->Intermediate_Hash[4];
832     for(t = 0; t < 20; t++)
833     {
834         temp =  SHA1CircularShift(5,A) +
835                 ((B & C) | ((~B) & D)) + E + W[t] + K[0];
836         E = D;
837         D = C;
838         C = SHA1CircularShift(30,B);
842 Eastlake & Jones             Informational                     [Page 15]
844 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
847         B = A;
848         A = temp;
849     }
851     for(t = 20; t < 40; t++)
852     {
853         temp = SHA1CircularShift(5,A) + (B ^ C ^ D) + E + W[t] + K[1];
854         E = D;
855         D = C;
856         C = SHA1CircularShift(30,B);
857         B = A;
858         A = temp;
859     }
861     for(t = 40; t < 60; t++)
862     {
863         temp = SHA1CircularShift(5,A) +
864                ((B & C) | (B & D) | (C & D)) + E + W[t] + K[2];
865         E = D;
866         D = C;
867         C = SHA1CircularShift(30,B);
868         B = A;
869         A = temp;
870     }
872     for(t = 60; t < 80; t++)
873     {
874         temp = SHA1CircularShift(5,A) + (B ^ C ^ D) + E + W[t] + K[3];
875         E = D;
876         D = C;
877         C = SHA1CircularShift(30,B);
878         B = A;
879         A = temp;
880     }
882     context->Intermediate_Hash[0] += A;
883     context->Intermediate_Hash[1] += B;
884     context->Intermediate_Hash[2] += C;
885     context->Intermediate_Hash[3] += D;
886     context->Intermediate_Hash[4] += E;
888     context->Message_Block_Index = 0;
893  *  SHA1PadMessage
898 Eastlake & Jones             Informational                     [Page 16]
900 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
903  *  Description:
904  *      According to the standard, the message must be padded to an even
905  *      512 bits.  The first padding bit must be a '1'.  The last 64
906  *      bits represent the length of the original message.  All bits in
907  *      between should be 0.  This function will pad the message
908  *      according to those rules by filling the Message_Block array
909  *      accordingly.  It will also call the ProcessMessageBlock function
910  *      provided appropriately.  When it returns, it can be assumed that
911  *      the message digest has been computed.
913  *  Parameters:
914  *      context: [in/out]
915  *          The context to pad
916  *      ProcessMessageBlock: [in]
917  *          The appropriate SHA*ProcessMessageBlock function
918  *  Returns:
919  *      Nothing.
921  */
923 void SHA1PadMessage(SHA1Context *context)
925     /*
926      *  Check to see if the current message block is too small to hold
927      *  the initial padding bits and length.  If so, we will pad the
928      *  block, process it, and then continue padding into a second
929      *  block.
930      */
931     if (context->Message_Block_Index > 55)
932     {
933         context->Message_Block[context->Message_Block_Index++] = 0x80;
934         while(context->Message_Block_Index < 64)
935         {
936             context->Message_Block[context->Message_Block_Index++] = 0;
937         }
939         SHA1ProcessMessageBlock(context);
941         while(context->Message_Block_Index < 56)
942         {
943             context->Message_Block[context->Message_Block_Index++] = 0;
944         }
945     }
946     else
947     {
948         context->Message_Block[context->Message_Block_Index++] = 0x80;
949         while(context->Message_Block_Index < 56)
950         {
954 Eastlake & Jones             Informational                     [Page 17]
956 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
959             context->Message_Block[context->Message_Block_Index++] = 0;
960         }
961     }
963     /*
964      *  Store the message length as the last 8 octets
965      */
966     context->Message_Block[56] = context->Length_High >> 24;
967     context->Message_Block[57] = context->Length_High >> 16;
968     context->Message_Block[58] = context->Length_High >> 8;
969     context->Message_Block[59] = context->Length_High;
970     context->Message_Block[60] = context->Length_Low >> 24;
971     context->Message_Block[61] = context->Length_Low >> 16;
972     context->Message_Block[62] = context->Length_Low >> 8;
973     context->Message_Block[63] = context->Length_Low;
975     SHA1ProcessMessageBlock(context);
978 7.3 Test Driver
980    The following code is a main program test driver to exercise the code
981    in sha1.c.
984  *  sha1test.c
986  *  Description:
987  *      This file will exercise the SHA-1 code performing the three
988  *      tests documented in FIPS PUB 180-1 plus one which calls
989  *      SHA1Input with an exact multiple of 512 bits, plus a few
990  *      error test checks.
992  *  Portability Issues:
993  *      None.
995  */
997 #include <stdint.h>
998 #include <stdio.h>
999 #include <string.h>
1000 #include "sha1.h"
1003  *  Define patterns for testing
1004  */
1005 #define TEST1   "abc"
1006 #define TEST2a  "abcdbcdecdefdefgefghfghighijhi"
1010 Eastlake & Jones             Informational                     [Page 18]
1012 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
1015 #define TEST2b  "jkijkljklmklmnlmnomnopnopq"
1016 #define TEST2   TEST2a TEST2b
1017 #define TEST3   "a"
1018 #define TEST4a  "01234567012345670123456701234567"
1019 #define TEST4b  "01234567012345670123456701234567"
1020     /* an exact multiple of 512 bits */
1021 #define TEST4   TEST4a TEST4b
1022 char *testarray[4] =
1024     TEST1,
1025     TEST2,
1026     TEST3,
1027     TEST4
1029 long int repeatcount[4] = { 1, 1, 1000000, 10 };
1030 char *resultarray[4] =
1032     "A9 99 3E 36 47 06 81 6A BA 3E 25 71 78 50 C2 6C 9C D0 D8 9D",
1033     "84 98 3E 44 1C 3B D2 6E BA AE 4A A1 F9 51 29 E5 E5 46 70 F1",
1034     "34 AA 97 3C D4 C4 DA A4 F6 1E EB 2B DB AD 27 31 65 34 01 6F",
1035     "DE A3 56 A2 CD DD 90 C7 A7 EC ED C5 EB B5 63 93 4F 46 04 52"
1038 int main()
1040     SHA1Context sha;
1041     int i, j, err;
1042     uint8_t Message_Digest[20];
1044     /*
1045      *  Perform SHA-1 tests
1046      */
1047     for(j = 0; j < 4; ++j)
1048     {
1049         printf( "\nTest %d: %d, '%s'\n",
1050                 j+1,
1051                 repeatcount[j],
1052                 testarray[j]);
1054         err = SHA1Reset(&sha);
1055         if (err)
1056         {
1057             fprintf(stderr, "SHA1Reset Error %d.\n", err );
1058             break;    /* out of for j loop */
1059         }
1061         for(i = 0; i < repeatcount[j]; ++i)
1062         {
1066 Eastlake & Jones             Informational                     [Page 19]
1068 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
1071             err = SHA1Input(&sha,
1072                   (const unsigned char *) testarray[j],
1073                   strlen(testarray[j]));
1074             if (err)
1075             {
1076                 fprintf(stderr, "SHA1Input Error %d.\n", err );
1077                 break;    /* out of for i loop */
1078             }
1079         }
1081         err = SHA1Result(&sha, Message_Digest);
1082         if (err)
1083         {
1084             fprintf(stderr,
1085             "SHA1Result Error %d, could not compute message digest.\n",
1086             err );
1087         }
1088         else
1089         {
1090             printf("\t");
1091             for(i = 0; i < 20 ; ++i)
1092             {
1093                 printf("%02X ", Message_Digest[i]);
1094             }
1095             printf("\n");
1096         }
1097         printf("Should match:\n");
1098         printf("\t%s\n", resultarray[j]);
1099     }
1101     /* Test some error returns */
1102     err = SHA1Input(&sha,(const unsigned char *) testarray[1], 1);
1103     printf ("\nError %d. Should be %d.\n", err, shaStateError );
1104     err = SHA1Reset(0);
1105     printf ("\nError %d. Should be %d.\n", err, shaNull );
1106     return 0;
1109 8. Security Considerations
1111    This document is intended to provide convenient open source access by
1112    the Internet community to the United States of America Federal
1113    Information Processing Standard Secure Hash Function SHA-1 [FIPS
1114    180-1].  No independent assertion of the security of this hash
1115    function by the authors for any particular use is intended.
1122 Eastlake & Jones             Informational                     [Page 20]
1124 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
1127 References
1129    [FIPS 180-1] "Secure Hash Standard", United States of American,
1130                 National Institute of Science and Technology, Federal
1131                 Information Processing Standard (FIPS) 180-1, April
1132                 1993.
1134    [MD4]        "The MD4 Message Digest Algorithm," Advances in
1135                 Cryptology - CRYPTO '90 Proceedings, Springer-Verlag,
1136                 1991, pp. 303-311.
1138    [RFC 1320]   Rivest, R., "The MD4 Message-Digest Algorithm", RFC
1139                 1320, April 1992.
1141    [RFC 1321]   Rivest, R., "The MD5 Message-Digest Algorithm", RFC
1142                 1321, April 1992.
1144    [RFC 1750]   Eastlake, D., Crocker, S. and J. Schiller, "Randomness
1145                 Requirements for Security", RFC 1750, December 1994.
1147 Authors' Addresses
1149    Donald E. Eastlake, 3rd
1150    Motorola
1151    155 Beaver Street
1152    Milford, MA 01757 USA
1154    Phone:   +1 508-634-2066 (h)
1155             +1 508-261-5434 (w)
1156    Fax:     +1 508-261-4777
1157    EMail:   Donald.Eastlake@motorola.com
1160    Paul E. Jones
1161    Cisco Systems, Inc.
1162    7025 Kit Creek Road
1163    Research Triangle Park, NC 27709 USA
1165    Phone:   +1 919 392 6948
1166    EMail:   paulej@packetizer.com
1178 Eastlake & Jones             Informational                     [Page 21]
1180 RFC 3174           US Secure Hash Algorithm 1 (SHA1)      September 2001
1183 Full Copyright Statement
1185    Copyright (C) The Internet Society (2001).  All Rights Reserved.
1187    This document and translations of it may be copied and furnished to
1188    others, and derivative works that comment on or otherwise explain it
1189    or assist in its implementation may be prepared, copied, published
1190    and distributed, in whole or in part, without restriction of any
1191    kind, provided that the above copyright notice and this paragraph are
1192    included on all such copies and derivative works.  However, this
1193    document itself may not be modified in any way, such as by removing
1194    the copyright notice or references to the Internet Society or other
1195    Internet organizations, except as needed for the purpose of
1196    developing Internet standards in which case the procedures for
1197    copyrights defined in the Internet Standards process must be
1198    followed, or as required to translate it into languages other than
1199    English.
1201    The limited permissions granted above are perpetual and will not be
1202    revoked by the Internet Society or its successors or assigns.
1204    This document and the information contained herein is provided on an
1205    "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
1206    TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
1207    BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
1208    HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
1209    MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
1211 Acknowledgement
1213    Funding for the RFC Editor function is currently provided by the
1214    Internet Society.
1234 Eastlake & Jones             Informational                     [Page 22]