Java 實作 RSA 加密演算法：從數學原理到完整程式碼教學

前言：非對稱加密的基石

RSA (Rivest-Shamir-Adleman) 是最經典的公開金鑰加密演算法，廣泛應用於 TLS/SSL、數位簽章、SSH、PGP 等安全協定。本文從數學原理推導、關鍵步驟說明，到 Java 完整實作與測試，帶您徹底掌握 RSA 核心機制。

RSA 數學原理

核心假設：大整數分解困難性

給定兩個大質數 p, q，計算 n = p × q 容易；但給定 n 反推 p, q 極難 (次指數複雜度)。這是 RSA 安全性的基石。

金鑰生成五步驟

1. 選擇兩個大質數：p, q (實務應用中 ≥ 1024 bits，通常 2048/4096 bits)
2. 計算模數與托特函數：n = p × q，φ(n) = (p-1)(q-1)
3. 選擇公鑰指數：e，滿足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1 (常用 65537 = 2¹⁶+1)
4. 計算私鑰指數：d ≡ e-1 (mod φ(n))，即 e × d ≡ 1 (mod φ(n))，用擴展歐幾里得算法求解
5. 公開/私密金鑰對：公鑰 (e, n)，私鑰 (d, n) (實務常保存 p, q, d, dP, dQ, qInv 以 CRT 加速解密)

加密與解密

• 加密：c ≡ me (mod n)，m 為明文整數 (0 ≤ m < n)
• 解密：m ≡ cd (mod n)
• 正確性證明：基於歐拉定理 mφ(n) ≡ 1 (mod n)，因 ed = kφ(n) + 1，故 med ≡ m (mod n)

Java 實作：教學版完整程式碼

注意：此為教學示範，使用 long 型別與簡易質數測試，**不可用於生產環境**。生產請使用 java.security、javax.crypto 或 Bouncy Castle。

import java.io.*;
import java.math.BigInteger;
import java.security.SecureRandom;

public class RSADemo {

    // 核心參數
    private BigInteger p, q, n, phi, e, d;

    // 建構子：指定位數生成金鑰對 (教學用 16-32 bits，實務 2048+)
    public RSADemo(int bitLength) {
        SecureRandom random = new SecureRandom();
        // 1. 生成兩個大質數
        p = BigInteger.probablePrime(bitLength / 2, random);
        q = BigInteger.probablePrime(bitLength / 2, random);
        // 2. 計算 n, φ(n)
        n = p.multiply(q);
        phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
        // 3. 選擇 e (常用 65537)
        e = BigInteger.valueOf(65537);
        // 確保 e 與 φ(n) 互質
        while (phi.gcd(e).compareTo(BigInteger.ONE) > 0) {
            e = e.add(BigInteger.TWO); // 簡單處理：嘗試下一個奇數
        }
        // 4. 計算 d = e^-1 mod φ(n)
        d = e.modInverse(phi);
    }

    // 加密：c = m^e mod n
    public BigInteger encrypt(BigInteger message) {
        return message.modPow(e, n);
    }

    // 解密：m = c^d mod n
    public BigInteger decrypt(BigInteger ciphertext) {
        return ciphertext.modPow(d, n);
    }

    // 取得公鑰/私鑰資訊
    public BigInteger getPublicExponent() { return e; }
    public BigInteger getModulus() { return n; }
    public BigInteger getPrivateExponent() { return d; }

    // 主程式測試
    public static void main(String[] args) throws Exception {
        // 使用 32 bits 模數演示 (極小，僅教學)
        RSADemo rsa = new RSADemo(32);
        
        System.out.println("=== RSA 金鑰資訊 ===");
        System.out.println("p = " + rsa.p);
        System.out.println("q = " + rsa.q);
        System.out.println("n = " + rsa.n);
        System.out.println("φ(n) = " + rsa.phi);
        System.out.println("公鑰 e = " + rsa.e);
        System.out.println("私鑰 d = " + rsa.d);
        
        // 測試加解密
        String plainText = "Hello RSA";
        System.out.println("\n=== 加解密測試 ===");
        System.out.println("原始明文: " + plainText);
        
        // 將字串轉為 BigInteger (UTF-8 位元組)
        byte[] msgBytes = plainText.getBytes("UTF-8");
        BigInteger message = new BigInteger(1, msgBytes); // 正數
        
        // 確保訊息 < n
        if (message.compareTo(rsa.n) >= 0) {
            System.err.println("訊息過長，超過模數 n。教學版請縮短訊息或增加位數。");
            return;
        }
        
        BigInteger encrypted = rsa.encrypt(message);
        BigInteger decrypted = rsa.decrypt(encrypted);
        
        System.out.println("加密後 (十六進位): " + encrypted.toString(16));
        System.out.println("解密後位元組: " + decrypted.toByteArray().length);
        System.out.println("解密後明文: " + new String(decrypted.toByteArray(), "UTF-8"));
        
        // 驗證數位簽章概念：私鑰加密 -> 公鑰解密
        System.out.println("\n=== 數位簽章示意 ===");
        BigInteger signature = rsa.decrypt(message); // 實際應用用 PKCS#1 v1.5 / PSS padding
        BigInteger verified = rsa.encrypt(signature);
        System.out.println("簽章驗證 " + (verified.equals(message) ? "通過" : "失敗"));
    }
}

關鍵 API 與最佳實務解析

生產環境標準用法：JCA (Java Cryptography Architecture)

import java.security.*;
import javax.crypto.Cipher;

public class RSAProductionExample {
    public static void main(String[] args) throws Exception {
        // 1. 金鑰對生成 (2048 bits)
        KeyPairGenerator kpg = KeyPairGenerator.getInstance("RSA");
        kpg.initialize(2048, SecureRandom.getInstanceStrong());
        KeyPair keyPair = kpg.generateKeyPair();
        PublicKey publicKey = keyPair.getPublic();
        PrivateKey privateKey = keyPair.getPrivate();

        // 2. 加密：RSA/ECB/OAEPWithSHA-256AndMGF1Padding
        Cipher encryptCipher = Cipher.getInstance("RSA/ECB/OAEPWithSHA-256AndMGF1Padding");
        encryptCipher.init(Cipher.ENCRYPT_MODE, publicKey);
        byte[] plaintext = "機密資料".getBytes("UTF-8");
        byte[] ciphertext = encryptCipher.doFinal(plaintext);
        System.out.println("加密完成，長度: " + ciphertext.length + " bytes");

        // 3. 解密
        Cipher decryptCipher = Cipher.getInstance("RSA/ECB/OAEPWithSHA-256AndMGF1Padding");
        decryptCipher.init(Cipher.DECRYPT_MODE, privateKey);
        byte[] decrypted = decryptCipher.doFinal(ciphertext);
        System.out.println("解密結果: " + new String(decrypted, "UTF-8"));

        // 4. 數位簽章：SHA256withRSA / RSASSA-PSS
        Signature sig = Signature.getInstance("SHA256withRSA");
        sig.initSign(privateKey);
        sig.update(plaintext);
        byte[] signature = sig.sign();
        
        Signature verifySig = Signature.getInstance("SHA256withRSA");
        verifySig.initVerify(publicKey);
        verifySig.update(plaintext);
        System.out.println("簽章驗證: " + verifySig.verify(signature));
    }
}

常見坑與安全建議

1. 絕不使用教科書 RSA (無填充)：易受選擇明文攻擊、可鍛造性攻擊。必須用 OAEP (加密) / PSS (簽章)。
2. 金鑰長度至少 2048 bits：1024 bits 已被淘汰，NIST 建議 2030 年後移至 3072 bits。
3. 私鑰保護：加密儲存、HSM、硬體安全模組、定期輪換。
4. 混合加密：RSA 只加密對稱金鑰 (AES-GCM)，大量資料用對稱加密。
5. 防時序攻擊：JDK modPow 已有常時間實作，但應用層比較 (如驗證簽章) 需用 MessageDigest.isEqual()。
6. 量子威脅：Shor 算法可在量子電腦上多項式時間破解 RSA。關注 NIST PQC 標準化 (CRYSTALS-Kyber, CRYSTALS-Dilithium 等)，規劃遷移路徑。

結語

RSA 以優雅的數學結構奠定現代公開金鑰密碼學基石。理解其原理 (模冪運算、歐拉定理、擴展歐幾里得算法) 能幫助開發者正確使用密碼學 API、避開常見陷阱。教學版實作展示核心邏輯；生產環境請務必使用經過嚴格審計的 JCA/Bouncy Castle 實作、標準填充模式、足夠金鑰長度、安全金鑰管理。隨著後量子密碼學 (PQC) 成熟，RSA 將逐步退出歷史舞台，但其設計思想將持續啟發新一代密碼演算法。