一、MD5算法
1、簡介
不管是MD2、MD4還是MD5，它們都需要獲得一個隨機長度的信息並產生一個128位的信息摘要。雖然這些算法的結構或多或少有些相似，但MD2的設計與MD4和MD5完全不同，那是因為MD2是為8位機器做過設計最佳化的，而MD4和MD5卻是面向32位的電腦。這三個算法的描述和C語言原始碼在Internet RFCs 1321中有詳細的描述（見擴展閱讀）。Van Oorschot和Wiener曾經考慮過一個在散列中暴力搜尋衝突的函式（Brute-Force Hash Function），而且他們猜測一個被設計專門用來搜尋MD5衝突的機器（這台機器在1994年的製造成本大約是一百萬美元）可以平均每24天就找到一個衝突。但單從1991年到2001年這10年間，竟沒有出現替代MD5算法的md6或被叫做其他什麼名字的新算法這一點，我們就可以看出這個瑕疵並沒有太多的影響MD5的安全性。上面所有這些都不足以成為MD5的在實際套用中的問題。並且，由於MD5算法的使用不需要支付任何著作權費用的，所以在一般的情況下（非絕密套用領域。但即便是套用在絕密領域內，MD5也不失為一種非常優秀的中間技術），MD5怎么都應該算得上是非常安全的了。
2、算法的套用
MD5的典型套用是對一段信息（Message）產生信息摘要（Message-Digest），以防止被篡改。比如，在UNIX下有很多軟體在下載的時候都有一個檔案名稱相同，檔案擴展名為.md5的檔案，在這個檔案中通常只有一行文本，大致結構如：MD5 (tanajiya.tar.gz) = 0ca175b9c0f726a831d895e269332461
這就是tanajiya.tar.gz檔案的數字簽名。MD5將整個檔案當作一個大文本信息，通過其不可逆的字元串變換算法，產生了這個唯一的MD5信息摘要。如果在以後傳播這個檔案的過程中，無論檔案的內容發生了任何形式的改變（包括人為修改或者下載過程中線路不穩定引起的傳輸錯誤等），只要你對這個檔案重新計算MD5時就會發現信息摘要不相同，由此可以確定你得到的只是一個不正確的檔案。如果再有一個第三方的認證機構，用MD5還可以防止檔案作者的"抵賴"，這就是所謂的數字簽名套用。
3、MD5還廣泛用於加密和解密技術上
比如在UNIX系統中用戶的密碼就是以MD5（或其它類似的算法）經加密後存儲在檔案系統中。當用戶登錄的時候，系統把用戶輸入的密碼計算成MD5值，然後再去和保存在檔案系統中的MD5值進行比較，進而確定輸入的密碼是否正確。通過這樣的步驟，系統在並不知道用戶密碼的明碼的情況下就可以確定用戶登錄系統的合法性。這不但可以避免用戶的密碼被具有系統管理員許可權的用戶知道，而且還在一定程度上增加了密碼被破解的難度。正是因為這個原因，現在被黑客使用最多的一種破譯密碼的方法就是一種被稱為"跑字典"的方法。有兩種方法得到字典，一種是日常蒐集的用做密碼的字元串表，另一種是用排列組合方法生成的，先用MD5程式計算出這些字典項的MD5值，然後再用目標的MD5值在這個字典中檢索。我們假設密碼的最大長度為8位位元組（8 Bytes），同時密碼只能是字母和數字，共26+26+10=62個字元，排列組合出的字典的項數則是P(62,1)+P(62,2)….+P(62,8)，那也已經是一個很天文的數字了，存儲這個字典就需要TB級的磁碟陣列，而且這種方法還有一個前提，就是能獲得目標賬戶的密碼MD5值的情況下才可以。這種加密技術被廣泛的套用於UNIX系統中，這也是為什麼UNIX系統比一般作業系統更為堅固一個重要原因。
二、算法描述
1、簡介
對MD5算法簡要的敘述可以為：MD5以512位分組來處理輸入的信息，且每一分組又被劃分為16個32位子分組，經過了一系列的處理後，算法的輸出由四個32位分組組成，將這四個32位分組級聯後將生成一個128位散列值。在MD5算法中，首先需要對信息進行填充，使其位長度對512求余的結果等於448。因此，信息的位長度（Bits Length）將被擴展至N*512+448，即N*64+56個位元組（Bytes），N為一個非負整數。填充的方法如下，在信息的後面填充一個1和無數個0，直到滿足上面的條件時才停止用0對信息的填充。然後，再在這個結果後面附加一個以64位二進制表示的填充前信息長度。經過這兩步的處理，現在的信息位元組長度=N*512+448+64=(N+1)*512，即長度恰好是512的整數倍。這樣做的原因是為滿足後面處理中對信息長度的要求。
MD5中有四個32位被稱作連結變數（Chaining Variable）的整數參數，他們分別為：A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210。
當設定好這四個連結變數後，就開始進入算法的四輪循環運算。循環的次數是信息中512位信息分組的數目。
將上面四個連結變數複製到另外四個變數中：A到a，B到b，C到c，D到d。
主循環有四輪（MD4隻有三輪），每輪循環都很相似。第一輪進行16次操作。每次操作對a、b、c和d中的其中三個作一次非線性函式運算，然後將所得結果加上第四個變數，文本的一個子分組和一個常數。再將所得結果向右環移一個不定的數，並加上a、b、c或d中之一。最後用該結果取代a、b、c或d中之一。
以一下是每次操作中用到的四個非線性函式（每輪一個）。
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))
（&是與，|是或，~是非，^是異或）
這四個函式的說明：如果X、Y和Z的對應位是獨立和均勻的，那么結果的每一位也應是獨立和均勻的。F是一個逐位運算的函式。即，如果X，那么Y，否則Z。函式H是逐位奇偶操作符。
假設Mj表示訊息的第j個子分組（從0到15），
（x）<< （n）表示把x循環左移n位
FF(a,b,c,d,Mj,s,ti)表示a=b+((a+(F(b,c,d)+Mj+ti))<
GG(a,b,c,d,Mj,s,ti)表示a=b+((a+(G(b,c,d)+Mj+ti))<
hh(a,b,c,d,Mj,s,ti)表示a=b+((a+(H(b,c,d)+Mj+ti))<
II(a,b,c,d,Mj,s,ti)表示a=b+((a+(I(b,c,d)+Mj+ti))<
這四輪（64步）是：
2、第一輪
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)
3、第二輪
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)
4、第三輪
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)
5、第四輪
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)
6、常數ti的選擇
在第i步中，ti是4294967296*abs(sin(i))的整數部分，i的單位是弧度。(4294967296等於2的32次方)所有這些完成之後，將A、B、C、D分別加上a、b、c、d。然後用下一分組數據繼續運行算法，最後的輸出是A、B、C和D的級聯。
當你按照我上面所說的方法實現MD5算法以後，你可以用以下幾個信息對你做出來的程式作一個簡單的測試，看看程式有沒有錯誤。
MD5 ("") = d41d8cd98f00b204e9800998ecf8427e
MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661
MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0
MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") =
d174ab98d277d9f5a5611c2c9f419d9f
MD5 ("123456789012345678901234567890123456789012345678901234567890123456789
01234567890") = 57edf4a22be3c955ac49da2e2107b67a
三、MD5的安全性
MD5相對MD4所作的改進：1、增加了第四輪
2、每一步均有唯一的加法常數
3、第三
為減弱第二輪中函式G的對稱性從(X&Y)|(X&Z)|(Y&Z)變為(X&Z)|(Y&(~Z))；4、第四
第一步加上了上一步的結果，這將引起更快的雪崩效應；5、第五
改變了第二輪和第三輪中訪問訊息子分組的次序，使其更不相似；6、第六
近似最佳化了每一輪中的循環左移位移量以實現更快的雪崩效應。各輪的位移量互不相同。四、C++算法
1、頭檔案
#ifndef MD5_H#define MD5_H
#include
#include
/* Type define */
typedef unsigned char byte;
typedef unsigned int uint32;
using std::string;
using std::ifstream;
/* MD5 declaration. */
class MD5 {
public:
MD5();
MD5(const void* input, size_t length);
MD5(const string& str);
MD5(ifstream& in);
void update(const void* input, size_t length);
void update(const string& str);
void update(ifstream& in);
const byte* digest();
string toString();
void reset();
private:
void update(const byte* input, size_t length);
void final();
void transform(const byte block[64]);
void encode(const uint32* input, byte* output, size_t length);
void decode(const byte* input, uint32* output, size_t length);
string bytesToHexString(const byte* input, size_t length);
/* class uncopyable */
MD5(const MD5&);
MD5& operator=(const MD5&);
private:
uint32 _state[4]; /* state (ABCD) */
uint32 _count[2]; /* number of bits, modulo 2^64 (low-order word first) */
byte _buffer[64]; /* input buffer */
byte _digest[16]; /* message digest */
bool _finished; /* calculate finished ? */
static const byte PADDING[64]; /* padding for calculate */
static const char HEX[16];
enum { BUFFER_SIZE = 1024 };
};
#endif /*MD5_H*/
2、CPP檔案
#include "md5.h"using namespace std;
/* Constants for MD5Transform routine. */
#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
/* F, G, H and I are basic MD5 functions.
*/
#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)))
/* ROTATE_LEFT rotates x left n bits.
*/
#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
/* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
Rotation is separate from addition to prevent recomputation.
*/
#define FF(a, b, c, d, x, s, ac) { \
(a) += F ((b), (c), (d)) + (x) + ac; \
(a) = ROTATE_LEFT ((a), (s)); \
(a) += (b); \
}
#define GG(a, b, c, d, x, s, ac) { \
(a) += G ((b), (c), (d)) + (x) + ac; \
(a) = ROTATE_LEFT ((a), (s)); \
(a) += (b); \
}
#define HH(a, b, c, d, x, s, ac) { \
(a) += H ((b), (c), (d)) + (x) + ac; \
(a) = ROTATE_LEFT ((a), (s)); \
(a) += (b); \
}
#define II(a, b, c, d, x, s, ac) { \
(a) += I ((b), (c), (d)) + (x) + ac; \
(a) = ROTATE_LEFT ((a), (s)); \
(a) += (b); \
}
const byte MD5::PADDING[64] = { 0x80 };
const char MD5::HEX[16] = {
'0', '1', '2', '3',
'4', '5', '6', '7',
'8', '9', 'a', 'b',
'c', 'd', 'e', 'f'
};
/* Default construct. */
MD5::MD5() {
reset();
}
/* Construct a MD5 object with a input buffer. */
MD5::MD5(const void* input, size_t length) {
reset();
update(input, length);
}
/* Construct a MD5 object with a string. */
MD5::MD5(const string& str) {
reset();
update(str);
}
/* Construct a MD5 object with a file. */
MD5::MD5(ifstream& in) {
reset();
update(in);
}
/* Return the message-digest */
const byte* MD5::digest() {
if (!_finished) {
_finished = true;
final();
}
return _digest;
}
/* Reset the calculate state */
void MD5::reset() {
_finished = false;
/* reset number of bits. */
_count[0] = _count[1] = 0;
/* Load magic initialization constants. */
_state[0] = 0x67452301;
_state[1] = 0xefcdab89;
_state[2] = 0x98badcfe;
_state[3] = 0x10325476;
}
/* Updating the context with a input buffer. */
void MD5::update(const void* input, size_t length) {
update((const byte*)input, length);
}
/* Updating the context with a string. */
void MD5::update(const string& str) {
update((const byte*)str.c_str(), str.length());
}
/* Updating the context with a file. */
void MD5::update(ifstream& in) {
if (!in) {
return;
}
std::streamsize length;
char buffer[BUFFER_SIZE];
while (!in.eof()) {
in.read(buffer, BUFFER_SIZE);
length = in.gcount();
if (length > 0) {
update(buffer, length);
}
}
in.close();
}
/* MD5 block update operation. Continues an MD5 message-digest
operation, processing another message block, and updating the
context.
*/
void MD5::update(const byte* input, size_t length) {
uint32 i, index, partLen;
_finished = false;
/* Compute number of bytes mod 64 */
index = (uint32)((_count[0] >> 3) & 0x3f);
/* update number of bits */
if ((_count[0] += ((uint32)length << 3)) < ((uint32)length << 3)) {
++_count[1];
}
_count[1] += ((uint32)length >> 29);
partLen = 64 - index;
/* transform as many times as possible. */
if (length >= partLen) {
memcpy(&_buffer[index], input, partLen);
transform(_buffer);
for (i = partLen; i + 63 < length; i += 64) {
transform(∈put[i]);
}
index = 0;
} else {
i = 0;
}
/* Buffer remaining input */
memcpy(&_buffer[index], ∈put[i], length - i);
}
/* MD5 finalization. Ends an MD5 message-_digest operation, writing the
the message _digest and zeroizing the context.
*/
void MD5::final() {
byte bits[8];
uint32 oldState[4];
uint32 oldCount[2];
uint32 index, padLen;
/* Save current state and count. */
memcpy(oldState, _state, 16);
memcpy(oldCount, _count, 8);
/* Save number of bits */
encode(_count, bits, 8);
/* Pad out to 56 mod 64. */
index = (uint32)((_count[0] >> 3) & 0x3f);
padLen = (index < 56) ? (56 - index) : (120 - index);
update(PADDING, padLen);
/* Append length (before padding) */
update(bits, 8);
/* Store state in digest */
encode(_state, _digest, 16);
/* Restore current state and count. */
memcpy(_state, oldState, 16);
memcpy(_count, oldCount, 8);
}
/* MD5 basic transformation. Transforms _state based on block. */
void MD5::transform(const byte block[64]) {
uint32 a = _state[0], b = _state[1], c = _state[2], d = _state[3], x[16];
decode(block, x, 64);
/* Round 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 */
/* Round 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 */
/* Round 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 */
/* Round 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;
}
/* Encodes input (ulong) into output (byte). Assumes length is
a multiple of 4.
*/
void MD5::encode(const uint32* input, byte* output, size_t length) {
for (size_t i = 0, j = 0; j < length; ++i, j += 4) {
output[j]= (byte)(input[i] & 0xff);
output[j + 1] = (byte)((input[i] >> 8) & 0xff);
output[j + 2] = (byte)((input[i] >> 16) & 0xff);
output[j + 3] = (byte)((input[i] >> 24) & 0xff);
}
}
/* Decodes input (byte) into output (ulong). Assumes length is
a multiple of 4.
*/
void MD5::decode(const byte* input, uint32* output, size_t length) {
for (size_t i = 0, j = 0; j < length; ++i, j += 4) {
output[i] = ((uint32)input[j]) | (((uint32)input[j + 1]) << 8) |
(((uint32)input[j + 2]) << 16) | (((uint32)input[j + 3]) << 24);
}
}
/* Convert byte array to hex string. */
string MD5::bytesToHexString(const byte* input, size_t length) {
string str;
str.reserve(length << 1);
for (size_t i = 0; i < length; ++i) {
int t = input[i];
int a = t / 16;
int b = t % 16;
str.append(1, HEX[a]);
str.append(1, HEX[b]);
}
return str;
}
/* Convert digest to string value */
string MD5::toString() {
return bytesToHexString(digest(), 16);
}
#include
using namespace std;
void PrintMD5(const string& str, MD5& md5) {
cout << "MD5(\"" << str << "\") = " << md5.toString() << endl;
}
string FileDigest(const string& file) {
ifstream in(file.c_str(), ios::binary);
if (!in) {
return "";
}
MD5 md5;
std::streamsize length;
char buffer[1024];
while (!in.eof()) {
in.read(buffer, 1024);
length = in.gcount();
if (length > 0) {
md5.update(buffer, length);
}
}
in.close();
return md5.toString();
}
3、測試檔案
#include "md5.h"int main(int argc, _TCHAR* argv[]) {
//cout << MD5("abc").toString() << endl;
//cout << MD5(ifstream("D:\\test.txt")).toString() << endl;
//cout << MD5(ifstream("D:\\test.exe", ios::binary)).toString() << endl;
//cout << FileDigest("D:\\test.exe") << endl;
MD5 md5;
md5.update("");
PrintMD5("", md5);
md5.update("a");
PrintMD5("a", md5);
md5.update("bc");
PrintMD5("abc", md5);
md5.update("defghijklmnopqrstuvwxyz");
PrintMD5("abcdefghijklmnopqrstuvwxyz", md5);
md5.reset();
md5.update("message digest");
PrintMD5("message digest", md5);
//md5.reset();
//md5.update(ifstream("D:\\test.txt"));
//PrintMD5("D:\\test.txt", md5);
return 0;
}
四、Java算法
public class MD5Code {/*
* 下面這些S11-S44實際上是一個4*4的矩陣，在原始的C實現中是用#define 實現的， 這裡把它們實現成為static
* final是表示了唯讀，且能在同一個進程空間內的多個 Instance間共享
*/
static final int S11 = 7;
static final int S12 = 12;
static final int S13 = 17;
static final int S14 = 22;
static final int S21 = 5;
static final int S22 = 9;
static final int S23 = 14;
static final int S24 = 20;
static final int S31 = 4;
static final int S32 = 11;
static final int S33 = 16;
static final int S34 = 23;
static final int S41 = 6;
static final int S42 = 10;
static final int S43 = 15;
static final int S44 = 21;
static final byte[] PADDING = { -128, 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 };
/*
* 下面的三個成員是MD5計算過程中用到的3個核心數據，在原始的C實現中 被定義到MD5_CTX結構中
*/
private long[] state = new long[4];// state (ABCD)
private long[] count = new long[2];// number of bits, modulo 2^64 (lsb
// first)
private byte[] buffer = new byte[64]; // input buffer
/*
* digestHexStr是MD5的唯一一個公共成員，是最新一次計算結果的 16進制ASCII表示.
*/
public String digestHexStr;
/*
* digest,是最新一次計算結果的2進制內部表示，表示128bit的MD5值.
*/
private byte[] digest = new byte[16];
/*
* getMD5ofStr是類MD5最主要的公共方法，入口參數是你想要進行MD5變換的字元串
* 返回的是變換完的結果，這個結果是從公共成員digestHexStr取得的．
*/
public String getMD5ofStr(String inbuf) {
md5Init();
md5Update(inbuf.getBytes(), inbuf.length());
md5Final();
digestHexStr = "";
for (int i = 0; i < 16; i++) {
digestHexStr += byteHEX(digest[i]);
}
return digestHexStr;
}
// 這是MD5這個類的標準構造函式，JavaBean要求有一個public的並且沒有參數的構造函式
public MD5Code() {
md5Init();
return;
}
/* md5Init是一個初始化函式，初始化核心變數，裝入標準的幻數 */
private void md5Init() {
count[0] = 0L;
count[1] = 0L;
// /* Load magic initialization constants.
state[0] = 0x67452301L;
state[1] = 0xefcdab89L;
state[2] = 0x98badcfeL;
state[3] = 0x10325476L;
return;
}
/*
* F, G, H ,I 是4個基本的MD5函式，在原始的MD5的C實現中，由於它們是
* 簡單的位運算，可能出於效率的考慮把它們實現成了宏，在java中，我們把它們 實現成了private方法，名字保持了原來C中的。
*/
private long F(long x, long y, long z) {
return (x & y) | ((~x) & z);
}
private long G(long x, long y, long z) {
return (x & z) | (y & (~z));
}
private long H(long x, long y, long z) {
return x ^ y ^ z;
}
private long I(long x, long y, long z) {
return y ^ (x | (~z));
}
/*
* FF,GG,HH和II將調用F,G,H,I進行近一步變換 FF, GG, HH, and II transformations for
* rounds 1, 2, 3, and 4. Rotation is separate from addition to prevent
* recomputation.
*/
private long FF(long a, long b, long c, long d, long x, long s, long ac) {
a += F(b, c, d) + x + ac;
a = ((int) a << s) | ((int) a >>> (32 - s));
a += b;
return a;
}
private long GG(long a, long b, long c, long d, long x, long s, long ac) {
a += G(b, c, d) + x + ac;
a = ((int) a << s) | ((int) a >>> (32 - s));
a += b;
return a;
}
private long HH(long a, long b, long c, long d, long x, long s, long ac) {
a += H(b, c, d) + x + ac;
a = ((int) a << s) | ((int) a >>> (32 - s));
a += b;
return a;
}
private long II(long a, long b, long c, long d, long x, long s, long ac) {
a += I(b, c, d) + x + ac;
a = ((int) a << s) | ((int) a >>> (32 - s));
a += b;
return a;
}
/*
* md5Update是MD5的主計算過程，inbuf是要變換的位元組串，inputlen是長度，這個
* 函式由getMD5ofStr調用，調用之前需要調用md5init，因此把它設計成private的
*/
private void md5Update(byte[] inbuf, int inputLen) {
int i, index, partLen;
byte[] block = new byte[64];
index = (int) (count[0] >>> 3) & 0x3F;
// /* Update number of bits */
if ((count[0] += (inputLen << 3)) < (inputLen << 3))
count[1]++;
count[1] += (inputLen >>> 29);
partLen = 64 - index;
// Transform as many times as possible.
if (inputLen >= partLen) {
md5Memcpy(buffer, inbuf, index, 0, partLen);
md5Transform(buffer);
for (i = partLen; i + 63 < inputLen; i += 64) {
md5Memcpy(block, inbuf, 0, i, 64);
md5Transform(block);
}
index = 0;
} else
i = 0;
// /* Buffer remaining input */
md5Memcpy(buffer, inbuf, index, i, inputLen - i);
}
/*
* md5Final整理和填寫輸出結果
*/
private void md5Final() {
byte[] bits = new byte[8];
int index, padLen;
// /* Save number of bits */
Encode(bits, count, 8);
// /* Pad out to 56 mod 64.
index = (int) (count[0] >>> 3) & 0x3f;
padLen = (index < 56) ? (56 - index) : (120 - index);
md5Update(PADDING, padLen);
// /* Append length (before padding) */
md5Update(bits, 8);
// /* Store state in digest */
Encode(digest, state, 16);
}
/*
* md5Memcpy是一個內部使用的byte數組的塊拷貝函式，從input的inpos開始把len長度的
* 位元組拷貝到output的outpos位置開始
*/
private void md5Memcpy(byte[] output, byte[] input, int outpos, int inpos,
int len) {
int i;
for (i = 0; i < len; i++)
output[outpos + i] = input[inpos + i];
}
/*
* md5Transform是MD5核心變換程式，有md5Update調用，block是分塊的原始位元組
*/
private void md5Transform(byte block[]) {
long a = state[0], b = state[1], c = state[2], d = state[3];
long[] x = new long[16];
Decode(x, block, 64);
/* Round 1 */
a = FF(a, b, c, d, x[0], S11, 0xd76aa478L); /* 1 */
d = FF(d, a, b, c, x[1], S12, 0xe8c7b756L); /* 2 */
c = FF(c, d, a, b, x[2], S13, 0x242070dbL); /* 3 */
b = FF(b, c, d, a, x[3], S14, 0xc1bdceeeL); /* 4 */
a = FF(a, b, c, d, x[4], S11, 0xf57c0fafL); /* 5 */
d = FF(d, a, b, c, x[5], S12, 0x4787c62aL); /* 6 */
c = FF(c, d, a, b, x[6], S13, 0xa8304613L); /* 7 */
b = FF(b, c, d, a, x[7], S14, 0xfd469501L); /* 8 */
a = FF(a, b, c, d, x[8], S11, 0x698098d8L); /* 9 */
d = FF(d, a, b, c, x[9], S12, 0x8b44f7afL); /* 10 */
c = FF(c, d, a, b, x[10], S13, 0xffff5bb1L); /* 11 */
b = FF(b, c, d, a, x[11], S14, 0x895cd7beL); /* 12 */
a = FF(a, b, c, d, x[12], S11, 0x6b901122L); /* 13 */
d = FF(d, a, b, c, x[13], S12, 0xfd987193L); /* 14 */
c = FF(c, d, a, b, x[14], S13, 0xa679438eL); /* 15 */
b = FF(b, c, d, a, x[15], S14, 0x49b40821L); /* 16 */
/* Round 2 */
a = GG(a, b, c, d, x[1], S21, 0xf61e2562L); /* 17 */
d = GG(d, a, b, c, x[6], S22, 0xc040b340L); /* 18 */
c = GG(c, d, a, b, x[11], S23, 0x265e5a51L); /* 19 */
b = GG(b, c, d, a, x[0], S24, 0xe9b6c7aaL); /* 20 */
a = GG(a, b, c, d, x[5], S21, 0xd62f105dL); /* 21 */
d = GG(d, a, b, c, x[10], S22, 0x2441453L); /* 22 */
c = GG(c, d, a, b, x[15], S23, 0xd8a1e681L); /* 23 */
b = GG(b, c, d, a, x[4], S24, 0xe7d3fbc8L); /* 24 */
a = GG(a, b, c, d, x[9], S21, 0x21e1cde6L); /* 25 */
d = GG(d, a, b, c, x[14], S22, 0xc33707d6L); /* 26 */
c = GG(c, d, a, b, x[3], S23, 0xf4d50d87L); /* 27 */
b = GG(b, c, d, a, x[8], S24, 0x455a14edL); /* 28 */
a = GG(a, b, c, d, x[13], S21, 0xa9e3e905L); /* 29 */
d = GG(d, a, b, c, x[2], S22, 0xfcefa3f8L); /* 30 */
c = GG(c, d, a, b, x[7], S23, 0x676f02d9L); /* 31 */
b = GG(b, c, d, a, x[12], S24, 0x8d2a4c8aL); /* 32 */
/* Round 3 */
a = HH(a, b, c, d, x[5], S31, 0xfffa3942L); /* 33 */
d = HH(d, a, b, c, x[8], S32, 0x8771f681L); /* 34 */
c = HH(c, d, a, b, x[11], S33, 0x6d9d6122L); /* 35 */
b = HH(b, c, d, a, x[14], S34, 0xfde5380cL); /* 36 */
a = HH(a, b, c, d, x[1], S31, 0xa4beea44L); /* 37 */
d = HH(d, a, b, c, x[4], S32, 0x4bdecfa9L); /* 38 */
c = HH(c, d, a, b, x[7], S33, 0xf6bb4b60L); /* 39 */
b = HH(b, c, d, a, x[10], S34, 0xbebfbc70L); /* 40 */
a = HH(a, b, c, d, x[13], S31, 0x289b7ec6L); /* 41 */
d = HH(d, a, b, c, x[0], S32, 0xeaa127faL); /* 42 */
c = HH(c, d, a, b, x[3], S33, 0xd4ef3085L); /* 43 */
b = HH(b, c, d, a, x[6], S34, 0x4881d05L); /* 44 */
a = HH(a, b, c, d, x[9], S31, 0xd9d4d039L); /* 45 */
d = HH(d, a, b, c, x[12], S32, 0xe6db99e5L); /* 46 */
c = HH(c, d, a, b, x[15], S33, 0x1fa27cf8L); /* 47 */
b = HH(b, c, d, a, x[2], S34, 0xc4ac5665L); /* 48 */
/* Round 4 */
a = II(a, b, c, d, x[0], S41, 0xf4292244L); /* 49 */
d = II(d, a, b, c, x[7], S42, 0x432aff97L); /* 50 */
c = II(c, d, a, b, x[14], S43, 0xab9423a7L); /* 51 */
b = II(b, c, d, a, x[5], S44, 0xfc93a039L); /* 52 */
a = II(a, b, c, d, x[12], S41, 0x655b59c3L); /* 53 */
d = II(d, a, b, c, x[3], S42, 0x8f0ccc92L); /* 54 */
c = II(c, d, a, b, x[10], S43, 0xffeff47dL); /* 55 */
b = II(b, c, d, a, x[1], S44, 0x85845dd1L); /* 56 */
a = II(a, b, c, d, x[8], S41, 0x6fa87e4fL); /* 57 */
d = II(d, a, b, c, x[15], S42, 0xfe2ce6e0L); /* 58 */
c = II(c, d, a, b, x[6], S43, 0xa3014314L); /* 59 */
b = II(b, c, d, a, x[13], S44, 0x4e0811a1L); /* 60 */
a = II(a, b, c, d, x[4], S41, 0xf7537e82L); /* 61 */
d = II(d, a, b, c, x[11], S42, 0xbd3af235L); /* 62 */
c = II(c, d, a, b, x[2], S43, 0x2ad7d2bbL); /* 63 */
b = II(b, c, d, a, x[9], S44, 0xeb86d391L); /* 64 */
state[0] += a;
state[1] += b;
state[2] += c;
state[3] += d;
}
/*
* Encode把long數組按順序拆成byte數組，因為java的long類型是64bit的， 只拆低32bit，以適應原始C實現的用途
*/
private void Encode(byte[] output, long[] input, int len) {
int i, j;
for (i = 0, j = 0; j < len; i++, j += 4) {
output[j] = (byte) (input[i] & 0xffL);
output[j + 1] = (byte) ((input[i] >>> 8) & 0xffL);
output[j + 2] = (byte) ((input[i] >>> 16) & 0xffL);
output[j + 3] = (byte) ((input[i] >>> 24) & 0xffL);
}
}
/*
* Decode把byte數組按順序合成成long數組，因為java的long類型是64bit的，
* 只合成低32bit，高32bit清零，以適應原始C實現的用途
*/
private void Decode(long[] output, byte[] input, int len) {
int i, j;
for (i = 0, j = 0; j < len; i++, j += 4)
output[i] = b2iu(input[j]) | (b2iu(input[j + 1]) << 8)
| (b2iu(input[j + 2]) << 16) | (b2iu(input[j + 3]) << 24);
return;
}
/*
* b2iu是我寫的一個把byte按照不考慮正負號的原則的"升位"程式，因為java沒有unsigned運算
*/
public static long b2iu(byte b) {
return b < 0 ? b & 0x7F + 128 : b;
}
/*
* byteHEX()，用來把一個byte類型的數轉換成十六進制的ASCII表示，
* 因為java中的byte的toString無法實現這一點，我們又沒有C語言中的 sprintf(outbuf,"%02X",ib)
*/
public static String byteHEX(byte ib) {
char[] Digit = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A',
'B', 'C', 'D', 'E', 'F' };
char[] ob = new char[2];
ob[0] = Digit[(ib >>> 4) & 0X0F];
ob[1] = Digit[ib & 0X0F];
String s = new String(ob);
return s;
}
}
