MD5算法的设计与实现.doc

实验三 MD5算法的设计与实现1、 实验目的： 设计并实现MD5算法，从而进一步加深对数据完整性保证和散列函数的理解。二、实验要求： 1、产生任意电子文档（包括文本和二进制）的128位信息摘要。 2、根据信息摘要验证该电子文档是否被更改过。三、实验内容:1、 MD5算法简介: Message Digest Algorithm MD5（中文名为消息摘要算法第五版）为计算机安全领域广泛使用的一种散列函数，用以提供消息的完整性保护。1991年，Rivest开发出技术上更为趋近成熟的md5算法。它在MD4的基础上增加了安全-带子（safety-belts）的概念。虽然MD5比MD4复杂度大一些，但却更为安全。这个算法很明显的由四个和MD4设计有少许不同的步骤组成。在MD5算法中，信息-摘要的大小和填充的必要条件与MD4完全相同。Den boer和Bosselaers曾发现MD5算法中的假冲突（pseudo-collisions），但除此之外就没有其他被发现的加密后结果了。对MD5算法简要的叙述可以为：MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。 2. MD5算法逻辑处理操作包括以下几步： 步骤一：附加填充比特。对报文填充使报文的长度（比特数）与448模512同余。即填充比特使长度为512的整数倍减去64。例如，如果报文是448比特长，那么将填充512比特形成960比特的报文。填充比特串的最高位为1，其余各位均为0。 步骤二：附加长度值。将用64比特表示的初始报文（填充前）的位长度附加在步骤一的结果后（低位字节优先）。如果初始长度大于264，仅使用该长度的低64比特。这样，该域所包含的长度值为初始报文长度模264的值。 这两步的结果将产生一个长度为512整数倍比特的报文。经扩展的报文表示成512比特的分组序列列Y1、Y2、Y3Y（n-1），因此扩展的报文长度等于L乘512比特。与之等价的是，该结果也等于字长为16比特或32比特的整数倍，如果让10NML表示扩展报文包含的字数，其中N是16的倍数，则N等于L 乘512。下图为使用MD5产生报文摘要的过程： 步骤三：初始化MD缓存。使用一个128比特的缓存来存放该散列函数的中间值及最终结果。该缓存可表示为4个32比特的寄存器(ABCD)。A=67452301，B=EFCDAB89，C=98BADCFE，D=10325476，这些值以低位字节放在在前的格式存储： A=01234567，B=89ABCDEF，C=FEDCBA98，D=76543210 步骤四：处理512比特报文分组序列。算法的核心是一个包含四个“循环”的压缩函数，下图为单个512比特分组MD5处理过程： 四个循环有相似的结构，但每次循环使用不同的原始逻辑函数，说明中表示为FGHI。每一循环都以当前的正在处理的512比特分组(Yq)和128比特的缓存值ABCD为输入，然后更新缓存的内容。每一循环使用一个64元素表T064的四分之一，该表通过正弦函数构建。T的第i个元素（表示为Ti）的值等于的整数部分值其中i的单位是弧度。因为是0到1之间的数，每个T的值均能用32比特表示集，它将消除输入数据的任何规律性。第四次循环的输出加到第一次循环的输入(CVq)上产生(CV q+1)，相加是缓存四个字与(CVq)中对应四个字以模相加。 步骤五：输出。所有L个512比特的分组处理完成后，第L阶段产生的输出便是128比特的报文摘要。总结MD5的操作如下： 其中： IV=缓存ABCD的初值，在步骤三定义 Yq=第q个长度为512比特的报文分组 L=报文（包括填充字段和长度字段）的分组数CVq=处理第q个报文分组时的连接变量RFx=使用原始逻辑函数x的循环函数 MD=最终的报文摘要 SUM32=对输入对中的每个字分别执行模相加 3、MD5的安全性： md5相对md4所作的改进： a. 增加了第四轮； b. 每一步均有唯一的加法常数； c. 为减弱第二轮中函数g的对称性从(x&y)|(x&z)|(y&z)变为(x&z)|(y&(z)； d. 第一步加上了上一步的结果，这将引起更快的雪崩效应； e. 改变了第二轮和第三轮中访问消息子分组的次序，使其更不相似； f. 近似优化了每一轮中的循环左移位移量以实现更快的雪崩效应。各轮的位移量互不相同。4. 设计MD5算法： (1)、MD5ChecksumDefines.h（定义相关常量的头文件）/Magic initialization constants#define MD5_INIT_STATE_0 0x67452301#define MD5_INIT_STATE_1 0xefcdab89#define MD5_INIT_STATE_2 0x98badcfe#define MD5_INIT_STATE_3 0x10325476/Constants for Transform routine.#define MD5_S11 7#define MD5_S12 12#define MD5_S13 17#define MD5_S14 22#define MD5_S21 5#define MD5_S22 9#define MD5_S23 14#define MD5_S24 20#define MD5_S31 4#define MD5_S32 11#define MD5_S33 16#define MD5_S34 23#define MD5_S41 6#define MD5_S42 10#define MD5_S43 15#define MD5_S44 21/Transformation Constants - Round 1#define MD5_T01 0xd76aa478 /Transformation Constant 1 #define MD5_T02 0xe8c7b756 /Transformation Constant 2#define MD5_T03 0x242070db /Transformation Constant 3#define MD5_T04 0xc1bdceee /Transformation Constant 4#define MD5_T05 0xf57c0faf /Transformation Constant 5#define MD5_T06 0x4787c62a /Transformation Constant 6#define MD5_T07 0xa8304613 /Transformation Constant 7#define MD5_T08 0xfd469501 /Transformation Constant 8#define MD5_T09 0x698098d8 /Transformation Constant 9#define MD5_T10 0x8b44f7af /Transformation Constant 10#define MD5_T11 0xffff5bb1 /Transformation Constant 11#define MD5_T12 0x895cd7be /Transformation Constant 12#define MD5_T13 0x6b901122 /Transformation Constant 13#define MD5_T14 0xfd987193 /Transformation Constant 14#define MD5_T15 0xa679438e /Transformation Constant 15#define MD5_T16 0x49b40821 /Transformation Constant 16/Transformation Constants - Round 2#define MD5_T17 0xf61e2562 /Transformation Constant 17#define MD5_T18 0xc040b340 /Transformation Constant 18#define MD5_T19 0x265e5a51 /Transformation Constant 19#define MD5_T20 0xe9b6c7aa /Transformation Constant 20#define MD5_T21 0xd62f105d /Transformation Constant 21#define MD5_T22 0x02441453 /Transformation Constant 22#define MD5_T23 0xd8a1e681 /Transformation Constant 23#define MD5_T24 0xe7d3fbc8 /Transformation Constant 24#define MD5_T25 0x21e1cde6 /Transformation Constant 25#define MD5_T26 0xc33707d6 /Transformation Constant 26#define MD5_T27 0xf4d50d87 /Transformation Constant 27#define MD5_T28 0x455a14ed /Transformation Constant 28#define MD5_T29 0xa9e3e905 /Transformation Constant 29#define MD5_T30 0xfcefa3f8 /Transformation Constant 30#define MD5_T31 0x676f02d9 /Transformation Constant 31#define MD5_T32 0x8d2a4c8a /Transformation Constant 32/Transformation Constants - Round 3#define MD5_T33 0xfffa3942 /Transformation Constant 33#define MD5_T34 0x8771f681 /Transformation Constant 34#define MD5_T35 0x6d9d6122 /Transformation Constant 35#define MD5_T36 0xfde5380c /Transformation Constant 36#define MD5_T37 0xa4beea44 /Transformation Constant 37#define MD5_T38 0x4bdecfa9 /Transformation Constant 38#define MD5_T39 0xf6bb4b60 /Transformation Constant 39#define MD5_T40 0xbebfbc70 /Transformation Constant 40#define MD5_T41 0x289b7ec6 /Transformation Constant 41#define MD5_T42 0xeaa127fa /Transformation Constant 42#define MD5_T43 0xd4ef3085 /Transformation Constant 43#define MD5_T44 0x04881d05 /Transformation Constant 44#define MD5_T45 0xd9d4d039 /Transformation Constant 45#define MD5_T46 0xe6db99e5 /Transformation Constant 46#define MD5_T47 0x1fa27cf8 /Transformation Constant 47#define MD5_T48 0xc4ac5665 /Transformation Constant 48/Transformation Constants - Round 4#define MD5_T49 0xf4292244 /Transformation Constant 49#define MD5_T50 0x432aff97 /Transformation Constant 50#define MD5_T51 0xab9423a7 /Transformation Constant 51#define MD5_T52 0xfc93a039 /Transformation Constant 52#define MD5_T53 0x655b59c3 /Transformation Constant 53#define MD5_T54 0x8f0ccc92 /Transformation Constant 54#define MD5_T55 0xffeff47d /Transformation Constant 55#define MD5_T56 0x85845dd1 /Transformation Constant 56#define MD5_T57 0x6fa87e4f /Transformation Constant 57#define MD5_T58 0xfe2ce6e0 /Transformation Constant 58#define MD5_T59 0xa3014314 /Transformation Constant 59#define MD5_T60 0x4e0811a1 /Transformation Constant 60#define MD5_T61 0xf7537e82 /Transformation Constant 61#define MD5_T62 0xbd3af235 /Transformation Constant 62#define MD5_T63 0x2ad7d2bb /Transformation Constant 63#define MD5_T64 0xeb86d391 /Transformation Constant 64/Null data (except for first BYTE) used to finalise the checksum calculationstatic unsigned char PADDING64 = 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;(2)、CountChecksum.h（md5校验和类的头文件）class CMD5Checksum public:/interface functions for the RSA MD5 calculationstatic CString GetMD5(BYTE* pBuf, UINT nLength);static CString GetMD5(CFile& File);static CString GetMD5(const CString& strFilePath);protected:/constructor/destructorCMD5Checksum();virtual CMD5Checksum() ;/RSA MD5 implementationvoid Transform(BYTE Block64);void Update(BYTE* Input, ULONG nInputLen);CString Final();inline DWORD RotateLeft(DWORD x, int n);inline void FF( DWORD& A, DWORD B, DWORD C, DWORD D, DWORD X, DWORD S, DWORD T);inline void GG( DWORD& A, DWORD B, DWORD C, DWORD D, DWORD X, DWORD S, DWORD T);inline void HH( DWORD& A, DWORD B, DWORD C, DWORD D, DWORD X, DWORD S, DWORD T);inline void II( DWORD& A, DWORD B, DWORD C, DWORD D, DWORD X, DWORD S, DWORD T);/utility functionsvoid DWordToByte(BYTE* Output, DWORD* Input, UINT nLength);void ByteToDWord(DWORD* Output, BYTE* Input, UINT nLength);private:BYTE m_lpszBuffer64; /input bufferULONG m_nCount2; /number of bits, modulo 264 (lsb first)ULONG m_lMD54; /MD5 checksum;#endif / !defined(AFX_MD5CHECKSUM_H_2BC7928E_4C15_11D3_B2EE_A4A60E20D2C3_INCLUDED_)(3)、CountChecksum.cpp （md5校验和类的实现文件）/*FUNCTION: CMD5Checksum:GetMD5DETAILS: static, publicDESCRIPTION: Gets the MD5 checksum for a specified fileRETURNS: CString : the hexadecimal MD5 checksum for the specified fileARGUMENTS: CString& strFilePath : the full pathname of the specified fileNOTES: Provides an interface to the CMD5Checksum class. strFilePath name should hold the full pathname of the file, eg C:My DocumentsArcticle.txt. NB. If any problems occur with opening or reading this file, a CFileException will be thrown; callers of this function should be ready to catch this exception.*/CString CMD5Checksum:GetMD5(const CString& strFilePath)/open the file as a binary file in readonly mode, denying write access CFile File(strFilePath, CFile:shareDenyNone);/the file has been successfully opened, so now get and return its checksumreturn GetMD5(File);/*FUNCTION: CMD5Checksum:GetMD5DETAILS: static, publicDESCRIPTION: Gets the MD5 checksum for a specified fileRETURNS: CString : the hexadecimal MD5 checksum for the specified fileARGUMENTS: CFile& File : the specified fileNOTES: Provides an interface to the CMD5Checksum class. File should be open in binary readonly mode before calling this function. NB. Callers of this function should be ready to catch any CFileException thrown by the CFile functions*/CString CMD5Checksum:GetMD5(CFile& File)try CMD5Checksum MD5Checksum; /checksum object int nLength = 0; /number of bytes read from the file const int nBufferSize = 1024; /checksum the file in blocks of 1024 bytes BYTE BuffernBufferSize; /buffer for data read from the file /checksum the file in blocks of 1024 bytes while (nLength = File.Read( Buffer, nBufferSize ) 0 ) MD5Checksum.Update( Buffer, nLength ); /finalise the checksum and return it return MD5Checksum.Final();/report any file exceptions in debug mode onlycatch (CFileException* e ) TRACE0(CMD5Checksum:GetMD5: CFileException caught); throw e;/*FUNCTION: CMD5Checksum:GetMD5DETAILS: static, publicDESCRIPTION: Gets the MD5 checksum for data in a BYTE arrayRETURNS: CString : the hexadecimal MD5 checksum for the specified dataARGUMENTS: BYTE* pBuf : pointer to the BYTE array UINT nLength : number of BYTEs of data to be checksumedNOTES: Provides an interface to the CMD5Checksum class. Any data that can be cast to a BYTE array of known length can be checksummed by this function. Typically, CString and char arrays will be checksumed, although this function can be used to check the integrity of any BYTE array. A buffer of zero length can be checksummed; all buffers of zero length will return the same checksum. */CString CMD5Checksum:GetMD5(BYTE* pBuf, UINT nLength)/entry invariantsAfxIsValidAddress(pBuf,nLength,FALSE);/calculate and return the checksumCMD5Checksum MD5Checksum;MD5Checksum.Update( pBuf, nLength );return MD5Checksum.Final();/*FUNCTION: CMD5Checksum:RotateLeftDETAILS: privateDESCRIPTION: Rotates the bits in a 32 bit DWORD left by a specified amountRETURNS: The rotated DWORD ARGUMENTS: DWORD x : the value to be rotated int n : the number of bits to rotate by*/DWORD CMD5Checksum:RotateLeft(DWORD x, int n)/check that DWORD is 4 bytes long - true in Visual C+ 6 and 32 bit WindowsASSERT( sizeof(x) = 4 );/rotate and return xreturn (x (32-n);/*FUNCTION: CMD5Checksum:FFDETAILS: protectedDESCRIPTION: Implementation of basic MD5 transformation algorithmRETURNS: noneARGUMENTS: DWORD &A, B, C, D : Current (partial) checksum DWORD X : Input data DWORD S : MD5_SXX Transformation constant DWORD T : MD5_TXX Transformation constantNOTES: None*/void CMD5Checksum:FF( DWORD& A, DWORD B, DWORD C, DWORD D, DWORD X, DWORD S, DWORD T)DWORD F = (B & C) | (B & D);A += F + X + T;A = RotateLeft(A, S);A += B;/*FUNCTION: CMD5Checksum:GGDETAILS: protectedDESCRIPTION: Implementation of basic MD5 transformation algorithmRETURNS: noneARGUMENTS: DWORD &A, B, C, D : Current (partial) checksum DWORD X : Input data DWORD S : MD5_SXX Transformation constant DWORD T : MD5_TXX Transformation constantNOTES: None*/void CMD5Checksum:GG( DWORD& A, DWORD B, DWORD C, DWORD D, DWORD X, DWORD S, DWORD T)DWORD G = (B & D) | (C & D);A += G + X + T;A = RotateLeft(A, S);A += B;/*FUNCTION: CMD5Checksum:HHDETAILS: protectedDESCRIPTION: Implementation of basic MD5 transformation algorithmRETURNS: noneARGUMENTS: DWORD &A, B, C, D : Current (partial) checksum DWORD X : Input data DWORD S : MD5_SXX Transformation constant DWORD T : MD5_TXX Transformation constantNOTES: None*/void CMD5Checksum:HH( DWORD& A, DWORD B, DWORD C, DWORD D, DWORD X, DWORD S, DWORD T)DWORD H = (B C D);A += H + X + T;A = RotateLeft(A, S);A += B;/*FUNCTION: CMD5Checksum:IIDETAILS: protectedDESCRIPTION: Implementation of basic MD5 transformation algorithmRETURNS: noneARGUMENTS: DWORD &A, B, C, D : Current (partial) checksum DWORD X : Input data DWORD S : MD5_SXX Transformation constant DWORD T : MD5_TXX Transformation constantNOTES: None*/void CMD5Checksum:II( DWORD& A, DWORD B, DWORD C, DWORD D, DWORD X, DWORD S, DWORD T)DWORD I = (C (B | D);A += I + X + T;A = RotateLeft(A, S);A += B;/*FUNCTION: CMD5Checksum:ByteToDWordDETAILS: privateDESCRIPTION: Transfers the data in an 8 bit array to a 32 bit arrayRETURNS: voidARGUMENTS: DWORD* Output : the 32 bit (unsigned long) destination array BYTE* Input : the 8 bit (unsigned char) source array UINT nLength : the number of 8 bit data items in the source arrayNOTES: Four BYTES from the input array are transferred to each DWORD entry of the output array. The first BYTE is transferred to the bits (0-7) of the output DWORD, the second BYTE to bits 8-15 etc. The algorithm assumes that the input array is a multiple of 4 bytes long so that there is a perfect fit into the array of 32 bit words.*/void CMD5Checksum:ByteToDWord(DWORD* Output, BYTE* Input, UINT nLength)/entry invariantsASSERT( nLength % 4 = 0 );ASSERT( AfxIsValidAddress(Output, nLength/4, TRUE) );ASSERT( AfxIsValidAddress(Input, nLength, FALSE) );/initialisationsUINT i=0; /index to Output arrayUINT j=0; /index to Input array/transfer the data by shifting and copyingfor ( ; j nLength; i+, j += 4) Outputi = (ULONG)Inputj | (ULONG)Inputj+1 8 | (ULONG)Inputj+2 16 | (ULONG)Inputj+3 24;/*FUNCTION: CMD5Checksum:TransformDETAILS: protectedDESCRIPTION: MD5 basic transformation algorithm; transforms m_lMD5RETURNS: voidARGUMENTS: BYTE Block64NOTES: An MD5 checksum is calculated by four rounds of Transformation. The MD5 checksum currently held in m_lMD5 is merged by the transformation process with data passed in Block. */void CMD5Checksum:Transform(BYTE Block64)/initialise local data with current checksumULONG a = m_lMD50;ULONG b = m_lMD51;ULONG c = m_lMD52;ULONG d = m_lMD53;/copy BYTES from input Block to an array of ULONGS XULONG X16;ByteToDWord( X, Block, 64 );/Perform Round 1 of the transformationFF (a, b, c, d, X 0, MD5_S11, MD5_T01); FF (d, a, b, c, X 1, MD5_S12, MD5_T02); FF (c, d, a, b, X 2, MD5_S13, MD5_T03); FF (b, c, d, a, X 3, MD5_S14, MD5_T04); FF (a, b, c, d, X 4, MD5_S11, MD5_T05); FF (d, a, b, c, X 5, MD5_S12, MD5_T06); FF (c, d, a, b, X 6, MD5_S13, MD5_T07); FF (b, c, d, a, X 7, MD5_S14, MD5_T08); FF (a, b, c, d, X 8, MD5_S11, MD5_T09); FF (d, a, b, c, X 9, MD5_S12, MD5_T10); FF (c, d, a, b, X10, MD5_S13, MD5_T11); FF (b, c, d, a, X11, MD5_S14, MD5_T12); FF (a, b, c, d, X12, MD5_S11, MD5_T13); FF (d, a, b, c, X13, MD5_S12, MD5_T14); FF (c, d, a, b, X14, MD5_S13, MD5_T15); FF (b, c, d, a, X15, MD5_S14, MD5_T16);/Perform R