rfc1186

MD4的源代码。该算法来源于应用密码学的随书附带光盘。已通过调试

Rivest                                                          [Page 6]

RFC 1186              MD4 Message Digest Algorithm          October 1990


5.  Summary

   The MD4 message digest algorithm is simple to implement, and provides
   a "fingerprint" or message digest of a message of arbitrary length.

   It is conjectured that the difficulty of coming up with two messages
   having the same message digest is on the order of 2^64 operations,
   and that the difficulty of coming up with any message having a given
   message digest is on the order of 2^128 operations.  The MD4
   algorithm has been carefully scrutinized for weaknesses.  It is,
   however, a relatively new algorithm and further security analysis is
   of course justified, as is the case with any new proposal of this
   sort.  The level of security provided by MD4 should be sufficient for
   implementing very high security hybrid digital signature schemes
   based on MD4 and the RSA public-key cryptosystem.

6.  Acknowledgements

   I'd like to thank Don Coppersmith, Burt Kaliski, Ralph Merkle, and
   Noam Nisan for numerous helpful comments and suggestions.

APPENDIX - Reference Implementation

This appendix contains the following files:

         md4.h        -- header file for using MD4 implementation
         md4.c        -- the source code for MD4 routines
         md4driver.c  -- a sample "user" routine
         session      -- sample results of running md4driver

 /*
 ** ********************************************************************
 ** md4.h -- Header file for implementation of                        **
 ** MD4 Message Digest Algorithm                                      **
 ** Updated: 2/13/90 by Ronald L. Rivest                              **
 ** (C) 1990 RSA Data Security, Inc.                                  **
 ** ********************************************************************
 */

 /* MDstruct is the data structure for a message digest computation.
 */
 typedef struct {
   unsigned int buffer[4]; /* Holds 4-word result of MD computation */
   unsigned char count[8]; /* Number of bits processed so far */
   unsigned int done;      /* Nonzero means MD computation finished */
 } MDstruct, *MDptr;

 /* MDbegin(MD)



Rivest                                                          [Page 7]

RFC 1186              MD4 Message Digest Algorithm          October 1990


 ** Input: MD -- an MDptr
 ** Initialize the MDstruct prepatory to doing a message digest
 ** computation.
 */
 extern void MDbegin();

 /* MDupdate(MD,X,count)
 ** Input: MD -- an MDptr
 **        X -- a pointer to an array of unsigned characters.
 **        count -- the number of bits of X to use (an unsigned int).
 ** Updates MD using the first "count" bits of X.
 ** The array pointed to by X is not modified.
 ** If count is not a multiple of 8, MDupdate uses high bits of
 ** last byte.
 ** This is the basic input routine for a user.
 ** The routine terminates the MD computation when count < 512, so
 ** every MD computation should end with one call to MDupdate with a
 ** count less than 512.  Zero is OK for a count.
 */
 extern void MDupdate();

 /* MDprint(MD)
 ** Input: MD -- an MDptr
 ** Prints message digest buffer MD as 32 hexadecimal digits.
 ** Order is from low-order byte of buffer[0] to high-order byte
 ** of buffer[3].
 ** Each byte is printed with high-order hexadecimal digit first.
 */
 extern void MDprint();

 /*
 ** End of md4.h
 ****************************(cut)***********************************/

 /*
 ** ********************************************************************
 ** md4.c -- Implementation of MD4 Message Digest Algorithm           **
 ** Updated: 2/16/90 by Ronald L. Rivest                              **
 ** (C) 1990 RSA Data Security, Inc.                                  **
 ** ********************************************************************
 */

 /*
 ** To use MD4:
 **   -- Include md4.h in your program
 **   -- Declare an MDstruct MD to hold the state of the digest
 **          computation.
 **   -- Initialize MD using MDbegin(&MD)



Rivest                                                          [Page 8]

RFC 1186              MD4 Message Digest Algorithm          October 1990


 **   -- For each full block (64 bytes) X you wish to process, call
 **          MDupdate(&MD,X,512)
 **      (512 is the number of bits in a full block.)
 **   -- For the last block (less than 64 bytes) you wish to process,
 **          MDupdate(&MD,X,n)
 **      where n is the number of bits in the partial block. A partial
 **      block terminates the computation, so every MD computation
 **      should terminate by processing a partial block, even if it
 **      has n = 0.
 **   -- The message digest is available in MD.buffer[0] ...
 **      MD.buffer[3].  (Least-significant byte of each word
 **      should be output first.)
 **   -- You can print out the digest using MDprint(&MD)
 */

 /* Implementation notes:
 ** This implementation assumes that ints are 32-bit quantities.
 ** If the machine stores the least-significant byte of an int in the
 ** least-addressed byte (e.g., VAX and 8086), then LOWBYTEFIRST
 ** should be set to TRUE.  Otherwise (e.g., SUNS), LOWBYTEFIRST
 ** should be set to FALSE.  Note that on machines with LOWBYTEFIRST
 ** FALSE the routine MDupdate modifies has a side-effect on its input
 ** array (the order of bytes in each word are reversed).  If this is
 ** undesired a call to MDreverse(X) can reverse the bytes of X back
 ** into order after each call to MDupdate.

 */
 #define TRUE  1
 #define FALSE 0
 #define LOWBYTEFIRST FALSE

 /* Compile-time includes
 */
 #include <stdio.h>
 #include "md4.h"

 /* Compile-time declarations of MD4 "magic constants".
 */
 #define I0  0x67452301       /* Initial values for MD buffer */
 #define I1  0xefcdab89
 #define I2  0x98badcfe
 #define I3  0x10325476
 #define C2  013240474631     /* round 2 constant = sqrt(2) in octal */
 #define C3  015666365641     /* round 3 constant = sqrt(3) in octal */
 /* C2 and C3 are from Knuth, The Art of Programming, Volume 2
 ** (Seminumerical Algorithms), Second Edition (1981), Addison-Wesley.
 ** Table 2, page 660.
 */



Rivest                                                          [Page 9]

RFC 1186              MD4 Message Digest Algorithm          October 1990


 #define fs1  3               /* round 1 shift amounts */
 #define fs2  7
 #define fs3 11
 #define fs4 19
 #define gs1  3               /* round 2 shift amounts */
 #define gs2  5
 #define gs3  9
 #define gs4 13
 #define hs1  3               /* round 3 shift amounts */
 #define hs2  9
 #define hs3 11
 #define hs4 15

 /* Compile-time macro declarations for MD4.
 ** Note: The "rot" operator uses the variable "tmp".
 ** It assumes tmp is declared as unsigned int, so that the >>
 ** operator will shift in zeros rather than extending the sign bit.
 */
 #define f(X,Y,Z)             ((X&Y) | ((~X)&Z))
 #define g(X,Y,Z)             ((X&Y) | (X&Z) | (Y&Z))
 #define h(X,Y,Z)             (X^Y^Z)
 #define rot(X,S)             (tmp=X,(tmp<<S) | (tmp>>(32-S)))
 #define ff(A,B,C,D,i,s)      A = rot((A + f(B,C,D) + X[i]),s)
 #define gg(A,B,C,D,i,s)      A = rot((A + g(B,C,D) + X[i] + C2),s)
 #define hh(A,B,C,D,i,s)      A = rot((A + h(B,C,D) + X[i] + C3),s)

 /* MDprint(MDp)
 ** Print message digest buffer MDp as 32 hexadecimal digits.
 ** Order is from low-order byte of buffer[0] to high-order byte of
 ** buffer[3].
 ** Each byte is printed with high-order hexadecimal digit first.
 ** This is a user-callable routine.
 */
 void
 MDprint(MDp)
 MDptr MDp;
 { int i,j;
   for (i=0;i<4;i++)
     for (j=0;j<32;j=j+8)
       printf("%02x",(MDp->buffer[i]>>j) & 0xFF);
 }

 /* MDbegin(MDp)
 ** Initialize message digest buffer MDp.
 ** This is a user-callable routine.
 */
 void
 MDbegin(MDp)



Rivest                                                         [Page 10]

RFC 1186              MD4 Message Digest Algorithm          October 1990


 MDptr MDp;
 { int i;
   MDp->buffer[0] = I0;
   MDp->buffer[1] = I1;
   MDp->buffer[2] = I2;
   MDp->buffer[3] = I3;
   for (i=0;i<8;i++) MDp->count[i] = 0;
   MDp->done = 0;
 }

 /* MDreverse(X)
 ** Reverse the byte-ordering of every int in X.
 ** Assumes X is an array of 16 ints.
 ** The macro revx reverses the byte-ordering of the next word of X.
 */
 #define revx { t = (*X << 16) | (*X >> 16); \
      *X++ = ((t & 0xFF00FF00) >> 8) | ((t & 0x00FF00FF) << 8); }
 MDreverse(X)
 unsigned int *X;
 { register unsigned int t;
   revx; revx; revx; revx; revx; revx; revx; revx;
   revx; revx; revx; revx; revx; revx; revx; revx;
 }

 /* MDblock(MDp,X)
 ** Update message digest buffer MDp->buffer using 16-word data block X.
 ** Assumes all 16 words of X are full of data.
 ** Does not update MDp->count.
 ** This routine is not user-callable.
 */
 static void
 MDblock(MDp,X)
 MDptr MDp;
 unsigned int *X;
 {
   register unsigned int tmp, A, B, C, D;
 #if LOWBYTEFIRST == FALSE
   MDreverse(X);
 #endif
   A = MDp->buffer[0];
   B = MDp->buffer[1];
   C = MDp->buffer[2];
   D = MDp->buffer[3];
   /* Update the message digest buffer */
   ff(A , B , C , D ,  0 , fs1); /* Round 1 */
   ff(D , A , B , C ,  1 , fs2);
   ff(C , D , A , B ,  2 , fs3);
   ff(B , C , D , A ,  3 , fs4);



Rivest                                                         [Page 11]

RFC 1186              MD4 Message Digest Algorithm          October 1990


   ff(A , B , C , D ,  4 , fs1);
   ff(D , A , B , C ,  5 , fs2);
   ff(C , D , A , B ,  6 , fs3);
   ff(B , C , D , A ,  7 , fs4);
   ff(A , B , C , D ,  8 , fs1);
   ff(D , A , B , C ,  9 , fs2);
   ff(C , D , A , B , 10 , fs3);
   ff(B , C , D , A , 11 , fs4);
   ff(A , B , C , D , 12 , fs1);
   ff(D , A , B , C , 13 , fs2);
   ff(C , D , A , B , 14 , fs3);
   ff(B , C , D , A , 15 , fs4);
   gg(A , B , C , D ,  0 , gs1); /* Round 2 */
   gg(D , A , B , C ,  4 , gs2);
   gg(C , D , A , B ,  8 , gs3);
   gg(B , C , D , A , 12 , gs4);
   gg(A , B , C , D ,  1 , gs1);
   gg(D , A , B , C ,  5 , gs2);
   gg(C , D , A , B ,  9 , gs3);
   gg(B , C , D , A , 13 , gs4);
   gg(A , B , C , D ,  2 , gs1);
   gg(D , A , B , C ,  6 , gs2);
   gg(C , D , A , B , 10 , gs3);
   gg(B , C , D , A , 14 , gs4);
   gg(A , B , C , D ,  3 , gs1);
   gg(D , A , B , C ,  7 , gs2);
   gg(C , D , A , B , 11 , gs3);
   gg(B , C , D , A , 15 , gs4);
   hh(A , B , C , D ,  0 , hs1); /* Round 3 */
   hh(D , A , B , C ,  8 , hs2);
   hh(C , D , A , B ,  4 , hs3);
   hh(B , C , D , A , 12 , hs4);
   hh(A , B , C , D ,  2 , hs1);
   hh(D , A , B , C , 10 , hs2);
   hh(C , D , A , B ,  6 , hs3);
   hh(B , C , D , A , 14 , hs4);
   hh(A , B , C , D ,  1 , hs1);
   hh(D , A , B , C ,  9 , hs2);
   hh(C , D , A , B ,  5 , hs3);
   hh(B , C , D , A , 13 , hs4);
   hh(A , B , C , D ,  3 , hs1);
   hh(D , A , B , C , 11 , hs2);
   hh(C , D , A , B ,  7 , hs3);
   hh(B , C , D , A , 15 , hs4);
   MDp->buffer[0] += A;
   MDp->buffer[1] += B;
   MDp->buffer[2] += C;
   MDp->buffer[3] += D;



Rivest                                                         [Page 12]