关于非对称加密算法

在互联网金融公司，包括比较火的区块链，对数据隐私比较敏感，加密算法得到大量应用。非对称加密算法RSA作为众多优秀的加密算法之一，担当起了可靠传输数据的大梁（毫不夸张的说，秘钥长度足够长、且秘钥不被泄露的情况下，信息在有价值时间内被破解的可能性为0。当然，量子计算机就另当别论了）。

RSA算法组成和应用场景

私钥，公钥，算法。其中公钥和算法是公开的，私钥不公开，想传输数据就把公钥给谁，公钥被泄露了也不在乎；私钥不对任何人公开，解密用。这样设计通俗理解就是很多人都可以用我的公钥加密数据，但是加密后的数据，只有拥有私钥的人才可以解密成功。但是这样会存在一个问题，知道公钥的人有很多，这些人都和我传输数据或者发送恶意请求怎么办，我的接口和业务岂不是要出问题。所以在大多数应用场景中，RSA加解密和加签是同时使用的。那加签是怎么回事？加签是这样的，发送消息的一方也生成一对公私钥（注意，和加解密用的公私钥不是同一对）。对加密后的数据用私钥加签，公钥暴露出去，接收方验签的时候用，这样就安全了，验签没通过的数据都都懒得做解密，直接丢掉。这样就保证了数据不会被篡改。真个RSA传输数据的过程是这样的：加密 ->> 加签 ->> 验签 ->> 解密 ，这里二次强调，加签和加密用的公私钥不是同一对。具体示例如下图：

RSA加密实例.jpg

RSA秘钥生成步骤和相关数论知识（可参考文末第二个链接）

 /**
     * 生成公私钥
     * @return 公私钥
     */
    public static Map<String, RSAKey> generateKeyMap() {
        PrimeUtils primeUtils = PrimeUtils.getInstance();
        // 随机生成质数对
        List<Integer> pairPrime = primeUtils.getRandomPairPrime();
        // 计算N
        int numberN = pairPrime.get(1) * pairPrime.get(0);
        // L根据欧拉函数特性： φ(N) = φ(p) * φ(q) = (p - 1) * (q - 1)
        int numberL = (pairPrime.get(0) - 1) * (pairPrime.get(1) - 1);
        // 随机选择d，d为区间[1, numberL)与numberL互质的数,即最大公约数为1的数
        int numberE;
        int numberD;
        do {
            // 运用欧几里得算法，即最大公约数为1的数
            numberE = getRandomGCD(numberL);
            //  运用扩展欧几里得算法求乘法逆元 (e * d - 1) % L = 0
            numberD = getNumberD(numberE, numberL);
        } while (numberD < 0 ); // 扩展欧几里得算法解存在负数,秘钥不选用负数，
        return getPairKeyInMap(numberN, numberE, numberD);
    }

1：随机挑选两个个质数p, q(越大越好，这里只是示例代码生成，所以质数选择在小范围以内挑选)，对两个质数求积，生成的数字为N ,即N = p * q。
2: 计算r在这里代表的意思是：区间从[1, N)区间内与N互质的数的个数，求出 φ(n),根据欧拉函数性质，可以求得：r = φ(N) = φ(p) * φ(q) = (p - 1) * (q - 1)。
3：欧几里得算法计算e, 1 < e < r, （e和r是互质的关系），私钥是根据公钥计算出的公式：根据扩展欧几里得算法，求乘法逆元，e * d ≡ 1 (mod r)，公式等价为：(e * d - 1) % r = 0 （存在一个数d，使等成立）。
4：这样秘钥对就已经出现了私钥：(N ,d), 公钥：（N，e）。

    /**
     * 随机选择与L互质的数，
     * @param numberL 区间
     * @return
     */
    private static int getRandomGCD(int numberL) {
        List<Integer> gcdList = IntStream.range(2, numberL)
                .filter(e -> GCD(numberL, e) == 1)  // 选取最大公约数为1的两个数
                .boxed()
                .collect(Collectors.toList());
        return gcdList.get(random.nextInt(gcdList.size()));
    }

    /**
     * 欧几里得算法，查找最大公约数
     * @param e   除数
     * @param num 被除数
     * @return 最大公约数
     */
    private static int GCD(int num, int e) {
        if (num % e == 0) {
            return e;
        } else {
            return GCD(e, num % e);
        }
    }
 /**
     * 获取numberD 的乘法逆元
     * @param numberE
     * @param numberL
     * @return  满足乘法逆元的数
     */
    public static int getNumberdDetail(int numberE, int numberL) {
        List<Integer> xArr = new ArrayList<>();  // 保存x的递归解集
        List<Integer> yArr = new ArrayList<>();  // 保存y的递归解集
        extgcd(numberE, numberL, xArr, yArr);  // xArr最后加入的元素就是numberD
        int numberD = xArr.get(xArr.size() - 1);
        return xArr.get(xArr.size() - 1);
    }

 /**
     * 扩展欧几里得算法， 求乘法逆元
     * @param a 除数
     * @param b 被除数
     * @param xArr x的递归解集
     * @param yArr y的递归解集
     * @return 最大公约数
     */
    private static int extgcd(int a, int b, List<Integer> xArr, List<Integer> yArr) {
        if (b == 0) {
            xArr.add(1);
            yArr.add(0);
            return a;
        }
        int ans = extgcd(b, a % b, xArr, yArr);
        int t = xArr.get(xArr.size() - 1);
        xArr.add(yArr.get(yArr.size() - 1));
        yArr.add(t - (a / b) * yArr.get(yArr.size() - 1));
        return ans;
    }

加密和解密

m: 明文 c：密文
加解密:
1：明文为m对应的二进制的必须小于N（每次的加密长度不能超过秘钥长度）。
2：加密公式： c ≡ m^e mod(N) 等价于： m^e % N = c 。
3：解密公式： m = c^d mod(N) 等价于: c^d % N = m 。

 /**
     * 加密明文
     * @param a 明文
     * @param pubKey 公钥
     * @return 加密后二进制字符串
     */
    public static String getEnString(String a, RSAPubKey pubKey) {
        // 获取对应的字节流
        byte[] bytes = a.getBytes(StandardCharsets.UTF_8);
        // 已字节为单位的加密长度
        int Nlen = Integer.toBinaryString(pubKey.getNumberN()).length();
        StringBuilder stringBuilder = new StringBuilder();
        // 对字节进行逐个加密
        for (byte b : bytes) {
//            JDK内部幂模运算
//            BigInteger bi = new BigInteger(Integer.toString(Byte.toUnsignedInt(b)));
//            BigInteger encodeElem = bi.pow(pubKey.getNumberE()).mod(new BigInteger(Integer.toString(pubKey.getNumberN())));
//            String elemBinStr = getShortBinStr(encodeElem.intValue(), Nlen);

            // 蒙哥马利幂模运算，求余数。加密字节, 特殊符和汉字会得到对应的负数，
            // 这里采用转换为无符号整型存储，解密时强转为byte（只留低八位）
            int molRes = modmul(Byte.toUnsignedInt(b), pubKey.getNumberE(), pubKey.getNumberN());
            String elemBinStr = getShortBinStr(molRes, Nlen);
            stringBuilder.append(elemBinStr);
        }
        return stringBuilder.toString();
    }

 /**
     * 私钥解密
     * @param enStr 密文二进制串
     * @param priKey  私钥
     * @return  明文
     */
    public static String getDeString(String enStr, RSAPriKey priKey) {
        int enLen = Integer.toBinaryString(priKey.getNumberN()).length();
        // deArr,存放解密后的字节数组。numberN的二进制字符串长度
        byte[] deArr = new byte[enStr.length() / enLen];
        for (int i = 0; i < enStr.length(); i += enLen) {
            short deElem = Short.valueOf(enStr.substring(i, i + enLen), 2);
            // JDK内部幂模预算
//            BigInteger me = new BigInteger(Short.toString(deElem))
//                    .pow(priKey.getNumberD()).mod(new BigInteger(Integer.toString(priKey.getNumberN())));
//            byte elem = (byte) me.intValue();
            // 蒙哥马利幂模运算
            int meRes = modmul(deElem, priKey.getNumberD(), priKey.getNumberN());
            // 强转为byte类型，恢复原始字节最高位代表的符号位
            byte elem = (byte) meRes;
            deArr[i / enLen] = elem;
        }
        return new String(deArr, StandardCharsets.UTF_8);
    }

密过程中会遇到结果过大的情况，如明文c为113，公钥为1134 此时 m^r会很大，解决方法有两种：
1：使用java BigInteger类内置的方法。
2：蒙哥马利幂模运算。本文中采用蒙哥马利幂模运算。

/**
     * 蒙哥马利幂模运算
     * @param base    底数
     * @param pow     指数
     * @param numberN 除数
     * @return 模结果
     */
    public static int modmul(int base, int pow, int numberN) {
        int res = 1;
        base = base % numberN;
        while (pow > 0) {
            if (pow % 2 == 1) {
                res = (res * base) % numberN;
            }
            base = (base * base) % numberN;
            pow = pow >> 1;
        }
        return res;
    }

至此RSA从秘钥生成，到加密解密，已经完成。
测试结果：

public static void main(String[] args) {
        int failCount = 0;
        int totalCount = 0;
        // 模拟加密100次，以防偶然性
        for (int i = 0; i < 100; i++) {
            // 获取秘钥对
            Map<String, RSAKey> map = generateKeyMap();
            RSAPriKey priKey = (RSAPriKey) map.get("privateKey");
            RSAPubKey pubKey = (RSAPubKey) map.get("publicKey");
            
            // 模拟需要加密数据
            Student zxerjones = new Student();
            zxerjones.setAge(random.nextInt(100));
            zxerjones.setDes("3a!^D`~&*#@%$^有位非常漂亮的女同事，有天起晚了没有时间化妆便急忙冲到公司。结果那天她被记旷工了……吃惊");
            zxerjones.setName("zxerjones");
            String str = JSON.toJSONString(zxerjones);

            System.out.println("加密前字符串: " + str);
            String enStr = getEnString(str, pubKey);
            System.out.println("加密之后的二进制串:" + enStr);
            String deStr = getDeString(enStr, priKey);
            System.out.println("解密后字符串: " + deStr);
            if (!deStr.equals(str)) {
                failCount++;
            }
            System.out.println("----------------------------");
            totalCount++;

        }
        System.out.println("-------------------总共失败了： " +  failCount +  " 次-----------");
        System.out.println("-------------------总共加密了： " +  totalCount +  " 次-----------");
    }

运行结果：

----------------------------
加密前字符串: {"age":4,"des":"3a!^D`~&*#@%$^有位非常漂亮的女同事，有天起晚了没有时间化妆便急忙冲到公司。结果那天她被记旷工了……吃惊","name":"zxerjones"}
加密之后的二进制串:000101111110110001101000000101000010011011000110000100100100101011000110100000100001110110101010110000010110111011010100011010000000111001111000010010010101010110101101110001101000001000011101101100011010000010011000001010101000010011010011101111100100010111001000110000110000100110111000110011010000110010011000010110001001001011010111000001101100011001000000001001011000110110010001011100011101001101001000000001100110101011110011101001010001111110110100111110000111000011000000101101101111111000000001111001111011110110001101110101000110111010011101001101000100001110100111100011011011101001010001111110010110010110111001100100101011100100010011110101000110000001111011110101010101111010100001110010001111011110100000111011010100101010110011101001010001111110010110001011010011100100001111000100001110100100101010110011101001101001000000001100110101011110001111011110100000100000100111110001100010000110001000101010111110010001001011011101001101000100000001010010001001111011101001010001111110010110011000101111011101001101001111100010110010111100011011101001101001000000001100110101011110011101001101001000011011010000111111011000011000000101000011011011000000110011001111011110101001010101100001010110001001111011110101101010001010011000101111011101001010010001010001100110010000111011101001101001000100111100101010111101001111011110101100100001110010000000101001111011110100110001011110111110001011001111011110100101011000010101110000110001111011110100000001011000011011001101001111011110100000100011111000110111010010000100110101000100111100111100011011100100101011100001110110100011111111101011101001101010000000011110100000000110000011000000101111000110110010100110011001111011110100000100000100111110001100001111011110101010101111010111100101011010000110001000100000000000000110110000010000110001000101101110010101110000110011101001101001000011011010010001001011001111011110100100010010110101010111101011101001010001111110010110011000101111010001101111001000100111100110101000101010001101111001000100111100110101000101001111011110100000111011010000110000111011101001101000001100001111010000110111100011010000001101110110101000110100000000110010011101010000100110111011010000001001001010110001101000001000011101101100011010000010011010011000101001001111001001001010101100000111100110110010100101000000001000011001001110010010010101010110101101110001101000000011001111010
解密后字符串: {"age":4,"des":"3a!^D`~&*#@%$^有位非常漂亮的女同事，有天起晚了没有时间化妆便急忙冲到公司。结果那天她被记旷工了……吃惊","name":"zxerjones"}
----------------------------
-------------------总共失败了： 0 次-----------
-------------------总共加密了： 100 次-----------

以上代码只用来试手，涉及上有也存在缺陷，有兴趣可以一起讨论。在实际应用中，秘钥长度经常取1024，2048 ，也意味着加密的数据长度不能超过秘钥长度，也就是对应的128字节和256字节，实际应用中，会使用分段加密的方式对明文加密，并且采用填充的方式每次加密的实际数据也不可能刚好是128字节，256字节，具体填充方式可参阅：http://www.faqs.org/rfcs/rfc2313.html。代码只涉及到了加密和解密，没有加签和验签，填充，后续有时间会补充。

参考文献：
https://blog.csdn.net/qq_40693171/article/details/84196607
https://blog.csdn.net/JohnnyMartin/article/details/84622214
https://baike.baidu.com/item/%E8%92%99%E5%93%A5%E9%A9%AC%E5%88%A9%E5%B9%82%E6%A8%A1%E8%BF%90%E7%AE%97/10566438?fr=aladdin