在互聯(lián)網(wǎng)金融公司捆姜，包括比較火的區(qū)塊鏈，對(duì)數(shù)據(jù)隱私比較敏感，加密算法得到大量應(yīng)用谆膳。非對(duì)稱加密算法RSA作為眾多優(yōu)秀的加密算法之一皮官，擔(dān)當(dāng)起了可靠傳輸數(shù)據(jù)的大梁（毫不夸張的說脯倒，秘鑰長(zhǎng)度足夠長(zhǎng)、且秘鑰不被泄露的情況下捺氢，信息在有價(jià)值時(shí)間內(nèi)被破解的可能性為0藻丢。當(dāng)然，量子計(jì)算機(jī)就另當(dāng)別論了）摄乒。

RSA算法組成和應(yīng)用場(chǎng)景

私鑰悠反，公鑰残黑，算法。其中公鑰和算法是公開的斋否，私鑰不公開梨水，想傳輸數(shù)據(jù)就把公鑰給誰，公鑰被泄露了也不在乎茵臭；私鑰不對(duì)任何人公開疫诽，解密用。這樣設(shè)計(jì)通俗理解就是很多人都可以用我的公鑰加密數(shù)據(jù)旦委，但是加密后的數(shù)據(jù)奇徒，只有擁有私鑰的人才可以解密成功。但是這樣會(huì)存在一個(gè)問題缨硝，知道公鑰的人有很多逼龟，這些人都和我傳輸數(shù)據(jù)或者發(fā)送惡意請(qǐng)求怎么辦，我的接口和業(yè)務(wù)豈不是要出問題追葡。所以在大多數(shù)應(yīng)用場(chǎng)景中腺律，RSA加解密和加簽是同時(shí)使用的。那加簽是怎么回事宜肉？加簽是這樣的匀钧，發(fā)送消息的一方也生成一對(duì)公私鑰（注意，和加解密用的公私鑰不是同一對(duì)）谬返。對(duì)加密后的數(shù)據(jù)用私鑰加簽之斯，公鑰暴露出去，接收方驗(yàn)簽的時(shí)候用遣铝，這樣就安全了佑刷，驗(yàn)簽沒通過的數(shù)據(jù)都都懶得做解密，直接丟掉酿炸。這樣就保證了數(shù)據(jù)不會(huì)被篡改瘫絮。真?zhèn)€RSA傳輸數(shù)據(jù)的過程是這樣的：加密 ->> 加簽 ->> 驗(yàn)簽 ->> 解密 ，這里二次強(qiáng)調(diào)填硕，加簽和加密用的公私鑰不是同一對(duì)麦萤。具體示例如下圖：

RSA加密實(shí)例.jpg

RSA秘鑰生成步驟和相關(guān)數(shù)論知識(shí)（可參考文末第二個(gè)鏈接）

 /**
     * 生成公私鑰
     * @return 公私鑰
     */
    public static Map<String, RSAKey> generateKeyMap() {
        PrimeUtils primeUtils = PrimeUtils.getInstance();
        // 隨機(jī)生成質(zhì)數(shù)對(duì)
        List<Integer> pairPrime = primeUtils.getRandomPairPrime();
        // 計(jì)算N
        int numberN = pairPrime.get(1) * pairPrime.get(0);
        // L根據(jù)歐拉函數(shù)特性： φ(N) = φ(p) * φ(q) = (p - 1) * (q - 1)
        int numberL = (pairPrime.get(0) - 1) * (pairPrime.get(1) - 1);
        // 隨機(jī)選擇d，d為區(qū)間[1, numberL)與numberL互質(zhì)的數(shù),即最大公約數(shù)為1的數(shù)
        int numberE;
        int numberD;
        do {
            // 運(yùn)用歐幾里得算法扁眯，即最大公約數(shù)為1的數(shù)
            numberE = getRandomGCD(numberL);
            //  運(yùn)用擴(kuò)展歐幾里得算法求乘法逆元 (e * d - 1) % L = 0
            numberD = getNumberD(numberE, numberL);
        } while (numberD < 0 ); // 擴(kuò)展歐幾里得算法解存在負(fù)數(shù),秘鑰不選用負(fù)數(shù)壮莹，
        return getPairKeyInMap(numberN, numberE, numberD);
    }

1： 隨機(jī)挑選兩個(gè)個(gè)質(zhì)數(shù)p, q(越大越好，這里只是示例代碼生成姻檀，所以質(zhì)數(shù)選擇在小范圍以內(nèi)挑選)命满，對(duì)兩個(gè)質(zhì)數(shù)求積， 生成的數(shù)字為N ,即N = p * q绣版。
2: 計(jì)算r在這里代表的意思是 ：區(qū)間從[1, N)區(qū)間內(nèi)與N互質(zhì)的數(shù)的個(gè)數(shù)胶台，求出 φ(n),根據(jù)歐拉函數(shù)性質(zhì)狭莱，可以求得：r = φ(N) = φ(p) * φ(q) = (p - 1) * (q - 1)。
3： 歐幾里得算法計(jì)算e, 1 < e < r, （e和r是互質(zhì)的關(guān)系）概作，私鑰是根據(jù)公鑰計(jì)算出的公式： 根據(jù)擴(kuò)展歐幾里得算法腋妙，求乘法逆元，e * d ≡ 1 (mod r)讯榕，公式等價(jià)為：(e * d - 1) % r = 0 （存在一個(gè)數(shù)d骤素，使等成立）。
4： 這樣秘鑰對(duì)就已經(jīng)出現(xiàn)了 私鑰：(N ,d), 公鑰：（N愚屁，e）济竹。

    /**
     * 隨機(jī)選擇與L互質(zhì)的數(shù)，
     * @param numberL 區(qū)間
     * @return
     */
    private static int getRandomGCD(int numberL) {
        List<Integer> gcdList = IntStream.range(2, numberL)
                .filter(e -> GCD(numberL, e) == 1)  // 選取最大公約數(shù)為1的兩個(gè)數(shù)
                .boxed()
                .collect(Collectors.toList());
        return gcdList.get(random.nextInt(gcdList.size()));
    }

    /**
     * 歐幾里得算法霎槐，查找最大公約數(shù)
     * @param e   除數(shù)
     * @param num 被除數(shù)
     * @return 最大公約數(shù)
     */
    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  滿足乘法逆元的數(shù)
     */
    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);
    }

 /**
     * 擴(kuò)展歐幾里得算法送浊， 求乘法逆元
     * @param a 除數(shù)
     * @param b 被除數(shù)
     * @param xArr x的遞歸解集
     * @param yArr y的遞歸解集
     * @return 最大公約數(shù)
     */
    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對(duì)應(yīng)的二進(jìn)制的必須小于N（每次的加密長(zhǎng)度不能超過秘鑰長(zhǎng)度）。
??2：加密公式： c ≡ m^e mod(N) 等價(jià)于： m^e % N = c 丘跌。
??3：解密公式： m = c^d mod(N) 等價(jià)于: c^d % N = m 袭景。

 /**
     * 加密明文
     * @param a 明文
     * @param pubKey 公鑰
     * @return 加密后二進(jìn)制字符串
     */
    public static String getEnString(String a, RSAPubKey pubKey) {
        // 獲取對(duì)應(yīng)的字節(jié)流
        byte[] bytes = a.getBytes(StandardCharsets.UTF_8);
        // 已字節(jié)為單位的加密長(zhǎng)度
        int Nlen = Integer.toBinaryString(pubKey.getNumberN()).length();
        StringBuilder stringBuilder = new StringBuilder();
        // 對(duì)字節(jié)進(jìn)行逐個(gè)加密
        for (byte b : bytes) {
//            JDK內(nèi)部?jī)缒＿\(yùn)算
//            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);

            // 蒙哥馬利冪模運(yùn)算，求余數(shù)闭树。加密字節(jié), 特殊符和漢字會(huì)得到對(duì)應(yīng)的負(fù)數(shù)耸棒，
            // 這里采用轉(zhuǎn)換為無符號(hào)整型存儲(chǔ)，解密時(shí)強(qiáng)轉(zhuǎn)為byte（只留低八位）
            int molRes = modmul(Byte.toUnsignedInt(b), pubKey.getNumberE(), pubKey.getNumberN());
            String elemBinStr = getShortBinStr(molRes, Nlen);
            stringBuilder.append(elemBinStr);
        }
        return stringBuilder.toString();
    }

 /**
     * 私鑰解密
     * @param enStr 密文二進(jìn)制串
     * @param priKey  私鑰
     * @return  明文
     */
    public static String getDeString(String enStr, RSAPriKey priKey) {
        int enLen = Integer.toBinaryString(priKey.getNumberN()).length();
        // deArr,存放解密后的字節(jié)數(shù)組报辱。numberN的二進(jìn)制字符串長(zhǎng)度
        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內(nèi)部?jī)缒ｎA(yù)算
//            BigInteger me = new BigInteger(Short.toString(deElem))
//                    .pow(priKey.getNumberD()).mod(new BigInteger(Integer.toString(priKey.getNumberN())));
//            byte elem = (byte) me.intValue();
            // 蒙哥馬利冪模運(yùn)算
            int meRes = modmul(deElem, priKey.getNumberD(), priKey.getNumberN());
            // 強(qiáng)轉(zhuǎn)為byte類型与殃，恢復(fù)原始字節(jié)最高位代表的符號(hào)位
            byte elem = (byte) meRes;
            deArr[i / enLen] = elem;
        }
        return new String(deArr, StandardCharsets.UTF_8);
    }

密過程中會(huì)遇到結(jié)果過大的情況，如明文c為113碍现，公鑰為1134 此時(shí) m^r會(huì)很大幅疼，解決方法有兩種：
??1：使用java BigInteger類內(nèi)置的方法。
??2：蒙哥馬利冪模運(yùn)算昼接。本文中采用蒙哥馬利冪模運(yùn)算爽篷。

/**
     * 蒙哥馬利冪模運(yùn)算
     * @param base    底數(shù)
     * @param pow     指數(shù)
     * @param numberN 除數(shù)
     * @return 模結(jié)果
     */
    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從秘鑰生成，到加密解密辩棒，已經(jīng)完成狼忱。
測(cè)試結(jié)果：

public static void main(String[] args) {
        int failCount = 0;
        int totalCount = 0;
        // 模擬加密100次膨疏，以防偶然性
        for (int i = 0; i < 100; i++) {
            // 獲取秘鑰對(duì)
            Map<String, RSAKey> map = generateKeyMap();
            RSAPriKey priKey = (RSAPriKey) map.get("privateKey");
            RSAPubKey pubKey = (RSAPubKey) map.get("publicKey");
            
            // 模擬需要加密數(shù)據(jù)
            Student zxerjones = new Student();
            zxerjones.setAge(random.nextInt(100));
            zxerjones.setDes("3a!^D`~&*#@%$^有位非常漂亮的女同事一睁，有天起晚了沒有時(shí)間化妝便急忙沖到公司。結(jié)果那天她被記曠工了……吃驚");
            zxerjones.setName("zxerjones");
            String str = JSON.toJSONString(zxerjones);

            System.out.println("加密前字符串: " + str);
            String enStr = getEnString(str, pubKey);
            System.out.println("加密之后的二進(jìn)制串:" + 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 +  " 次-----------");
    }

運(yùn)行結(jié)果：

----------------------------
加密前字符串: {"age":4,"des":"3a!^D`~&*#@%$^有位非常漂亮的女同事佃却，有天起晚了沒有時(shí)間化妝便急忙沖到公司者吁。結(jié)果那天她被記曠工了……吃驚","name":"zxerjones"}
加密之后的二進(jìn)制串:000101111110110001101000000101000010011011000110000100100100101011000110100000100001110110101010110000010110111011010100011010000000111001111000010010010101010110101101110001101000001000011101101100011010000010011000001010101000010011010011101111100100010111001000110000110000100110111000110011010000110010011000010110001001001011010111000001101100011001000000001001011000110110010001011100011101001101001000000001100110101011110011101001010001111110110100111110000111000011000000101101101111111000000001111001111011110110001101110101000110111010011101001101000100001110100111100011011011101001010001111110010110010110111001100100101011100100010011110101000110000001111011110101010101111010100001110010001111011110100000111011010100101010110011101001010001111110010110001011010011100100001111000100001110100100101010110011101001101001000000001100110101011110001111011110100000100000100111110001100010000110001000101010111110010001001011011101001101000100000001010010001001111011101001010001111110010110011000101111011101001101001111100010110010111100011011101001101001000000001100110101011110011101001101001000011011010000111111011000011000000101000011011011000000110011001111011110101001010101100001010110001001111011110101101010001010011000101111011101001010010001010001100110010000111011101001101001000100111100101010111101001111011110101100100001110010000000101001111011110100110001011110111110001011001111011110100101011000010101110000110001111011110100000001011000011011001101001111011110100000100011111000110111010010000100110101000100111100111100011011100100101011100001110110100011111111101011101001101010000000011110100000000110000011000000101111000110110010100110011001111011110100000100000100111110001100001111011110101010101111010111100101011010000110001000100000000000000110110000010000110001000101101110010101110000110011101001101001000011011010010001001011001111011110100100010010110101010111101011101001010001111110010110011000101111010001101111001000100111100110101000101010001101111001000100111100110101000101001111011110100000111011010000110000111011101001101000001100001111010000110111100011010000001101110110101000110100000000110010011101010000100110111011010000001001001010110001101000001000011101101100011010000010011010011000101001001111001001001010101100000111100110110010100101000000001000011001001110010010010101010110101101110001101000000011001111010
解密后字符串: {"age":4,"des":"3a!^D`~&*#@%$^有位非常漂亮的女同事，有天起晚了沒有時(shí)間化妝便急忙沖到公司饲帅。結(jié)果那天她被記曠工了……吃驚","name":"zxerjones"}
----------------------------
-------------------總共失敗了： 0 次-----------
-------------------總共加密了： 100 次-----------

以上代碼只用來試手复凳，涉及上有也存在缺陷瘤泪，有興趣可以一起討論。在實(shí)際應(yīng)用中育八，秘鑰長(zhǎng)度經(jīng)常取1024对途，2048 ，也意味著加密的數(shù)據(jù)長(zhǎng)度不能超過秘鑰長(zhǎng)度髓棋， 也就是對(duì)應(yīng)的128字節(jié)和256字節(jié)实檀，實(shí)際應(yīng)用中，會(huì)使用分段加密的方式對(duì)明文加密按声，并且采用填充的方式每次加密的實(shí)際數(shù)據(jù)也不可能剛好是128字節(jié)膳犹，256字節(jié)，具體填充方式可參閱：http://www.faqs.org/rfcs/rfc2313.html签则。代碼只涉及到了加密和解密须床，沒有加簽和驗(yàn)簽，填充渐裂，后續(xù)有時(shí)間會(huì)補(bǔ)充豺旬。

參考文獻(xiàn)：
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