【密码学】MD5原理与java实现
程序员文章站
2022-05-12 22:13:07
...
一、概述
1.概念
MD5即Message Digest Algorithm 5（中文名为消息摘要算法第五版），是计算机广泛使用的杂凑算法之一（又译摘要算法、哈希算法），用以提供消息的完整性保护。主要是通过特定的hash方法将文本信息转换成简短的信息摘要，压缩+加密+hash算法的结合体，是绝对不可逆的。
2.特征（1）压缩性：任意长度输入，得到固定长度输出（一般取128bit）。
（2）易计算：从原数据计算出MD5值很容易。
（3）防篡改：对原数据进行任何改动，哪怕只修改1个字节，所得到的MD5值大概率不同。
（4）难碰撞：由于使用哈希函数，无法避免碰撞，但碰撞是小概率事件。
（1）完整性验证：由特征三知，可验证消息在传输过程中是否被篡改。
（2）数字签名：在上一条的基础上，如果再有一个第三方的认证机构，用MD5还可以防止文件作者的“抵赖”，这就是所谓的数字签名应用。
二、过程
MD5以512位分组来处理输入数据，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。
1.填充
如果输入信息的长度(bit)对512求余的结果不等于448，就需要填充使得对512求余的结果等于448。填充的方法是填充一个1和n个0。填充完后，信息的长度就为N*512+448(bit)； 用64位来存储填充前信息长度。这64位加在第一步结果的后面，这样信息长度就变为N*512+448+64=(N+1)*512位。2.初始化向量IV
初始化：A=0x01234567，B=0x89ABCDEF，C=0xFEDCBA98，D=0x76543210（内存中吗，大端模式）。
实际值：A=0x67452301，B=0xEFCDAB89，C=0x98BADCFE，D=0x10325476
H0=A0B0C0D0
3.循环轮（哈希过程）
一共有N+1次循环，每次循环4轮，每次循环处理16个32位子分组共512位数据。
对于每次循环中的四轮：
（1）首先认识四个轮函数：(&是与,|是或,~是非,^是异或)
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))（2）a、b、c、d、初值分别为Hi-1=（A、B、C、D、）i-1；Mj表示第j(j从0到15)个子分组;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) （3）四轮运算
第一轮
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) 这四轮结束后：Hi=Hi-1 + (a,b,c,d)用于下一512分组abcd的初值。
三、java实现与使用
1.实现
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)
*填充方式为先加一个1,其它位补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){
String str=MD5.getInstance().getMD5("");
System.out.println(str);
}
}2.使用
调用java API,与上面实现无关，彩虹表和加盐将在下一篇博客中讲解（MD5的使用和概念特性掌握，原理作了解）
package EncryptAndDecrypt;
import java.security.MessageDigest;
import java.util.Random;
/**
* 散列加密之32位哈希值的MD5算法，调用JDK里的API
*ps：准确来说散列加密不是加密算法，因为它是不可逆的（只能加密，不能解密）
*/
public class MyMD5 {
private static char[] hex = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
public static void main(String[] args) throws Exception {
String input = "123456";
System.out.println("MD5加密" + "\n"
+ "明文：" + input + "\n"
+ "无盐密文：" + MD5WithoutSalt(input));
System.out.println("带盐密文：" + MD5WithSalt(input,0));
}
/**
*@Author: DavidHuang
*@Time: 2018/5/11 14:55
*@return:
*@params: [inputStr] 输入明文
*@Descrption: 不加盐MD5
*/
public static String MD5WithoutSalt(String inputStr) {
try {
MessageDigest md = MessageDigest.getInstance("MD5");//申明使用MD5算法,更改参数为"SHA"就是SHA算法了
return byte2HexStr(md.digest(inputStr.getBytes()));//哈希计算,转换输出
} catch (Exception e) {
e.printStackTrace();
return e.toString();
}
}
/**
*@Author: DavidHuang
*@Time: 2018/5/11 14:47
*@return:
*@params: [inputStr, type] inputStr是输入的明文;type是处理类型，0表示注册存hash值到库时，1表示登录验证时
*@Descrption: MD5加盐，盐的获取分两种情况;输入明文加盐；输出密文带盐(将salt存储到hash值中)
*/
public static String MD5WithSalt(String inputStr, int type) {
try {
MessageDigest md = MessageDigest.getInstance("MD5");//申明使用MD5算法,更改参数为"SHA"就是SHA算法了
String salt = null;
if (type == 0) {//注册存hash值到库时，new salt
salt = salt();
} else if (type == 1) {//登录验证时，使用从库中查找到的hash值提取出的salt
String queriedHash=null;//从库中查找到的hash值
salt=getSaltFromHash(queriedHash);
}
String inputWithSalt = inputStr + salt;//加盐，输入加盐
String hashResult = byte2HexStr(md.digest(inputWithSalt.getBytes()));//哈希计算,转换输出
System.out.println("加盐密文："+hashResult);
/*将salt存储到hash值中，用于登陆验证密码时使用相同的盐*/
char[] cs = new char[48];
for (int i = 0; i < 48; i += 3) {
cs[i] = hashResult.charAt(i / 3 * 2);
cs[i + 1] = salt.charAt(i / 3);//输出带盐，存储盐到hash值中;每两个hash字符中间插入一个盐字符
cs[i + 2] = hashResult.charAt(i / 3 * 2 + 1);
}
hashResult = new String(cs);
return hashResult;
} catch (Exception e) {
e.printStackTrace();
return e.toString();
}
}
/**
* @Author: DavidHuang
* @Time: 2018/5/10 21:14
* @return: salt
* @params:
* @Descrption: 自定义简单加盐，是一个随机生成的长度为16的字符串，每一个字符是随机的十六进制字符
*/
public static String salt() {
Random random = new Random();
StringBuilder sb = new StringBuilder(16);
for (int i = 0; i < sb.capacity(); i++) {
sb.append(hex[random.nextInt(16)]);
}
return sb.toString();
}
/**
* @Author: DavidHuang
* @Time: 2018/5/11 14:08
* @return: 十六进制字符串
* @params: [bytes]
* @Descrption: 将字节数组转换成十六进制字符串
*/
private static String byte2HexStr(byte[] bytes) {
/**
*@Author: DavidHuang
*@Time: 19:41 2018/5/10
*@return: java.lang.String
*@params: * @param bytes
*@Descrption:
*/
int len = bytes.length;
StringBuffer result = new StringBuffer();
for (int i = 0; i < len; i++) {
byte byte0 = bytes[i];
result.append(hex[byte0 >>> 4 & 0xf]);
result.append(hex[byte0 & 0xf]);
}
return result.toString();
}
/**
*@Author: DavidHuang
*@Time: 2018/5/11 14:32
*@return: 提取的salt
*@params: [hash] 3i byte带盐的hash值,带盐方法与MD5WithSalt中相同
*@Descrption: 从库中查找到的hash值提取出的salt
*/
public static String getSaltFromHash(String hash){
StringBuilder sb=new StringBuilder();
char [] h=hash.toCharArray();
for(int i=0;i<hash.length();i+=3){
sb.append(h[i+1]);
}
return sb.toString();
}
}一次运行结果：
MD5加密
明文：123456
无盐密文：E10ADC3949BA59ABBE56E057F20F883E
加盐密文：650B429350224E94B150C2DDFE0C2D19
带盐密文：61505B4029F35C028240E994BF15F0CF2DCDFDE0BC2CD1C9上一篇： 草根站长创业需要解决哪些难题？
下一篇： 一个老站长创业定下的22条军规