[Docs] [txt|pdf] [Tracker] [Email] [Nits]

Versions: 00 01 RFC 3174

Network Working Group                             Donald E. Eastlake 3rd
INTERNET-DRAFT                                                  Motorola
                                                           Paul E. Jones
                                                           Cisco Systems
Expires: September 2001                                       March 2001



                   US Secure Hash Algorithm 1 (SHA1)
                   -- ------ ---- --------- - ------
                      <draft-eastlake-sha1-00.txt>



Status of This Document

   This draft is intended to be become an Informational RFC.
   Distribution of this document is unlimited. Comments should be sent
   to the authors.

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC 2026.  Internet-Drafts are
   working documents of the Internet Engineering Task Force (IETF), its
   areas, and its working groups.  Note that other groups may also
   distribute working documents as Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet- Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.



Abstract

   The United States of America has adopted the SHA-1 hash algorithm
   described herein as a Federal Information Processing Standard.  The
   purpose of this document is to make it conveniently available to the
   Internet community.  Most of the text herein was taken by the authors
   from FIPS 180-1.  Only the C code implementation is "original" and
   that is patterned after the MD2/MD4/MD5 RFCs.








D. Eastlake 3rd, P. Jones                                       [Page 1]

INTERNET-DRAFT                  US SHA-1                      March 2001


Acknowledgements

   Almost all of the text herein was taken by the authors from [FIPS
   180-1].  Only the C code implementation is "original" but its style
   is similar to the previously published MD2, MD4, and MD5 RFCs [RFCs
   1319, 1320, 1321].

   The SHA-1 is based on principles similar to those used by Professor
   Ronald L. Rivest of MIT when designing the MD4 message digest
   algorithm [MD4] and is closely modelled after that algorithm [RFC
   1320].



Table of Contents

      Status of This Document....................................1
      Abstract...................................................1

      Acknowledgements...........................................2
      Table of Contents..........................................2

      1. Overview of Contents....................................3
      2. Definitions.............................................3
      2.1  Bit Strings and Integers..............................3
      3. Operations on Words.....................................4
      4. Message Padding.........................................5
      5. Functions and Constants Used............................6
      6. Computing the Message Digest............................7
      6.1 Method 1...............................................7
      6.2 Method 2...............................................8
      7. C Code..................................................9
      7.1 .h file................................................9
      7.2 .c file...............................................10
      7.3 Test Driver...........................................17
      8. Security Considerations................................19
      References................................................19

      Author's Address..........................................21
      Expiration and File Name..................................21












D. Eastlake 3rd, P. Jones                                       [Page 2]

INTERNET-DRAFT                  US SHA-1                      March 2001


1. Overview of Contents

   This document specifies a Secure Hash Algorithm, SHA-1, for computing
   a condensed representation of a message or a data file.  When a
   message of any length < 2^64 bits is input, the SHA-1 produces a
   160-bit output called a message digest.  The message digest can then,
   for example, be input to a signature algorithm which generates or
   verifies the signature for the message.  Signing the message digest
   rather than the message often improves the efficiency of the process
   because the message digest is usually much smaller in size than the
   message.  The same hash algorithm must be used by the verifier of a
   digital signature as was used by the creator of the digital
   signature.  Any change to the message in transit will, with very high
   probability, result in a different message digest, and the signature
   will fail to verify.

   The SHA-1 is called secure because it is computationally infeasible
   to find a message which corresponds to a given message digest, or to
   find two different messages which produce the same message digest.
   Any change to a message in transit will, with very high probability,
   result in a different message digest, and the signature will fail to
   verify.

   Section 2 below defines the terminology and functions used as
   building blocks to form SHA-1.



2. Definitions



2.1  Bit Strings and Integers

   The following terminology related to bit strings and integers will be
   used:

   a.  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.  Examples:
        7 = 0111, A = 1010.

   b.  A word equals a 32-bit string which may be represented as a
        sequence of 8 hex digits. To convert a word to 8 hex digits each
        4-bit string is converted to its hex equivalent as described in
        (a) above.  Example:

    1010 0001 0000 0011 1111 1110 0010 0011 = A103FE23.

   c.  An integer between 0 and 2^32 - 1 inclusive may be represented as
        a word.  The least significant four bits of the integer are


D. Eastlake 3rd, P. Jones                                       [Page 3]

INTERNET-DRAFT                  US SHA-1                      March 2001


        represented by the right-most hex digit of the word
        representation.  Example: the integer 291 = 2^8+2^5+2^1+2^0 =
        256+32+2+1 is represented by the hex word, 00000123.

        If z is an integer, 0 <= z < 2^64, then z = (2^32)x + y where 0
        <= x < 2^32 and 0 <= y < 2^32.  Since x and y can be represented
        as words X and Y, respectively, z can be represented as the pair
        of words (X,Y).

   d.  block = 512-bit string.  A block (e.g., B) may be represented as
        a sequence of 16 words.



3. Operations on Words

   The following logical operators will be applied to words:

   a.  Bitwise logical word operations

        X AND Y  =  bitwise logical "and" of  X and Y.

        X OR Y   =  bitwise logical "inclusive-or" of X and Y.

        X XOR Y  =  bitwise logical "exclusive-or" of X and Y.

        NOT X    =  bitwise logical "complement" of X.

        Example:
                 01101100101110011101001001111011
           XOR   01100101110000010110100110110111
                 --------------------------------
             =   00001001011110001011101111001100

   b.  The operation X + Y is defined as follows:  words X and Y
        represent integers x and y, where 0 <= x < 2^32 and 0 <= y <
        2^32.  For positive integers n and m, let n mod m be the
        remainder upon dividing n by m.  Compute

             z  =  (x + y) mod 2^32.

        Then 0 <= z < 2^32.  Convert z to a word,  Z, and define Z = X +
        Y.

   c.  The circular left shift operation S^n(X), where X is a word and n
        is an integer with 0 <= n < 32, is defined by

             S^n(X)  =  (X << n) OR (X >> 32-n).

        In the above, X << n is obtained as follows: discard the left-


D. Eastlake 3rd, P. Jones                                       [Page 4]

INTERNET-DRAFT                  US SHA-1                      March 2001


        most n bits of X and then pad the result with n zeroes on the
        right (the result will still be 32 bits).  X >> n is obtained by
        discarding the right-most n bits of X and then padding the
        result with n zeroes on the left.  Thus S^n(X) is equivalent to
        a circular shift of X by n positions to the left.



4. Message Padding

   SHA-1 is used to compute a message digest for a message or data file
   that is provided as input.  The message or data file should be
   considered to be a bit string.  The length of the message is the
   number of bits in the message (the empty message has length 0).  If
   the number of bits in a message is a multiple of 8, for compactness
   we can represent the message in hex.  The purpose of message padding
   is to make the total length of a padded message a multiple of 512.
   SHA-1 sequentially processes blocks of 512 bits when computing the
   message digest.  The following specifies how this padding shall be
   performed.  As a summary, a "1" followed by m "0"s followed by a 64-
   bit integer are appended to the end of the message to produce a
   padded message of length 512 * n.  The 64-bit integer is the length
   of the original message.  The padded message is then processed by the
   SHA-1 as n 512-bit blocks.

   Suppose a message has length l < 2^64.  Before it is input to the
   SHA-1, the message is padded on the right as follows:

   a.  "1" is appended.  Example: if the original message is "01010000",
        this is padded to "010100001".

   b.  "0"s are appended.  The number of "0"s will depend on the
        original length of the message.  The last 64 bits of the last
        512-bit block are reserved

        for the length l of the original message.

        Example:  Suppose the original message is the bit string

             01100001 01100010 01100011 01100100 01100101.

        After step (a) this gives

             01100001 01100010 01100011 01100100 01100101 1.

        Since l = 40, the number of bits in the above is 41 and 407 "0"s
        are appended, making the total now 448. This gives (in hex)

             61626364 65800000 00000000 00000000
             00000000 00000000 00000000 00000000


D. Eastlake 3rd, P. Jones                                       [Page 5]

INTERNET-DRAFT                  US SHA-1                      March 2001


             00000000 00000000 00000000 00000000
             00000000 00000000.

   c.  Obtain the 2-word representation of l, the number of bits in the
        original message.  If l < 2^32 then the first word is all
        zeroes.  Append these two words to the padded message.

        Example: Suppose the original message is as in (b). Then l = 40
        (note that l is computed before any padding). The two-word
        representation of 40 is hex 00000000 00000028. Hence the final
        padded message is hex

             61626364 65800000 00000000 00000000
             00000000 00000000 00000000 00000000
             00000000 00000000 00000000 00000000
             00000000 00000000 00000000 00000028.

        The padded message will contain 16 * n words for some n > 0.
        The padded message is regarded as a sequence of n blocks M(1) ,
        M(2), first characters (or bits) of the message.



5. Functions and Constants Used

   A sequence of logical functions f(0), f(1),..., f(79) is used in
   SHA-1.  Each f(t), 0 <= t <= 79, operates on three 32-bit words B, C,
   D and produces a 32-bit word as output.  f(t;B,C,D) is defined as
   follows: for words B, C, D,


        f(t;B,C,D) = (B AND C) OR ((NOT B) AND D)         ( 0 <= t <= 19)

        f(t;B,C,D) = B XOR C XOR D                        (20 <= t <= 39)

        f(t;B,C,D) = (B AND C) OR (B AND D) OR (C AND D)  (40 <= t <= 59)

        f(t;B,C,D) = B XOR C XOR D                        (60 <= t <= 79).

   A sequence of constant words K(0), K(1), ... , K(79) is used in the
   SHA-1.  In hex these are given by

        K(t) = 5A827999         ( 0 <= t <= 19)

        K(t) = 6ED9EBA1         (20 <= t <= 39)

        K(t) = 8F1BBCDC         (40 <= t <= 59)

        K(t) = CA62C1D6         (60 <= t <= 79).



D. Eastlake 3rd, P. Jones                                       [Page 6]

INTERNET-DRAFT                  US SHA-1                      March 2001


6. Computing the Message Digest

   The methods given in 6.1 and 6.2 below yield the same message digest.
   Although using method 2 saves sixty-four 32-bit words of storage, it
   is likely to lengthen execution time due to the increased complexity
   of the address computations for the { W[t] } in step (c).  There are
   other computation methods which give identical results.



6.1 Method 1

   The message digest is computed using the message padded as described
   in section 4. The computation is described using two buffers, each
   consisting of five 32-bit words, and a sequence of eighty 32-bit
   words.  The words of the first 5-word buffer are labeled A,B,C,D,E.
   The words of the second 5-word buffer are labeled H0, H1, H2, H3, H4.
   The words of the 80-word sequence are labeled W(0), W(1),..., W(79).
   A single word buffer TEMP is also employed.

   To generate the message digest, the 16-word blocks M(1), M(2),...,
   M(n) defined in section 4 are processed in order.  The processing of
   each M(i) involves 80 steps.

   Before processing any blocks, the H's are initialized as follows: in
   hex,

        H0 = 67452301

        H1 = EFCDAB89

        H2 = 98BADCFE

        H3 = 10325476

        H4 = C3D2E1F0.

   Now M(1), M(2), ... , M(n) are processed.  To process M(i), we
   proceed as follows:

      a. Divide M(i) into 16 words W(0), W(1), ... , W(15), where W(0)
         is the left-most word.

      b. For t = 16 to 79 let

         W(t) = S^1(W(t-3) XOR W(t-8) XOR W(t-14) XOR W(t-16)).

      c. Let A = H0, B = H1, C = H2, D = H3, E = H4.

      d. For t = 0 to 79 do


D. Eastlake 3rd, P. Jones                                       [Page 7]

INTERNET-DRAFT                  US SHA-1                      March 2001


         TEMP = S^5(A) + f(t;B,C,D) + E + W(t) + K(t);

         E = D;  D = C;  C = S^30(B);  B = A; A = TEMP;

      e. Let H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4
         + E.

   After processing M(n), the message digest is the 160-bit string
   represented by the 5 words

        H0 H1 H2 H3 H4.



6.2 Method 2

   The method above assumes that the sequence W(0), ... , W(79) is
   implemented as an array of eighty 32-bit words.  This is efficient
   from the standpoint of minimization of execution time, since the
   addresses of W(t-3), ...  ,W(t-16) in step (b) are easily computed.
   If space is at a premium, an alternative is to regard { W(t) } as a
   circular queue, which may be implemented using an array of sixteen
   32-bit words W[0], ... W[15].  In this case, in hex let

   MASK = 0000000F.  Then processing of M(i) is as follows:

      a. Divide M(i) into 16 words W[0], ... , W[15], where W[0] is the
         left-most word.

      b. Let A = H0, B = H1, C = H2, D = H3, E = H4.

      c. For t = 0 to 79 do

         s = t AND MASK;

         if (t >= 16) W[s] = S^1(W[(s + 13) AND MASK] XOR W[(s + 8) AND
         MASK] XOR W[(s + 2) AND MASK] XOR W[s]);

         TEMP = S^5(A) + f(t;B,C,D) + E + W[s] + K(t);

         E = D; D = C; C = S^30(B); B = A; A = TEMP;

      d. Let H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4
         + E.








D. Eastlake 3rd, P. Jones                                       [Page 8]

INTERNET-DRAFT                  US SHA-1                      March 2001


7. C Code

   Below is a demonstration implementation of SHA-1 in C.  Section 7.1
   contains the header file, 7.2 the C code, and 7.3 a test driver.



7.1 .h file

/*
 *  sha1.h
 *
 *  Description:
 *      This class implements the Secure Hashing Standard as defined
 *      in FIPS PUB 180-1 published April 17, 1995.
 *
 *      Many of the variable names in the SHA1Context, especially the
 *      single character names, were used because those were the names
 *      used in the publication.
 *
 *      Please read the file sha1.c for more information.
 *
 */

#ifndef _SHA1_H_
#define _SHA1_H_

/*
 *  Define the circular shift macro
 */
#define SHA1CircularShift(bits,word) \
                ((((word) << (bits)) & 0xFFFFFFFF) | \
                (((word) & 0xFFFFFFFF) >> (32-(bits))))

/*
 *  This structure will hold context information for the hashing
 *  operation
 */
typedef struct SHA1Context
{
    unsigned Message_Digest[5]; /* Message Digest (output)          */

    unsigned Length_Low;        /* Message length in bits           */
    unsigned Length_High;       /* Message length in bits           */

    unsigned char Message_Block[64]; /* 512-bit message blocks      */
    int Message_Block_Index;    /* Index into message block array   */

    int Computed;               /* Is the digest computed?          */
    int Corrupted;              /* Is the message digest corruped?  */


D. Eastlake 3rd, P. Jones                                       [Page 9]

INTERNET-DRAFT                  US SHA-1                      March 2001


} SHA1Context;

/*
 *  Function Prototypes
 */
void SHA1Reset(SHA1Context *);
int SHA1Result(SHA1Context *);
void SHA1Input( SHA1Context *,
                const unsigned char *,
                unsigned            );
void SHA1ProcessMessageBlock(SHA1Context *);
void SHA1PadMessage(SHA1Context *);

#endif



7.2 .c file

/*
 *  sha1.c
 *
 *  Description:
 *      This file implements the Secure Hashing Standard as defined
 *      in FIPS PUB 180-1 published April 17, 1995.
 *
 *      The Secure Hashing Standard, which uses the Secure Hashing
 *      Algorithm (SHA), produces a 160-bit message digest for a
 *      given data stream.  In theory, it is highly improbable that
 *      two messages will produce the same message digest.  Therefore,
 *      this algorithm can serve as a means of providing a "fingerprint"
 *      for a message.
 *
 *  Portability Issues:
 *      SHA-1 is defined in terms of 32-bit "words".  This code was
 *      written with the expectation that the processor has at least
 *      a 32-bit machine word size.  If the machine word size is larger,
 *      the code should still function properly.  One caveat to that
 *      is that the input functions taking characters and character
 *      arrays assume that only 8 bits of information are stored in each
 *      character.
 *
 *  Caveats:
 *      SHA-1 is designed to work with messages less than 2^64 bits
 *      long. Although SHA-1 allows a message digest to be generated for
 *      messages of any number of bits less than 2^64, this
 *      implementation only works with messages with a length that is a
 *      multiple of the size of an 8-bit character.
 *
 */


D. Eastlake 3rd, P. Jones                                      [Page 10]

INTERNET-DRAFT                  US SHA-1                      March 2001


#include "sha1.h"

/*
 *  SHA1Reset
 *
 *  Description:
 *      This function will initialize the SHA1Context in preparation
 *      for computing a new message digest.
 *
 *  Parameters:
 *      context: [in/out]
 *          The context to reset.
 *
 *  Returns:
 *      Nothing.
 *
 *  Comments:
 *
 */
void SHA1Reset(SHA1Context *context)
{
    context->Length_Low             = 0;
    context->Length_High            = 0;
    context->Message_Block_Index    = 0;

    context->Message_Digest[0]      = 0x67452301;
    context->Message_Digest[1]      = 0xEFCDAB89;
    context->Message_Digest[2]      = 0x98BADCFE;
    context->Message_Digest[3]      = 0x10325476;
    context->Message_Digest[4]      = 0xC3D2E1F0;

    context->Computed   = 0;
    context->Corrupted  = 0;
}

/*
 *  SHA1Result
 *
 *  Description:
 *      This function will return the 160-bit message digest into the
 *      Message_Digest array within the SHA1Context provided
 *
 *  Parameters:
 *      context: [in/out]
 *          The context to use to calculate the SHA-1 hash.
 *
 *  Returns:
 *      1 if successful, 0 if it failed.
 *
 *  Comments:


D. Eastlake 3rd, P. Jones                                      [Page 11]

INTERNET-DRAFT                  US SHA-1                      March 2001


 *
 */
int SHA1Result(SHA1Context *context)
{

    if (context->Corrupted)
    {
        return 0;
    }

    if (!context->Computed)
    {
        SHA1PadMessage(context);
        context->Computed = 1;
    }

    return 1;
}

/*
 *  SHA1Input
 *
 *  Description:
 *      This function accepts an array of octets as the next portion of
 *      the message.
 *
 *  Parameters:
 *      context: [in/out]
 *          The SHA-1 context to update
 *      message_array: [in]
 *          An array of characters representing the next portion of the
 *          message.
 *      length: [in]
 *          The length of the message in message_array
 *
 *  Returns:
 *      Nothing.
 *
 *  Comments:
 *
 */
void SHA1Input(     SHA1Context         *context,
                    const unsigned char *message_array,
                    unsigned            length)
{
    if (!length)
    {
        return;
    }



D. Eastlake 3rd, P. Jones                                      [Page 12]

INTERNET-DRAFT                  US SHA-1                      March 2001


    if (context->Computed || context->Corrupted)
    {
        context->Corrupted = 1;
        return;
    }

    while(length-- && !context->Corrupted)
    {
        context->Message_Block[context->Message_Block_Index++] =
                                                (*message_array & 0xFF);

        context->Length_Low += 8;
        /* Force it to 32 bits */
        context->Length_Low &= 0xFFFFFFFF;
        if (context->Length_Low == 0)
        {
            context->Length_High++;
            /* Force it to 32 bits */
            context->Length_High &= 0xFFFFFFFF;
            if (context->Length_High == 0)
            {
                /* Message is too long */
                context->Corrupted = 1;
            }
        }

        if (context->Message_Block_Index == 64)
        {
            SHA1ProcessMessageBlock(context);
        }

        message_array++;
    }
}

/*
 *  SHA1ProcessMessageBlock
 *
 *  Description:
 *      This function will process the next 512 bits of the message
 *      stored in the Message_Block array.
 *
 *  Parameters:
 *      None.
 *
 *  Returns:
 *      Nothing.
 *
 *  Comments:
 *      Many of the variable names in the SHAContext, especially the


D. Eastlake 3rd, P. Jones                                      [Page 13]

INTERNET-DRAFT                  US SHA-1                      March 2001


 *      single character names, were used because those were the names
 *      used in the publication.
 *
 *
 */
void SHA1ProcessMessageBlock(SHA1Context *context)
{
    const unsigned K[] =    {       /* Constants defined in SHA-1   */
                                0x5A827999,
                                0x6ED9EBA1,
                                0x8F1BBCDC,
                                0xCA62C1D6
                            };
    int         t;                  /* Loop counter                 */
    unsigned    temp;               /* Temporary word value         */
    unsigned    W[80];              /* Word sequence                */
    unsigned    A, B, C, D, E;      /* Word buffers                 */

    /*
     *  Initialize the first 16 words in the array W
     */
    for(t = 0; t < 16; t++)
    {
        W[t] = context->Message_Block[t * 4] << 24;
        W[t] |= context->Message_Block[t * 4 + 1] << 16;
        W[t] |= context->Message_Block[t * 4 + 2] << 8;
        W[t] |= context->Message_Block[t * 4 + 3];
    }

    for(t = 16; t < 80; t++)
    {
       W[t] = SHA1CircularShift(1,W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]);
    }

    A = context->Message_Digest[0];
    B = context->Message_Digest[1];
    C = context->Message_Digest[2];
    D = context->Message_Digest[3];
    E = context->Message_Digest[4];

    for(t = 0; t < 20; t++)
    {
        temp =  SHA1CircularShift(5,A) +
                ((B & C) | ((~B) & D)) + E + W[t] + K[0];
        temp &= 0xFFFFFFFF;
        E = D;
        D = C;
        C = SHA1CircularShift(30,B);
        B = A;
        A = temp;


D. Eastlake 3rd, P. Jones                                      [Page 14]

INTERNET-DRAFT                  US SHA-1                      March 2001


    }

    for(t = 20; t < 40; t++)
    {
        temp = SHA1CircularShift(5,A) + (B ^ C ^ D) + E + W[t] + K[1];
        temp &= 0xFFFFFFFF;
        E = D;
        D = C;
        C = SHA1CircularShift(30,B);
        B = A;
        A = temp;
    }

    for(t = 40; t < 60; t++)
    {
        temp = SHA1CircularShift(5,A) +
               ((B & C) | (B & D) | (C & D)) + E + W[t] + K[2];
        temp &= 0xFFFFFFFF;
        E = D;
        D = C;
        C = SHA1CircularShift(30,B);
        B = A;
        A = temp;
    }

    for(t = 60; t < 80; t++)
    {
        temp = SHA1CircularShift(5,A) + (B ^ C ^ D) + E + W[t] + K[3];
        temp &= 0xFFFFFFFF;
        E = D;
        D = C;
        C = SHA1CircularShift(30,B);
        B = A;
        A = temp;
    }

    context->Message_Digest[0] =
                        (context->Message_Digest[0] + A) & 0xFFFFFFFF;
    context->Message_Digest[1] =
                        (context->Message_Digest[1] + B) & 0xFFFFFFFF;
    context->Message_Digest[2] =
                        (context->Message_Digest[2] + C) & 0xFFFFFFFF;
    context->Message_Digest[3] =
                        (context->Message_Digest[3] + D) & 0xFFFFFFFF;
    context->Message_Digest[4] =
                        (context->Message_Digest[4] + E) & 0xFFFFFFFF;

    context->Message_Block_Index = 0;
}



D. Eastlake 3rd, P. Jones                                      [Page 15]

INTERNET-DRAFT                  US SHA-1                      March 2001


/*
 *  SHA1PadMessage
 *
 *  Description:
 *      According to the standard, the message must be padded to an even
 *      512 bits.  The first padding bit must be a '1'.  The last 64
 *      bits represent the length of the original message.  All bits in
 *      between should be 0.  This function will pad the message
 *      according to those rules by filling the Message_Block array
 *      accordingly.  It will also call SHA1ProcessMessageBlock()
 *      appropriately.  When it returns, it can be assumed that the
 *      message digest has been computed.
 *
 *  Parameters:
 *      context: [in/out]
 *          The context to pad
 *
 *  Returns:
 *      Nothing.
 *
 *  Comments:
 *
 */
void SHA1PadMessage(SHA1Context *context)
{
    /*
     *  Check to see if the current message block is too small to hold
     *  the initial padding bits and length.  If so, we will pad the
     *  block, process it, and then continue padding into a second
     *  block.
     */
    if (context->Message_Block_Index > 55)
    {
        context->Message_Block[context->Message_Block_Index++] = 0x80;
        while(context->Message_Block_Index < 64)
        {
            context->Message_Block[context->Message_Block_Index++] = 0;
        }

        SHA1ProcessMessageBlock(context);

        while(context->Message_Block_Index < 56)
        {
            context->Message_Block[context->Message_Block_Index++] = 0;
        }
    }
    else
    {
        context->Message_Block[context->Message_Block_Index++] = 0x80;
        while(context->Message_Block_Index < 56)


D. Eastlake 3rd, P. Jones                                      [Page 16]

INTERNET-DRAFT                  US SHA-1                      March 2001


        {
            context->Message_Block[context->Message_Block_Index++] = 0;
        }
    }

    /*
     *  Store the message length as the last 8 octets
     */
    context->Message_Block[56] = (context->Length_High >> 24) & 0xFF;
    context->Message_Block[57] = (context->Length_High >> 16) & 0xFF;
    context->Message_Block[58] = (context->Length_High >> 8) & 0xFF;
    context->Message_Block[59] = (context->Length_High) & 0xFF;
    context->Message_Block[60] = (context->Length_Low >> 24) & 0xFF;
    context->Message_Block[61] = (context->Length_Low >> 16) & 0xFF;
    context->Message_Block[62] = (context->Length_Low >> 8) & 0xFF;
    context->Message_Block[63] = (context->Length_Low) & 0xFF;

    SHA1ProcessMessageBlock(context);
}



7.3 Test Driver

/*
 *  shatest.c
 *
 *  Description:
 *      This file will exercise the SHA1 class and perform the three
 *      tests documented in FIPS PUB 180-1.
 *
 *  Portability Issues:
 *      None.
 *
 */

#include <stdio.h>
#include <string.h>
#include "sha1.h"

/*
 *  Define patterns for testing
 */
#define TESTA   "abc"
#define TESTB   "abcdbcdecdefdefgefghfghighijhi" \
                "jkijkljklmklmnlmnomnopnopq"
#define TESTC   "a"

int main()
{


D. Eastlake 3rd, P. Jones                                      [Page 17]

INTERNET-DRAFT                  US SHA-1                      March 2001


    SHA1Context sha;
    int i;

    /*
     *  Perform test A
     */
    printf("\nTest A: 'abc'\n");

    SHA1Reset(&sha);
    SHA1Input(&sha, (const unsigned char *) TESTA, strlen(TESTA));

    if (!SHA1Result(&sha))
    {
        fprintf(stderr, "ERROR-- could not compute message digest\n");
    }
    else
    {
        printf("\t");
        for(i = 0; i < 5 ; i++)
        {
            printf("%X ", sha.Message_Digest[i]);
        }
        printf("\n");
        printf("Should match:\n");
        printf("\tA9993E36 4706816A BA3E2571 7850C26C 9CD0D89D\n");
    }

    /*
     *  Perform test B
     */
    printf("\nTest B:\n");

    SHA1Reset(&sha);
    SHA1Input(&sha, (const unsigned char *) TESTB, strlen(TESTB));

    if (!SHA1Result(&sha))
    {
        fprintf(stderr, "ERROR-- could not compute message digest\n");
    }
    else
    {
        printf("\t");
        for(i = 0; i < 5 ; i++)
        {
            printf("%X ", sha.Message_Digest[i]);
        }
        printf("\n");
        printf("Should match:\n");
        printf("\t84983E44 1C3BD26E BAAE4AA1 F95129E5 E54670F1\n");
    }


D. Eastlake 3rd, P. Jones                                      [Page 18]

INTERNET-DRAFT                  US SHA-1                      March 2001


    /*
     *  Perform test C
     */
    printf("\nTest C: One million 'a' characters\n");

    SHA1Reset(&sha);
    for(i = 1; i <= 1000000; i++) {
        SHA1Input(&sha, (const unsigned char *) TESTC, 1);
    }

    if (!SHA1Result(&sha))
    {
        fprintf(stderr, "ERROR-- could not compute message digest\n");
    }
    else
    {
        printf("\t");
        for(i = 0; i < 5 ; i++)
        {
            printf("%X ", sha.Message_Digest[i]);
        }
        printf("\n");
        printf("Should match:\n");
        printf("\t34AA973C D4C4DAA4 F61EEB2B DBAD2731 6534016F\n");
    }

    return 0;
}



8. Security Considerations

   This document is intended to provide convenient open source access by
   the Internet community to the United States of America Federal
   Information Processing Standard Secure Hash Function.  No independent
   assertion of the security of this hash function by the authors for
   any particular use is intended.



References

   [FIPS 180-1] - "Secure Hash Standard", United States of American,
   National Institute of Science and Technology, Federal Information
   Processing Standard (FIPS) 180-1, April 1993.

   [MD4] - "The MD4 Message Digest Algorithm," Advances in Cryptology -
   CRYPTO '90 Proceedings, Springer-Verlag, 1991, pp. 303-311.



D. Eastlake 3rd, P. Jones                                      [Page 19]

INTERNET-DRAFT                  US SHA-1                      March 2001


   [RFC 1319] - "The MD2 Message-Digest Algorithm", B. Kaliski, April
   1992.

   [RFC 1320] - "The MD4 Message-Digest Algorithm", R. Rivest, April
   1992.

   [RFC 1321] - "The MD5 Message-Digest Algorithm", R. Rivest, April
   1992.

   [RFC 1750] - "Randomness Requirements for Security", D. Eastlake, S.
   Crocker, J. Schiller, December 1994.









































D. Eastlake 3rd, P. Jones                                      [Page 20]

INTERNET-DRAFT                  US SHA-1                      March 2001


Author's Address

   Donald E. Eastlake, 3rd
   Motorola
   155 Beaver Street
   Milford, MA 01757 USA

   Telephone:   +1 508-634-2066 (h)
                +1 508-261-5434 (w)
   FAX:         +1 508-261-4777
   EMail:       Donald.Eastlake@motorola.com


   Paul E. Jones
   Cisco Systems, Inc.
   7025 Kit Creek Road
   Research Triangle Park, NC 27709

   Telephone:   +1 919 392 6948
   Email:       paulej@packetizer.com



Expiration and File Name

   This draft expires September 2001.

   Its file name is draft-eastlake-sha1-00.txt.
























D. Eastlake 3rd, P. Jones                                      [Page 21]


Html markup produced by rfcmarkup 1.109, available from https://tools.ietf.org/tools/rfcmarkup/