MD5算法实现注意点

前记

最近很有危机感，发现自己相对别人毫无优势。虽然在班里成绩还算拔尖，但最近想静下来认认真真做一个小东西出来，却发现自己虽然感觉什么都知道一些，但却什么都做不出来！盗版李宗盛《最近比较烦》的一句歌词“最近比较烦比较烦比较烦，我看那前方怎麽也看不到岸；那个后面还有一班天才追赶哎呦，写一段皆大欢喜的程序，是越来越难”...打击太大了。

这种时候最不能混乱了，我要安安稳稳、认认真真、集中精力只去做一件事。就先编个MD5算法吧，很早就看它不爽了，但一直狠不下心来自己写一个。

所谓祸不单行，困难就好像约好了一样，本来一件简单的事情居然让我折腾到半夜，特来记下中间的坎坷。

正文

早在高中的时候，做过一段时间工具黑客，每每入侵一个论坛（比如动网），获得管理员的密码后，都要拿工具暴力破解 md5 密码。打那会儿开始就没对它有好感。现在学过Ｃ语言了，终于能自己来写个“乱七八糟”的程序了，回想起当年的雄心壮志，就开始自己动手来实现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还是byte。
    2. 最后8位的内存存储形式是低到高。这一点也没有说明的，开始我也一直在想，这8位到底是怎么用的？因为内存是从低到高的，而我们平时写数字，比如0x1234是从高到低的。最后我查看Linux下开源的程序md5sum，才知道是把8位作为一个整数从低到高存储的，所有在实现的时候，我直接用了long long来存储，然后用memmove()来追加到信息串里。
  5. 填充完后，整个信息串就是(N+1)*64个字节，关于N，百度百科里说N是一个正整数，也就是说填充完的信息最短是128字节；但实际上N是一个非负整数！也就是说，N可以为0，而信息的长度最短是64字节。这个错误让我郁闷很久。

二、四个初始常量的值

百度百科里原文：“MD5中有四个32位被称作链接变量（Chaining Variable）的整数参数，他们分别为： A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210。”

这又是一个错误的地方，英文原文中说这个四个常量的值从低到高依次是：

word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10

上面说过内存存储方向和我们平时书写是相反的，所以定义的时候应该是：

#define A 0x67452301UL
#define B 0xEFCDAB89UL
#define C 0x98BADCFEUL
#define D 0x10325476UL

这一开始也让我郁闷。

三、四轮加密的函数

四个非线性函数没有问题：

#define F( X, Y, Z ) ( ( (X) & (Y) ) | ( (~(X)) & (Z) ) )
#define G( X, Y, Z ) ( ( (X) & (Z) ) | ( (Y) & (~(Z)) ) )
#define H( X, Y, Z ) ( (X) ^ (Y) ^ (Z) )
#define I( X, Y, Z ) ( (Y) ^ ( (X) | (~(Z)) ) )

但是四轮的加密函数就有问题，我看过几篇不同的md5算法文章，不知道是不是显示问题，函数表达式连括号都不匹配！所以想不用想，那些表达式没有参考价值！最后看 md5sum 的源代码才知道具体的实现方法：

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

四、最后的输出

几乎所有文章都是写道四轮加密就结束了。而我的算法实现到这里，产生的最终的四个数值：a, b, c ,d。这四个数都是32位的整数。于是我就直接用printf ( "%08x%08x%08x%08x/n", a, b, c, d ); 结果却怎么都不能正确！但按文档上的算法说明，没有错误呀。无奈还得参看 md5sum 的代码，单步跟踪下去，发现算法完全正确！再看他的输出函数，原来是先把结果在转入一个长度为16的 char 数组里，再逐个输出！又是数值存储的高低位顺序问题！改完就通过了！

下面附上我的代码，在 FC6 + GCC 下通过。其实代码还能再精简一下的。晚了，先睡觉！

程序清单

/*
* md5 -- compute and check MD5 message digest.
* this version only can calculate the char string.
*
* MD5 (Message-Digest algorithm 5) is a widely used, partially
* insecure cryptographic hash function with a 128-bit hash value.
*
* Author: redraiment@ZJGSU.edu.cn
* Date: Aug 27, 2008
* Version: 0.1.6
*/
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
#define SINGLE_ONE_BIT 0x80
#define BLOCK_SIZE 512
#define MOD_SIZE 448
#define APP_SIZE 64
#define BITS 8
// MD5 Chaining Variable
#define A 0x67452301UL
#define B 0xEFCDAB89UL
#define C 0x98BADCFEUL
#define D 0x10325476UL
// Creating own types
#ifdef UINT64
# undef UINT64
#endif
#ifdef UINT32
# undef UINT32
#endif
typedef unsigned long long UINT64;
typedef unsigned long UINT32;
typedef unsigned char UINT8;
typedef struct
{
char * message;
UINT64 length;
}STRING;
const UINT32 X[4][2] = {{0, 1}, {1, 5}, {5, 3}, {0, 7}};
// Constants for MD5 transform routine.
const UINT32 S[4][4] = {
{ 7, 12, 17, 22 },
{ 5, 9, 14, 20 },
{ 4, 11, 16, 23 },
{ 6, 10, 15, 21 }
};
// F, G, H and I are basic MD5 functions.
UINT32 F( UINT32 X, UINT32 Y, UINT32 Z )
{
return ( X & Y ) | ( ~X & Z );
}
UINT32 G( UINT32 X, UINT32 Y, UINT32 Z )
{
return ( X & Z ) | ( Y & ~Z );
}
UINT32 H( UINT32 X, UINT32 Y, UINT32 Z )
{
return X ^ Y ^ Z;
}
UINT32 I( UINT32 X, UINT32 Y, UINT32 Z )
{
return Y ^ ( X | ~Z );
}
// rotates x left s bits.
UINT32 rotate_left( UINT32 x, UINT32 s )
{
return ( x << s ) | ( x >> ( 32 - s ) );
}
// Pre-processin
UINT32 count_padding_bits ( UINT32 length )
{
UINT32 div = length * BITS / BLOCK_SIZE;
UINT32 mod = length * BITS % BLOCK_SIZE;
UINT32 c_bits;
if ( mod == 0 )
c_bits = MOD_SIZE; //BLOCK_SIZE;
else
c_bits = ( MOD_SIZE + BLOCK_SIZE - mod ) % BLOCK_SIZE;
return 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 string;
string.message = (char *)malloc(msg_length + bit_length + APP_SIZE / BITS);
// Save message
strncpy ( string.message, argv, msg_length );
// Pad out to mod 64.
memset ( string.message + msg_length, 0, bit_length );
string.message [ msg_length ] = SINGLE_ONE_BIT;
// Append length (before padding).
memmove ( string.message + msg_length + bit_length, (char *)&app_length, sizeof( UINT64 ) );
string.length = msg_length + bit_length + sizeof( UINT64 );
return string;
}
int main ( int argc, char *argv[] )
{
STRING string;
UINT32 w[16];
UINT32 chain[4];
UINT32 state[4];
UINT8 r[16];
UINT32 ( *auxi[ 4 ])( UINT32, UINT32, UINT32 ) = { F, G, H, I };
int roundIdx;
int argIdx;
int sIdx;
int wIdx;
int i;
int j;
if ( argc < 2 )
{
fprintf ( stderr, "usage: %s string .../n", argv[ 0 ] );
return EXIT_FAILURE;
}
for ( argIdx = 1; argIdx < argc; argIdx++ )
{
string = append_padding_bits ( argv[ argIdx ] );
// MD5 initialization.
chain[0] = A;
chain[1] = B;
chain[2] = C;
chain[3] = D;
for ( j = 0; j < string.length; j += BLOCK_SIZE / BITS)
{
memmove ( (char *)w, string.message + j, BLOCK_SIZE / BITS );
memmove ( state, chain, sizeof(chain) );
for ( roundIdx = 0; roundIdx < 4; roundIdx++ )
{
wIdx = X[ roundIdx ][ 0 ];
sIdx = 0;
for ( i = 0; i < 16; i++ )
{
// FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
// Rotation is separate from addition to prevent recomputation.
state[sIdx] = state [ (sIdx + 1) % 4 ] +
rotate_left ( state[sIdx] +
( *auxi[ roundIdx ] )
( state[(sIdx+1) % 4], state[(sIdx+2) % 4], state[(sIdx+3) % 4]) +
w[ wIdx ] +
(UINT32)floor( (1ULL << 32) * fabs(sin( roundIdx * 16 + i + 1 )) ),
S[ roundIdx ][ i % 4 ]);
sIdx = ( sIdx + 3 ) % 4;
wIdx = ( wIdx + X[ roundIdx ][ 1 ] ) & 0xF;
}
}
chain[ 0 ] += state[ 0 ];
chain[ 1 ] += state[ 1 ];
chain[ 2 ] += state[ 2 ];
chain[ 3 ] += state[ 3 ];
}
memmove ( r + 0, (char *)&chain[0], sizeof(UINT32) );
memmove ( r + 4, (char *)&chain[1], sizeof(UINT32) );
memmove ( r + 8, (char *)&chain[2], sizeof(UINT32) );
memmove ( r + 12, (char *)&chain[3], sizeof(UINT32) );
for ( i = 0; i < 16; i++ )
printf ( "%02x", r[i] );
putchar ( '/n' );
}
return EXIT_SUCCESS;
}

后记

源代码中有一处笔误，第 78 行：

原来的:
   if ( mod == 0 )
       c_bits = BLOCK_SIZE;
应该是:
   if ( mod == 0 )
       c_bits = MOD_SIZE;

否则，当传入数据的长度正好是512的整数倍时，就会出错。感想热心网友Ted Feng指正！

版权声明

本人的所有原创文章皆保留版权，请尊重原创作品。
转载必须包含本声明，保持本文完整，并以超链接形式注明原始作者“redraiment”和主站点上的本文原始地址。

联系方式

我的邮箱，欢迎来信（redraiment@gmail.com）
我的Blogger（子清行）
我的Google Sites（子清行）
我的CSDN博客（梦婷轩）
我的百度空间（梦婷轩）

时间： 2024-09-14 20:09:38

MD5算法实现注意点的相关文章

【VB】MD5算法

昨天才真正搞懂,ASP.NET和ASP是不同的!! google上搜了下,感觉这个介绍的挺好的: ASP.Net和ASP的最大区别在于编程思维的转换,而不仅仅在于功能的增强.ASP使用VBS/JS这样的脚本语言混合html来编程,而那些脚本语言属于弱类型.面向结构的编程语言,而非面向对象,这就明显产生以下几个问题: 1.代码逻辑混乱,难于管理:由于ASP是脚本语言混合html编程,所以你很难看清代码的逻辑关系,并且随着程序的复杂性增加,使得代码的管理十分困难,甚至超出一个程序员所能达到的管理能力

MD5算法研究

算法 综述 MD5的全称是Message-Digest Algorithm 5(信息-摘要算法),在90年代初由MIT Laboratory for Computer Science和RSA Data Security Inc的Ronald L. Rivest开发出来,经MD2.MD3和MD4发展而来.它的作用是让大容量信息在用数字签名软件签署私人密匙前被"压缩"成一种保密的格式(就是把一个任意长度的字节串变换成一定长的大整数).不管是MD2.MD4还是MD5,它们都需要获得一个随机长

MD5算法研究(1)

算法 综述 MD5的全称是Message-Digest Algorithm 5(信息-摘要算法),在90年代初由MIT Laboratory for Computer Science和RSA Data Security Inc的Ronald L. Rivest开发出来,经MD2.MD3和MD4发展而来.它的作用是让大容量信息在用数字签名软件签署私人密匙前被"压缩"成一种保密的格式(就是把一个任意长度的字节串变换成一定长的大整数).不管是MD2.MD4还是MD5,它们都需要获得一个随机长

java MD5算法返回数字型字串

算法   常有人问及MD5算法为何有些程序片断返回完全数字型结果而有些返回数字与字母的混合字串. 其实两种返回结果只是因为加密结果的不同显示形式,Blog中已经有.Net的实现,在此附加JAVA实现,供参考. JAVA的标准类库理论上功能也很强大,但由于虚拟机/运行时的实现太多,加之版本差异,有些代码在不同环境下运行会出现奇怪的异常结果,尤其以涉及字符集的操作为甚. package com.bee.framework.common; import java.security.MessageDig

MD5算法研究(2)

算法 FF(b,c,d,a,M3,22,0xc1bdceee) FF(a,b,c,d,M4,7,0xf57c0faf) FF(d,a,b,c,M5,12,0x4787c62a) FF(c,d,a,b,M6,17,0xa8304613) FF(b,c,d,a,M7,22,0xfd469501) FF(a,b,c,d,M8,7,0x698098d8) FF(d,a,b,c,M9,12,0x8b44f7af) FF(c,d,a,b,M10,17,0xffff5bb1) FF(b,c,d,a,M11,2

MD5算法说明(转)

算法 MD5算法说明 1.MD5算法是对输入的数据进行补位,使得如果数据位长度LEN对512求余的结果是448.  即数据扩展至K*512+448位.即K*64+56个字节,K为整数.  具体补位操作:补一个1,然后补0至满足上述要求 2.补数据长度:  用一个64位的数字表示数据的原始长度B,把B用两个32位数表示.这时,数据就被填  补成长度为512位的倍数. 3. 初始化MD5参数   四个32位整数 (A,B,C,D) 用来计算信息摘要,初始化使用的是十六进制表示的数字       A=

MD5算法之C#程序 MD5算法描述

程序|算法 当我要写一个MD5算法的程序时,发现中英文的语言描述都有一些不确切的地方,某些个细节讲得不清楚,或者说很费解.最后不得不拿出C语言的源程序来调试,这对于理解算法是很不利的.于是就总结了一下我摸索到的一些要点. 1.来历MD5的全称是message-digest algorithm 5(信息-摘要算法,在90年代初由mit laboratory for computer science和rsa data security inc的ronald l. rivest开发出来,经md2.md

MD5算法描述的C#描述程序

MD5算法描述 当我要写一个MD5算法的程序时,发现中英文的语言描述都有一些不确切的地方,某些个细节讲得不清楚,或者说很费解.最后不得不拿出C语言的源程序来调试,这对于理解算法是很不利的.于是就总结了一下我摸索到的一些要点. 1.来历 MD5的全称是message-digest algorithm 5(信息-摘要算法,在90年代初由mit laboratory for computer science和rsa data security inc的ronald l. rivest开发出来,经md2

由汇编内核的MD5算法编写谈代码优化

开始我们做个实验,先打开两个文档附带的程序,一个工程是MD5C,一个工程是MD5ASM,其中MD5C是从VCKBASE下载的md5算法的标准C语言原代码,MD5ASM是我修改后的md5算法原代码.我给这两个工程的main函数里面都添加了一段回朔代码,用来产生0-99999999的数字,然后用这两个工程里面的可执行文件去对每个数字md5加密.好了,经过一段时间的等待后,就可以看到类似的结果了: MD5ASM工程在我的机器上的结果是181秒,MD5C在我的机器上产生的结果是999秒,呵呵,数字有点怪

用Swift实现MD5算法&amp;amp;引入第三方类库（MBProgressHUD）

之前项目里面是用objc写的MD5加密算法,最近在用swift重写以前的项目,遇到了这个问题.好在最后解决了.顺带解决掉的还有如何引入第三方的类库,例如MBProgressHUD(SVProgressHUD)等一些特别好的控件 解决的方法其实是用objc和swift混合编程的方法,利用Bridging-header文件. 什么是Briding-header?你可以简单的理解为在一个用swift语言开发的工程中,引入objective-c文件是需要做的一个串联文件,好比架设了一个桥,让swift中