MD5算法和C#實作
1 MD5簡介
MD5是由麻省理工學院（MIT）的Ronald L. Rivest教授發明的。MD5算法可以接受任意長度的輸入并且産生一個128位（bit）的“指紋”或者“消息摘要”輸出。通常不同的消息不會産生相同的消息摘要，而且通過消息摘要也無法還原出原始資訊。從本質上說，MD5算法是一種驗證資料完整性的方法，并且它比其它許多方法都要可靠的多。但是MD5并不是一種完美的方法。
2 術語和概念
2.1 位(Bit)，位元組（Byte）和字（Word）
MD5始終把消息當成一個位（bit）字元串來處理。本文中，一個“字”（Word）是32位，而一個“位元組”（Byte）是8位。比如，我們把10001100看成一個位元組并且MSB（Most Significant Bit）在左邊，那就是說，最左邊的“1”是高位。對于“字”來說，和“位元組”有所不同。一個字通常是4位元組并且LSB（Least Significant Bit）在左邊。比如，10001100 11000011 10010001 01001000 可以看成一個字并且LSB是10001100，那就是說，最左邊的位元組是低位。
2.2 符号
符号“+”表示以2^32為模的加法。假設Word = Word1 + Word2。如果Word>2^32，那麼Word = Word & 0XFFFFFFFF。符号“<<<”表示循環移位。如果X<<<s，那麼就表示對X循環移動s位。符号“not”表示按位取反。“v”表示按位或，“xor”表示按位異或。
3 MD5算法簡介
在MD5算法中，我們必須把原始消息（字元串，檔案等）轉換成位字元串。MD5算法隻接受位作為輸入。假設我們對字元串“abc”産生消息摘要。首先，我們将它轉換成位字元串如下：
01100001 01100010 01100011
―――――――――――――
‘a’=97 ‘b’=98 ‘c’=99
這個位字元串的長度為24。下面我們需要5個步驟來計算MD5。
3.1 補位
消息必須進行補位，以使其長度在對512取模以後的餘數是448。也就是說，（補位後的消息長度）%512 = 448。即使長度已經滿足對512取模後餘數是448，補位也必須要進行。
補位是這樣進行的：先補一個1，然後再補0，直到長度滿足對512取模後餘數是448。總而言之，補位是至少補一位，最多補512位。還是以前面的“abc”為例顯示補位的過程。
原始資訊： 01100001 01100010 01100011
補位第一步：01100001 01100010 01100011 1
首先補一個“1”
補位第二步：01100001 01100010 01100011 10…..0
然後補423個“0”
我們可以把最後補位完成後的資料用16進制寫成下面的樣子
61626380 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000
現在，資料的長度是448了，我們可以進行下一步操作。
3.2 補長度
所謂的補長度是将原始資料的長度補到已經進行了補位操作的消息後面。通常用一個64位的資料來表示原始消息的長度。對于資料長度大于2^64這種極其少見的情況，我們隻取其低64位。通常把資料長度分成2個32位的字，并且先補低位的資料，再補高位的資料。在進行了補長度的操作以後，整個消息就變成下面這樣了（16進制格式）
61626380 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 18000000 00000000
如果原始的消息長度超過了512，我們需要将它補成512的倍數。然後我們把整個消息分成一個一個512位的資料塊，分别處理每一個資料塊，進而得到消息摘要。
3.3 初始化消息摘要緩沖區
一個四個字長的緩沖區（A，B，C，D）用來存儲消息摘要。A，B，C，D都是32位寄存器。這些寄存器被初始化為下面的值（16進制格式，低位在前）
A：01 23 45 67 （在我們的程式中，我們需要把它寫成A=0x67452301）
B：89 ab cd ef （在我們的程式中，我們需要把它寫成B=0xefcdab89）
C：fe dc ba 98 （在我們的程式中，我們需要把它寫成C=0x98badcfe）
D：76 54 32 10 （在我們的程式中，我們需要把它寫成D=0x10325476）
3.4 處理16個字長的消息塊
首先我們定義4個輔助函數，每個函數都能接受3個32位的字，并且輸出一個32位的字
F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))
我們使用了一個有64個元素的表T[1…..64]。假設i從1到64，那麼：
T[i] = [4294967296*abs(sin(i))]，[x]表示取x的整數部分。
3.5 計算消息摘要
我們已經補齊了資料并且有了所有的函數，接下來就可以計算消息摘要了。計算的過程如下：
//處理每一個16個字的資料塊
// 将A另存為AA，B存為BB，C存為CC，D存為DD
AA = A
BB = B
CC = C
DD = D
// 第一輪
// [abcd k s i] 表示：a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s).
// 進行下面的16步操作
[ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4]
[ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8]
[ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12]
[ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]
// 第二輪
// [abcd k s i] 表示：a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s).
// 進行下面的16步操作
[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20]
[ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24]
[ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28]
[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]
// 第三輪
// [abcd k s t]表示：a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s).
// 進行下面的16步操作
[ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36]
[ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]
[ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44]
[ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48]
// 第四輪
// [abcd k s t] 表示：a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s).
// 進行下面的16步操作
[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52]
[ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56]
[ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60]
[ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]
//累加寄存器
A = A + AA
B = B + BB
C = C + CC
D = D + DD
這樣就處理完了一個16個字的資料塊，按照同樣的方法依次處理完所有的資料塊以後，就從寄存器A，B，C，D中得到了消息摘要。
4 參考文獻
1: MD5 Homepage (unoffical): http://userpages.umbc.edu/~mabzug1/cs/md5/md5.html
2: The website of Professor Ronald L. Rivest: http://theory.lcs.mit.edu/~rivest/homepage.html
3: The MD5 Message-Digest Algorithm: http://www.faqs.org/rfcs/rfc1321.html
4: The MD4 Message-Digest Algorithm: http://www.ietf.org/rfc/rfc1320.txt
5 C#實作代碼
public class MyMD5
{
private static UInt32 A;
private static UInt32 B;
private static UInt32 C;
private static UInt32 D;
private const int S11 = 7 ;
private const int S12 = 12 ;
private const int S13 = 17 ;
private const int S14 = 22 ;
private const int S21 = 5 ;
private const int S22 = 9 ;
private const int S23 = 14 ;
private const int S24 = 20 ;
private const int S31 = 4 ;
private const int S32 = 11 ;
private const int S33 = 16 ;
private const int S34 = 23 ;
private const int S41 = 6 ;
private const int S42 = 10 ;
private const int S43 = 15 ;
private const int S44 = 21 ;
// F, G, H and I are basic MD5 functions.
// 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))
// (& AND，| OR，~NOT，^XOR)
private static UInt32 F(UInt32 x,UInt32 y,UInt32 z)
{
return (x & y) | (( ~ x) & z);
}
private static UInt32 G(UInt32 x,UInt32 y,UInt32 z)
{
return (x & z) | (y & ( ~ z));
}
private static UInt32 H(UInt32 x,UInt32 y,UInt32 z)
{
return x ^ y ^ z;
}
private static UInt32 I(UInt32 x,UInt32 y,UInt32 z)
{
return y ^ (x | ( ~ z));
}
// FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
// Rotation is separate from addition to prevent recomputation.
private static void FF( ref UInt32 a,UInt32 b,UInt32 c,UInt32 d,UInt32 mj, int s,UInt32 ti)
{
a = a + F(b,c,d) + mj + ti;
a = a << s | a >> ( 32 - s);
a += b;
}
private static void GG( ref UInt32 a,UInt32 b,UInt32 c,UInt32 d,UInt32 mj, int s,UInt32 ti)
{
a = a + G(b,c,d) + mj + ti;
a = a << s | a >> ( 32 - s);
a += b;
}
private static void HH( ref UInt32 a,UInt32 b,UInt32 c,UInt32 d,UInt32 mj, int s,UInt32 ti)
{
a = a + H(b,c,d) + mj + ti;
a = a << s | a >> ( 32 - s);
a += b;
}
private static void II( ref UInt32 a,UInt32 b,UInt32 c,UInt32 d,UInt32 mj, int s,UInt32 ti)
{
a = a + I(b,c,d) + mj + ti;
a = a << s | a >> ( 32 - s);
a += b;
}
private static void MD5_Init()
{
A = 0x67452301 ; // in memory, this is 0x01234567
B = 0xefcdab89 ; // in memory, this is 0x89abcdef
C = 0x98badcfe ; // in memory, this is 0xfedcba98
D = 0x10325476 ; // in memory, this is 0x76543210
}
private static UInt32[] MD5_Append( byte [] input)
{
int zeros = 0 ;
int ones = 1 ;
int size = 0 ;
int n = input.Length;
int m = n % 64 ;
if ( m < 56 )
{
zeros = 55 - m;
size = n - m + 64 ;
}
else if (m == 56 )
{
zeros = 63 ;
ones = 1 ;
size = n + 8 + 64 ;
}
else
{
zeros = 63 - m + 56 ;
size = n + 64 - m + 64 ;
}
ArrayList bs = new ArrayList(input);
if (ones == 1 )
{
bs.Add( ( byte ) 0x80 ); // 0x80 = 10000000
}
for ( int i = 0 ;i < zeros;i ++ )
{
bs.Add( ( byte ) 0 );
}
UInt64 N = (UInt64) n * 8 ;
byte h1 = ( byte )(N & 0xFF );
byte h2 = ( byte )((N >> 8 ) & 0xFF );
byte h3 = ( byte )((N >> 16 ) & 0xFF );
byte h4 = ( byte )((N >> 24 ) & 0xFF );
byte h5 = ( byte )((N >> 32 ) & 0xFF );
byte h6 = ( byte )((N >> 40 ) & 0xFF );
byte h7 = ( byte )((N >> 48 ) & 0xFF );
byte h8 = ( byte )(N >> 56 );
bs.Add(h1);
bs.Add(h2);
bs.Add(h3);
bs.Add(h4);
bs.Add(h5);
bs.Add(h6);
bs.Add(h7);
bs.Add(h8);
byte [] ts = ( byte [])bs.ToArray( typeof ( byte ));
// Decodes input (byte[]) into output (UInt32[]). Assumes len is
// a multiple of 4.
UInt32[] output = new UInt32[size / 4 ];
for (Int64 i = 0 ,j = 0 ;i < size;j ++ ,i += 4 )
{
output[j] = (UInt32)(ts[i] | ts[i + 1 ] << 8 | ts[i + 2 ] << 16 | ts[i + 3 ] << 24 );
}
return output;
}
private static UInt32[] MD5_Trasform(UInt32[] x)
{
UInt32 a,b,c,d;
for ( int k = 0 ;k < x.Length;k += 16 )
{
a = A;
b = B;
c = C;
d = D;
// Round 1
FF ( ref a, b, c, d, x[k + 0 ], S11, 0xd76aa478 ); // 1
FF ( ref d, a, b, c, x[k + 1 ], S12, 0xe8c7b756 ); // 2
FF ( ref c, d, a, b, x[k + 2 ], S13, 0x242070db ); // 3
FF ( ref b, c, d, a, x[k + 3 ], S14, 0xc1bdceee ); // 4
FF ( ref a, b, c, d, x[k + 4 ], S11, 0xf57c0faf ); // 5
FF ( ref d, a, b, c, x[k + 5 ], S12, 0x4787c62a ); // 6
FF ( ref c, d, a, b, x[k + 6 ], S13, 0xa8304613 ); // 7
FF ( ref b, c, d, a, x[k + 7 ], S14, 0xfd469501 ); // 8
FF ( ref a, b, c, d, x[k + 8 ], S11, 0x698098d8 ); // 9
FF ( ref d, a, b, c, x[k + 9 ], S12, 0x8b44f7af ); // 10
FF ( ref c, d, a, b, x[k + 10 ], S13, 0xffff5bb1 ); // 11
FF ( ref b, c, d, a, x[k + 11 ], S14, 0x895cd7be ); // 12
FF ( ref a, b, c, d, x[k + 12 ], S11, 0x6b901122 ); // 13
FF ( ref d, a, b, c, x[k + 13 ], S12, 0xfd987193 ); // 14
FF ( ref c, d, a, b, x[k + 14 ], S13, 0xa679438e ); // 15
FF ( ref b, c, d, a, x[k + 15 ], S14, 0x49b40821 ); // 16
// Round 2
GG ( ref a, b, c, d, x[k + 1 ], S21, 0xf61e2562 ); // 17
GG ( ref d, a, b, c, x[k + 6 ], S22, 0xc040b340 ); // 18
GG ( ref c, d, a, b, x[k + 11 ], S23, 0x265e5a51 ); // 19
GG ( ref b, c, d, a, x[k + 0 ], S24, 0xe9b6c7aa ); // 20
GG ( ref a, b, c, d, x[k + 5 ], S21, 0xd62f105d ); // 21
GG ( ref d, a, b, c, x[k + 10 ], S22, 0x2441453 ); // 22
GG ( ref c, d, a, b, x[k + 15 ], S23, 0xd8a1e681 ); // 23
GG ( ref b, c, d, a, x[k + 4 ], S24, 0xe7d3fbc8 ); // 24
GG ( ref a, b, c, d, x[k + 9 ], S21, 0x21e1cde6 ); // 25
GG ( ref d, a, b, c, x[k + 14 ], S22, 0xc33707d6 ); // 26
GG ( ref c, d, a, b, x[k + 3 ], S23, 0xf4d50d87 ); // 27
GG ( ref b, c, d, a, x[k + 8 ], S24, 0x455a14ed ); // 28
GG ( ref a, b, c, d, x[k + 13 ], S21, 0xa9e3e905 ); // 29
GG ( ref d, a, b, c, x[k + 2 ], S22, 0xfcefa3f8 ); // 30
GG ( ref c, d, a, b, x[k + 7 ], S23, 0x676f02d9 ); // 31
GG ( ref b, c, d, a, x[k + 12 ], S24, 0x8d2a4c8a ); // 32
// Round 3
HH ( ref a, b, c, d, x[k + 5 ], S31, 0xfffa3942 ); // 33
HH ( ref d, a, b, c, x[k + 8 ], S32, 0x8771f681 ); // 34
HH ( ref c, d, a, b, x[k + 11 ], S33, 0x6d9d6122 ); // 35
HH ( ref b, c, d, a, x[k + 14 ], S34, 0xfde5380c ); // 36
HH ( ref a, b, c, d, x[k + 1 ], S31, 0xa4beea44 ); // 37
HH ( ref d, a, b, c, x[k + 4 ], S32, 0x4bdecfa9 ); // 38
HH ( ref c, d, a, b, x[k + 7 ], S33, 0xf6bb4b60 ); // 39
HH ( ref b, c, d, a, x[k + 10 ], S34, 0xbebfbc70 ); // 40
HH ( ref a, b, c, d, x[k + 13 ], S31, 0x289b7ec6 ); // 41
HH ( ref d, a, b, c, x[k + 0 ], S32, 0xeaa127fa ); // 42
HH ( ref c, d, a, b, x[k + 3 ], S33, 0xd4ef3085 ); // 43
HH ( ref b, c, d, a, x[k + 6 ], S34, 0x4881d05 ); // 44
HH ( ref a, b, c, d, x[k + 9 ], S31, 0xd9d4d039 ); // 45
HH ( ref d, a, b, c, x[k + 12 ], S32, 0xe6db99e5 ); // 46
HH ( ref c, d, a, b, x[k + 15 ], S33, 0x1fa27cf8 ); // 47
HH ( ref b, c, d, a, x[k + 2 ], S34, 0xc4ac5665 ); // 48
// Round 4
II ( ref a, b, c, d, x[k + 0 ], S41, 0xf4292244 ); // 49
II ( ref d, a, b, c, x[k + 7 ], S42, 0x432aff97 ); // 50
II ( ref c, d, a, b, x[k + 14 ], S43, 0xab9423a7 ); // 51
II ( ref b, c, d, a, x[k + 5 ], S44, 0xfc93a039 ); // 52
II ( ref a, b, c, d, x[k + 12 ], S41, 0x655b59c3 ); // 53
II ( ref d, a, b, c, x[k + 3 ], S42, 0x8f0ccc92 ); // 54
II ( ref c, d, a, b, x[k + 10 ], S43, 0xffeff47d ); // 55
II ( ref b, c, d, a, x[k + 1 ], S44, 0x85845dd1 ); // 56
II ( ref a, b, c, d, x[k + 8 ], S41, 0x6fa87e4f ); // 57
II ( ref d, a, b, c, x[k + 15 ], S42, 0xfe2ce6e0 ); // 58
II ( ref c, d, a, b, x[k + 6 ], S43, 0xa3014314 ); // 59
II ( ref b, c, d, a, x[k + 13 ], S44, 0x4e0811a1 ); // 60
II ( ref a, b, c, d, x[k + 4 ], S41, 0xf7537e82 ); // 61
II ( ref d, a, b, c, x[k + 11 ], S42, 0xbd3af235 ); // 62
II ( ref c, d, a, b, x[k + 2 ], S43, 0x2ad7d2bb ); // 63
II ( ref b, c, d, a, x[k + 9 ], S44, 0xeb86d391 ); // 64
A += a;
B += b;
C += c;
D += d;
}
return new UInt32[]{A,B,C,D};
}
public static byte [] MyMD5Array( byte [] input)
{
MD5_Init();
UInt32[] block = MD5_Append(input);
UInt32[] bits = MD5_Trasform(block);
// Encodes bits (UInt32[]) into output (byte[]). Assumes len is
// a multiple of 4.
byte [] output = new byte [bits.Length * 4 ];
for ( int i = 0 ,j = 0 ;i < bits.Length;i ++ ,j += 4 )
{
output[j] = ( byte )(bits[i] & 0xff );
output[j + 1 ] = ( byte )((bits[i] >> 8 ) & 0xff );
output[j + 2 ] = ( byte )((bits[i] >> 16 ) & 0xff );
output[j + 3 ] = ( byte )((bits[i] >> 24 ) & 0xff );
}
return output;
}
public static string ArrayToHexString( byte [] array, bool uppercase)
{
string hexString = "" ;
string format = " x2 " ;
if (uppercase)
{
format = " X2 " ;
}
foreach ( byte b in array)
{
hexString += b.ToString(format);
}
return hexString;
}
public static string MyMD5String( string message)
{
char [] c = message.ToCharArray();
byte [] b = new byte [c.Length];
for ( int i = 0 ;i < c.Length;i ++ )
{
b[i] = ( byte )c[i];
}
byte [] digest = MyMD5Array(b);
return ArrayToHexString(digest, true );
}
public static string MyMD5File( string fileName)
{
byte [] array = null ;
FileStream fs = null ;
try
{
fs = File.Open(fileName,FileMode.Open,FileAccess.Read);
array = new byte [fs.Length];
fs.Read(array, 0 ,( int )fs.Length);
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
byte [] digest = MyMD5Array(array);
fs.Close();
return ArrayToHexString(digest, true );
}
#region UnitTest
public static string Test( string message)
{
return " \r\nMD5 (\ "" +message+ " \ " ) = " + MyMD5.MyMD5String(message);
}
public static string TestSuite()
{
string s = "" ;
s += Test( "" );
s += Test( " a " );
s += Test( " abc " );
s += Test( " abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq " );
s += Test( " message digest " );
s += Test( " abcdefghijklmnopqrstuvwxyz " );
s += Test( " ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789 " );
s += Test( " 12345678901234567890123456789012345678901234567890123456789012345678901234567890 " );
return s;
}
public static void Main()
{
Console.WriteLine(TestSuite());
Console.ReadLine();
}
#endregion
}
轉載于:https://www.cnblogs.com/FlyingBread/archive/2006/12/24/602511.html
![各種二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)