随笔-153  评论-235  文章-19  trackbacks-0
MD5
收集于网络


MD5简介:

MD5
的全称是Message-Digest Algorithm 5,在90年代初由MIT的计算机科学实验室和RSA Data Security Inc发明,经MD2MD3MD4发展而来。

Message-Digest
泛指字节串(Message)Hash变换,就是把一个任意长度的字节串变换成一定长的大整数。请注意我使用了字节串而不是字符串这个词,是因为这种变换只与字节的值有关,与字符集或编码方式无关。

MD5
将任意长度的字节串变换成一个128bit的大整数,并且它是一个不可逆的字符串变换算法,(我刚开始还愚蠢的认为MD5是可逆的算法感谢Stkman大哥的讲解)换句话说就是,即使你看到源程序和算法描述,也无法将一个MD5的值变换回原始的字符串,从数学原理上说,是因为原始的字符串有无穷多个,这有点象不存在反函数的数学函数。

MD5
的典型应用是对一段Message(字节串)产生fingerprint(指纹),以防止被篡改。举个例子,你将一段话写在一个叫readme.txt文件中,并对这个readme.txt产生一个MD5的值并记录在案,然后你可以传播这个文件给别人,别人如果修改了文件中的任何内容,你对这个文件重新计算MD5时就会发现。如果再有一个第三方的认证机构,用MD5还可以防止文件作者的抵赖,这就是所谓的数字签名应用。

MD5
还广泛用于加密和解密技术上,在很多操作系统中,用户的密码是以MD5值(或类似的其它算法)的方式保存的,用户Login的时候,系统是把用户输入的密码计算成MD5值,然后再去和系统中保存的MD5值进行比较,而系统并不知道用户的密码是什么。

一些黑客破获这种密码的方法是一种被称为跑字典的方法。有两种方法得到字典,一种是日常搜集的用做密码的字符串表,另一种是用排列组合方法生成的,先用MD5程序计算出这些字典项的MD5值,然后再用目标的MD5值在这个字典中检索。

即使假设密码的最大长度为8,同时密码只能是字母和数字,共26+26+10=62个字符,排列组合出的字典的项数则是P(62,1)+P(62,2)….+P(62,8),那也已经是一个很天文的数字了,存储这个字典就需要TB级的磁盘组,而且这种方法还有一个前提,就是能获得目标账户的密码MD5值的情况下才可以。

在软件的加密保护中 很多软件采用MD5保护 但是由于MD5算法为不可逆算法所以所有的软件都是使用MD5算法作为一个加密的中间步骤,比如对用户名做一个MD5变换,结果再进行一个可逆的加密变换,做注册机时也只要先用MD5变换,然后再用一个逆算法。所以对于破解者来说只要能看出是MD5就很容易了。

MD5
代码的特点明显,跟踪时很容易发现,如果软件采用MD5算法,在数据初始化的时候必然用到以下的四个常数
0x67452301;
0xefcdab89;
0x98badcfe;
0x10325476;
若常数不等 则可能是变形的MD5算法 或者根本就不是这个算法。在内存了也就是
01 23 45 67 89 ab cd ef fe dc ......32 10 16
个字节
————————————————————————————————————————————

MD5
算法:

第一步:增加填充
增加padding使得数据长度(bit为单位)模512448。如果数据长度正好是模512448,增加512个填充bit,也就是说填充的个数为1-512。第一个bit1,其余全部为0
第二步:补足长度
将数据长度转换为64bit的数值,如果长度超过64bit所能表示的数据长度的范围,值保留最后64bit,增加到前面填充的数据后面,使得最后的数据为512bit的整数倍。也就是32bit16倍的整数倍。在RFC1321中,32bit称为一个word
第三步:初始化变量:
用到4个变量,分别为ABCD,均为32bit长。初始化为:
A: 01 23 45 67
B: 89 ab cd ef
C: fe dc ba 98
D: 76 54 32 10
第四步:数据处理:
首先定义4个辅助函数:
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))
其中:XY表示按位与,X v Y表示按位或,not(X)表示按位取反。xor表示按位异或。
函数中的XYZ均为32bit

定义一个需要用到的数组:T(i),i取值1-64,T(i)等于abs(sin(i))4294967296倍的整数部分,i为弧度。
假设前三步处理后的数据长度为32*16*Nbit

第五步:输出:
最后得到的ABCD为输出结果,共128bitA为低位,D为高位。


MD5在编程中的实现--JAVA



/************************************************
MD5 算法的Java Bean
************************************************
*/
import java.lang.reflect.*;
/*************************************************
md5 类实现了RSA Data Security, Inc.在提交给IETF
的RFC1321中的MD5 message-digest 算法。
************************************************
*/

public class MD5 {
    
/* 下面这些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 = { -12800000000,
        
000000000000000000,
        
000000000000000000,
        
0000000000000000000 };
        
/* 下面的三个成员是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 MD5() {
                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;
        }

        
public static void main(String args[]) {


                MD5 m 
= new MD5();
                
if (Array.getLength(args) == 0) {   //如果没有参数,执行标准的Test Suite

                           System.out.println(
"MD5 Test suite:");
                    System.out.println(
"MD5(\"\"):"+m.getMD5ofStr(""));
                    System.out.println(
"MD5(\"a\"):"+m.getMD5ofStr("a"));
                    System.out.println(
"MD5(\"abc\"):"+m.getMD5ofStr("abc"));
                    System.out.println(
"MD5(\"message digest\"):"+m.getMD5ofStr("message digest"));
                    System.out.println(
"MD5(\"abcdefghijklmnopqrstuvwxyz\"):"+
                        m.getMD5ofStr(
"abcdefghijklmnopqrstuvwxyz"));
                    System.out.println(
"MD5(\"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\"):"+
                         m.getMD5ofStr(
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"));
                    
                    
                }
                
else
                          System.out.println(
"MD5(" + args[0+ ")=" + m.getMD5ofStr(args[0]));


                String a
=m.getMD5ofStr(new String("jkz"));
                System.out.print(a
+" "+a.equals(m.getMD5ofStr(new String("aaaa"))));
        }

}



posted on 2006-11-24 21:12 流浪汗 阅读(801) 评论(0)  编辑  收藏 所属分类: Java

只有注册用户登录后才能发表评论。


网站导航: