MD5算法--网盘秒传

　　在用网盘传东西的时候，突然发现传某些几个G的文件竟然几秒钟就传到网盘上去了，刚开始还以为是传送发生了错误，然后又重复传了几次还是一样。然后上网一查，看到知乎上的一个提问的讨论查了些网上的资料才明白其中原理。

　　对于网盘服务器上的每一个文件，服务器上都存有一个相应的唯一的特征值，然后当你从客户端传文件到网盘上时，会先计算你要传的文件的特征值，然后与服务器中存的对比，发现相同特征值则表明你要传的文件在服务器上已经存在，这时就实现秒传了。

　　那这个唯一的特征值是如何计算的呢？不部分是用MD5算法。

　　MD5算法功能就是对于你传入的一个任意长度的数据（其实根据算法的原理应该小于2的64次方bit，这个在目前的文件来说已经是无穷大了），然后经过处理，产生一个“唯一”的128位的信息。而且这个过程是不可逆的，也即你不能通过这个128位信息反推出原数据。

1、MD5算法的历史

　　1992年8月Ronald L. Rivest在向IETF提交了一份重要文件，描述了这种算法的原理，由于这种算法的公开性和安全性，在90年代被广泛使用在各种程序语言中，用以确保资料传递无误等。MD5由MD4、MD3、MD2改进而来，主要增强算法复杂度和不可逆性

　　MD5较老，散列长度通常为128位，随着计算机运算能力提高，找到“碰撞”是可能的。因此，在少数安全要求高的场合不使用MD5。

　　2004年，中国数学家王小云证明MD5数字签名算法可以产生碰撞。2007年，Marc Stevens，Arjen K. Lenstra和Benne de Weger进一步指出通过伪造软件签名，可重复性攻击MD5算法。研究者使用前缀碰撞法（chosen-prefix collision），使程序前端包含恶意程序，利用后面的空间添上垃圾代码凑出同样的MD5 哈希值。

2、MD5算法的原理 (摘自: http://blog.csdn.net/forgotaboutgirl/article/details/7258109)

MD5算法过程：
    对MD5算法简要的叙述可以为：MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。

     第一步、填充：如果输入信息的长度(bit)对512求余的结果不等于448，就需要填充使得对512求余的结果等于448。填充的方法是填充一个1和n个0。填充完后，信息的长度就为N*512+448(bit)；

     第二步、记录信息长度：用64位来存储填充前信息长度。这64位加在第一步结果的后面，这样信息长度就变为N*512+448+64=(N+1)*512位。

     第三步、装入标准的幻数（四个整数）：标准的幻数（物理顺序）是（A=(01234567)₁₆，B=(89ABCDEF)₁₆，C=(FEDCBA98)₁₆，D=(76543210)₁₆）。如果在程序中定义应该是（A=0X67452301L，B=0XEFCDAB89L，C=0X98BADCFEL，D=0X10325476L）。有点晕哈，其实想一想就明白了。

     第四步、四轮循环运算：循环的次数是分组的个数（N+1）

     1）将每一512字节细分成16个小组，每个小组64位（8个字节）

     2）先认识四个线性函数(&是与,|是或,~是非,^是异或)

  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))

3）设Mj表示消息的第j个子分组（从0到15），<<<s表示循环左移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)

4）四轮运算

第一轮
a=FF(a,b,c,d,M0,7,0xd76aa478)
b=FF(d,a,b,c,M1,12,0xe8c7b756)
c=FF(c,d,a,b,M2,17,0x242070db)
d=FF(b,c,d,a,M3,22,0xc1bdceee)
a=FF(a,b,c,d,M4,7,0xf57c0faf)
b=FF(d,a,b,c,M5,12,0x4787c62a)
c=FF(c,d,a,b,M6,17,0xa8304613)
d=FF(b,c,d,a,M7,22,0xfd469501)
a=FF(a,b,c,d,M8,7,0x698098d8)
b=FF(d,a,b,c,M9,12,0x8b44f7af)
c=FF(c,d,a,b,M10,17,0xffff5bb1)
d=FF(b,c,d,a,M11,22,0x895cd7be)
a=FF(a,b,c,d,M12,7,0x6b901122)
b=FF(d,a,b,c,M13,12,0xfd987193)
c=FF(c,d,a,b,M14,17,0xa679438e)
d=FF(b,c,d,a,M15,22,0x49b40821)

第二轮
a=GG(a,b,c,d,M1,5,0xf61e2562)
b=GG(d,a,b,c,M6,9,0xc040b340)
c=GG(c,d,a,b,M11,14,0x265e5a51)
d=GG(b,c,d,a,M0,20,0xe9b6c7aa)
a=GG(a,b,c,d,M5,5,0xd62f105d)
b=GG(d,a,b,c,M10,9,0x02441453)
c=GG(c,d,a,b,M15,14,0xd8a1e681)
d=GG(b,c,d,a,M4,20,0xe7d3fbc8)
a=GG(a,b,c,d,M9,5,0x21e1cde6)
b=GG(d,a,b,c,M14,9,0xc33707d6)
c=GG(c,d,a,b,M3,14,0xf4d50d87)
d=GG(b,c,d,a,M8,20,0x455a14ed)
a=GG(a,b,c,d,M13,5,0xa9e3e905)
b=GG(d,a,b,c,M2,9,0xfcefa3f8)
c=GG(c,d,a,b,M7,14,0x676f02d9)
d=GG(b,c,d,a,M12,20,0x8d2a4c8a)

第三轮
a=HH(a,b,c,d,M5,4,0xfffa3942)
b=HH(d,a,b,c,M8,11,0x8771f681)
c=HH(c,d,a,b,M11,16,0x6d9d6122)
d=HH(b,c,d,a,M14,23,0xfde5380c)
a=HH(a,b,c,d,M1,4,0xa4beea44)
b=HH(d,a,b,c,M4,11,0x4bdecfa9)
c=HH(c,d,a,b,M7,16,0xf6bb4b60)
d=HH(b,c,d,a,M10,23,0xbebfbc70)
a=HH(a,b,c,d,M13,4,0x289b7ec6)
b=HH(d,a,b,c,M0,11,0xeaa127fa)
c=HH(c,d,a,b,M3,16,0xd4ef3085)
d=HH(b,c,d,a,M6,23,0x04881d05)
a=HH(a,b,c,d,M9,4,0xd9d4d039)
b=HH(d,a,b,c,M12,11,0xe6db99e5)
c=HH(c,d,a,b,M15,16,0x1fa27cf8)
d=HH(b,c,d,a,M2,23,0xc4ac5665)

第四轮
a=II(a,b,c,d,M0,6,0xf4292244)
b=II(d,a,b,c,M7,10,0x432aff97)
c=II(c,d,a,b,M14,15,0xab9423a7)
d=II(b,c,d,a,M5,21,0xfc93a039)
a=II(a,b,c,d,M12,6,0x655b59c3)
b=II(d,a,b,c,M3,10,0x8f0ccc92)
c=II(c,d,a,b,M10,15,0xffeff47d)
d=II(b,c,d,a,M1,21,0x85845dd1)
a=II(a,b,c,d,M8,6,0x6fa87e4f)
b=II(d,a,b,c,M15,10,0xfe2ce6e0)
c=II(c,d,a,b,M6,15,0xa3014314)
d=II(b,c,d,a,M13,21,0x4e0811a1)
a=II(a,b,c,d,M4,6,0xf7537e82)
b=II(d,a,b,c,M11,10,0xbd3af235)
c=II(c,d,a,b,M2,15,0x2ad7d2bb)
d=II(b,c,d,a,M9,21,0xeb86d391)

5）每轮循环后，将A，B，C，D分别加上a，b，c，d，然后进入下一循环。

3、MD5算法的java实现 (摘自: http://blog.csdn.net/forgotaboutgirl/article/details/7258109)

  1 /************************************************
  2  * MD5 算法
  3  * @author 我行我素
  4  * @Date 2007-07-01
  5 *************************************************/
  6 public class MD5 {
  7 
  8     static final String hexs[]={"0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F"};
  9     //标准的幻数
 10     private static final long A=0x67452301L;
 11     private static final long B=0xefcdab89L;
 12     private static final long C=0x98badcfeL;
 13     private static final long D=0x10325476L;
 14 
 15     
 16     //下面这些S11-S44实际上是一个4*4的矩阵，在四轮循环运算中用到
 17     static final int S11 = 7;
 18     static final int S12 = 12;
 19     static final int S13 = 17;
 20     static final int S14 = 22;
 21 
 22     static final int S21 = 5;
 23     static final int S22 = 9;
 24     static final int S23 = 14;
 25     static final int S24 = 20;
 26 
 27     static final int S31 = 4;
 28     static final int S32 = 11;
 29     static final int S33 = 16;
 30     static final int S34 = 23;
 31 
 32     static final int S41 = 6;
 33     static final int S42 = 10;
 34     static final int S43 = 15;
 35     static final int S44 = 21;
 36     
 37     //java不支持无符号的基本数据（unsigned）
 38     private long [] result={A,B,C,D};//存储hash结果，共4×32=128位，初始化值为（幻数的级联）
 39     
 40     public static void main(String []args){
 41         MD5 md=new MD5();
 42         System.out.println("md5(abc)="+md.digest("abc"));
 43     }
 44     
 45     private String digest(String inputStr){
 46         byte [] inputBytes=inputStr.getBytes();
 47         int byteLen=inputBytes.length;//长度（字节）
 48         int groupCount=0;//完整分组的个数
 49         groupCount=byteLen/64;//每组512位（64字节）
 50         long []groups=null;//每个小组(64字节)再细分后的16个小组(4字节)
 51         
 52         //处理每一个完整 分组
 53         for(int step=0;step<groupCount;step++){
 54             groups=divGroup(inputBytes,step*64);
 55             trans(groups);//处理分组，核心算法
 56         }
 57         
 58         //处理完整分组后的尾巴
 59         int rest=byteLen%64;//512位分组后的余数
 60         byte [] tempBytes=new byte[64];
 61         if(rest<=56){
 62             for(int i=0;i<rest;i++)
 63                 tempBytes[i]=inputBytes[byteLen-rest+i];
 64             if(rest<56){
 65                 tempBytes[rest]=(byte)(1<<7);
 66                 for(int i=1;i<56-rest;i++)
 67                     tempBytes[rest+i]=0;
 68             }
 69             long len=(long)(byteLen<<3);
 70             for(int i=0;i<8;i++){
 71                 tempBytes[56+i]=(byte)(len&0xFFL);
 72                 len=len>>8;
 73             }
 74             groups=divGroup(tempBytes,0);
 75             trans(groups);//处理分组
 76         }else{
 77             for(int i=0;i<rest;i++)
 78                 tempBytes[i]=inputBytes[byteLen-rest+i];
 79             tempBytes[rest]=(byte)(1<<7);
 80             for(int i=rest+1;i<64;i++)
 81                 tempBytes[i]=0;
 82             groups=divGroup(tempBytes,0);
 83             trans(groups);//处理分组
 84             
 85             for(int i=0;i<56;i++)
 86                 tempBytes[i]=0;
 87             long len=(long)(byteLen<<3);
 88             for(int i=0;i<8;i++){
 89                 tempBytes[56+i]=(byte)(len&0xFFL);
 90                 len=len>>8;
 91             }
 92             groups=divGroup(tempBytes,0);
 93             trans(groups);//处理分组
 94         }
 95         
 96         //将Hash值转换成十六进制的字符串
 97         String resStr="";
 98         long temp=0;
 99         for(int i=0;i<4;i++){
100             for(int j=0;j<4;j++){
101                 temp=result[i]&0x0FL;
102                 String a=hexs[(int)(temp)];
103                 result[i]=result[i]>>4;
104                 temp=result[i]&0x0FL;
105                 resStr+=hexs[(int)(temp)]+a;
106                 result[i]=result[i]>>4;
107             }
108         }
109         return resStr;
110     }
111     
112     /**
113      * 从inputBytes的index开始取512位，作为新的分组
114      * 将每一个512位的分组再细分成16个小组，每个小组64位（8个字节）
115      * @param inputBytes
116      * @param index
117      * @return
118      */
119     private static long[] divGroup(byte[] inputBytes,int index){
120         long [] temp=new long[16];
121         for(int i=0;i<16;i++){
122             temp[i]=b2iu(inputBytes[4*i+index])|
123                 (b2iu(inputBytes[4*i+1+index]))<<8|
124                 (b2iu(inputBytes[4*i+2+index]))<<16|
125                 (b2iu(inputBytes[4*i+3+index]))<<24;
126         }
127         return temp;
128     }
129     
130     /**
131      * 这时不存在符号位（符号位存储不再是代表正负），所以需要处理一下
132      * @param b
133      * @return
134      */
135     public static long b2iu(byte b){
136         return b < 0 ? b & 0x7F + 128 : b;
137      }
138     
139     /**
140      * 主要的操作，四轮循环
141      * @param groups[]--每一个分组512位（64字节）
142      */
143     private void trans(long[] groups) {
144         long a = result[0], b = result[1], c = result[2], d = result[3];
145         /*第一轮*/
146         a = FF(a, b, c, d, groups[0], S11, 0xd76aa478L); /* 1 */
147         d = FF(d, a, b, c, groups[1], S12, 0xe8c7b756L); /* 2 */
148         c = FF(c, d, a, b, groups[2], S13, 0x242070dbL); /* 3 */
149         b = FF(b, c, d, a, groups[3], S14, 0xc1bdceeeL); /* 4 */
150         a = FF(a, b, c, d, groups[4], S11, 0xf57c0fafL); /* 5 */
151         d = FF(d, a, b, c, groups[5], S12, 0x4787c62aL); /* 6 */
152         c = FF(c, d, a, b, groups[6], S13, 0xa8304613L); /* 7 */
153         b = FF(b, c, d, a, groups[7], S14, 0xfd469501L); /* 8 */
154         a = FF(a, b, c, d, groups[8], S11, 0x698098d8L); /* 9 */
155         d = FF(d, a, b, c, groups[9], S12, 0x8b44f7afL); /* 10 */
156         c = FF(c, d, a, b, groups[10], S13, 0xffff5bb1L); /* 11 */
157         b = FF(b, c, d, a, groups[11], S14, 0x895cd7beL); /* 12 */
158         a = FF(a, b, c, d, groups[12], S11, 0x6b901122L); /* 13 */
159         d = FF(d, a, b, c, groups[13], S12, 0xfd987193L); /* 14 */
160         c = FF(c, d, a, b, groups[14], S13, 0xa679438eL); /* 15 */
161         b = FF(b, c, d, a, groups[15], S14, 0x49b40821L); /* 16 */
162 
163         /*第二轮*/
164         a = GG(a, b, c, d, groups[1], S21, 0xf61e2562L); /* 17 */
165         d = GG(d, a, b, c, groups[6], S22, 0xc040b340L); /* 18 */
166         c = GG(c, d, a, b, groups[11], S23, 0x265e5a51L); /* 19 */
167         b = GG(b, c, d, a, groups[0], S24, 0xe9b6c7aaL); /* 20 */
168         a = GG(a, b, c, d, groups[5], S21, 0xd62f105dL); /* 21 */
169         d = GG(d, a, b, c, groups[10], S22, 0x2441453L); /* 22 */
170         c = GG(c, d, a, b, groups[15], S23, 0xd8a1e681L); /* 23 */
171         b = GG(b, c, d, a, groups[4], S24, 0xe7d3fbc8L); /* 24 */
172         a = GG(a, b, c, d, groups[9], S21, 0x21e1cde6L); /* 25 */
173         d = GG(d, a, b, c, groups[14], S22, 0xc33707d6L); /* 26 */
174         c = GG(c, d, a, b, groups[3], S23, 0xf4d50d87L); /* 27 */
175         b = GG(b, c, d, a, groups[8], S24, 0x455a14edL); /* 28 */
176         a = GG(a, b, c, d, groups[13], S21, 0xa9e3e905L); /* 29 */
177         d = GG(d, a, b, c, groups[2], S22, 0xfcefa3f8L); /* 30 */
178         c = GG(c, d, a, b, groups[7], S23, 0x676f02d9L); /* 31 */
179         b = GG(b, c, d, a, groups[12], S24, 0x8d2a4c8aL); /* 32 */
180 
181         /*第三轮*/
182         a = HH(a, b, c, d, groups[5], S31, 0xfffa3942L); /* 33 */
183         d = HH(d, a, b, c, groups[8], S32, 0x8771f681L); /* 34 */
184         c = HH(c, d, a, b, groups[11], S33, 0x6d9d6122L); /* 35 */
185         b = HH(b, c, d, a, groups[14], S34, 0xfde5380cL); /* 36 */
186         a = HH(a, b, c, d, groups[1], S31, 0xa4beea44L); /* 37 */
187         d = HH(d, a, b, c, groups[4], S32, 0x4bdecfa9L); /* 38 */
188         c = HH(c, d, a, b, groups[7], S33, 0xf6bb4b60L); /* 39 */
189         b = HH(b, c, d, a, groups[10], S34, 0xbebfbc70L); /* 40 */
190         a = HH(a, b, c, d, groups[13], S31, 0x289b7ec6L); /* 41 */
191         d = HH(d, a, b, c, groups[0], S32, 0xeaa127faL); /* 42 */
192         c = HH(c, d, a, b, groups[3], S33, 0xd4ef3085L); /* 43 */
193         b = HH(b, c, d, a, groups[6], S34, 0x4881d05L); /* 44 */
194         a = HH(a, b, c, d, groups[9], S31, 0xd9d4d039L); /* 45 */
195         d = HH(d, a, b, c, groups[12], S32, 0xe6db99e5L); /* 46 */
196         c = HH(c, d, a, b, groups[15], S33, 0x1fa27cf8L); /* 47 */
197         b = HH(b, c, d, a, groups[2], S34, 0xc4ac5665L); /* 48 */
198 
199         /*第四轮*/
200         a = II(a, b, c, d, groups[0], S41, 0xf4292244L); /* 49 */
201         d = II(d, a, b, c, groups[7], S42, 0x432aff97L); /* 50 */
202         c = II(c, d, a, b, groups[14], S43, 0xab9423a7L); /* 51 */
203         b = II(b, c, d, a, groups[5], S44, 0xfc93a039L); /* 52 */
204         a = II(a, b, c, d, groups[12], S41, 0x655b59c3L); /* 53 */
205         d = II(d, a, b, c, groups[3], S42, 0x8f0ccc92L); /* 54 */
206         c = II(c, d, a, b, groups[10], S43, 0xffeff47dL); /* 55 */
207         b = II(b, c, d, a, groups[1], S44, 0x85845dd1L); /* 56 */
208         a = II(a, b, c, d, groups[8], S41, 0x6fa87e4fL); /* 57 */
209         d = II(d, a, b, c, groups[15], S42, 0xfe2ce6e0L); /* 58 */
210         c = II(c, d, a, b, groups[6], S43, 0xa3014314L); /* 59 */
211         b = II(b, c, d, a, groups[13], S44, 0x4e0811a1L); /* 60 */
212         a = II(a, b, c, d, groups[4], S41, 0xf7537e82L); /* 61 */
213         d = II(d, a, b, c, groups[11], S42, 0xbd3af235L); /* 62 */
214         c = II(c, d, a, b, groups[2], S43, 0x2ad7d2bbL); /* 63 */
215         b = II(b, c, d, a, groups[9], S44, 0xeb86d391L); /* 64 */
216 
217         /*加入到之前计算的结果当中*/
218         result[0] += a;
219         result[1] += b;
220         result[2] += c;
221         result[3] += d;
222         result[0]=result[0]&0xFFFFFFFFL;
223         result[1]=result[1]&0xFFFFFFFFL;
224         result[2]=result[2]&0xFFFFFFFFL;
225         result[3]=result[3]&0xFFFFFFFFL;
226     }
227     
228     /**
229      * 下面是处理要用到的线性函数
230      */
231     private static long F(long x, long y, long z) {
232         return (x & y) | ((~x) & z);
233     }
234 
235     private static long G(long x, long y, long z) {
236         return (x & z) | (y & (~z));
237     }
238 
239     private static long H(long x, long y, long z) {
240         return x ^ y ^ z;
241     }
242 
243     private static long I(long x, long y, long z) {
244         return y ^ (x | (~z));
245     }
246 
247     private static long FF(long a, long b, long c, long d, long x, long s,
248             long ac) {
249         a += (F(b, c, d)&0xFFFFFFFFL) + x + ac;
250         a = ((a&0xFFFFFFFFL)<< s) | ((a&0xFFFFFFFFL) >>> (32 - s));
251         a += b;
252         return (a&0xFFFFFFFFL);
253     }
254 
255     private static long GG(long a, long b, long c, long d, long x, long s,
256             long ac) {
257         a += (G(b, c, d)&0xFFFFFFFFL) + x + ac;
258         a = ((a&0xFFFFFFFFL) << s) | ((a&0xFFFFFFFFL) >>> (32 - s));
259         a += b;
260         return (a&0xFFFFFFFFL);
261     }
262 
263     private static long HH(long a, long b, long c, long d, long x, long s,
264             long ac) {
265         a += (H(b, c, d)&0xFFFFFFFFL) + x + ac;
266         a = ((a&0xFFFFFFFFL) << s) | ((a&0xFFFFFFFFL) >>> (32 - s));
267         a += b;
268         return (a&0xFFFFFFFFL);
269     }
270 
271     private static long II(long a, long b, long c, long d, long x, long s,
272             long ac) {
273         a += (I(b, c, d)&0xFFFFFFFFL) + x + ac;
274         a = ((a&0xFFFFFFFFL) << s) | ((a&0xFFFFFFFFL) >>> (32 - s));
275         a += b;
276         return (a&0xFFFFFFFFL);
277     }
278 }