md5算法的java实现-ag真人游戏

一、算法原理概述

md5 即message-digest algorithm 5 (信息-摘要算法5)

• md4 (1990)、md5(1992, rfc 1321) 由ron rivest发明，是广泛 使用的hash 算法，用于确保信息传输的完整性和一致性。
• md5 使用little-endian(小端模式)，输入任意不定长度信息，以 512-bit 进行分组，生成四个32-bit 数据，最后联合输出固定 128-bit 的信息摘要。
• md5 算法的基本过程为：填充、分块、缓冲区初始化、循环压 缩、得出结果。
• md5 不是足够安全的。
  • hans dobbertin在1996年找到了两个不同的512-bit 块,它们 在md5 计算下产生相同的hash 值。
  • 至今还没有真正找到两个不同的消息，它们的md5 的hash 值相等。

基本流程

填充padding

• 在长度为kbits 的原始消息数据尾部填充长度为pbits 的标识 100…0，1< p < 512 (即至少要填充1个bit)，使得填充后的消息位 数为：k p=448 (mod 512).
  • 注意到当k=448 (mod 512) 时，需要p= 512.
• 再向上述填充好的消息尾部附加k 值的低64位(即k mod 264)， 最后得到一个长度位数为k p 64= 0 (mod 512) 的消息。

分块

• 把填充后的消息结果分割为l个512-bit 分组：y0, y1, …, yl-1。
• 分组结果也可表示成n个32-bit 字m0, m1, …, mn-1，n= lx16。

初始化

• 初始化一个128-bit 的md 缓冲区，记为cvq，表示成4个32-bit 寄存器(a, b, c,d)；cv0= iv。迭代在md 缓冲区进行，最后一 步的128-bit 输出即为算法结果。

压缩函数

每轮循环中的一次迭代运算逻辑

1. 对a迭代：a <— b ((a g(b, c, d) x[k] t[i]) <<
2. 缓冲区(a, b, c, d) 作循环轮换： (b, c, d, a) <—(a, b, c, d)

说明：

• a, b, c, d: md 缓冲区(a, b, c, d) 的当前值。
• g: 轮函数(f, g, h, i中的一个)。
• <<
• x[k] : 当前处理消息分组的第k个(k= 0…15) 32位字，即 m(qx16 k)。
• t[i] : t表的第i个元素，32位字；t表总共有64个元素，也 称为加法常数。
• • : 模232 加法。

二、总体结构

public class md5 {
  
	//一系列常量数值
    
    //开始使用md5加密
    private string start(string message){
  
        //分块
        
        //填充
        
        //即小于448bit的情况，先填充100...0再填充k值的低64位
        //此时只会新增一个分组
        if(rest <= 56){
  
            //填充100...0
            //填充k值低64位
            //处理分组
             h(divide(inputbytes, i*64));
        //即大于448bit的情况，先填充100...0再填充k值的低64位
        //此时会新增两个分组
        }else{
  
            //填充10000000
            //填充00000000
            //填充低64位
            //处理第一个尾部分组
            h(divide(inputbytes, i*64));
            //处理第二个尾部分组
             h(divide(inputbytes, i*64));
        }
        //将hash值转换成十六进制的字符串
        //小端方式!
    }
    
    //从inputbytes的index开始取512位，作为新的512bit的分组
    private static long[] divide(byte[] inputbytes,int start){
  
    	//存储一整个分组,就是512bit,数组里每个是32bit，就是4字节，为了消除符号位的影响，所以使用long
        
    }
    
    // groups[] 中每一个分组512位（64字节）
    // md5压缩函数
    private void h(long[] groups) {
  
    	//缓冲区（寄存器）数组
        //四轮循环
        for(int n = 0; n < 4; n  ) {
  
        	//16轮迭代
        	for(int i = 0; i < 16; i  ) {
  
            }
        }
        //加入之前计算的结果
        //防止溢出
    }
    public static void main(string []args){
  
        md5 md=new md5();
        string message = "hellomd5";
        system.out.println("md5-algorithm:\n\norigin message: "   message);
        system.out.println("result message: "   md.start(message));
        system.out.println("result message(uppercase): "   md.resultmessage.touppercase());
        //f0f99260b5a02508c71f6d81c15e9a44
        //3ed9e5f6855dbcdbcd95ac6c4fe0c0a5
    }
}

三、模块分解

填充

填充时有两种情况

• 如果去掉整数个512bit的小组，剩下的位数不超过448bit，那样就可以先填充100…00（如果正好是448bit就不用填充了），再填充用k值的低64位64bit，那样的话就只是新增了一个小组
• 如果去掉整数个512bit的小组，剩下的位数超过了448bit，那样不够填充64bit，所以需要填充100…00到512bit，构成一个小组；然后再在第二个小组填充448bit个0，最后填充k值的低64位bit，这样就会新增两个小组

//填充
        int rest = bytelen % 64;
        //即将填充的一个分组
        byte [] paddingbytes=new byte[64];
        //原来的尾部数据
        for(int i=0;i>8;
            }
            //处理分组
            h(divide(paddingbytes,0));
        //即大于448bit的情况，先填充100...0再填充k值的低64位
        //此时会新增两个分组
        }else{
  
            //填充10000000
            paddingbytes[rest]=(byte)(1<<7);
            //填充00000000
            for(int i=rest 1;i<64;i  )
            	paddingbytes[i]=0;
            //处理第一个尾部分组
            h(divide(paddingbytes,0));
            
            //填充00000000
            for(int i=0;i<56;i  )
            	paddingbytes[i]=0;
            //填充低64位
            for(int i=0;i<8;i  ){
  
            	//这里很关键，使用小端方式，即byte数组先存储len的低位数据，然后右移len
            	paddingbytes[56 i]=(byte)(k&0xffl);
                k=k>>8;
            }
            //处理第二个尾部分组
            h(divide(paddingbytes,0));
        }

分块

这里调用了divide分组函数，将完整小组分成个数为16，单个元素为32bit的数组

再直接调用h压缩函数，进行四轮循环和16次迭代

//分块
//完整小组(512bit)(64byte)的个数
        int groupcount = bytelen/64;
        for(int i = 0;i < groupcount;i  ){
  
        	//每次取512bit
            //处理一个分组
            h(divide(inputbytes, i*64));
        }

分组函数

这个函数传入的参数是一个字节数组，以及一个代表从哪里开始截取的int值

效果就是将这个字节数组从start开始的64个字节组成一个

元素个数为16，单个元素为32bit的数组

采用的方法是每次取四个字节，采用小端的方式拼接成一个long型的整数

因为int在某些情况下是4个字节，所以就是正好32bit，但是带符号，就影响后面数据的运算

//从inputbytes的index开始取512位，作为新的512bit的分组
    private static long[] divide(byte[] inputbytes,int start){
  
    	//存储一整个分组,就是512bit,数组里每个是32bit，就是4字节，为了消除符号位的影响，所以使用long
        long [] group=new long[16];
        for(int i=0;i<16;i  ){
  
        	//每个32bit由4个字节拼接而来
        	//小端的从byte数组到bit恢复方法
            group[i]=byte2unsign(inputbytes[4*i start])|
                (byte2unsign(inputbytes[4*i 1 start]))<<8|
                (byte2unsign(inputbytes[4*i 2 start]))<<16|
                (byte2unsign(inputbytes[4*i 3 start]))<<24;
        }
        return group;
    }

md5压缩函数

用了两层循环

第一层表示四轮循环

第二层表示16轮迭代

中间按照缓冲区运算的要求处理数据

这里直接处理的是result数组，也就是真实的缓冲区，所以在开始暂存了它们当时的值为a,b,c,d

运算完毕后要加上这些值

运算过程中以及运算结束会有一些防溢出的操作

（有时候没有这个就会出错）

// groups[] 中每一个分组512位（64字节）
    // md5压缩函数
    private void h(long[] groups) {
  
    	//缓冲区（寄存器）数组
        long a = result[0], b = result[1], c = result[2], d = result[3];
        //四轮循环
        for(int n = 0; n < 4; n  ) {
  
        	//16轮迭代
        	for(int i = 0; i < 16; i  ) {
  
            	result[0]  = (g(n, result[1], result[2], result[3])&0xffffffffl)   groups[k[n][i]]   t[n][i];
                result[0] = result[1]   ((result[0]&0xffffffffl)<< s[n][i % 4] | ((result[0]&0xffffffffl) >>> (32 - s[n][i % 4])));
                //循环轮换
                long temp = result[3];
                result[3] = result[2];
                result[2] = result[1];
                result[1] = result[0];
                result[0] = temp;
            }
        }
        //加入之前计算的结果
        result[0]  = a;
        result[1]  = b;
        result[2]  = c;
        result[3]  = d;
        //防止溢出
        for(int n = 0; n < 4 ; n  ) {
  
        	result[n] &=0xffffffffl;
        }
    }

最后结果转换为字符串

之前得到的结果就是result数组，四个元素，每个元素是一个32bit的数据

现在要把他们转换为字符串

但是需要小端的处理方式

即long的低位作为字符串的高位

每次以一个字节处理，32bit四个字节分别通过与运算和移位运算分离出来，再让long的低位在前，高位在后，得到十六进制字符串就是md5编码的结果

//将hash值转换成十六进制的字符串
        //小端方式!
        for(int i=0;i<4;i  ){
  
        	resultmessage  = long.tohexstring(result[i] & 0xff)  
            		long.tohexstring((result[i] & 0xff00) >> 8)  
            		long.tohexstring((result[i] & 0xff0000) >> 16)  
            		long.tohexstring((result[i] & 0xff000000) >> 24);
  
        }

四、数据结构

long []groups 存储小组

string resultmessage存储结果字符串

//四个寄存器的初始向量iv,采用小端存储
static final long a=0x67452301l
static final long b=0xefcdab89l
static final long c=0x98badcfel
static final long d=0x10325476l

private long [] result={a,b,c,d}; 模拟存储结果的四个寄存器

static final long t[][]迭代过程中采用的近似值int(2^32 x |sin(i)|)

static final int k[][] 表示x[k]中的的k取值，决定如何使用消息分组中的字

static final int s[][] 各次迭代中采用的做循环移位的s值

private static long g(int i, long b, long c, long d) 4轮循环中使用的生成函数(轮函数)g

五、运行结果

输入原始消息：hellomd5

得到编码结果为：3ed9e5f6855dbcdbcd95ac6c4fe0c0a5

用站长之家的工具验证，结果正确

六、源代码

/**
 * @author janking
 */
public class md5 {
  
    //存储小组
    long[] groups = null;
    //存储结果
    string resultmessage = "";
    //四个寄存器的初始向量iv,采用小端存储
    static final long a = 0x67452301l;
    static final long b = 0xefcdab89l;
    static final long c = 0x98badcfel;
    static final long d = 0x10325476l;
    //java不支持无符号的基本数据(unsigned),所以选用long数据类型
    private long[] result = {
  a, b, c, d};
    static final long t[][] = {
  
            {
  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}};
    //表示x[k]中的的k取值，决定如何使用消息分组中的字
    static final int k[][] = {
  
            {
  0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15},
            {
  1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12},
            {
  5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2},
            {
  0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9}};
    //各次迭代中采用的做循环移位的s值
    static final int s[][] = {
  
            {
  7, 12, 17, 22},
            {
  5, 9, 14, 20},
            {
  4, 11, 16, 23},
            {
  6, 10, 15, 21}};
    //4轮循环中使用的生成函数(轮函数)g
    private static long g(int i, long b, long c, long d) {
  
        switch (i) {
  
            case 0:
                return (b & c) | ((~b) & d);
            case 1:
                return (b & d) | (c & (~d));
            case 2:
                return b ^ c ^ d;
            case 3:
                return c ^ (b | (~d));
            default:
                return 0;
        }
    }
    //开始使用md5加密
    private string start(string message) {
  
        //转化为字节数组
        byte[] inputbytes = message.getbytes();
        //6a 61 6e 6b 69 6e 67
        //获取字节数组的长度
        int bytelen = inputbytes.length;
        //得到k值（以bit作单位的message长度）
        long k = (long) (bytelen << 3);
        //完整小组(512bit)(64byte)的个数
        int groupcount = bytelen / 64;
        //分块
        for (int i = 0; i < groupcount; i  ) {
  
            //每次取512bit
            //处理一个分组
            h(divide(inputbytes, i * 64));
        }
        //填充
        int rest = bytelen % 64;
        //即将填充的一个分组
        byte[] paddingbytes = new byte[64];
        //原来的尾部数据
        for (int i = 0; i < rest; i  )
            paddingbytes[i] = inputbytes[bytelen - rest   i];
        //即小于448bit的情况，先填充100...0再填充k值的低64位
        //此时只会新增一个分组
        if (rest <= 56) {
  
            //填充100...0
            if (rest < 56) {
  
                //填充10000000
                paddingbytes[rest] = (byte) (1 << 7);
                //填充00000000
                for (int i = 1; i < 56 - rest; i  )
                    paddingbytes[rest   i] = 0;
            }
            //填充k值低64位
            for (int i = 0; i < 8; i  ) {
  
                paddingbytes[56   i] = (byte) (k & 0xffl);
                k = k >> 8;
            }
            //处理分组
            h(divide(paddingbytes, 0));
            //即大于448bit的情况，先填充100...0再填充k值的低64位
            //此时会新增两个分组
        } else {
  
            //填充10000000
            paddingbytes[rest] = (byte) (1 << 7);
            //填充00000000
            for (int i = rest   1; i < 64; i  )
                paddingbytes[i] = 0;
            //处理第一个尾部分组
            h(divide(paddingbytes, 0));
            //填充00000000
            for (int i = 0; i < 56; i  )
                paddingbytes[i] = 0;
            //填充低64位
            for (int i = 0; i < 8; i  ) {
  
                //这里很关键，使用小端方式，即byte数组先存储len的低位数据，然后右移len
                paddingbytes[56   i] = (byte) (k & 0xffl);
                k = k >> 8;
            }
            //处理第二个尾部分组
            h(divide(paddingbytes, 0));
        }
        //将hash值转换成十六进制的字符串
        //小端方式!
        for (int i = 0; i < 4; i  ) {
  
            //解决缺少前置0的问题
            resultmessage  = string.format("x", result[i] & 0xff)  
                    string.format("x", (result[i] & 0xff00) >> 8)  
                    string.format("x", (result[i] & 0xff0000) >> 16)  
                    string.format("x", (result[i] & 0xff000000) >> 24);
        }
        return resultmessage;
    }
    //从inputbytes的index开始取512位，作为新的512bit的分组
    private static long[] divide(byte[] inputbytes, int start) {
  
        //存储一整个分组,就是512bit,数组里每个是32bit，就是4字节，为了消除符号位的影响，所以使用long
        long[] group = new long[16];
        for (int i = 0; i < 16; i  ) {
  
            //每个32bit由4个字节拼接而来
            //小端的从byte数组到bit恢复方法
            group[i] = byte2unsign(inputbytes[4 * i   start]) |
                    (byte2unsign(inputbytes[4 * i   1   start])) << 8 |
                    (byte2unsign(inputbytes[4 * i   2   start])) << 16 |
                    (byte2unsign(inputbytes[4 * i   3   start])) << 24;
        }
        return group;
    }
    //其实byte相当于一个字节的有符号整数，这里不需要符号位，所以把符号位去掉
    public static long byte2unsign(byte b) {
  
        return b < 0 ? b & 0x7f   128 : b;
    }
    // groups[] 中每一个分组512位（64字节）
    // md5压缩函数
    private void h(long[] groups) {
  
        //缓冲区（寄存器）数组
        long a = result[0], b = result[1], c = result[2], d = result[3];
        //四轮循环
        for (int n = 0; n < 4; n  ) {
  
            //16轮迭代
            for (int i = 0; i < 16; i  ) {
  
                result[0]  = (g(n, result[1], result[2], result[3]) & 0xffffffffl)   groups[k[n][i]]   t[n][i];
                result[0] = result[1]   ((result[0] & 0xffffffffl) << s[n][i % 4] | ((result[0] & 0xffffffffl) >>> (32 - s[n][i % 4])));
                //循环轮换
                long temp = result[3];
                result[3] = result[2];
                result[2] = result[1];
                result[1] = result[0];
                result[0] = temp;
            }
        }
        //加入之前计算的结果
        result[0]  = a;
        result[1]  = b;
        result[2]  = c;
        result[3]  = d;
        //防止溢出
        for (int n = 0; n < 4; n  ) {
  
            result[n] &= 0xffffffffl;
        }
    }
    public static void main(string[] args) {
  
        md5 md = new md5();
        string message = "hellomd5";
        system.out.println("md5-algorithm:\n\norigin message: "   message);
        system.out.println("result message: "   md.start(message));
        system.out.println("result message(uppercase): "   md.resultmessage.touppercase());
        //origin message: hellomd5
        //result message: 3ed9e5f6855dbcdbcd95ac6c4fe0c0a5
        //result message(uppercase): 3ed9e5f6855dbcdbcd95ac6c4fe0c0a5
    }
}