【编程开发】MD5算法原理

MD5（单向散列算法）的全称是Message-Digest
Algorithm 5（信息-摘要算法），经MD2、MD3和MD4发展而来。MD5算法的使用不需要支付任何版权费用。



    MD5功能：

    输入任意长度的信息，经过处理，输出为128位的信息（数字指纹）；

    不同的输入得到的不同的结果（唯一性）；

    根据128位的输出结果不可能反推出输入的信息（不可逆）； 



    MD5属不属于加密算法：

    认为不属于的人是因为他们觉得不能从密文（散列值）反过来得到原文，即没有解密算法，所以这部分人认为MD5只能属于算法，不能称为加密算法；

    认为属于的人是因为他们觉得经过MD5处理后看不到原文，即已经将原文加密，所以认为MD5属于加密算法；我个人支持后者。



    MD5用途：

    1、防止被篡改：

    1）比如发送一个电子文档，发送前，我先得到MD5的输出结果a。然后在对方收到电子文档后，对方也得到一个MD5的输出结果b。如果a与b一样就代表中途未被篡改。2）比如我提供文件下载，为了防止不法分子在安装程序中添加木马，我可以在网站上公布由安装文件得到的MD5输出结果。3）SVN在检测文件是否在CheckOut后被修改过，也是用到了MD5.



    2、防止直接看到明文：

    现在很多网站在数据库存储用户的密码的时候都是存储用户密码的MD5值。这样就算不法分子得到数据库的用户密码的MD5值，也无法知道用户的密码(其实这样是不安全的，后面我会提到)。（比如在UNIX系统中用户的密码就是以MD5（或其它类似的算法）经加密后存储在文件系统中。当用户登录的时候，系统把用户输入的密码计算成MD5值，然后再去和保存在文件系统中的MD5值进行比较，进而确定输入的密码是否正确。通过这样的步骤，系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。这不但可以避免用户的密码被具有系统管理员权限的用户知道，而且还在一定程度上增加了密码被破解的难度。）



    3、防止抵赖（数字签名）：

    这需要一个第三方认证机构。例如A写了一个文件，认证机构对此文件用MD5算法产生摘要信息并做好记录。若以后A说这文件不是他写的，权威机构只需对此文件重新产生摘要信息，然后跟记录在册的摘要信息进行比对，相同的话，就证明是A写的了。这就是所谓的“数字签名”。



    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,0xd76aa478)

b,0xe8c7b756)

c,0x242070db)

d,0xc1bdceee)

a,0xf57c0faf)

b,0x4787c62a)

c,0xa8304613)

d,0xfd469501)

a,0x698098d8)

b,0x8b44f7af)

c,0xffff5bb1)

d,0x895cd7be)

a,0x6b901122)

b,0xfd987193)

c,0xa679438e)

d,0x49b40821)



第二轮

a,0xf61e2562)

b,0xc040b340)

c,0x265e5a51)

d,0xe9b6c7aa)

a,0xd62f105d)

b,0x02441453)

c,0xd8a1e681)

d,0xe7d3fbc8)

a,0x21e1cde6)

b,0xc33707d6)

c,0xf4d50d87)

d,0x455a14ed)

a,0xa9e3e905)

b,0xfcefa3f8)

c,0x676f02d9)

d,0x8d2a4c8a)



第三轮

a,0xfffa3942)

b,0x8771f681)

c,0x6d9d6122)

d,0xfde5380c)

a,0xa4beea44)

b,0x4bdecfa9)

c,0xf6bb4b60)

d,0xbebfbc70)

a,0x289b7ec6)

b,0xeaa127fa)

c,0xd4ef3085)

d,0x04881d05)

a,0xd9d4d039)

b,0xe6db99e5)

c,0x1fa27cf8)

d,0xc4ac5665)



第四轮

a,0xf4292244)

b,0x432aff97)

c,0xab9423a7)

d,0xfc93a039)

a,0x655b59c3)

b,0x8f0ccc92)

c,0xffeff47d)

d,0x85845dd1)

a,0x6fa87e4f)

b,0xfe2ce6e0)

c,0xa3014314)

d,0x4e0811a1)

a,0xf7537e82)

b,0xbd3af235)

c,0x2ad7d2bb)

d,0xeb86d391)

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

 

    如果上面的过程用JAVA代码来实现的话，代码如下：

package woxingwosu;





/************************************************

 * MD5 算法

 * @author 我行我素

 * @Date 2007-07-01

*************************************************/

public class MD5 {



    ","A","B","C","D","E","F"};

    //标准的幻数

    private static final long A=0x67452301L;

    private static final long B=0xefcdab89L;

    private static final long C=0x98badcfeL;

    private static final long D=0x10325476L;



    

    //下面这些S11-S44实际上是一个4*4的矩阵，在四轮循环运算中用到

;

    ;

    ;

    ;



    ;

    ;

    ;

    ;



    ;

    ;

    ;

    ;



    ;

    ;

    ;

    ;

    

    //java不支持无符号的基本数据（unsigned）

    private long [] result={A,B,C,D};//存储hash结果，共4×32=128位，初始化值为（幻数的级联）

    

    public static void main(String []args){

        MD5 md=new MD5();

        System.out.println("md5(abc)="+md.digest("abc"));

    }

    

    private String digest(String inputStr){

        byte [] inputBytes=inputStr.getBytes();

        int byteLen=inputBytes.length;//长度（字节）

;//完整分组的个数

;//每组512位（64字节）

        long []groups=null;//每个小组(64字节)再细分后的16个小组(4字节)

        

        //处理每一个完整 分组

;step<groupCount;step++){

            groups);

            trans(groups);//处理分组，核心算法

        }

        

        //处理完整分组后的尾巴

;//512位分组后的余数

];

        ){

            ;i<rest;i++)

                tempBytes[i]=inputBytes[byteLen-rest+i];

            ){

                tempBytes[rest]);

                -rest;i++)

                    tempBytes[rest;

            }

            );

            ;i++){

                tempBytes[+i]=(byte)(len&0xFFL);

                len;

            }

            groups);

            trans(groups);//处理分组

        }else{

            ;i<rest;i++)

                tempBytes[i]=inputBytes[byteLen-rest+i];

            tempBytes[rest]);

            ;i++)

                tempBytes[i];

            groups);

            trans(groups);//处理分组

            

            ;i++)

                tempBytes[i];

            );

            ;i++){

                tempBytes[+i]=(byte)(len&0xFFL);

                len;

            }

            groups);

            trans(groups);//处理分组

        }

        

        //将Hash值转换成十六进制的字符串

        String resStr="";

        ;

        ;i++){

            ;j++){

                temp=result[i]&0x0FL;

                String a=hexs[(int)(temp)];

                result[i];

                temp=result[i]&0x0FL;

                resStr+=hexs[(int)(temp)]+a;

                result[i];

            }

        }

        return resStr;

    }

    

    /**

     * 从inputBytes的index开始取512位，作为新的分组

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

     * @param inputBytes

     * @param index

     * @return

     */

    private static long[] divGroup(byte[] inputBytes,int index){

        ];

        ;i++){

            temp[i]*i+index])|

                (b2iu(inputBytes[|

                (b2iu(inputBytes[|

                (b2iu(inputBytes[;

        }

        return temp;

    }

    

    /**

     * 这时不存在符号位（符号位存储不再是代表正负），所以需要处理一下

     * @param b

     * @return

     */

    public static long b2iu(byte b){

         : b;

     }

    

    /**

     * 主要的操作，四轮循环

     * @param groups[]--每一个分组512位（64字节）

     */

    private void trans(long[] groups) {

        ];

        /*第一轮*/

        a ], S11, 0xd76aa478L); /* 1 */

        d ], S12, 0xe8c7b756L); /* 2 */

        c ], S13, 0x242070dbL); /* 3 */

        b ], S14, 0xc1bdceeeL); /* 4 */

        a ], S11, 0xf57c0fafL); /* 5 */

        d ], S12, 0x4787c62aL); /* 6 */

        c ], S13, 0xa8304613L); /* 7 */

        b ], S14, 0xfd469501L); /* 8 */

        a ], S11, 0x698098d8L); /* 9 */

        d ], S12, 0x8b44f7afL); /* 10 */

        c ], S13, 0xffff5bb1L); /* 11 */

        b ], S14, 0x895cd7beL); /* 12 */

        a ], S11, 0x6b901122L); /* 13 */

        d ], S12, 0xfd987193L); /* 14 */

        c ], S13, 0xa679438eL); /* 15 */

        b ], S14, 0x49b40821L); /* 16 */



        /*第二轮*/

        a ], S21, 0xf61e2562L); /* 17 */

        d ], S22, 0xc040b340L); /* 18 */

        c ], S23, 0x265e5a51L); /* 19 */

        b ], S24, 0xe9b6c7aaL); /* 20 */

        a ], S21, 0xd62f105dL); /* 21 */

        d ], S22, 0x2441453L); /* 22 */

        c ], S23, 0xd8a1e681L); /* 23 */

        b ], S24, 0xe7d3fbc8L); /* 24 */

        a ], S21, 0x21e1cde6L); /* 25 */

        d ], S22, 0xc33707d6L); /* 26 */

        c ], S23, 0xf4d50d87L); /* 27 */

        b ], S24, 0x455a14edL); /* 28 */

        a ], S21, 0xa9e3e905L); /* 29 */

        d ], S22, 0xfcefa3f8L); /* 30 */

        c ], S23, 0x676f02d9L); /* 31 */

        b ], S24, 0x8d2a4c8aL); /* 32 */



        /*第三轮*/

        a ], S31, 0xfffa3942L); /* 33 */

        d ], S32, 0x8771f681L); /* 34 */

        c ], S33, 0x6d9d6122L); /* 35 */

        b ], S34, 0xfde5380cL); /* 36 */

        a ], S31, 0xa4beea44L); /* 37 */

        d ], S32, 0x4bdecfa9L); /* 38 */

        c ], S33, 0xf6bb4b60L); /* 39 */

        b ], S34, 0xbebfbc70L); /* 40 */

        a ], S31, 0x289b7ec6L); /* 41 */

        d ], S32, 0xeaa127faL); /* 42 */

        c ], S33, 0xd4ef3085L); /* 43 */

        b ], S34, 0x4881d05L); /* 44 */

        a ], S31, 0xd9d4d039L); /* 45 */

        d ], S32, 0xe6db99e5L); /* 46 */

        c ], S33, 0x1fa27cf8L); /* 47 */

        b ], S34, 0xc4ac5665L); /* 48 */



        /*第四轮*/

        a ], S41, 0xf4292244L); /* 49 */

        d ], S42, 0x432aff97L); /* 50 */

        c ], S43, 0xab9423a7L); /* 51 */

        b ], S44, 0xfc93a039L); /* 52 */

        a ], S41, 0x655b59c3L); /* 53 */

        d ], S42, 0x8f0ccc92L); /* 54 */

        c ], S43, 0xffeff47dL); /* 55 */

        b ], S44, 0x85845dd1L); /* 56 */

        a ], S41, 0x6fa87e4fL); /* 57 */

        d ], S42, 0xfe2ce6e0L); /* 58 */

        c ], S43, 0xa3014314L); /* 59 */

        b ], S44, 0x4e0811a1L); /* 60 */

        a ], S41, 0xf7537e82L); /* 61 */

        d ], S42, 0xbd3af235L); /* 62 */

        c ], S43, 0x2ad7d2bbL); /* 63 */

        b ], S44, 0xeb86d391L); /* 64 */



        /*加入到之前计算的结果当中*/

        result[] += a;

        result[] += b;

        result[] += c;

        result[] += d;

        result[]&0xFFFFFFFFL;

        result[]&0xFFFFFFFFL;

        result[]&0xFFFFFFFFL;

        result[]&0xFFFFFFFFL;

    }

    

    /**

     * 下面是处理要用到的线性函数

     */

    private static long F(long x, long y, long z) {

        return (x & y) | ((~x) & z);

    }



    private static long G(long x, long y, long z) {

        return (x & z) | (y & (~z));

    }



    private static long H(long x, long y, long z) {

        return x ^ y ^ z;

    }



    private static long I(long x, long y, long z) {

        return y ^ (x | (~z));

    }



    private static long FF(long a, long b, long c, long d, long x, long s,

            long ac) {

        a += (F(b, c, d)&0xFFFFFFFFL) + x + ac;

        a  - s));

        a += b;

        return (a&0xFFFFFFFFL);

    }



    private static long GG(long a, long b, long c, long d, long x, long s,

            long ac) {

        a += (G(b, c, d)&0xFFFFFFFFL) + x + ac;

        a  - s));

        a += b;

        return (a&0xFFFFFFFFL);

    }



    private static long HH(long a, long b, long c, long d, long x, long s,

            long ac) {

        a += (H(b, c, d)&0xFFFFFFFFL) + x + ac;

        a  - s));

        a += b;

        return (a&0xFFFFFFFFL);

    }



    private static long II(long a, long b, long c, long d, long x, long s,

            long ac) {

        a += (I(b, c, d)&0xFFFFFFFFL) + x + ac;

        a  - s));

        a += b;

        return (a&0xFFFFFFFFL);

    }

}

MD5安全性：

    普遍认为MD5是很安全，因为暴力破解的时间是一般人无法接受的。实际上如果把用户的密码MD5处理后再存储到数据库，其实是很不安全的。因为用户的密码是比较短的，而且很多用户的密码都使用生日，手机号码，身份证号码，电话号码等等。或者使用常用的一些吉利的数字，或者某个英文单词。如果我把常用的密码先MD5处理，把数据存储起来，然后再跟你的MD5结果匹配，这时我就有可能得到明文。比如某个MD5破解网站http://www.cmd5.com/default.aspx，我把其网站下的公告复制如下

  md5破解、动网论坛密码破解等不再需要用穷举法，本站共有md5记录235亿条，还在不断增长中，已包含10位及10位以下数字、7位字母、部分7位字母＋数字,全部6位及以下字母加数字等组合，并针对国内用户做了大量优化，例如已经包含所有手机号码、全国部分大中城市固定电话号码、百家姓、常用拼音等大量组合，另加入了某大型网站真实会员密码数据10万条。本站数据量大，查询速度快，同时支持16位及32位密码查询。通过对10万会员的真实动网论坛样本数据的测试，本站对于动网论坛密码的命中率达到83%。

  本站4T的硬盘已经上线，正在生成数据，预计需要2个月左右时间，到时候本站能查询到12位数字和9位字母。

你可以用你的生日，手机号码去测试一下。

   我觉得只需要将上面我写的MD5的标准幻数A,B,C,D的值修改一下，修改后也不是MD5算法了，因为不能保证唯一性。这样就算别人得到32位的值，他如果不知道幻数的值是无法还原明文的。就算得到了幻数，也是很难破解的。



     JAVA实现MD5

    在java中实现MD5是很简单的，在包java.security有个类MessageDigest。官方文档如下

    MessageDigest 类为应用程序提供信息摘要算法的功能，如 MD5 或 SHA 算法。信息摘要是安全的单向哈希函数，它接收任意大小的数据，输出固定长度的哈希值。 



    MessageDigest 对象开始被初始化。该对象通过使用 update 方法处理数据。任何时候都可以调用 reset 方法重置摘要。一旦所有需要更新的数据都已经被更新了，应该调用 digest 方法之一完成哈希计算。 



    对于给定数量的更新数据，digest 方法只能被调用一次。digest 被调用后，MessageDigest 对象被重新设置成其初始状态。

使用MessageDigest很简单，例如

package woxingwosu;

/************************************************

 * MD5 算法

 * @author 我行我素

 * @Date 2007-07-06

*************************************************/

import java.security.MessageDigest;



public class MyMD5 {



    ','A','B','C','D','E','F'}; 

    public static void main(String[] args) {

        try{

            MessageDigest md5 = MessageDigest.getInstance("MD5");//申明使用MD5算法

            md5.update("a".getBytes());//

            System.out.println("md5(a)="+byte2str(md5.digest()));

            md5.update("a".getBytes());

            md5.update("bc".getBytes());

            System.out.println("md5(abc)="+byte2str(md5.digest()));

        }catch(Exception e){

            e.printStackTrace();

        }

    }

    

    /**

     * 将字节数组转换成十六进制字符串

     * @param bytes

     * @return

     */

    private static String byte2str(byte []bytes){

        int len = bytes.length;   

        StringBuffer result = new StringBuffer();    

        ; i < len; i++) {   

            byte byte0 = bytes[i];   

            result.append(hex[byte0  & 0xf]);   

            result.append(hex[byte0 & 0xf]);   

        }

        return result.toString();

    }

} 

另外附上其他版本的MD5算法的实现(来自网络)

    1)JS版的MD5(调用方法：md5(明文))

/*

 * A JavaScript implementation of the RSA Data Security, Inc. MD5 Message

 * Digest Algorithm, as defined in RFC 1321.

 * Version 2.1 Copyright (C) Paul Johnston 1999 - 2002.

 * Other contributors: Greg Holt, Andrew Kepert, Ydnar, Lostinet

 * Distributed under the BSD License

 * See http://pajhome.org.uk/crypt/md5 for more info.

 */



/*

 * Configurable variables. You may need to tweak these to be compatible with

 * the server-side, but the defaults work in most cases.

 */

;  /* hex output format. 0 - lowercase; 1 - uppercase        */

var b64pad  = ""; /* base-64 pad character. "=" for strict RFC compliance   */

;  /* bits per input character. 8 - ASCII; 16 - Unicode      */



/*

 * These are the functions you'll usually want to call

 * They take string arguments and return either hex or base-64 encoded strings

 */

function hex_md5(s){ return binl2hex(core_md5(str2binl(s), s.length * chrsz));}

function str_md5(s){ return binl2str(core_md5(str2binl(s), s.length * chrsz));}

function hex_hmac_md5(key, data) { return binl2hex(core_hmac_md5(key, data)); }

function str_hmac_md5(key, data) { return binl2str(core_hmac_md5(key, data)); }



/*

 * Calculate the MD5 of an array of little-endian words, and a bit length

 */

function core_md5(x, len)

{

  /* append padding */

  x[len );

  x[(((len ] = len;



  ;

  ;

  ;

  ;



  )

  {

    var olda = a;

    var oldb = b;

    var oldc = c;

    var oldd = d;



    a );

    d );

    c );

    b );

    a );

    d );

    c );

    b );

    a );

    d );

    c );

    b );

    a );

    d );

    c );

    b );



    a );

    d );

    c );

    b );

    a );

    d );

    c );

    b );

    a );

    d );

    c );

    b );

    a );

    d );

    c );

    b );



    a );

    d );

    c );

    b );

    a );

    d );

    c );

    b );

    a );

    d );

    c );

    b );

    a );

    d );

    c );

    b );



    a );

    d );

    c );

    b );

    a );

    d );

    c );

    b );

    a );

    d );

    c );

    b );

    a );

    d );

    c );

    b );



    a = safe_add(a, olda);

    b = safe_add(b, oldb);

    c = safe_add(c, oldc);

    d = safe_add(d, oldd);

  }

  return Array(a, b, c, d);



}



/*

 * These functions implement the four basic operations the algorithm uses.

 */

function md5_cmn(q, a, b, x, s, t)

{

  return safe_add(bit_rol(safe_add(safe_add(a, q), safe_add(x, t)), s),b);

}

function md5_ff(a, b, c, d, x, s, t)

{

  return md5_cmn((b & c) | ((~b) & d), a, b, x, s, t);

}

function md5_gg(a, b, c, d, x, s, t)

{

  return md5_cmn((b & d) | (c & (~d)), a, b, x, s, t);

}

function md5_hh(a, b, c, d, x, s, t)

{

  return md5_cmn(b ^ c ^ d, a, b, x, s, t);

}

function md5_ii(a, b, c, d, x, s, t)

{

  return md5_cmn(c ^ (b | (~d)), a, b, x, s, t);

}



/*

 * Calculate the HMAC-MD5, of a key and some data

 */

function core_hmac_md5(key, data)

{

  var bkey = str2binl(key);

  ) bkey = core_md5(bkey, key.length * chrsz);



  );

  ; i++)

  {

    ipad[i] = bkey[i] ^ 0x36363636;

    opad[i] = bkey[i] ^ 0x5C5C5C5C;

  }



   + data.length * chrsz);

  );

}



/*

 * Add integers, wrapping at 2^32. This uses 16-bit operations internally

 * to work around bugs in some JS interpreters.

 */

function safe_add(x, y)

{

  var lsw = (x & 0xFFFF) + (y & 0xFFFF);

  );

  ) | (lsw & 0xFFFF);

}



/*

 * Bitwise rotate a 32-bit number to the left.

 */

function bit_rol(num, cnt)

{

   - cnt));

}



/*

 * Convert a string to an array of little-endian words

 * If chrsz is ASCII, characters >255 have their hi-byte silently ignored.

 */

function str2binl(str)

{

  var bin = Array();

  ;

  ; i < str.length * chrsz; i += chrsz)

    bin[i);

  return bin;

}



/*

 * Convert an array of little-endian words to a string

 */

function binl2str(bin)

{

  var str = "";

  ;

  ; i += chrsz)

    str )) & mask);

  return str;

}



/*

 * Convert an array of little-endian words to a hex string.

 */

function binl2hex(binarray)

{

  var hex_tab = hexcase ? "0123456789ABCDEF" : "0123456789abcdef";

  var str = "";

  ; i++)

  {

    str )) & 0xF) +

           hex_tab.charAt((binarray[i  )) & 0xF);

  }

  return str;

}



String.prototype.trim = function(){return this.replace(/(^s*)|(s*$)/g, "");}



function md5(text) {

    return hex_md5(text.trim());

}