訊息摘要演算法MD5圖解及C語言實現
前言
最近看了很多關於訊息摘要演算法這方面的資料，既有CSDN上面各路大神寫的文章，也有這些演算法的標準文件。有的講的比較囉嗦，有的給出來的程式碼是直接調庫的。我想寫一篇文章，幫助自己理清思路，
利用圖解簡明扼要地說清目前最流行的MD5演算法的原理。
MD5演算法概述
MD5資訊摘要演算法（MD5 Message-Digest Algorithm）是一種被廣泛使用的密碼雜湊函式，由MD4改進而來。點我看MD4演算法原理。
MD5本質上是一個雜湊函式。但是MD5具有雪崩效應（Avalanche Effect）、抗碰撞性等的性質。為了保證這些性質，MD5的演算法設計比較複雜。下面就來說明MD5演算法的原理。
MD5演算法的處理步驟可以概括為三步：資料填充、分組迴圈變換、拼接輸出。
資料填充
MD5演算法的第二步“分組迴圈變換”是
以512位為一個分組進行處理
的。因此，需要把資料填充成長度為512位的倍數。具體填充步驟如下：
1、先填充一個“1”，後面加上k個“0”。其中k是滿足（n+1+k） mod 512 = 448的最小正整數。
2、追加64位的資料長度（bit為單位，
小端序
存放）
填充完的資料大概長這樣：
分組迴圈變換
先
初始化A、B、C、D四個32位常數
，然後
將填充完成後的資料劃分成一個個512位的分組，依次進入迴圈變換。
A、B、C、D也參與到迴圈變換中。資料分組進去變換的時候，大概走這麼個流程：
分組迴圈變換示意圖
迴圈變換是整個MD5演算法最核心，也是最複雜的部分。一個512位分組的資料被進一步劃分為16個32位的子分組，對每個子分組進行下圖所示的變換：
一個子分組進行的變換
上面只是畫出了一個子分組進行的變換。下面對圖中的元素進行說明：
圖中的F函式代表一次
由位運算構成的非線性變換
，每一輪迴圈變換用到的F函式不一樣。
加號表示加法運算。
常數AC的值在每一次變換中
都不一樣
，表示式為
，i表示第i次變換。
左移位數S有規律地
週期性變化
。
資料的16個子分組都參與到上圖所示的變換，順序不定。當16個子分組處理完成時，我們就說完成了一輪迴圈變換。
MD5的一個數據分組一共需要進行四輪的迴圈變換。
將四輪迴圈變換後得到的A、B、C、D的值
分別和原來的值相加
，就是A、B、C、D進行迴圈變換後的結果。
拼接輸出
這裡用一句話概括：將經過若干次迴圈變換後的A、B、C、D
以十六進位制的形式拼接起來
，就是傳說中的MD5碼了。
C語言實現
以下程式碼根據參考文獻修改、註釋而來，畢竟MD5演算法不是我原創的。
/*
函式使用說明：
先呼叫MD5Init初始化一個MD5_CTX型別結構體，再使用MD5Update計算MD5碼，最後呼叫MD5Final獲取
使用示例見最下面的main函式。
*/
#include
#include
typedef
unsigned
char
*
POINTER
；
//指標型別定義
typedef
struct
{
unsigned
int
state
［
4
］；
/* A，B，C，D四個常數 */
unsigned
int
count
［
2
］；
/* 資料的bit數計數器（對2^64取餘） */
unsigned
char
buffer
［
64
］；
/* 輸入資料緩衝區 */
}
MD5_CTX
；
//存放MD5演算法相關資訊的結構體定義
void
MD5Init
（
MD5_CTX
*
）；
void
MD5Update
（
MD5_CTX
*
，
unsigned
char
*
，
unsigned
int
）；
void
MD5Final
（
unsigned
char
［
16
］，
MD5_CTX
*
）；
void
MD5Transform
（
unsigned
int
［
4
］，
unsigned
char
［
64
］）；
void
Encode
（
unsigned
char
*
，
unsigned
int
*
，
unsigned
int
）；
void
Decode
（
unsigned
int
*
，
unsigned
char
*
，
unsigned
int
）；
//迴圈左移的位數
#define S11 7
#define S12 12
#define S13 17
#define S14 22
#define S21 5
#define S22 9
#define S23 14
#define S24 20
#define S31 4
#define S32 11
#define S33 16
#define S34 23
#define S41 6
#define S42 10
#define S43 15
#define S44 21
//資料填充的內容
unsigned
char
PADDING
［
64
］
=
{
0x80
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
，
0
}；
//F，G，H，I四個非線性變換函式
#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）））
//x迴圈左移n位的操作
#define ROTATE_LEFT（x， n） （（（x） << （n）） | （（x） >> （32-（n））））
//FF，GG，HH，II是四輪迴圈變換分別用到的變換函式
#define FF（a， b， c， d， x， s， ac） { \
（a） += F （（b）， （c）， （d）） + （x） + （unsigned int）（ac）； \
（a） = ROTATE_LEFT （（a）， （s））； \
（a） += （b）； \
}
#define GG（a， b， c， d， x， s， ac） { \
（a） += G （（b）， （c）， （d）） + （x） + （unsigned int）（ac）； \
（a） = ROTATE_LEFT （（a）， （s））； \
（a） += （b）； \
}
#define HH（a， b， c， d， x， s， ac） { \
（a） += H （（b）， （c）， （d）） + （x） + （unsigned int）（ac）； \
（a） = ROTATE_LEFT （（a）， （s））； \
（a） += （b）； \
}
#define II（a， b， c， d， x， s， ac） { \
（a） += I （（b）， （c）， （d）） + （x） + （unsigned int）（ac）； \
（a） = ROTATE_LEFT （（a）， （s））； \
（a） += （b）； \
}
//MD5演算法初始化操作
void
MD5Init
（
MD5_CTX
*
context
）
{
//bit計數器清零
context
->
count
［
0
］
=
context
->
count
［
1
］
=
0
；
//A，B，C，D被初始化為四個特定的常數（Magic Number）
context
->
state
［
0
］
=
0x67452301
；
context
->
state
［
1
］
=
0xefcdab89
；
context
->
state
［
2
］
=
0x98badcfe
；
context
->
state
［
3
］
=
0x10325476
；
}
//使用MD5演算法對input的資料進行處理
void
MD5Update
（
MD5_CTX
*
context
，
unsigned
char
*
input
，
unsigned
int
inputLen
）
{
unsigned
int
i
，
index
，
partLen
；
//計算［已處理資料長度（byte） mod 64］
index
=
（
unsigned
int
）（（
context
->
count
［
0
］
>>
3
）
&
0x3F
）；
//bit計數器累加
if
（（
context
->
count
［
0
］
+=
（（
unsigned
int
）
inputLen
<<
3
））
<
（（
unsigned
int
）
inputLen
<<
3
））
//處理加法進位溢位的情況
context
->
count
［
1
］
++
；
context
->
count
［
1
］
+=
（（
unsigned
int
）
inputLen
>>
29
）；
//計算緩衝區還有多少位元組空間
partLen
=
64
-
index
；
//以512位資料為一組進行處理
if
（
inputLen
>=
partLen
）
{
memcpy
（
&
context
->
buffer
［
index
］，
input
，
partLen
）；
MD5Transform
（
context
->
state
，
context
->
buffer
）；
for
（
i
=
partLen
；
i
+
63
<
inputLen
；
i
+=
64
）
MD5Transform
（
context
->
state
，
&
input
［
i
］）；
index
=
0
；
}
else
i
=
0
；
//快取未處理的輸入
memcpy
（
&
context
->
buffer
［
index
］，
&
input
［
i
］，
inputLen
-
i
）；
}
//獲取MD5碼（由digest返回），順便清除context資料
void
MD5Final
（
unsigned
char
digest
［
16
］，
MD5_CTX
*
context
）
{
unsigned
char
bits
［
8
］；
unsigned
int
index
，
padLen
；
//記錄資料長度
Encode
（
bits
，
context
->
count
，
8
）；
//填充資料
index
=
（
unsigned
int
）（（
context
->
count
［
0
］
>>
3
）
&
0x3f
）；
padLen
=
（
index
<
56
）
？
（
56
-
index
）
：
（
120
-
index
）；
MD5Update
（
context
，
PADDING
，
padLen
）；
//追加資料長度資訊
MD5Update
（
context
，
bits
，
8
）；
//獲取MD5碼。其實就是將ABCD四個32位整數以16進位制方式級聯
Encode
（
digest
，
context
->
state
，
16
）；
//清除資料
memset
（
context
，
0
，
sizeof
（
*
context
））；
}
//MD5變換函式
void
MD5Transform
（
unsigned
int
state
［
4
］，
unsigned
char
block
［
64
］）
{
unsigned
int
a
=
state
［
0
］，
b
=
state
［
1
］，
c
=
state
［
2
］，
d
=
state
［
3
］，
x
［
16
］；
//將64位元組的一組資料進一步劃分為16個子分組
Decode
（
x
，
block
，
64
）；
//第1輪迴圈變換
FF
（
a
，
b
，
c
，
d
，
x
［
0
］，
S11
，
0xd76aa478
）；
/* 1 */
FF
（
d
，
a
，
b
，
c
，
x
［
1
］，
S12
，
0xe8c7b756
）；
/* 2 */
FF
（
c
，
d
，
a
，
b
，
x
［
2
］，
S13
，
0x242070db
）；
/* 3 */
FF
（
b
，
c
，
d
，
a
，
x
［
3
］，
S14
，
0xc1bdceee
）；
/* 4 */
FF
（
a
，
b
，
c
，
d
，
x
［
4
］，
S11
，
0xf57c0faf
）；
/* 5 */
FF
（
d
，
a
，
b
，
c
，
x
［
5
］，
S12
，
0x4787c62a
）；
/* 6 */
FF
（
c
，
d
，
a
，
b
，
x
［
6
］，
S13
，
0xa8304613
）；
/* 7 */
FF
（
b
，
c
，
d
，
a
，
x
［
7
］，
S14
，
0xfd469501
）；
/* 8 */
FF
（
a
，
b
，
c
，
d
，
x
［
8
］，
S11
，
0x698098d8
）；
/* 9 */
FF
（
d
，
a
，
b
，
c
，
x
［
9
］，
S12
，
0x8b44f7af
）；
/* 10 */
FF
（
c
，
d
，
a
，
b
，
x
［
10
］，
S13
，
0xffff5bb1
）；
/* 11 */
FF
（
b
，
c
，
d
，
a
，
x
［
11
］，
S14
，
0x895cd7be
）；
/* 12 */
FF
（
a
，
b
，
c
，
d
，
x
［
12
］，
S11
，
0x6b901122
）；
/* 13 */
FF
（
d
，
a
，
b
，
c
，
x
［
13
］，
S12
，
0xfd987193
）；
/* 14 */
FF
（
c
，
d
，
a
，
b
，
x
［
14
］，
S13
，
0xa679438e
）；
/* 15 */
FF
（
b
，
c
，
d
，
a
，
x
［
15
］，
S14
，
0x49b40821
）；
/* 16 */
//第2輪迴圈變換
GG
（
a
，
b
，
c
，
d
，
x
［
1
］，
S21
，
0xf61e2562
）；
/* 17 */
GG
（
d
，
a
，
b
，
c
，
x
［
6
］，
S22
，
0xc040b340
）；
/* 18 */
GG
（
c
，
d
，
a
，
b
，
x
［
11
］，
S23
，
0x265e5a51
）；
/* 19 */
GG
（
b
，
c
，
d
，
a
，
x
［
0
］，
S24
，
0xe9b6c7aa
）；
/* 20 */
GG
（
a
，
b
，
c
，
d
，
x
［
5
］，
S21
，
0xd62f105d
）；
/* 21 */
GG
（
d
，
a
，
b
，
c
，
x
［
10
］，
S22
，
0x2441453
）；
/* 22 */
GG
（
c
，
d
，
a
，
b
，
x
［
15
］，
S23
，
0xd8a1e681
）；
/* 23 */
GG
（
b
，
c
，
d
，
a
，
x
［
4
］，
S24
，
0xe7d3fbc8
）；
/* 24 */
GG
（
a
，
b
，
c
，
d
，
x
［
9
］，
S21
，
0x21e1cde6
）；
/* 25 */
GG
（
d
，
a
，
b
，
c
，
x
［
14
］，
S22
，
0xc33707d6
）；
/* 26 */
GG
（
c
，
d
，
a
，
b
，
x
［
3
］，
S23
，
0xf4d50d87
）；
/* 27 */
GG
（
b
，
c
，
d
，
a
，
x
［
8
］，
S24
，
0x455a14ed
）；
/* 28 */
GG
（
a
，
b
，
c
，
d
，
x
［
13
］，
S21
，
0xa9e3e905
）；
/* 29 */
GG
（
d
，
a
，
b
，
c
，
x
［
2
］，
S22
，
0xfcefa3f8
）；
/* 30 */
GG
（
c
，
d
，
a
，
b
，
x
［
7
］，
S23
，
0x676f02d9
）；
/* 31 */
GG
（
b
，
c
，
d
，
a
，
x
［
12
］，
S24
，
0x8d2a4c8a
）；
/* 32 */
//第3輪迴圈變換
HH
（
a
，
b
，
c
，
d
，
x
［
5
］，
S31
，
0xfffa3942
）；
/* 33 */
HH
（
d
，
a
，
b
，
c
，
x
［
8
］，
S32
，
0x8771f681
）；
/* 34 */
HH
（
c
，
d
，
a
，
b
，
x
［
11
］，
S33
，
0x6d9d6122
）；
/* 35 */
HH
（
b
，
c
，
d
，
a
，
x
［
14
］，
S34
，
0xfde5380c
）；
/* 36 */
HH
（
a
，
b
，
c
，
d
，
x
［
1
］，
S31
，
0xa4beea44
）；
/* 37 */
HH
（
d
，
a
，
b
，
c
，
x
［
4
］，
S32
，
0x4bdecfa9
）；
/* 38 */
HH
（
c
，
d
，
a
，
b
，
x
［
7
］，
S33
，
0xf6bb4b60
）；
/* 39 */
HH
（
b
，
c
，
d
，
a
，
x
［
10
］，
S34
，
0xbebfbc70
）；
/* 40 */
HH
（
a
，
b
，
c
，
d
，
x
［
13
］，
S31
，
0x289b7ec6
）；
/* 41 */
HH
（
d
，
a
，
b
，
c
，
x
［
0
］，
S32
，
0xeaa127fa
）；
/* 42 */
HH
（
c
，
d
，
a
，
b
，
x
［
3
］，
S33
，
0xd4ef3085
）；
/* 43 */
HH
（
b
，
c
，
d
，
a
，
x
［
6
］，
S34
，
0x4881d05
）；
/* 44 */
HH
（
a
，
b
，
c
，
d
，
x
［
9
］，
S31
，
0xd9d4d039
）；
/* 45 */
HH
（
d
，
a
，
b
，
c
，
x
［
12
］，
S32
，
0xe6db99e5
）；
/* 46 */
HH
（
c
，
d
，
a
，
b
，
x
［
15
］，
S33
，
0x1fa27cf8
）；
/* 47 */
HH
（
b
，
c
，
d
，
a
，
x
［
2
］，
S34
，
0xc4ac5665
）；
/* 48 */
//第4輪迴圈變換
II
（
a
，
b
，
c
，
d
，
x
［
0
］，
S41
，
0xf4292244
）；
/* 49 */
II
（
d
，
a
，
b
，
c
，
x
［
7
］，
S42
，
0x432aff97
）；
/* 50 */
II
（
c
，
d
，
a
，
b
，
x
［
14
］，
S43
，
0xab9423a7
）；
/* 51 */
II
（
b
，
c
，
d
，
a
，
x
［
5
］，
S44
，
0xfc93a039
）；
/* 52 */
II
（
a
，
b
，
c
，
d
，
x
［
12
］，
S41
，
0x655b59c3
）；
/* 53 */
II
（
d
，
a
，
b
，
c
，
x
［
3
］，
S42
，
0x8f0ccc92
）；
/* 54 */
II
（
c
，
d
，
a
，
b
，
x
［
10
］，
S43
，
0xffeff47d
）；
/* 55 */
II
（
b
，
c
，
d
，
a
，
x
［
1
］，
S44
，
0x85845dd1
）；
/* 56 */
II
（
a
，
b
，
c
，
d
，
x
［
8
］，
S41
，
0x6fa87e4f
）；
/* 57 */
II
（
d
，
a
，
b
，
c
，
x
［
15
］，
S42
，
0xfe2ce6e0
）；
/* 58 */
II
（
c
，
d
，
a
，
b
，
x
［
6
］，
S43
，
0xa3014314
）；
/* 59 */
II
（
b
，
c
，
d
，
a
，
x
［
13
］，
S44
，
0x4e0811a1
）；
/* 60 */
II
（
a
，
b
，
c
，
d
，
x
［
4
］，
S41
，
0xf7537e82
）；
/* 61 */
II
（
d
，
a
，
b
，
c
，
x
［
11
］，
S42
，
0xbd3af235
）；
/* 62 */
II
（
c
，
d
，
a
，
b
，
x
［
2
］，
S43
，
0x2ad7d2bb
）；
/* 63 */
II
（
b
，
c
，
d
，
a
，
x
［
9
］，
S44
，
0xeb86d391
）；
/* 64 */
state
［
0
］
+=
a
；
state
［
1
］
+=
b
；
state
［
2
］
+=
c
；
state
［
3
］
+=
d
；
}
//將無符號整數轉為位元組型別陣列
void
Encode
（
unsigned
char
*
output
，
unsigned
int
*
input
，
unsigned
int
len
）
{
unsigned
int
i
，
j
；
for
（
i
=
0
，
j
=
0
；
j
<
len
；
i
++
，
j
+=
4
）
{
output
［
j
］
=
（
unsigned
char
）（
input
［
i
］
&
0xff
）；
output
［
j
+
1
］
=
（
unsigned
char
）（（
input
［
i
］
>>
8
）
&
0xff
）；
output
［
j
+
2
］
=
（
unsigned
char
）（（
input
［
i
］
>>
16
）
&
0xff
）；
output
［
j
+
3
］
=
（
unsigned
char
）（（
input
［
i
］
>>
24
）
&
0xff
）；
}
}
//將位元組型別陣列轉為無符號整數
void
Decode
（
unsigned
int
*
output
，
unsigned
char
*
input
，
unsigned
int
len
）
{
unsigned
int
i
，
j
；
for
（
i
=
0
，
j
=
0
；
j
<
len
；
i
++
，
j
+=
4
）
output
［
i
］
=
（（
unsigned
int
）
input
［
j
］）
|
（（（
unsigned
int
）
input
［
j
+
1
］）
<<
8
）
|
（（（
unsigned
int
）
input
［
j
+
2
］）
<<
16
）
|
（（（
unsigned
int
）
input
［
j
+
3
］）
<<
24
）；
}
int
main
（）
{
MD5_CTX
md5_calc
；
char
c
［］
=
“abc”
；
unsigned
char
md5
［
16
］；
//演示計算字串abc的MD5碼
MD5Init
（
&
md5_calc
）；
MD5Update
（
&
md5_calc
，（
unsigned
char
*
）
c
，
strlen
（
c
））；
MD5Final
（
md5
，
&
md5_calc
）；
//輸出MD5碼
printf
（
“字串abc的MD5碼為：”
）；
for
（
int
i
=
0
；
i
<
15
；
i
++
）
printf
（
“%02x”
，
md5
［
i
］）；
printf
（
“
\n
”
）；
return
0
；
}
參考文獻
［1］ Rivest， R。， “The MD5 Message Digest Algorithm”， RFC 1321， MIT and RSA Data Security， Inc。， April 1992。