MD5演算法

來自專欄 演算法、編程

一、MD5簡介

MD5即Message-Digest Algorithm 5（信息-摘要演算法5），用於確保信息傳輸完整一致。是計算機廣泛使用的雜湊演算法之一（又譯摘要演算法、哈希演算法），主流編程語言普遍已有MD5實現。

MD5演算法具有以下特點：

1、壓縮性：任意長度的數據，算出的MD5值長度都是固定的。

2、容易計算：從原數據計算出MD5值很容易。

3、抗修改性：對原數據進行任何改動，哪怕只修改1個位元組，所得到的MD5值都有很大區別。

4、強抗碰撞：已知原數據和其MD5值，想找到一個具有相同MD5值的數據（即偽造數據）是非常困難的。

MD5的作用是讓大容量信息在用數字簽名軟體簽署私人密鑰前被"壓縮"成一種保密的格式（就是把一個任意長度的位元組串變換成一定長的16進位數字串）。

大家都知道，地球上任何人都有自己獨一無二的指紋，這常常成為司法機關鑒別罪犯身份最值得信賴的方法；與之類似，MD5就可以為任何文件（不管其大小、格式、數量）產生一個同樣獨一無二的MD5「數字指紋」，如果任何人對文件做了任何改動，其MD5也就是對應的「數字指紋」都會發生變化。

二、MD5加密原理步驟

1.填充

在MD5演算法中，首先需要對信息進行填充，使其位長對512求余的結果等於448，並且填充必須進行，即使其位長對512求余的結果等於448。因此，信息的位長（Bits Length）將被擴展至N*512+448，N為一個非負整數，N可以是零。

填充的方法如下：

1) 在信息的後面填充一個1和無數個0，直到滿足上面的條件時才停止用0對信息的填充。

2) 在這個結果後面附加一個以64位二進位表示的填充前信息長度（單位為Bit），如果二

進位表示的填充前信息長度超過64位，則取低64位。

經過這兩步的處理，信息的位長=N*512+448+64=(N+1）*512，即長度恰好是512的整數倍。這樣做的原因是為滿足後面處理中對信息長度的要求。

2. 初始化變數

初始的128位值為初試鏈接變數，這些參數用於第一輪的運算，以大端位元組序來表示，他們分別為： A=0x01234567，B=0x89ABCDEF，C=0xFEDCBA98，D=0x76543210。

（每一個變數給出的數值是高位元組存於內存低地址，低位元組存於內存高地址，即大端位元組序。在程序中變數A、B、C、D的值分別為0x67452301，0xEFCDAB89，0x98BADCFE，0x10325476）

3. 處理分組數據

每一分組的演算法流程如下：

第一分組需要將上面四個鏈接變數複製到另外四個變數中：A到a，B到b，C到c，D到d。從第二分組開始的變數為上一分組的運算結果，即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) )

（&是與（And），|是或（Or），~是非（Not），^是異或（Xor））

這四個函數的說明：如果X、Y和Z的對應位是獨立和均勻的，那麼結果的每一位也應是獨立和均勻的。

F是一個逐位運算的函數。即，如果X，那麼Y，否則Z。函數H是逐位奇偶操作符。

假設Mj表示消息的第j個子分組（從0到15），常數ti是4294967296*abs( sin(i) ）的整數部分，i 取值從1到64，單位是弧度。（4294967296=2的32次方）

現定義：

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)

現定義：

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 )

所有這些完成之後，將a、b、c、d分別在原來基礎上再加上A、B、C、D。

即a = a + A，b = b + B，c = c + C，d = d + D

然後用下一分組數據繼續運行以上演算法。

4. 輸出

最後的輸出是a、b、c和d的級聯。

當你按照我上面所說的方法實現MD5演算法以後，你可以用以下幾個信息對你做出來的程序作一個簡單的測試，看看程序有沒有錯誤。

MD5 ("") = d41d8cd98f00b204e9800998ecf8427e

MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661

MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72

MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0

MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b

MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz") =

f29939a25efabaef3b87e2cbfe641315

MD5 ("8a683566bcc7801226b3d8b0cf35fd97") =cf2cb5c89c5e5eeebef4a76becddfcfd

MD5加密字元串實例

現以字元串「jklmn」為例。

該字元串在內存中表示為：6A 6B 6C 6D 6E（從左到右為低地址到高地址，後同），信息長度為40 bits， 即0x28。

對其填充，填充至448位，即56位元組。結果為：

6A 6B 6C 6D 6E 80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

剩下64位，即8位元組填充填充前信息位長，按小端位元組序填充剩下的8位元組，結果為。

6A 6B 6C 6D 6E 80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 28 00 00 00 00 00 00 00

（64位元組，512 bits）

初始化A、B、C、D四個變數。

將這64位元組填充後數據分成16個小組（程序中對應為16個數組），即：

M0：6A 6B 6C 6D （這是內存中的順序，按照小端位元組序原則，對應數組M(0)的值為0x6D6C6B6A，下同）

M1：6E 80 00 00

M2：00 00 00 00

.....

M14：28 00 00 00

M15：00 00 00 00

經過「3. 分組數據處理」後，a、b、c、d值分別為0xD8523F60、0x837E0144、0x517726CA、0x1BB6E5FE

在內存中為a：60 3F 52 D8

b：44 01 7E 83

c：CA 26 77 51

d：FE E5 B6 1B

a、b、c、d按內存順序輸出即為最終結果：603F52D844017E83CA267751FEE5B61B。這就是字元串「jklmn」的MD5值。

三、代碼實現MD5轉換器

主程序：

package com.oop.lhw0524;import java.awt.BorderLayout;import java.awt.Color;import javax.swing.ImageIcon;import javax.swing.JButton;import javax.swing.JFrame;import javax.swing.JLabel;import javax.swing.JPasswordField;import javax.swing.JTextField;public class MD5 { /* * 四個鏈接變數 */ private final int A = 0x67452301; private final int B = 0xefcdab89; private final int C = 0x98badcfe; private final int D = 0x10325476; /* * ABCD的臨時變數 */ private int Atemp, Btemp, Ctemp, Dtemp; /* * 常量ti公式:floor(abs(sin(i+1))×(2pow32) */ private final int K[] = { 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee, 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501, 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be, 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821, 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa, 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8, 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed, 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a, 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c, 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70, 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05, 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665, 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039, 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1, 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1, 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 }; /* * 向左位移數,計算方法未知 */ private final int s[] = { 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21 }; /* * 初始化函數 */ private void init() { Atemp = A; Btemp = B; Ctemp = C; Dtemp = D; } /* * 移動一定位數 */ private int shift(int a, int s) { return (a << s) | (a >>> (32 - s));// 右移的時候，高位一定要補零，而不是補充符號位 } /* * 主循環 */ private void MainLoop(int M[]) { int F, g; int a = Atemp; int b = Btemp; int c = Ctemp; int d = Dtemp; for (int i = 0; i < 64; i++) { if (i < 16) { F = (b & c) | ((~b) & d); g = i; } else if (i < 32) { F = (d & b) | ((~d) & c); g = (5 * i + 1) % 16; } else if (i < 48) { F = b ^ c ^ d; g = (3 * i + 5) % 16; } else { F = c ^ (b | (~d)); g = (7 * i) % 16; } int tmp = d; d = c; c = b; b = b + shift(a + F + K[i] + M[g], s[i]); a = tmp; } Atemp = a + Atemp; Btemp = b + Btemp; Ctemp = c + Ctemp; Dtemp = d + Dtemp; } /* * 填充函數處理後應滿足bits≡448(mod512),位元組就是bytes≡56（mode64)填充方式為先加一個0,其它位補零 * 最後加上64位的原來長度 */ private int[] add(String str) { int num = ((str.length() + 8) / 64) + 1;// 以512位，64個位元組為一組 int strByte[] = new int[num * 16];// 64/4=16，所以有16個整數 for (int i = 0; i < num * 16; i++) {// 全部初始化0 strByte[i] = 0; } int i; for (i = 0; i < str.length(); i++) { strByte[i >> 2] |= str.charAt(i) << ((i % 4) * 8);// 一個整數存儲四個位元組，小端序 } strByte[i >> 2] |= 0x80 << ((i % 4) * 8);// 尾部添加1 /* * 添加原長度，長度指位的長度，所以要乘8，然後是小端序，所以放在倒數第二個,這裡長度只用了32位 */ strByte[num * 16 - 2] = str.length() * 8; return strByte; } /* * 調用函數 */ public String getMD5(String source) { init(); int strByte[] = add(source); for (int i = 0; i < strByte.length / 16; i++) { int num[] = new int[16]; for (int j = 0; j < 16; j++) { num[j] = strByte[i * 16 + j]; } MainLoop(num); } return changeHex(Atemp) + changeHex(Btemp) + changeHex(Ctemp) + changeHex(Dtemp); } /* * 整數變成16進位字元串 */ private String changeHex(int a) { String str = ""; for (int i = 0; i < 4; i++) { str += String.format("%2s", Integer.toHexString(((a >> i * 8) % (1 << 8)) & 0xff)).replace( , 0); } return str; } /* * 單例 */ private static MD5 instance; public static MD5 getInstance() { if (instance == null) { instance = new MD5(); } return instance; } private MD5() { }; public static void main(String[] args) { JFrame jf = new JFrame(); jf.setTitle("MD5"); jf.setSize(400, 400); jf.setLayout(new BorderLayout()); jf.setLocationRelativeTo(null); jf.setDefaultCloseOperation(3); jf.setResizable(false); jf.setBackground(Color.DARK_GRAY); java.awt.FlowLayout f1=new java.awt.FlowLayout(); jf.setLayout(f1); JLabel input=new JLabel("輸入"); jf.add(input); JTextField inputcontent=new JTextField(30); jf.add(inputcontent); JLabel output=new JLabel("輸出"); jf.add(output); JTextField outputcontent=new JTextField(30); jf.add(outputcontent); JButton change=new JButton("加密"); jf.add(change); MD5Listener md5=new MD5Listener(inputcontent,outputcontent); change.addActionListener(md5); jf.setVisible(true); }

監聽程序：

package com.oop.lhw0524;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import javax.swing.JTextField;public class MD5Listener implements ActionListener { private JTextField inputcontent; private JTextField outputcontent; public MD5Listener(JTextField f1, JTextField f2) { inputcontent = f1; outputcontent = f2; } public void actionPerformed(ActionEvent e) { String str = MD5.getInstance().getMD5(inputcontent.getText()); outputcontent.setText(str); System.out.println(str); }}