home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Libraries / hash / README.shs < prev    next >
Encoding:
Text File  |  1994-03-25  |  17.1 KB  |  466 lines  |  [TEXT/R*ch]
  1. @(#)README.shs    10.1 3/25/94 08:04:07
  2.  
  3. Landon Curt Noll    chongo@toad.com        /\../\
  4.  
  5. This is an implementation of the Secure Hash Standard (SHS).
  6.  
  7. This code is based on code by Peter C. Gutmann.  Much thanks goes 
  8. to Peter C. Gutman (pgut1@cs.aukuni.ac.nz) , Shawn A. Clifford
  9. (sac@eng.ufl.edu), Pat Myrto (pat@rwing.uucp), Colin Plumb
  10. (colin@nyx10.cs.du.edu), Rich Schroeppel (rcs@cs.arizona.edu)
  11. and others who wrote and/or worked on the original code.
  12.  
  13. The digests produced from strings (-s string), files or stdin are
  14. identical to the Gutmann's program.  The command line and output
  15. interface are upward compatible as well.  Users of the original shs
  16. program may replace it with this version has their existing use
  17. and digests will be preserved.
  18.  
  19. See shsdrvr.c for version information.  See the man page shs.1
  20. for other details.
  21.  
  22.                     -- Landon Curt Noll
  23.                        chongo@toad.com
  24.  
  25. =-=
  26.  
  27. The following in the original README and documentation for this code:
  28.  
  29. From:  Dennis Branstad, NIST Fellow
  30.  
  31.     [[Text about the standard proposal process was deleted as the
  32.       Secure Hash Standard (SHS) is now a real approved standard 
  33.       (FIPS Pub 180).]]
  34.  
  35.  
  36.                          Specifications for a
  37.  
  38.  
  39.                        SECURE HASH STANDARD (SHS)
  40.  
  41.  
  42.                             1. INTRODUCTION
  43.  
  44.    The Secure Hash Algorithm (SHA) specified in this standard is
  45. necessary to ensure the security of the Digital Signature Standard. 
  46. When a message of length < 2^64 bits is input, the SHA produces a
  47. 160-bit representation of the message called the message digest. 
  48. The message digest is used during generation of a signature for the
  49. message.  The same message digest should be computed for the
  50. received version of the message, during the process of verifying
  51. the signature.  Any change to the message in transit will, with
  52. very high probability, result in a different message digest, and
  53. the signature will fail to verify.
  54.  
  55.    The SHA is designed to have the following properties: it is
  56. computationally infeasible to recover a message corresponding to a
  57. given message digest, or to find two different messages which
  58. produce the same message digest.
  59.  
  60.                      2. BIT STRINGS AND INTEGERS
  61.  
  62.    The following terminology related to bit strings and integers
  63. will be used:
  64.       
  65.    a. hex digit = 0, 1, ... , 9, a, ... , f.  A hex digit is the  
  66.       representation of a 4-bit string.  Examples: 7 = 0111, a =  
  67.       1010.
  68.  
  69.    b. word = 32-bit string b(31) b(30) ... b(0).  A word may be represented
  70.  
  71.       as a sequence of 8 hex digits.  To convert the latter to    
  72.       a 32-bit string, each hex digit is converted to a 4-bit     
  73.       string as in (a).  Example: 
  74.  
  75.          a103fe23 = 1010 0001 0000 0011 1111 1110 0010 0011.
  76.  
  77.       A word is also the representation of an unsigned integer    
  78.       between 0 and 2^32 - 1, inclusive, with the most significant 
  79.       bit first.  Example: the hex string a103fe23 represents     
  80.       the decimal integer 2701393443.
  81.  
  82.    c. block = 512-bit string.  A block may be represented as a    
  83.       sequence of 16 words.
  84.  
  85.    d. integer: each integer x in the standard will satisfy 0 <=
  86.       x < 2^64.  For the purpose of this standard, "integer" and   
  87.       "unsigned integer" are equivalent.  If an integer x         
  88.       satisfies 0 <= x < 2^32, x may be represented as a word as in     
  89.       (b).  If 2^32 <= x < 2^64, then x = 2^32 y + z where 0 <= y < 2^32 
  90.       and 0 <= z < 2^32.  Hence y and z can be represented as words A and B,
  91.  
  92.       respectively, and x can be represented as the pair of       
  93.       words (A,B).
  94.  
  95.    Suppose 0 <= x < 2^32.  To convert x to a 32-bit string, the
  96. following algorithm may be employed:
  97.  
  98.       y(0) = x;
  99.       for i = 0 to 31 do
  100.         {
  101.         b(i) = 1 if y(i) is odd, b(i) = 0 if y(i) is even;
  102.         y(i+1) = (y(i) - b(i))/2;
  103.         }
  104.  
  105.    Then x has the 32-bit representation b(31) b(30) ... b(0).  Example:
  106.  
  107.       25 = 00000000 00000000 00000000 00011001
  108.          = hex 00000019.
  109.  
  110.    If 2^32 <= x < 2^64, the 2-word representation of x is obtained
  111. similarly. 
  112. Example:
  113.  
  114.       2^35 + 25 = 8 * 2^32 + 25
  115.                = 00000000 00000000 00000000 00001000
  116.                  00000000 00000000 00000000 00011001
  117.                = hex 00000008 00000019.
  118.  
  119.    Conversely, the string b(31) b(30) ... b(0) represents the integer
  120.  
  121.       b(31) * 2^31 + b(30) * 2^30 + ... + b(1) * 2 + b(0).
  122.  
  123.                       3. OPERATIONS ON WORDS
  124.    
  125.    The following logical operators will be applied to words:   
  126.  
  127.       AND    =  bitwise logical and.
  128.  
  129.       OR    =  bitwise logical inclusive-or.
  130.     
  131.       XOR  =  bitwise logical exclusive-or.
  132.  
  133.       ~x   =  bitwise logical complement of x.
  134.  
  135.    Example: 
  136.  
  137.             01101100101110011101001001111011
  138.       XOR   01100101110000010110100110110111
  139.             --------------------------------
  140.         =   00001001011110001011101111001100.
  141.  
  142.    Another operation on words is A + B.  This is defined as
  143. follows: words A and B represent integers x and y, where 0 <= x < 2^32
  144. and 0 <= y < 2^32.  Compute 
  145.  
  146.       z = (x + y) mod 2^32.
  147.  
  148.    Then 0 <= z < 2^32. Convert z to a word, C, and define A + B = C.
  149.  
  150.    Another function on words is S(n,X), where X is a word and n is
  151. an integer with 0 <= n < 32.  This is defined by
  152.  
  153.       S(n,X) = (X << n) OR (X >> 32-n).
  154.  
  155.    In the above, X << n is obtained as follows: discard the
  156. leftmost n bits of X and then pad the result with n zeroes on the
  157. right (the result will still be 32 bits).  X >> m is obtained by
  158. discarding the rightmost m bits of X and then padding the result
  159. with m zeroes on the left.  Thus S(n,X) is equivalent to a circular
  160. shift of X by n positions to the left.
  161.  
  162.                         4. MESSAGE PADDING
  163.  
  164.    The SHA takes bit strings as input.  Thus, for the purpose of
  165. this standard, a message will be considered to be a bit string. 
  166. The length of the message is the number of bits (the empty message
  167. has length 0).  If the number of bits in a message is a multiple of
  168. 8, for compactness we can represent the message in hex.
  169.  
  170.    Suppose a message has length L < 2^64.  Before it is input to the
  171. SHA, the message is padded on the right as follows:
  172.  
  173.    a. "1" is appended.  Example: if the original message is       
  174.       "01010011", this is padded to "010100111".
  175.  
  176.    b. If necessary, "0"s are then appended until the number of bits 
  177.       in the padded message is congruent to 448 modulo 512.       
  178.       Example: suppose the original message is the bit string
  179.          
  180.          01100001 01100010 01100011 01100100 01100101.
  181.  
  182.       After step (a) this gives
  183.  
  184.          01100001 01100010 01100011 01100100 01100101 1.
  185.  
  186.       The number of bits in the above is 41; we pad with 407 "0"s 
  187.       to make the length of the padded message congruent to 448   
  188.       modulo 512.  This gives (in hex)
  189.  
  190.  
  191.          61626364 65800000 00000000 00000000
  192.          00000000 00000000 00000000 00000000
  193.          00000000 00000000 00000000 00000000
  194.          00000000 00000000.
  195.  
  196.       Note that the padding is arranged so that at this point
  197.       the padded message contains 16s + 14 words, for some s >=
  198.       0.
  199.  
  200.    c. Obtain the 2-word representation of L = the number of bits in 
  201.       the original message.  If L < 2^32 then the first word is all 
  202.       zeroes.  Append these two words to the padded message.      
  203.       Example: suppose the original message is as in (b). Then L = 
  204.       40 (note that L is computed before any padding). The two-word 
  205.       representation of 40 is hex 00000000 00000028.  Hence the   
  206.       final padded message is hex
  207.  
  208.          61626364 65800000 00000000 00000000
  209.          00000000 00000000 00000000 00000000
  210.          00000000 00000000 00000000 00000000
  211.          00000000 00000000 00000000 00000028.
  212.  
  213.    The final padded message will contain 16N words for some N > 0.
  214. Example: in (c) above, the final padded message has N = 1. The
  215. final padded message may be regarded as a sequence of N blocks M(1)
  216. , M(2), ... , M(N), where each M(i) contains 16 words and M(1) is leftmost.
  217.  
  218.                          5. FUNCTIONS USED
  219.  
  220.    A sequence of logical functions f(0,x,y,z), ... , f(79,x,y,z) is used in
  221. the
  222. SHA.  Each f operates on three 32-bit words {x,y,z} and produces a 32-bit
  223. word as output.  f(t,x,y,z) is defined as follows: for words x,y,z,
  224.  
  225.       f(t,x,y,z) = (x AND y) OR (~x AND z)             (0  <= t <= 19)
  226.  
  227.       f(t,x,y,z) = x XOR y XOR z                  (20 <= t <= 39)
  228.  
  229.       f(t,x,y,z) = (x AND y) OR (x AND z) OR (y AND z)    (40 <= t <= 59)
  230.  
  231.       f(t,x,y,z) = x XOR y XOR z                  (60 <= t <= 79).
  232.  
  233.                           6. CONSTANTS USED
  234.  
  235.    A sequence of constant words K(0), K(1), ... , K(79) is used in the SHA.
  236. In hex these are given by
  237.  
  238.       K(t) = 5a827999         (0  <= t <= 19)
  239.  
  240.       K(t) = 6ed9eba1         (20 <= t <= 39)
  241.  
  242.       K(t) = 8f1bbcdc         (40 <= t <= 59)
  243.  
  244.       K(t) = ca62c1d6         (60 <= t <= 79).
  245.  
  246.                      7. COMPUTING THE MESSAGE DIGEST
  247.    
  248.    The message digest is computed using the final padded message.
  249. The computation uses two buffers, each consisting of five 32-bit
  250. words, and a sequence of eighty 32-bit words.  The words of the
  251. first 5-word buffer are labeled A,B,C,D,E.  The words of the second
  252. 5-word buffer are labeled h0, h1, h2, h3, h4.  The words of the 80-
  253. word sequence are labeled W(0), W(1), ... , W(79).  A single word buffer
  254. TEMP is also employed.
  255.    
  256.    To generate the message digest, the 16-word blocks M(1), M(2), ...
  257. , M(N) defined in Section 4 are processed in order.  The processing
  258. of each M(i) involves 80 steps.
  259.  
  260.    Before processing any blocks, the {hj} are initialized as
  261. follows: in hex,
  262.  
  263.       h0 = 67452301
  264.  
  265.       h1 = efcdab89
  266.  
  267.       h2 = 98badcfe
  268.  
  269.       h3 = 10325476
  270.  
  271.       h4 = c3d2e1f0.
  272.  
  273.    Now M(1), M(2), ... , M(N) are processed.  To process M(i), we proceed as
  274. follows:
  275.  
  276.    a. Divide M(i) into 16 words W(0), W(1), ... , W(15), where W(0) is the
  277.       leftmost word.
  278.  
  279.    b. For t = 16 to 79 let W(t) = W(t-3) XOR W(t-8) XOR W(t-14) XOR W(t-16).
  280.  
  281.    c. Let A = h0, B = h1, C = h2, D = h3, E = h4.
  282.  
  283.    d. For t = 0 to 79 do
  284.  
  285.         TEMP = S(5,A) + f(t,B,C,D) + E + W(t) + K(t);
  286.  
  287.         E = D;  D = C;  C = S(30,B);  B = A; A = TEMP;
  288.  
  289.    e. Let h0 = h0 + A, h1 = h1 + B, h2 = h2 + C, h3 = h3 + D, h4 = h4 + E.
  290.  
  291.    After processing M(N), the message digest is the 160-bit string
  292. represented by the 5 words
  293.  
  294.       h0 h1 h2 h3 h4.
  295.  
  296.    The above assumes that the sequence W(0), ... , W(79) is implemented
  297. as an array of eighty 32-bit words.  This is efficient from the
  298. standpoint of minimization of execution time, since the addresses
  299. of W(t-3), ... , W(t-16) in step (b) are easily computed.  If space is at
  300. a premium, an alternative is to regard { W(t) } as a circular queue,
  301. which may be implemented using an array of sixteen 32-bit words
  302. W[0], ... W[15].  In this case, in hex let MASK = 0000000f.  Then
  303. processing of M(i) is as follows:
  304.  
  305.    aa. Divide M(i) into 16 words W[0], ... , W[15], where W[0] is the 
  306.        leftmost word.
  307.  
  308.    bb. Let A = h0, B = h1, C = h2, D = h3, E = h4.
  309.  
  310.    cc. For t = 0 to 79 do
  311.         
  312.          s = t AND MASK;
  313.  
  314.          if (t >= 16) W[s] = W[(s + 13) AND MASK] XOR W[(s + 8) AND 
  315.             
  316.             MASK] XOR W[(s + 2) AND MASK] XOR W[s];
  317.  
  318.          TEMP = S(5,A) + f(t,B,C,D) + E + W[s] + K(t);
  319.   
  320.          E = D; D = C; C = S(30,B); B = A; A = TEMP;
  321.  
  322.    dd. Let h0 = h0 + A, h1 = h1 + B, h2 = h2 + C, h3 = h3 + D, h4    
  323.        = h4 + E.
  324.  
  325.    Both (a) - (d) and (aa) - (dd) yield the same message digest.
  326. Although using (aa) - (dd) saves sixty-four 32-bit words of
  327. storage, it is likely to lengthen execution time due to the
  328. increased complexity of the address computations for the { W[t] }
  329. in step (cc).  Other computation methods which give identical
  330. results may be implemented in conformance with the standard.
  331.  
  332.    Examples are given in the appendices.
  333.  
  334.            APPENDIX A. A SAMPLE MESSAGE AND ITS MESSAGE DIGEST
  335.  
  336.    This appendix is for informational purposes only and is not
  337. required to meet the standard.
  338.  
  339.    Let the message be the ASCII binary-coded form of "abc", i.e.
  340.  
  341.       01100001 01100010 01100011.
  342.  
  343.    This message has length L = 24.  In step (a) of Section 4, we
  344. append "1", giving a new length of 25.  In step (b) we append 423
  345. "0"s.  In step (c) we append hex 00000000 00000018, the 2-word
  346. representation of 24.  Thus the final padded message consists of
  347. one block, so that N = 1 in the notation of Section 4.  The single
  348. block has hex words
  349.  
  350. W[ 0] = 61626380
  351. W[ 1] = 00000000
  352. W[ 2] = 00000000
  353. W[ 3] = 00000000
  354. W[ 4] = 00000000
  355. W[ 5] = 00000000
  356. W[ 6] = 00000000
  357. W[ 7] = 00000000
  358. W[ 8] = 00000000
  359. W[ 9] = 00000000
  360. W[10] = 00000000
  361. W[11] = 00000000
  362. W[12] = 00000000
  363. W[13] = 00000000
  364. W[14] = 00000000
  365. W[15] = 00000018
  366.  
  367.    Initial hex values of h:
  368.          
  369.          h0        h1        h2        h3        h4
  370.  
  371.       67452301  efcdab89  98badcfe  10325476  c3d2e1f0
  372.  
  373.    Hex values of A,B,C,D,E after pass t of the "for t = 0 to 79"
  374. loop (step (d) or (cc)) in Section 7:
  375.  
  376.             A        B        C        D        E
  377.  
  378. t =  0:  0116fc33 67452301 7bf36ae2 98badcfe 10325476
  379. t =  1:  8990536d 0116fc33 59d148c0 7bf36ae2 98badcfe
  380. t =  2:  a1390f08 8990536d c045bf0c 59d148c0 7bf36ae2
  381. t =  3:  cdd8e11b a1390f08 626414db c045bf0c 59d148c0
  382. t =  4:  cfd499de cdd8e11b 284e43c2 626414db c045bf0c
  383. t =  5:  3fc7ca40 cfd499de f3763846 284e43c2 626414db
  384. t =  6:  993e30c1 3fc7ca40 b3f52677 f3763846 284e43c2
  385. t =  7:  9e8c07d4 993e30c1 0ff1f290 b3f52677 f3763846
  386. t =  8:  4b6ae328 9e8c07d4 664f8c30 0ff1f290 b3f52677
  387. t =  9:  8351f929 4b6ae328 27a301f5 664f8c30 0ff1f290
  388. t = 10:  fbda9e89 8351f929 12dab8ca 27a301f5 664f8c30
  389. t = 11:  63188fe4 fbda9e89 60d47e4a 12dab8ca 27a301f5
  390. t = 12:  4607b664 63188fe4 7ef6a7a2 60d47e4a 12dab8ca
  391. t = 13:  9128f695 4607b664 18c623f9 7ef6a7a2 60d47e4a
  392. t = 14:  196bee77 9128f695 1181ed99 18c623f9 7ef6a7a2
  393. t = 15:  20bdd62f 196bee77 644a3da5 1181ed99 18c623f9
  394. t = 16:  ed2ff4a3 20bdd62f c65afb9d 644a3da5 1181ed99
  395. t = 17:  565df73c ed2ff4a3 c82f758b c65afb9d 644a3da5
  396. t = 18:  550b1e7f 565df73c fb4bfd28 c82f758b c65afb9d
  397. t = 19:  fe0f9e4b 550b1e7f 15977dcf fb4bfd28 c82f758b
  398. t = 20:  b4d4c943 fe0f9e4b d542c79f 15977dcf fb4bfd28
  399. t = 21:  43993572 b4d4c943 ff83e792 d542c79f 15977dcf
  400. t = 22:  f7106486 43993572 ed353250 ff83e792 d542c79f
  401. t = 23:  775924e6 f7106486 90e64d5c ed353250 ff83e792
  402. t = 24:  45a7ef23 775924e6 bdc41921 90e64d5c ed353250
  403. t = 25:  ccead674 45a7ef23 9dd64939 bdc41921 90e64d5c
  404. t = 26:  02d0c6d1 ccead674 d169fbc8 9dd64939 bdc41921
  405. t = 27:  070c437f 02d0c6d1 333ab59d d169fbc8 9dd64939
  406. t = 28:  301e90be 070c437f 40b431b4 333ab59d d169fbc8
  407. t = 29:  b898c685 301e90be c1c310df 40b431b4 333ab59d
  408. t = 30:  669723e2 b898c685 8c07a42f c1c310df 40b431b4
  409. t = 31:  d9316f96 669723e2 6e2631a1 8c07a42f c1c310df
  410. t = 32:  db81a5c7 d9316f96 99a5c8f8 6e2631a1 8c07a42f
  411. t = 33:  99c8dfb2 db81a5c7 b64c5be5 99a5c8f8 6e2631a1
  412. t = 34:  6be6ae07 99c8dfb2 f6e06971 b64c5be5 99a5c8f8
  413. t = 35:  c01cc62c 6be6ae07 a67237ec f6e06971 b64c5be5
  414. t = 36:  6433fdd0 c01cc62c daf9ab81 a67237ec f6e06971
  415. t = 37:  0a33ccf7 6433fdd0 3007318b daf9ab81 a67237ec
  416. t = 38:  4bf58dc8 0a33ccf7 190cff74 3007318b daf9ab81
  417. t = 39:  ebbd5233 4bf58dc8 c28cf33d 190cff74 3007318b
  418. t = 40:  825a3460 ebbd5233 12fd6372 c28cf33d 190cff74
  419. t = 41:  b62cbb93 825a3460 faef548c 12fd6372 c28cf33d
  420. t = 42:  aa3f9707 b62cbb93 20968d18 faef548c 12fd6372
  421. t = 43:  fe1d0273 aa3f9707 ed8b2ee4 20968d18 faef548c
  422. t = 44:  57ad526b fe1d0273 ea8fe5c1 ed8b2ee4 20968d18
  423. t = 45:  93ebbe3f 57ad526b ff87409c ea8fe5c1 ed8b2ee4
  424. t = 46:  f9adf47b 93ebbe3f d5eb549a ff87409c ea8fe5c1
  425. t = 47:  875586d2 f9adf47b e4faef8f d5eb549a ff87409c
  426. t = 48:  d0a22ffb 875586d2 fe6b7d1e e4faef8f d5eb549a
  427. t = 49:  c12b6426 d0a22ffb a1d561b4 fe6b7d1e e4faef8f
  428. t = 50:  ebc90281 c12b6426 f4288bfe a1d561b4 fe6b7d1e
  429. t = 51:  e7d0ec05 ebc90281 b04ad909 f4288bfe a1d561b4
  430. t = 52:  7cb98e55 e7d0ec05 7af240a0 b04ad909 f4288bfe
  431. t = 53:  0d48dba2 7cb98e55 79f43b01 7af240a0 b04ad909
  432. t = 54:  c2d477bf 0d48dba2 5f2e6395 79f43b01 7af240a0
  433. t = 55:  236bd48d c2d477bf 835236e8 5f2e6395 79f43b01
  434. t = 56:  9b4364d6 236bd48d f0b51def 835236e8 5f2e6395
  435. t = 57:  5b8c33c9 9b4364d6 48daf523 f0b51def 835236e8
  436. t = 58:  be2a4656 5b8c33c9 a6d0d935 48daf523 f0b51def
  437. t = 59:  8ff296db be2a4656 56e30cf2 a6d0d935 48daf523
  438. t = 60:  c10c8993 8ff296db af8a9195 56e30cf2 a6d0d935
  439. t = 61:  6ac23cbf c10c8993 e3fca5b6 af8a9195 56e30cf2
  440. t = 62:  0708247d 6ac23cbf f0432264 e3fca5b6 af8a9195
  441. t = 63:  35d201f8 0708247d dab08f2f f0432264 e3fca5b6
  442. t = 64:  969b2fc8 35d201f8 41c2091f dab08f2f f0432264
  443. t = 65:  3cac6514 969b2fc8 0d74807e 41c2091f dab08f2f
  444. t = 66:  14cd9a35 3cac6514 25a6cbf2 0d74807e 41c2091f
  445. t = 67:  ba564047 14cd9a35 0f2b1945 25a6cbf2 0d74807e
  446. t = 68:  c241f74d ba564047 4533668d 0f2b1945 25a6cbf2
  447. t = 69:  2896b70f c241f74d ee959011 4533668d 0f2b1945
  448. t = 70:  564bbed1 2896b70f 70907dd3 ee959011 4533668d
  449. t = 71:  8fa15d5a 564bbed1 ca25adc3 70907dd3 ee959011
  450. t = 72:  9a226c11 8fa15d5a 5592efb4 ca25adc3 70907dd3
  451. t = 73:  f0b94489 9a226c11 a3e85756 5592efb4 ca25adc3
  452. t = 74:  1809d5e2 f0b94489 66889b04 a3e85756 5592efb4
  453. t = 75:  b86c5a40 1809d5e2 7c2e5122 66889b04 a3e85756
  454. t = 76:  dfe7e487 b86c5a40 86027578 7c2e5122 66889b04
  455. t = 77:  70286c07 dfe7e487 2e1b1690 86027578 7c2e5122
  456. t = 78:  24ff7ed5 70286c07 f7f9f921 2e1b1690 86027578
  457. t = 79:  9a1f95a8 24ff7ed5 dc0a1b01 f7f9f921 2e1b1690
  458.  
  459.    After processing, values of h:
  460.  
  461.          h0        h1        h2        h3        h4
  462.  
  463.       0164b8a9  14cd2a5e  74c4f7ff   082c4d97  f1edf880
  464.  
  465.    Message digest =  0164b8a9 14cd2a5e 74c4f7ff 082c4d97 f1edf880
  466.