-
-
[原创]MD5算法详解
-
发表于: 2021-3-25 00:09 12394
-
概要
MD5全称Message-Digest-Algrithm5（信息摘要算法），作用是让大容量信息在数字签名软件签署私人密匙前被“压缩”成一种保密的格式（就是将一个任意长度的字节串变换成一定长的大整数）。
算法讲解
MD5是以512位（64个字节或者是16个DWORD类型）为单位进行分组来处理输入的信息，且每一组分组又被划分为16个32位子分组，经过一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。
1 信息填充
首先需要对信息进行填充，使其字节长度模512位字节等于448。
填充方法：先附上位1在消息后面，然后用0进行填充，至少填充1位，至多填充512位。（原消息长度记为msg_len，须填充长度byte_len，单位字节）
接着在后面附上64位的原消息长度msg_len（注意是直接将64数进行位复制）。如果填充前消息的长度大于2^64，则只使用其低64位，这时填充完后消息长度刚好是512的整数倍。（填充后长度app_len = msg_len + byte_len + 64/8 ）
2 初始化4个变量
A = 0x67452301 B=0xEFCDAB89
C = 0x98BADCFE D=0x76543210
在内存中存储形式如下：01 23 45 67 89 AB CD EF FE DC BA 98 76 54 32 10
3 数据处理
首先定义4个辅助函数，每个都是以DWORD作为输入，输出一个32位双字。
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 );
}假设Mj表示消息的第j个子分组（从0到15）
FF(a, b, c, d, Mj, s, ti)表示 a = b + ((a + (F(b, c, d) + Mj + ti) << s
GG(a, b, c, d, Mj, s, ti)表示 a = b + ((a + (G(b, c, d) + Mj + ti) << s
HH(a, b, c, d, Mj, s, ti)表示 a = b + ((a + (H(b, c, d) + Mj + ti) << s
II(a, b, c, d, Mj, s, ti)表示 a = b + ((a + (I(b, c, d) + Mj + ti) << s
这四轮（64步）是：
//一轮： FF(a, b, c, d, M0, 7, 0xd76aa478) FF(d, a, b, c, M1, 12, 0xe8c7b756) FF(c, d, a, b, M2, 17, 0x242070db) 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, 22, 0x895cd7be) FF(a, b, c, d, M12, 7, 0x6b901122) FF(d, a, b, c, M13, 12, 0xfd987193) FF(c, d, a, b, M14, 17, 0xa679438e) FF(b, c, d, a, M15, 22, 0x49b40821) // 第二轮 GG(a, b, c, d, M1, 5, 0xf61e2562) GG(d, a, b, c, M6, 9, 0xc040b340) GG(c, d, a, b, M11, 14, 0x265e5a51) GG(b, c, d, a, M0, 20, 0xe9b6c7aa) GG(a, b, c, d, M5, 5, 0xd62f105d) GG(d, a, b, c, M10, 9, 0x02441453) GG(c, d, a, b, M15, 14, 0xd8a1e681) GG(b, c, d, a, M4, 20, 0xe7d3fbc8) GG(a, b, c, d, M9, 5, 0x21e1cde6) GG(d, a, b, c, M14, 9, 0xc33707d6) GG(c, d, a, b, M3, 14, 0xf4d50d87) GG(b, c, d, a, M8, 20, 0x455a14ed) GG(a, b, c, d, M13, 5, 0xa9e3e905) GG(d, a, b, c, M2, 9, 0xfcefa3f8) GG(c, d, a, b, M7, 14, 0x676f02d9) GG(b, c, d, a, M12, 20, 0x8d2a4c8a) //第三轮 HH(a, b, c, d, M5, 4, 0xfffa3942) HH(d, a, b, c, M8, 11, 0x8771f681) HH(c, d, a, b, M11, 16, 0x6d9d6122) HH(b, c, d, a, M14, 23, 0xfde5380c) HH(a, b, c, d, M1, 4, 0xa4beea44) HH(d, a, b, c, M4, 11, 0x4bdecfa9) HH(c, d, a, b, M7, 16, 0xf6bb4b60) HH(b, c, d, a, M10, 23, 0xbebfbc70) HH(a, b, c, d, M13, 4, 0x289b7ec6) HH(d, a, b, c, M0, 11, 0xeaa127fa) HH(c, d, a, b, M3, 16, 0xd4ef3085) HH(b, c, d, a, M6, 23, 0x04881d05) HH(a, b, c, d, M9, 4, 0xd9d4d039) HH(d, a, b, c, M12, 11, 0xe6db99e5) HH(c, d, a, b, M15, 16, 0x1fa27cf8) HH(b, c, d, a, M2, 23, 0xc4ac5665) //第四轮 II(a, b, c, d, M0, 6, 0xf4292244) II(d, a, b, c, M7, 10, 0x432aff97) II(c, d, a, b, M14, 15, 0xab9423a7) II(b, c, d, a, M5, 21, 0xfc93a039) II(a, b, c, d, M12, 6, 0x655b59c3) II(d, a, b, c, M3, 10, 0x8f0ccc92) II(c, d, a, b, M10, 15, 0xffeff47d) II(b, c, d, a, M1, 21, 0x85845dd1) II(a, b, c, d, M8, 6, 0x6fa87e4f) II(d, a, b, c, M15, 10, 0xfe2ce6e0) II(c, d, a, b, M6, 15, 0xa3014314) II(b, c, d, a, M13, 21, 0x4e0811a1) II(a, b, c, d, M4, 6, 0xf7537e82) II(d, a, b, c, M11, 10, 0xbd3af235) II(c, d, a, b, M2, 15, 0x2ad7d2bb) II(b, c, d, a, M9, 21, 0xeb86d391)
常数ti可以如下选择：
在第i步中，ti是4294967296*abs(sin(i))的整数部分，i的单位是弧度。(4294967296等于2的32次方)，i是64次循环中的第几步（从1算起）。
= (UINT32)floor( (1ULL << 32) * fabs(sin( roundIdx * 16 + i + 1 ))
这里需要细讲一下，每轮：
要点一：
初始化：a=A,b=B,c=C,d=D
首先是a、b、c、d的变化规律，这里是类似一个循环链表，开头每次后移一位。
要点二：
M[j]的j是这次计算取512位消息中的一块，这也是有规律的:
const UINT32 X[4][2] = {{0, 1}, {1, 5}, {5, 3}, {0, 7}};每轮开始初始为：
wIdx = X[roundIdx] [0]; //roundIdx表示轮数
接着：
wIdx = ( wIdx + X[ roundIdx ][ 1 ] ) & 0xF; //注意消息块一共16块
要点三：
w的值不是固定的，它是根据一个数组
const UINT32 S[4][4] = { { 7, 12, 17, 22 },
{ 5, 9, 14, 20 },
{ 4, 11, 16, 23 },
{ 6, 10, 15, 21 }};和轮数及次数确定的= S[ roundIdx ][ i % 4 ] 。//i是次数，roundIdx是轮数
取到的值是每次循环左移的值。
要点四：
Ti是2^32 * fabs（sin（roundIdx * 16 + i + 1）) 的整数部分。
要点五：
每轮计算后，需要将计算后的a、b、c、d加上还没开始该轮计算前的a、b、c、d。然后以新的a、b、c、d进行新的一轮计算。
要点六：
最后输出的是A、B、C、D的级联:从A的低字节开始，直到D的高字节。
具体代码如下：
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
#define SINGLE_ONE_BIT 0x80 //相当于10000000b
#define BLOCK_SIZE 512
#define MOD_SIZE 448
#define APP_SIZE 64
#define BITS 8
// MD5 Chaining Variable
#define A 0x67452301UL //相当于字符串0123456789ABCDEFEDCBA9876543210
#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;
// g_X表示块的数索引，左边代码初始值，游标代表增加值，由于块数为16，故需要取mod
const UINT32 g_X[4][2] = {{0, 1}, {1, 5}, {5, 3}, {0, 7}};
// MD5变换的常数(左移位数)
const UINT32 g_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 );
}
// X循环左移s位
UINT32 rotate_left( UINT32 x, UINT32 s )
{
return ( x << s ) | ( x >> ( 32 - s ) );
}
// Pre-processin 预处理
// 计算需要填充0部分的字节长度
UINT32 count_padding_bits ( UINT32 length ) //需填充字节数
{
UINT32 mod = length * BITS % BLOCK_SIZE; //模
//需要填充的位数
UINT32 c_bits = ( MOD_SIZE + BLOCK_SIZE - mod ) % BLOCK_SIZE;
return c_bits / BITS;
}
//补充消息字符串
STRING append_padding_bits ( char * msg )
{
UINT32 msg_length = strlen ( msg );
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);
memcpy(string.message, msg, msg_length); // Save message
// Pad out to mod 64. 填充bit_length字节个0
memset (string.message + msg_length, 0, bit_length );
string.message [msg_length] = SINGLE_ONE_BIT;
// Append length (before padding).填充原字符串长度64位
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 chain[4]; //中间结果
UINT32 state[4];
// state[0] - a
// state[1] - b
// state[2] - c
// state[3] - d
UINT8 result[16]; //结果放置
UINT32 ( *auxi[ 4 ])( UINT32, UINT32, UINT32 ) = { F, G, H, I }; //函数指针数组
if ( argc != 2 )
{
fprintf ( stderr, "usage: %s <src string>\n", argv[ 0 ] );
return EXIT_FAILURE;
}
string = append_padding_bits (argv[1]);
// MD5 initialization.MD5初始化
chain[0] = A;
chain[1] = B;
chain[2] = C;
chain[3] = D;
UINT32 block[16];
int wIdx;
for (UINT64 j = 0; j < string.length; j += BLOCK_SIZE / BITS) //主循环(每512位来一次)
{
// 取其中一块
memmove ( (char *)block, string.message + j, BLOCK_SIZE / BITS );
memmove ( state, chain, sizeof(chain) );
// 4 * 16循环
for (int roundIdx = 0; roundIdx < 4; roundIdx++ )
{
wIdx = g_X[ roundIdx ][ 0 ];
int sIdx = 0;
for (int 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.
//a = b + ( a + auxi[i](b ,c , d) + mj + ti) <<< w
state[sIdx] = state [ (sIdx + 1) % 4 ] +
rotate_left ( state[sIdx] +
(*auxi[roundIdx])
( state[(sIdx+1) % 4], state[(sIdx+2) % 4], state[(sIdx+3) % 4]) +
block[ wIdx ] + // 块内容
(UINT32)floor( (1ULL << 32) * fabs(sin( roundIdx * 16 + i + 1 )) ), // 常数
g_S[ roundIdx ][ i % 4 ]);// w
sIdx = ( sIdx + 3 ) % 4;
wIdx = ( wIdx + g_X[ roundIdx ][ 1 ] ) & 0xF;
}
}
chain[0] += state[0];
chain[1] += state[1];
chain[2] += state[2];
chain[3] += state[3];
}
// 保存最终结果到result
memmove ( result + 0, (char *)&chain[0], sizeof(UINT32) );
memmove ( result + 4, (char *)&chain[1], sizeof(UINT32) );
memmove ( result + 8, (char *)&chain[2], sizeof(UINT32) );
memmove ( result + 12, (char *)&chain[3], sizeof(UINT32) );
for (int i = 0; i < 16; i++ )
printf ( "%02x", result[i] );
putchar ( '\n' );
return EXIT_SUCCESS;
}[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
最后于 2021-3-25 00:14
被10ngvv编辑
，原因：
赞赏
|
|
|---|---|
|
|
赞赏
雪币:
留言:
