MD5算法实现注意点
2011年03月02日
最近很有危机感,发现自己相对别人毫无优势。虽然在班里成绩还算拔尖,但最近想静下来认认真真做一个小东西出来,却发现自己虽然感觉什么都知道一些,但却什么都做不出来!盗版李宗盛《最近比较烦》的一句歌词“最近比较烦比较烦比较烦,我看那前方怎麽也看不到岸;那个后面还有一班天才追赶哎呦,写一段皆大欢喜的程序,是越来越难”...打击太大了。
这种时候最不能混乱了,我要安安稳稳、认认真真、集中精力只去做一件事。就先编个MD5算法吧,很早就看它不爽了,但一直狠不下心来自己写一个。
所谓祸不单行,困难就好像约好了一样,本来一件简单的事情居然让我折腾到半夜,特来记下中间的坎坷。
正文
早在高中的时候,做过一段时间工具黑客,每每入侵一个论坛(比如动网),获得管理员的密码后,都要拿工具暴力破解 md5 密码。打那会儿开始就没对它有好感。现在学过C语言了,终于能自己来写个“乱七八糟”的程序了,回想起当年的雄心壮志,就开始自己动手来实现md5加密算法!
第一步当然是先到 Google 上搜索相关资料咯。先饿补一下 md5 的知识。我这次鬼使神差地进入了 www.google.cn,而不是以往的 www.google.com 英文版。也因此埋下了祸根呀!用关键词“md5”直接搜索,看到百度百科的链接。心想自己怎么糊涂了,这么出名的算法,百科里一定有的呀。打开链接,简单地浏览了前面的历史背景介绍什么的,进入了主题“算法描述”。 看完之后,我感觉我这次又要黄了,根据它的描述,我实在无法实现这个算法,因为有太多地方描述不清楚了!我一步一步写完程序后,本打算自己把所有可能的情况都试试看,希望找到正确的结果。但很快发现这不可能。
所幸,百科里留下一个链接:http://www.ietf.org/rfc/rfc1321.txt),这是一份最权威的文档,由 Ronald L. Rivest 在1992年8月向 IETF 提交。我对照英文原文看,发现中文版里不仅有很多没描述清楚,甚至还有很多错误!下面我按照算法实现步骤,把需要注意的地方列举一下,具体实现可以参考英文原文:
一、首先是要对信息进行填充
在原来的信息基础上,在后面进行填充,使其字节长度除64余56。即64*N+56的形式。
用于填充的位是:第一位为1,其他都为0。
填充必须进行!也就是说,即使原始信息长度余数本来就是56,那也得再填充64字节的信息。
最后8字节长度的空间来保存原始信息的长度。
单位是bit,即位。这一点我查可很多中文资料,都没有说明,所有一开始我一直在琢磨长度单位是bit还是byte。
最后8位的内存存储形式是低到高。这一点也没有说明的,开始我也一直在想,这8位到底是怎么用的?因为内存是从低到高的,而我们平时写数字,比如0x1234是从高到低的。最后我查看Linux下开源的程序md5sum,才知道是把8位作为一个整数从低到高存储的,所有在实现的时候,我直接用了long long来存储,然后用memmove()来追加到信息串里。
填充完后,整个信息串就是(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 下通过。其实代码还能再精简一下的。晚了,先睡觉!
程序清单
view plaincopy to clipboardprint?
/*
* 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
#include
#include
#include
#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 > ( 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
#include
#include
#include
#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 > ( 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 );
putchar ( '\n' );
}
return EXIT_SUCCESS;
}
后记
源代码中有一处笔误,第 78 行:
原来的:
if ( mod == 0 )
c_bits = BLOCK_SIZE;
应该是:
if ( mod == 0 )
c_bits = MOD_SIZE;
否则,当传入数据的长度正好是512的整数倍时,就会出错。感想热心网友Ted Feng指正!
发表评论
-
CQ与其他聊天工具继承
2012-01-20 01:40 554CQ与其他聊天工具继承 2010年06月13日 VBSc ... -
隐藏命令行CMD框
2012-01-20 01:39 822隐藏命令行CMD框 2010年07月18日 vbs脚本: ... -
insert->Step Generator
2012-01-20 01:39 490insert->Step Generator 2010 ... -
[转]使用C#开发ActiveX控件全攻略
2012-01-20 01:39 762[转]使用C#开发ActiveX控 ... -
程式交易(一)大智慧函数(下)
2012-01-19 09:29 849程式交易(一)大智慧函数(下) 2011年07月24日 ... -
关于图像格式
2012-01-19 09:29 797关于图像格式 2010年06 ... -
.net如何上传图片,并生成缩略图效果
2012-01-19 09:29 748.net如何上传图片,并生成缩略图效果 2011年04月18 ... -
学Photoshop前的19句经典忠告
2012-01-19 09:29 857学Photoshop前的19句经典 ... -
安全bios手册(5)
2012-01-19 09:29 555安全bios手册(5) 2010年06月20日 ... -
指针与引用的一角
2012-01-17 02:04 723指针与引用的一角 2011 ... -
【转】Android 的cpu 硬盘 内存 网络设置 系统信息 硬件信息
2012-01-17 02:04 603【转】Android 的cpu 硬盘 ... -
C++Union结构体转换成C#代码
2012-01-17 02:04 1712C++Union结构体转换成C#代码 2010年10月27日 ... -
日语词汇
2012-01-15 21:25 395日语词汇 2010年11月24日 时间变化:推移:すいい ... -
1级能力考试知识汇总
2012-01-15 21:25 6091级能力考试知识汇总 2009年06月04日 人物题包括 ... -
小儿时,我这样被剃头
2012-01-15 21:25 332小儿时,我这样被剃头 2 ... -
化村姑为女郎
2012-01-15 21:25 528化村姑为女郎 2009年07 ...
相关推荐
MD5算法实现注意方法.TXT MD5算法实现注意方法.TXT MD5算法实现注意方法.TXT MD5算法实现注意方法.TXT
消息摘要算法第五版(英语:Message-Digest Algorithm 5,缩写为MD5),是当前计算机领域用于确保信息传输完整一致而广泛使用的散列算法之一(又译哈希算法、摘要算法等),主流编程语言普遍已有MD5的实现。...
运行注意事项:使用matlab2021a或者更高版本测试,运行里面的md5.m文件,不要直接运行子函数文件。运行时注意matlab左侧的当前文件夹窗口必须是当前工程所在路径。具体可观看提供的操作录像视频跟着操作。
介绍MD5加密算法基本情况MD5的全称是Message-Digest Algorithm 5,在90年代初由MIT的计算机科学实验室和RSA Data Security Inc发明,经MD2、MD3和MD4发展而来。 Message-Digest泛指字节串(Message)的Hash变换,就是...
注意:本算法在生成加密key时,使用了md5算法,编译本demo需要依赖 C++自行实现MD5算法 里面的算法。 #ifndef _AES_20140317_H_ #define _AES_20140317_H_ #define Bits128 16 #define Bits192 24 #define...
实现过程中需要注意事项:最后把四个变量A B C D 链接成结果时 ,注意变量高低位的先后顺序,具体参考 LinkResult()方法。 md5.h #ifndef _MD5_H_ #define _MD5_H_ #include #include using namespace std; ...
适合学习/练手、毕业设计、课程设计、期末/期中/大作业、工程实训、相关...# 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。
<br> MD5将任意长度的“字节串”变换成一个128bit的大整数,并且它是一个不可逆的字符串变换算法,换句话说就是,即使你看到源程序和算法描述,也无法将一个MD5的值变换回原始的字符串,从数学原理上说,是因为...
SparkMD5 是 MD5 算法的快速 md5 实现。 该脚本基于 JKM md5 库,这是算法。 这最适合浏览器使用,因为nodejs版本可能更快。 注意:请在执行测试时禁用 Firebug! Firebug 会消耗大量内存和 CPU,大大降低了测试...
<br> MD5将任意长度的“字节串”变换成一个128bit的大整数,并且它是一个不可逆的字符串变换算法,换句话说就是,即使你看到源程序和算法描述,也无法将一个MD5的值变换回原始的字符串,从数学原理上说,是因为...
使用 AES 加密算法时需要注意以下几点: 密钥长度:AES 支持不同的密钥长度,包括 128、192 和 256 位。通常情况下,密钥长度越长,加密强度越高,但同时也会增加加密和解密的时间和成本。在选择密钥长度时需要综合...
本文介绍一个C#函数,可以实现计算文件的MD5值,可以用于文件传输后进行有效性校验。 我们知道可以通过将一个字符串进行散列(Hash)运算得到一个32位字符串,将其作为密码来保存是最常见的MD5应用。不知道大家有...
MD5全称Message_Digest Algorithm-5,即信息-摘要算法5,消息摘要是采用任意大小的数据并输出固定长度散列值的安全单向散列函数(加密算法如SHA-1或SHA...,是计算机广泛使用的杂凑算法之一(又译摘要算法、哈希算法)...
基于YOLOV7实现人脸检测模型训练,优化在原有的yolo算法上加入CBAM注意力检测机制python源码+文档说明+ - 不懂运行,下载完可以私聊问,可远程教学 该资源内项目源码是个人的毕设,代码都测试ok,都是运行成功后才...
国际算法比较 国际加密算法:RSA、SHA/MD5、DES等常用算法,RSA是非对称算法(签名和验签),SHA/MD5为摘要算法(HASH值),DES为对称加密(数据加密)。 国密算法的SM2对应于RSA,SM2对应于SHA,SM3对应于DES。 非...
大厂前端面试算法|# 数据结构和算法 数据结构和算法,是大厂前端面试的“拦路虎”,很多同学都望而生畏。其实如果了解常用数据结构,掌握基本的算法思维,就不能应对。本章将通过多个面试题,为你讲解算法面试题的...
该算法基于模拟退火,使用为ATSP设计的特定邻域候选生成函数,能够在合理的时间内输出非常好的结果。 数据准备 有两种可接受的数据格式: TSPLIB 中的全距离矩阵 - 在此处查看有关 TSPLIB 的详细信息 请注意,只能...
Totres Jbook 留言本采用纯粹的jsp页面实现...注意:密码需要采用本系统中的MD5加密算法生成后再存入数据库,为保证安全,该算法经过简单改动,与公开的MD5算法有区别。 原创,欢迎交流。作者联系方式:QQ:68780221。
TextRank算法 配置方案 安装 进入含有setup.py文件的文件夹中,以此目录为当前路径进入终端输入下面命令行进行安装 $ sudo python setup.py install 注意: Python 3下需要将上面的python改成python3,pip改成pip3 ...