Java自定义变换产生摘要数据

前景回顾

在之前的两篇文章中：
Java了解消息摘要算法 ：介绍了消息摘要算法的发展历史及现行的国内外的消息摘要算法。
Java各种摘要算法的工具类 提供了Java环境下的各种消息摘要算法的工具类及使用。

面临的问题

虽然摘要算法，简单便捷，但所有加密算法都需要面临的同一个问题：如何避免摘要被破解？

正常加密逻辑是：

但是如果有人可以使得箭头反向呢（对于消息摘要算法来说算法层面基本是难以实现的）？变成以下这样：

是的，你没有看错，不需要破解算法，也可以破解密文得到明文数据。在这其中最简单有效的莫过于：彩虹表攻击。

彩虹表攻击

所谓彩虹表攻击就是指攻击者持有一张表，里面有明文和对应的密文摘要的一一对应关系，攻击者利用这些关系来破解明文。

比如你的字符123经过某个摘要算法生成的摘要为A。那么我的表里存这样的一个数据：A - 123，那么当我下次遇到A这样的摘要，我只要去我的彩虹表里面找，我就自然知道其明文为123。

现行的彩虹表攻击

我们都知道有些网站上提供了通过摘要获取明文信息的功能。直接搜索引擎搜索：MD5在线解密，可以找一个一堆根据摘要获取明文的网站，类似于以下这样输入摘要获取明文：
MD5破解:

SHA-1破解:

SHA-256破解:

现在你知道现行公布的摘要算法有多么脆弱了吧。任何一个调用原生算法产生的摘要，都面临着彩虹表攻击。

但是其基于可以获得摘要算法，并且构建彩虹表。请注意这句话。

彩虹表攻击的局限

好消息是，对于复杂的字符，解密仍然是困难的，上述的只是简单的字符生成的摘要，但是当彩虹表足够大，能够包含摘要算法的产生所有摘要，那么该算法不攻自破。不过值得一提的是，该方法基本不可能，因为实在太大了。

理论上破解MD5算法所需彩虹表大小

我们可以做一个简单的计算。比如MD5算法产生一个32位的密文，一字符占一byte也就是一个字节，所以一个32字符的摘要大小为32b。而32位的密文的变化为（仅小写或者大写）可以算算有多少种，字母变化为26种，数字为10种，那么一个位置上就是36种变化，也就是一个MD5算法可以产生共36的32次方个摘要。有兴趣的朋友可以运行以下代码，可以清晰的感受到彩虹表攻击的局限性。

 		//基本结果
        BigInteger b1 = new BigInteger("1");
        //增加一位  该位的可能性为36
        BigInteger b2 = new BigInteger("36");
        //1Gb对应的bite数 1024 * 1024 * 1024
        BigInteger b3 = new BigInteger("1073741824");
        //一个32位摘要占用64b的空间
        BigInteger b4 = new BigInteger("32");

        for (int i = 1; i <= 32; i++) {
            b1 = b1.multiply(b2);
            System.out.println("字符" + i + "位产生的可能结果为：" + b1.toString() + "种");
            BigInteger b5 = b1.multiply(b4);
            System.out.println("占用空间:" + b5.divide(b3).toString() + "GB");
            System.out.println("=====================================================");
        }

我这里放前六位产生的摘要大小

可以看到仅仅是前六位生成的所有摘要大小占到了64G，而32位字符所产生所有摘要，所占的大小为：

字符32位产生的可能结果为：63340286662973277706162286946811886609896461828096种
占用空间:1887687643258967331235476939285155731734528GB

防范彩虹表攻击的理由

虽然彩虹表攻击的局限很大，但并不妨碍其破解简单的密码。

如上面演示的那样，破解简单的数字、字母组合密码还是没问题的。
为了尽可能的避免摘要被破解（大都是用于密码验证、敏感信息的保护等方面，如数据库里基本不存储明文密码，而是存储密码的摘要，同理对于敏感性息，诸如不需要查看的身份证、电话等，也可这么存储），所以有必要对生成的摘要进行一些本地化的处理。问题在于在这场数据安全的攻防中，怎么本地化尽量避免被攻破？

本地化处理

基于以上两种情况：网站直接破解及彩虹表攻击。（本质是一种， 这里暂且让我分开来讲。）

简单矩阵变换及字符替换

网站破解的方法是基于原摘要算法的，以MD5举例，任何人以MD5算法来对同一个数据获取摘要，得到的结果都是一样的，所以网站上只要能得到MD5这个算法，从而构建彩虹表，实现彩虹表攻击。

那么如果我使用的算法，是对MD5算法生成的摘要做过更改的。

比如对从MD5算法获取的摘要，做一些小手段，比如移位、替换等。

那么使用原生的MD5算法获取到的彩虹表进行的攻击，对我一点威胁就都没有了。但是需要注意的是，
如果有人会拿着你的摘要和原生的摘要去进行对比，试图找出规律，那么你一些简单的变换可能很快就会被破解（比如简单移位或者字符替换），可以再加一些如下的操作：

1. 字符替换

2. 特殊值模糊处理（也就是防止攻击者根据某些固定的摘要片段在原算法生成的摘要和本地化处理后的摘要之间推测出算法细节）

以下是用MD5算法为演示，并进行一些对摘要进行上述的操作得到的结果：

原生MD5产生的摘要为               :202cb962ac59075b964b07152d234b70
矩阵第0行左移一位后得到的摘要       :02cb9622ac59075b964b07152d234b70
矩阵第0行右移一位后得到的摘要即原摘要:202cb962ac59075b964b07152d234b70
迭代移动的摘要为                  :2507b592cbbc75d24420126a309709b6
字符替换后的摘要为                :115hg875in4032er09lv98q0vv36ff61
字符替换及迭代移动后得到的摘要      :1496ge03nvfh20v5lf53qv7i610818r9

很明显在经过迭代移动和字符替换之后，整个摘要就已经面目全非了。除非破解本地化算法的细节，不然是无法以原生的彩虹表破解。

彻底解决彩虹表攻击的方法

上面的方法虽然可以解决网站上原生消息摘要算法获取彩虹表的攻击，但是如果有人对你的系统念念不忘，特地为你的本地化构建了一个彩虹表，那么照样不需要你本地化的细节，就可以实现根据你的摘要获取明文。

要彻底解决彩虹表攻击，我们先分析其原理。原理是：

根据密文获取摘要，然后以键值对形式存储起来，然后根据相同的摘要获取对应的明文即可。虽然全部获取很困难，但是我获取比较常见的明文生成的摘要即可，如：abc , 123456 , abc123456等简单摘要就可以了。

这里我们要注意彩虹表是基于一个明文对应一个摘要，然后根据摘要获取明文信息。

那么要破解彩虹表攻击就要同一段明文，得到不同的摘要，并且可以验证，这里的验证指的是下次输入同样的明文你验证这个字符串需要验证通过。

给五秒钟想想怎么破解彩虹表攻击。

好，时间到。公布答案：盐（salt）。

不知道盐的朋友，移步关于盐加密

这里暂时就不详细讲了，可以简单理解为：同一个字符串，加入不同的盐可以得到不同的摘要。

那么这样的话，就轻易解决了彩虹表攻击。因为之前是一个字符对应一个摘要，也就是一对一的关系，现在一个字符可以对应无限多个摘要，那么彩虹表自然是失效了。

我这里以SHA256的加盐及验证为例(参考Spring框架的BCryptPasswordEncoder，只是很大概的类似)。

以下是以字符123、SHA256算法作为演示，其中验证的部分是就如上图演示的那样：

123字符 原生SHA256算法   摘要：a665a45920422f9d417e4867efdc4fb8a04a1f3fff1fa07e998e86f7f7a27ae3
预防彩虹表攻击 123字符获取摘要1：7b541274478e26b3c8286cb2a0eb12f4144db77adb3788cbeb0e4fd0d1600cfb
预防彩虹表攻击 123字符获取摘要2：547deec50ee48b15b2a88c88b13260407605a932e08c202d958b98112a1a8934
验证1的结果为：true
验证2的结果为：true

代码简单实现

TwoDimensionalTransform工具类

该类中包含了对摘要变换的基本的操作，比如行、列移位，字符替换、迭代移位等等。还包括了防止彩虹表攻击的获取摘要以及验证的功能。

/**
 * @author 三文鱼先生
 * @title
 * @description 自定义的二维变换
 * @date 2022/9/26
 **/
public class TwoDimensionalTransform {
    private static String str;//摘要字符
    private static char[][] cs;//摘要产生的矩阵
    private static int rowLength;//矩阵行长度
    private static int columnLength = 8;//矩阵列长度
    private static char[] chars;//摘要的字符数组
    private static boolean isLower = true;//是否小写
    private static TwoDimensionalTransform tdt;//单例模式

    /**
     * @description 用于获取一个实例 单例模式
     * @author 三文鱼先生
     * @date 15:05 2022/9/28 
     * @return com.util.TwoDimensionalTransform
     **/
    public static TwoDimensionalTransform getInstance() {
        if (tdt != null) {
            reSet();
            return tdt;
        }else {
            return new TwoDimensionalTransform();
        }
    }

    /**
     * @description 行移动
     * @author 三文鱼先生
     * @date 15:06 2022/9/28
     * @param rows 西需要移动的行号
     * @param n 移动位数
     * @param module 移动方向 0-左移 1-右移
     * @return void
     **/
    public void rowShift(int rows , int n , int module) {
        if(n > rowLength)
            n = n % rowLength;
        char[] tempChars = new char[columnLength];
        for (int i = 0; i < columnLength; i++){
            tempChars[i] = cs[rows][i];
        }

        for (int i = 0; i < columnLength; i++){
            if (module == 0)
                cs[rows][i] = tempChars[(i+n)%columnLength];
            else
                cs[rows][i] = tempChars[(i-n + columnLength)%columnLength];
        }
    }

    /**
     * @description  列移动
     * @author 三文鱼先生
     * @date 15:08 2022/9/28
     * @param column 移动列号
     * @param n 移动位数
     * @param module 移动方向 0 - 上移 1 - 下移
     * @return void
     **/
    public  void columnShift(int column , int n , int module) {
        if (n > columnLength)
            n = n % columnLength;

        char[] tempChars = new char[rowLength];
        for (int i = 0; i < rowLength; i++){
            tempChars[i] = cs[i][column];
        }

        for (int i = 0; i < rowLength; i++){
            if (module == 0)
                cs[i][column] = tempChars[(i+n)%rowLength];
            else
                cs[i][column] = tempChars[(i-n + rowLength)%rowLength];
        }
    }

    /**
     * @description 初始化基本信息
     * @author 三文鱼先生
     * @date 15:10 2022/9/28
     * @param str1 摘要字符串
     * @return void
     **/
    public void init(String str1) {
        str = str1;
        chars = str1.toCharArray();
        rowLength = chars.length /columnLength;
        cs = new char[rowLength][columnLength];
        for (int i = 0; i < chars.length; i++) {
            //判断是大写还是小写摘要 默认为小写
            if(isLower) {
                if(Character.isUpperCase(chars[i]))
                    isLower = false;
            }
            cs[i/columnLength][i%columnLength] = chars[i];
        }
    }

    /**
     * @description 迭代变换
     * 0行左移0位 1行左移一位 2行左移两位
     * 列的话是上移 规矩从上
     * @author 三文鱼先生
     * @date 15:11 2022/9/28
     * @return void
     **/
    public void iterateShift() {
        for (int i =0; i < rowLength; i++) {
            //0行左移0 1行左移1位
            rowShift(i , i%columnLength , 0);
        }

        for (int i =0; i < columnLength; i++) {
            //0列上移0 列上移1位 。。。
            columnShift(i , i%rowLength , 0);
        }
    }

    /**
     * @description 字符替换
     * 将摘要的数字和字母按照规律替换
     * 并且控制摘要中的数字与字母差在五以内
     * @author 三文鱼先生
     * @date 15:15 2022/9/28
     * @return void
     **/
    public  void replaceCharacters() {
        int strs = 0;
        int nums = 0;
        int result = 0;
        int c = 0;
        for (int i = 0; i < chars.length; i++) {
            result = strs - nums;
            //字符数大于数字数量在 0 - 5中间
            if(Character.isLowerCase(chars[i]) && Math.abs(result) <= 5) {
                //小写字母替换
                c = chars[i];
                c = (c + c%10 + i)%26 + 97;
                chars[i] = (char) c;
                strs = strs + 1;
            } else if(Character.isUpperCase(chars[i]) && Math.abs(result) <= 5) {
                //大写字母替换
                c = chars[i];
                c = (c + c%10 + i)%26 + 65;
                chars[i] = (char) c;
                strs = strs + 1;
            } else if((int)chars[i] <= 57 && (int)chars[i] >= 48 && Math.abs(result) <= 5){
                //数字替换
                c = chars[i];
                c = (c + i*2 + 1)%10 + 48;
                chars[i] = (char) c;
                nums = nums + 1;
            } else if((Character.isUpperCase(chars[i])||Character.isLowerCase(chars[i])) && result > 5) {
                //字符数量比数字多5以上 则将当前字符转为数字
                c = chars[i];
                c = (c + i*2 + 1)%10 + 48;
                chars[i] = (char) c;
                nums = nums + 1;
            } else if((int)chars[i] <= 57 && (int)chars[i] >= 48 && result < -5) {
                //数字数量比字母多5以上 则将当前数字转为字母
                if(isLower) {
                    //数字转小写
                    c = chars[i];
                    c = (c + i*2 + 1)%26 + 97;
                    chars[i] = (char) c;
                } else {
                    //数字转大写
                    c = chars[i];
                    c = (c + i*2 + 1)%26 + 65;
                    chars[i] = (char) c;
                    //大写转数字
                }
                //超出数字转为字符
                strs = strs + 1;
            }
        }
        //更新二维数组
        for (int i = 0; i < chars.length; i++) {
            cs[i/columnLength][i%columnLength] = chars[i];
        }
    }

    /**
     * @description 获取当前对象内的摘要字符串
     * @author 三文鱼先生
     * @date 15:19 2022/9/28 
     * @return java.lang.String
     **/
    public String getStr() {
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < rowLength;i++) {
            for (int j = 0; j < columnLength; j++){
                sb.append(cs[i][j]);
            }
        }
        return sb.toString();
    }

    /**
     * @description 重置对象
     * @author 三文鱼先生
     * @date 15:19 2022/9/28 
     * @return void
     **/
    public static void reSet() {
        tdt.str = null;
        tdt.cs = null;
        tdt.rowLength = 0;
        tdt.chars = null;
        tdt.isLower = true;
    }

    /**
     * @description 预防彩虹表攻击 以随机盐和数据产生摘要 并将盐藏进摘要里
     * @author 三文鱼先生
     * @date 15:19 2022/9/28
     * @param str 产生摘要数据
     * @param algorithm 摘要算法
     * @return void
     **/
    public void preventRainbowTable(String str ,  String algorithm) {
        //重置对象
        reSet();
        StringBuilder sb = new StringBuilder(str);
        //获取当前时间的后三位
        String time = String.valueOf(System.currentTimeMillis());
        String times = time.substring(time.length() - 4);
        //加到字符后面
        sb.append(times);

        //获取新字符串的摘要
        String newStr = getDigestFromAlgorithm(sb.toString() , algorithm);
        //重新初始化对象
        init(newStr);
        //把盐藏进摘要中
        cs[0][rowLength-1] = times.charAt(0);
        cs[1][rowLength-1] = times.charAt(1);
        cs[2][rowLength-1] = times.charAt(2);
        cs[3][rowLength-1] = times.charAt(3);
    }

    /**
     * @description 彩虹表的指定验证方式
     * @author 三文鱼先生
     * @date 15:21 2022/9/28
     * @param str 需验证的明文
     * @param enDigest 数据库中的摘要
     * @param algorithm 指定的算法
     * @return boolean
     **/
    public boolean match(String str , String enDigest , String algorithm){
        StringBuilder sb = new StringBuilder(str);
        init(enDigest);
        char[] temp = new char[4];
        temp[0] = cs[0][rowLength-1];
        temp[1] = cs[1][rowLength-1];
        temp[2] = cs[2][rowLength-1];
        temp[3] = cs[3][rowLength-1];

        sb.append(temp[0]);
        sb.append(temp[1]);
        sb.append(temp[2]);
        sb.append(temp[3]);

        String newStr = getDigestFromAlgorithm(sb.toString() , algorithm);
        reSet();
        init(newStr);

        cs[0][rowLength-1] = temp[0];
        cs[1][rowLength-1] = temp[1];
        cs[2][rowLength-1] = temp[2];
        cs[3][rowLength-1] = temp[3];

        if (getStr().equals(enDigest))
            return true;
        //获取密文里的盐数据
        return false;
    }

    /**
     * @description 根据所给算法和数据 产生对应的摘要
     * @author 三文鱼先生
     * @date 15:22 2022/9/28
     * @param strAddSalt 添加了盐的数据
     * @param algorithm 算法
     * @return java.lang.String
     **/
    public String  getDigestFromAlgorithm(String strAddSalt, String algorithm) {
        if("MD5".equals(algorithm))
            return MD5Utils.getLowerCaseAbstract(strAddSalt);
        if("SHA1".equals(algorithm))
            return SHAUtils.getLowerCaseAbstractBySHA1(strAddSalt);
        if("SHA256".equals(algorithm))
            return SHAUtils.getLowerCaseAbstractBySHA256(strAddSalt);
        if("SM3".equals(algorithm))
            return SM3Utils.getLowerCaseAbstract(strAddSalt);
        return null;
    }
}

TestForDimensional

测试类，上述的简单示范都来自于该类

import com.util.MD5Utils;
import com.util.SHAUtils;
import com.util.TwoDimensionalTransform;

/**
 * @author 三文鱼先生
 * @title
 * @description
 * @date 2022/9/26
 **/
public class TestForDimensional {
    public static void main(String[] args) throws InterruptedException {
        TwoDimensionalTransform tdt = TwoDimensionalTransform.getInstance();
        String digest = MD5Utils.getLowerCaseAbstract("123");
        System.out.println("原生MD5产生的摘要为               :" + digest);
        tdt.init(digest);
        tdt.rowShift(0 , 1 , 0);
        System.out.println("矩阵第0行左移一位后得到的摘要       :"  + tdt.getStr());
        tdt.rowShift(0 , 1 , 1);
        System.out.println("矩阵第0行右移一位后得到的摘要即原摘要:"  + tdt.getStr());
        tdt.iterateShift();
        System.out.println("迭代移动的摘要为                  :" + tdt.getStr());
        tdt.reSet();
        tdt.init(digest);
        tdt.replaceCharacters();
        System.out.println("字符替换后的摘要为                :" + tdt.getStr());
        tdt.iterateShift();
        System.out.println("字符替换及迭代移动后得到的摘要      :" + tdt.getStr());

        tdt.reSet();
        System.out.println("123字符 原生SHA256算法   摘要：" + SHAUtils.getLowerCaseAbstractBySHA256("123"));
        tdt.preventRainbowTable("123" , "SHA256");
        System.out.println("预防彩虹表攻击 123字符获取摘要1：" + tdt.getStr());
        Thread.sleep(1256);
        tdt.preventRainbowTable("123" , "SHA256");
        System.out.println("预防彩虹表攻击 123字符获取摘要2：" + tdt.getStr());

        System.out.println("验证1的结果为：" + tdt.match("123", "ca270c27d49b37061759f6c24ed538f469f0973581aef2e9af978c056a8d8223", "SHA256"));
        System.out.println("验证2的结果为：" + tdt.match("123", "2dc8013854a5a5f8410df0c8f970c3706359b608a0c9cedb5e773af87dc0b5a6", "SHA256"));

    }
}