md5算法:MD5算法实现注意方法

前记:
　　最近很有危机感发现自己相对别人毫无优势虽然在班里成绩还算拔尖但最近想静下来认认真真做个小东西出来却发现自己虽然感觉什么都知道些但却什么都做不出来！
　　盗版李宗盛最近比较烦句歌词“最近比较烦比较烦比较烦我看那前方怎麽也看不到岸；那个后面还有班天才追赶哎呦写段皆大欢喜是越来越难”...打击太大了
　　这种时候最不能混乱了我要安安稳稳、认认真真、集中精力只去做件事
　　就先编个ＭＤ５算法吧很早就看它不爽了但直狠不下心来自己写个
　　所谓祸不单行困难就好像约好了样本来件简单事情居然让我折腾到半夜特来记下中间坎坷

正文:
　　早在高中时候做过段时间工具黑客每每入侵个论坛(比如动网)获得管理员密码后都要拿工具暴力破解ＭＤ５密码打那会儿开始就没对它有好感
　　现在学过Ｃ语言了终于能自己来写个“乱 7 8糟”了回忆起当年雄心壮志就开始自己动手来实现md5加密算法！

　　第步当然是先到Google上搜索相关资料咯先饿补下md5知识
　　我这次鬼使神差地进入了www.google.cn而不是以往www.google.com英文版也因此埋下了祸根呀！
　　用关键词“md5”直接搜索看到百度百科链接心想自己如何糊涂了这么出名算法百科里定有呀
　　打开链接简单地浏览了前面历史背景介绍什么进入了主题“算法描述”
　　看完的后我感觉我这次又要黄了根据它描述我实在无法实现这个算法有太多地方描述不清楚了！
　　我步步写完后本打算自己把所有可能情况都试试看希望找到正确结果但很快发现这不可能
　　所幸百科里留下个链接:http://www.ietf.org/rfc/rfc1321.txt)这是份最权威文档由Ronald L. Rivest在1992年8月向IETF提交
　　我对照英文原文看发现中文版里不仅有很多没描述清楚甚至还有很多！

　　下面我按照算法实现步骤把需要注意地方列举下具体实现可以参考英文原文:
、首先是要对信息进行填充
　　1.在原来信息基础上在后面进行填充使其字节长度除64余56即64*N+56形式
　　2.用于填充位是:第位为1其他都为0
　　3.填充必须进行！也就是说即使原始信息长度余数本来就是56那也得再填充64字节信息
　　4.最后8字节长度空间来保存原始信息长度
　　　　1)单位是bit即位这点我查可很多中文资料都没有介绍说明所有开始我直在琢磨长度单位是bit还是
　　　　2)最后8位内存存储形式是低到高这点也没有介绍说明开始我也直在想这8位到底是如何用？内存是从低到高而我们平时写数字比如0x1234是从高到低最后我查看Linux下开源md5sum才知道是把8位作为个整数从低到高存储所有在实现时候我直接用了long long来存储然后用memmove来追加到信息串里
　　5.填充完后整个信息串就是(N+1)*64个字节有关N百度百科里说N是个正整数也就是说填充完信息最短是128字节；但实际上N是个非负整数！也就是说N可以为0而信息长度最短是64字节这个让我郁闷很久

2、 4个常量值
　　百度百科里原文:“MD5中有 4个32位被称作链接变量(Chaining Variable)整数参数他们分别为: A=0x01234567B=0x89abcdefC=0xfedcba98D=0x76543210”
　　这又是个地方英文原文中说这个 4个常量值从低到高依次是:

word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10
　　上面说过内存存储方向和我们平时书写是相反所以定义时候应该是:

# A 0x67452301UL
# B 0xEFCDAB89UL
# C 0x98BADCFEUL
# D 0x10325476UL
　　这开始也让我郁闷

3、 4轮加密
　　1. 4个非线性没有问题:

# F( X, Y, Z ) ( ( (X) & (Y) ) | ( (~(X)) & (Z) ) )
# G( X, Y, Z ) ( ( (X) & (Z) ) | ( (Y) & (~(Z)) ) )
# H( X, Y, Z ) ( (X) ^ (Y) ^ (Z) )
# I( X, Y, Z ) ( (Y) ^ ( (X) | (~(Z)) ) )
　　2.但是 4轮加密就有问题我看过几篇区别md5算法文章不知道是不是显示问题表达式连括号都不匹配！所以想不用想那些表达式没有参考价值！最后看md5sum源代码才知道具体实现思路方法:

# FF( a, b, c, d, Mj, s, ti ) \
(a = b + LOGIC_SHIFT_LEFT( ( a + F( b, c, d ) + Mj + ti ), s ))
# GG( a, b, c, d, Mj, s, ti ) \
(a = b + LOGIC_SHIFT_LEFT( ( a + G( b, c, d ) + Mj + ti ), s ))
# HH( a, b, c, d, Mj, s, ti ) \
(a = b + LOGIC_SHIFT_LEFT( ( a + H( b, c, d ) + Mj + ti ), s ))
# II( a, b, c, d, Mj, s, ti ) \
(a = b + LOGIC_SHIFT_LEFT( ( a + I( b, c, d ) + Mj + ti ), s ))
4、最后输出
　　1.几乎所有文章都是写道 4轮加密就结束了而我算法实现到这里产生最终 4个数值:a, b, c ,d这 4个数都是32位整数于是我就直接用prf ( "%08x%08x%08x%08x\n", a, b, c, d );
　　结果却如何都不能正确！但按文档上算法介绍说明没有呀无奈还得参看md5sum代码单步跟踪下去发现算法完全正确！在看他输出原来是先把结果在转入个长度为16char里再逐个输出！又是数值存储高低顺序问题！改完就通过了！

下面附上我代码在fc6+gcc下通过其实代码还能再精简下晚了先睡觉！

/*
* md5 -- compute and check MD5 message digest.
*
* MD5 (Message-Digest algorithm 5) is a widely used, partially


* insecure cryptographic hash function with a 128-bit hash value.
*
* Author: [email protected]
* Date: Aug 28, 2008
* Version: 0.1.5
*/

# <stdlib.h>
# <.h>
# <stdio.h>
# <math.h>



# SINGLE_ONE_BIT 0x80
# BLOCK_SIZE 512
# MOD_SIZE 448
# APP_SIZE 64
# BITS 8



// MD5 Chaining Variable
# A 0x67452301UL
# B 0xEFCDAB89UL
# C 0x98BADCFEUL
# D 0x10325476UL



// Four auxiliary functions
# F( X, Y, Z ) ( ( (X) & (Y) ) | ( (~(X)) & (Z) ) )
# G( X, Y, Z ) ( ( (X) & (Z) ) | ( (Y) & (~(Z)) ) )
# H( X, Y, Z ) ( (X) ^ (Y) ^ (Z) )
# I( X, Y, Z ) ( (Y) ^ ( (X) | (~(Z)) ) )



// common function
# LOGIC_SHIFT_LEFT( x, c ) ( ((x) << (c)) | ((x) >> (32 - c)) )

# FF( a, b, c, d, Mj, s, ti ) \
(a = b + LOGIC_SHIFT_LEFT( ( a + F( b, c, d ) + Mj + ti ), s ))
# GG( a, b, c, d, Mj, s, ti ) \
(a = b + LOGIC_SHIFT_LEFT( ( a + G( b, c, d ) + Mj + ti ), s ))
# HH( a, b, c, d, Mj, s, ti ) \
(a = b + LOGIC_SHIFT_LEFT( ( a + H( b, c, d ) + Mj + ti ), s ))
# II( a, b, c, d, Mj, s, ti ) \
(a = b + LOGIC_SHIFT_LEFT( ( a + I( b, c, d ) + Mj + ti ), s ))



// Creating own types
#def UINT64
# undef UINT64
#end

#def UINT32
# undef UINT32
#end



typedef unsigned long long UINT64;
typedef unsigned long UINT32;
typedef struct
{
char * message;
UINT64 length;
}STRING;



// Pre-processin
UINT32 count_padding_bits ( UINT32 length )
{
UINT32 div = length * BITS / BLOCK_SIZE;
UINT32 mod = length * BITS % BLOCK_SIZE;
UINT32 c_bits;



( mod 0 )
c_bits = BLOCK_SIZE;

c_bits = ( MOD_SIZE + BLOCK_SIZE - mod ) % BLOCK_SIZE;



c_bits / BITS;
}



STRING append_padding_bits ( char * argv )
{
UINT32 msg_length = strlen ( argv );
UINT32 bit_length = count_padding_bits ( msg_length );
UINT64 app_length = msg_length * BITS;
STRING ;



.message = (char *)malloc(msg_length + bit_length + APP_SIZE / BITS);


strncpy ( .message, argv, msg_length );
mem ( .message + msg_length, 0, bit_length );
memmove ( .message + msg_length + bit_length, (char *)&app_length, ( UINT64 ) );
.message [ msg_length ] = SINGLE_ONE_BIT;



.length = msg_length + bit_length + ( UINT64 );

;
}



( argc, char *argv )
{
STRING ;
UINT32 w[16];
UINT32 h0, a;
UINT32 h1, b;
UINT32 h2, c;
UINT32 h3, d;
unsigned char r[16];
i;
j;
l;



( argc < 2 )
{
fprf ( stderr, "usage: %s ...\n", argv[ 0 ] );
EXIT_FAILURE;
}



for ( l = 1; l < argc; l )
{
= append_padding_bits ( argv[ l ] );



h0 = A;
h1 = B;
h2 = C;
h3 = D;



for ( j = 0; j < .length; j BLOCK_SIZE / BITS)
{
memmove ( (char *)w, .message + j, BLOCK_SIZE / BITS );



a = h0;
b = h1;
c = h2;
d = h3;



// Round 1
FF( a, b, c, d, w[0], 7, 0xd76aa478);
FF( d, a, b, c, w[1], 12, 0xe8c7b756);
FF( c, d, a, b, w[2], 17, 0x242070db);
FF( b, c, d, a, w[3], 22, 0xc1bdceee);
FF( a, b, c, d, w[4], 7, 0xf57c0faf);
FF( d, a, b, c, w[5], 12, 0x4787c62a);
FF( c, d, a, b, w[6], 17, 0xa8304613);
FF( b, c, d, a, w[7], 22, 0xfd469501);
FF( a, b, c, d, w[8], 7, 0x698098d8);
FF( d, a, b, c, w[9], 12, 0x8b44f7af);
FF( c, d, a, b, w[10], 17, 0xffff5bb1);
FF( b, c, d, a, w[11], 22, 0x895cd7be);
FF( a, b, c, d, w[12], 7, 0x6b901122);
FF( d, a, b, c, w[13], 12, 0xfd987193);
FF( c, d, a, b, w[14], 17, 0xa679438e);
FF( b, c, d, a, w[15], 22, 0x49b40821);



// Round 2
GG( a, b, c, d, w[1], 5, 0xf61e2562 );
GG( d, a, b, c, w[6], 9, 0xc040b340 );
GG( c, d, a, b, w[11], 14, 0x265e5a51 );
GG( b, c, d, a, w[0], 20, 0xe9b6c7aa );
GG( a, b, c, d, w[5], 5, 0xd62f105d );
GG( d, a, b, c, w[10], 9, 0x02441453 );
GG( c, d, a, b, w[15], 14, 0xd8a1e681 );
GG( b, c, d, a, w[4], 20, 0xe7d3fbc8 );
GG( a, b, c, d, w[9], 5, 0x21e1cde6 );
GG( d, a, b, c, w[14], 9, 0xc33707d6 );
GG( c, d, a, b, w[3], 14, 0xf4d50d87 );


GG( b, c, d, a, w[8], 20, 0x455a14ed );
GG( a, b, c, d, w[13], 5, 0xa9e3e905 );
GG( d, a, b, c, w[2], 9, 0xfcefa3f8 );
GG( c, d, a, b, w[7], 14, 0x676f02d9 );
GG( b, c, d, a, w[12], 20, 0x8d2a4c8a );



// Round 3
HH( a, b, c, d, w[5], 4, 0xfffa3942 );
HH( d, a, b, c, w[8], 11, 0x8771f681 );
HH( c, d, a, b, w[11], 16, 0x6d9d6122 );
HH( b, c, d, a, w[14], 23, 0xfde5380c );
HH( a, b, c, d, w[1], 4, 0xa4beea44 );
HH( d, a, b, c, w[4], 11, 0x4bdecfa9 );
HH( c, d, a, b, w[7], 16, 0xf6bb4b60 );
HH( b, c, d, a, w[10], 23, 0xbebfbc70 );
HH( a, b, c, d, w[13], 4, 0x289b7ec6 );
HH( d, a, b, c, w[0], 11, 0xeaa127fa );
HH( c, d, a, b, w[3], 16, 0xd4ef3085 );
HH( b, c, d, a, w[6], 23, 0x04881d05 );
HH( a, b, c, d, w[9], 4, 0xd9d4d039 );
HH( d, a, b, c, w[12], 11, 0xe6db99e5 );
HH( c, d, a, b, w[15], 16, 0x1fa27cf8 );
HH( b, c, d, a, w[2], 23, 0xc4ac5665 );



// Round 4
II( a, b, c, d, w[0], 6, 0xf4292244 );
II( d, a, b, c, w[7], 10, 0x432aff97 );
II( c, d, a, b, w[14], 15, 0xab9423a7 );
II( b, c, d, a, w[5], 21, 0xfc93a039 );
II( a, b, c, d, w[12], 6, 0x655b59c3 );
II( d, a, b, c, w[3], 10, 0x8f0ccc92 );
II( c, d, a, b, w[10], 15, 0xffeff47d );
II( b, c, d, a, w[1], 21, 0x85845dd1 );
II( a, b, c, d, w[8], 6, 0x6fa87e4f );
II( d, a, b, c, w[15], 10, 0xfe2ce6e0 );
II( c, d, a, b, w[6], 15, 0xa3014314 );
II( b, c, d, a, w[13], 21, 0x4e0811a1 );
II( a, b, c, d, w[4], 6, 0xf7537e82 );
II( d, a, b, c, w[11], 10, 0xbd3af235 );
II( c, d, a, b, w[2], 15, 0x2ad7d2bb );
II( b, c, d, a, w[9], 21, 0xeb86d391 );



h0 a;
h1 b;
h2 c;
h3 d;
}



memmove ( r + 0, (char *)&h0, (h0) );
memmove ( r + 4, (char *)&h1, (h1) );
memmove ( r + 8, (char *)&h2, (h2) );
memmove ( r + 12, (char *)&h3, (h3) );


for ( i = 0; i < 16; i )
prf ( "%02x", r[i] );
putchar ( '\n' );
// prf ( "%08x%08x%08x%08x\n", h0, h1, h2, h3 );
}



EXIT_SUCCESS;
}

延伸阅读

• 2010-11-24-- 加密算法,谈谈数据加密的处理--提供各种算法处理
• 2010-12-9-- md5加密,java 易懂易用的MD5加密（可直接运行）（2）
• 2010-12-9-- md5加密,asp MD5加密方式使用建议
• 2011-4-8-- md5加密,如何使用RFC1321中MD5加密
• 2010-12-9-- md5加密,java易懂易用的MD5加密（可直接运行） （1）
• 2009-9-12-- md5数据库:使用MD5加密数据库中的用户密码
• 2009-9-12-- md5算法:MD5官方算法
• 2009-9-12-- md5算法:MD5算法汇编代码[着重优化]
• 2009-9-12-- md5加密:获取任意用户MD5加密信息的测试程序
• 2009-9-2-- 加密算法:QQ2004 sp1加密文件结构和加密算法分析