MD4 算法代码实现

大家好，欢迎来到IT知识分享网。

介绍

MD4是一种信息摘要算法，由麻省理工学院教Ronald Rivest于1990年开发完成，算法根据输入的数值计算128位的摘要信息，用于检测信息的完整性。该算法影响了后来其他的密码算法的设计,如MD5、sha-1和RIPEMD算法。

安全性

1991年，Den Boer和Bosselaers发表论文揭示了MD4算法的脆弱性。1995年， Hans Dobbertin第一次利用算法的漏洞全方位攻击该算法，仅仅在几秒钟内该便被激活成功教程。2004年，该算法再次遭遇挑战，研究人员发现一种有效的攻击该算法的方式，包括其后的MD4/MD5/SHA-1/RIPEMD 家族的摘要算法均存在此漏洞。现在，正向计算hash值和反向推断原值的耗时几乎相同，因此在2011年，RFC6150中阐明该算法已经被淘汰。（From Wikipedia）

代码实现（openssl源码修改）

MD4.h 头文件中定义了计算hash值所需的结构体Md4，代码实现如下：

#define min(a,b) (((a) < (b)) ? (a) : (b)) /**************/ /* Global Struct Define Section /**************/ enum {  MD4_BLOCK_SIZE = 64,  MD4_DIGEST_SIZE = 16,  MD4_PAD_SIZE = 56 }; typedef struct Md4 {  unsigned int buffLen; /* in bytes */  unsigned int loLen; /* length in bytes */  unsigned int hiLen; /* length in bytes */  unsigned int digest[MD4_DIGEST_SIZE / sizeof(unsigned int)];  unsigned int buffer[MD4_BLOCK_SIZE / sizeof(unsigned int)]; } Md4;

 void main() { unsigned char buffer[] = "abcdefghijklmnopqrstuvwxyz"; unsigned char md4Code[MD4_DIGEST_SIZE ] = { 
     0}; Md4 *md4 = 0; md4 = (struct Md4*)malloc(sizeof(struct Md4)); memset(md4, 0, sizeof(md4)); initMd4(md4); md4Update(md4, buffer, strlen(buffer)); md4Final(md4, md4Code); free(md4); } void initMd4(Md4* md4) { md4->digest[0] = 0xL; md4->digest[1] = 0xefcdab89L; md4->digest[2] = 0x98badcfeL; md4->digest[3] = 0xL; md4->buffLen = 0; md4->loLen = 0; md4->hiLen = 0; } static void AddLength(Md4* md4, unsigned int len) { unsigned int tmp = md4->loLen; if ((md4->loLen += len) < tmp) md4->hiLen++; /* carry low to high */ } static unsigned int rotlFixed(unsigned int x, unsigned int y) { return y ? _lrotl(x, y) : x; } static void Transform(Md4* md4) { #define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z)))) #define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z))) #define H(x, y, z) ((x) ^ (y) ^ (z)) /* Copy context->state[] to working vars */ unsigned int A = md4->digest[0]; unsigned int B = md4->digest[1]; unsigned int C = md4->digest[2]; unsigned int D = md4->digest[3]; #define function(a,b,c,d,k,s) a=rotlFixed(a+F(b,c,d)+md4->buffer[k],s); function(A, B, C, D, 0, 3); function(D, A, B, C, 1, 7); function(C, D, A, B, 2, 11); function(B, C, D, A, 3, 19); function(A, B, C, D, 4, 3); function(D, A, B, C, 5, 7); function(C, D, A, B, 6, 11); function(B, C, D, A, 7, 19); function(A, B, C, D, 8, 3); function(D, A, B, C, 9, 7); function(C, D, A, B, 10, 11); function(B, C, D, A, 11, 19); function(A, B, C, D, 12, 3); function(D, A, B, C, 13, 7); function(C, D, A, B, 14, 11); function(B, C, D, A, 15, 19); #undef function  #define function(a,b,c,d,k,s) \ a=rotlFixed(a+G(b,c,d)+md4->buffer[k]+0x5a,s); function(A, B, C, D, 0, 3); function(D, A, B, C, 4, 5); function(C, D, A, B, 8, 9); function(B, C, D, A, 12, 13); function(A, B, C, D, 1, 3); function(D, A, B, C, 5, 5); function(C, D, A, B, 9, 9); function(B, C, D, A, 13, 13); function(A, B, C, D, 2, 3); function(D, A, B, C, 6, 5); function(C, D, A, B, 10, 9); function(B, C, D, A, 14, 13); function(A, B, C, D, 3, 3); function(D, A, B, C, 7, 5); function(C, D, A, B, 11, 9); function(B, C, D, A, 15, 13); #undef function  #define function(a,b,c,d,k,s) \ a=rotlFixed(a+H(b,c,d)+md4->buffer[k]+0x6ed9eba1,s); function(A, B, C, D, 0, 3); function(D, A, B, C, 8, 9); function(C, D, A, B, 4, 11); function(B, C, D, A, 12, 15); function(A, B, C, D, 2, 3); function(D, A, B, C, 10, 9); function(C, D, A, B, 6, 11); function(B, C, D, A, 14, 15); function(A, B, C, D, 1, 3); function(D, A, B, C, 9, 9); function(C, D, A, B, 5, 11); function(B, C, D, A, 13, 15); function(A, B, C, D, 3, 3); function(D, A, B, C, 11, 9); function(C, D, A, B, 7, 11); function(B, C, D, A, 15, 15); /* Add the working vars back into digest state[] */ md4->digest[0] += A; md4->digest[1] += B; md4->digest[2] += C; md4->digest[3] += D; } void md4Update(Md4* md4, const unsigned char* data, unsigned int len) { /* do block size increments */ unsigned char* local = (unsigned char*)md4->buffer; while (len) { unsigned int add = min(len, MD4_BLOCK_SIZE - md4->buffLen); memcpy(&local[md4->buffLen], data, add); md4->buffLen += add; data += add; len -= add; if (md4->buffLen == MD4_BLOCK_SIZE) { Transform(md4); AddLength(md4, MD4_BLOCK_SIZE); md4->buffLen = 0; } } } void md4Final(Md4* md4, unsigned char* hash) { unsigned char* local = (unsigned char*)md4->buffer; AddLength(md4, md4->buffLen); /* before adding pads */ local[md4->buffLen++] = 0x80; /* add 1 */ /* pad with zeros */ if (md4->buffLen > MD4_PAD_SIZE) { memset(&local[md4->buffLen], 0, MD4_BLOCK_SIZE - md4->buffLen); md4->buffLen += MD4_BLOCK_SIZE - md4->buffLen; Transform(md4); md4->buffLen = 0; } memset(&local[md4->buffLen], 0, MD4_PAD_SIZE - md4->buffLen); /* put lengths in bits */ md4->hiLen = (md4->loLen >> (8 * sizeof(md4->loLen) - 3)) + (md4->hiLen << 3); md4->loLen = md4->loLen << 3; /* ! length ordering dependent on digest endian type ! */ memcpy(&local[MD4_PAD_SIZE], &md4->loLen, sizeof(unsigned int)); memcpy(&local[MD4_PAD_SIZE + sizeof(unsigned int)], &md4->hiLen, sizeof(unsigned int)); Transform(md4); memcpy(hash, md4->digest, MD4_DIGEST_SIZE); initMd4(md4); /* reset state */ }