從零手寫 Java RSA：密鑰生成、加解密核心原理與完整實現

從零手寫 Java RSA：密鑰生成、加解密核心原理與完整實現

RSA 核心數學基礎

• 易算：給定大素數 p, q，計算 n = p*q 容易
• 難解：給定 n，分解為 p, q 極難（大整數因子分解問題）

密鑰體系定義

• n = p * q
• φ(n) = (p-1)(q-1)
• 選擇 b (公鑰指數)，滿足 1 < b < φ(n) 且 gcd(b, φ(n)) = 1，常用 65537
• 計算 a (私鑰指數)，滿足 a*b ≡ 1 (mod φ(n))，即模逆元
• 公鑰：(n, b) | 私鑰：(n, a)（p, q 銷毀）

加解密公式

• 加密：C = M^b mod n
• 解密：M = C^a mod n

核心代碼實現

1. 密鑰封裝類

public class PublicKey { private final BigInteger n, b; /* getter */ }
public class PrivateKey { private final BigInteger n, a; /* getter */ }
public class RsaKeyPair { private final PublicKey publicKey; private final PrivateKey privateKey; /* getter */ }

2. 大素數生成（借用 BigInteger）

SecureRandom random = new SecureRandom();
random.setSeed(new Date().getTime());
BigInteger p = BigInteger.probablePrime(bitLength, random);
BigInteger q = BigInteger.probablePrime(bitLength, random);

3. 擴展歐幾里得算法求模逆元（核心）

private static BigInteger x, y;

// 遞歸求解 ax + by = gcd(a,b)
public static BigInteger ex_gcd(BigInteger a, BigInteger b) {
    if (b.equals(BigInteger.ZERO)) {
        x = BigInteger.ONE; y = BigInteger.ZERO; return a;
    }
    BigInteger ans = ex_gcd(b, a.mod(b));
    BigInteger tmp = x;
    x = y;
    y = tmp.subtract(a.divide(b).multiply(y));
    return ans;
}

// 求 a 對模 k 的乘法逆元
public static BigInteger cal(BigInteger a, BigInteger k) {
    BigInteger gcd = ex_gcd(a, k);
    if (!BigInteger.ONE.equals(gcd)) return BigInteger.valueOf(-1);
    x = x.multiply(BigInteger.ONE.divide(gcd));
    k = k.abs();
    BigInteger ans = x.mod(k);
    return ans.compareTo(BigInteger.ZERO) < 0 ? ans.add(k) : ans;
}

4. 密鑰對生成整合

public static RsaKeyPair generatorKey(int bitLength) {
    // 生成 p, q, n, φ(n)
    // 選擇 b (公鑰指數)
    BigInteger a = cal(b, k); // 計算私鑰指數
    return new RsaKeyPair(new PublicKey(n, b), new PrivateKey(n, a));
}

5. 加解密工具類（含 Base64 編碼）

public static String encrypt(String src, PublicKey key, String charset) {
    byte[] bytes = src.getBytes(charset);
    BigInteger m = new BigInteger(1, bytes); // 正數標識
    BigInteger c = m.modPow(key.getB(), key.getN());
    return Base64.encodeBase64String(c.toByteArray());
}

public static String decrypt(String cipher, PrivateKey key, String charset) {
    byte[] bytes = Base64.decodeBase64(cipher);
    BigInteger c = new BigInteger(bytes);
    BigInteger m = c.modPow(key.getA(), key.getN());
    byte[] plain = m.toByteArray();
    // 關鍵：BigInteger 以符號位開頭，需去除首字節
    plain = Arrays.copyOfRange(plain, 1, plain.length);
    return new String(plain, charset);
}

關鍵坑點提示

• BigInteger 符號位：toByteArray() 最高位為符號位，解密時必須 copyOfRange(1, len) 去除，否則中文解密會出現亂碼/前綴空格
• 編碼一致性：加解密雙端必須使用相同字符集（推薦 UTF-8）
• 密鑰長度：演示用 256/1024 位，生產環境建議 ≥ 2048 位

JUnit 測試驗證

@Test
public void testRSA() {
    RsaKeyPair kp = RSAGeneratorKey.generatorKey(1024);
    String src = "哈哈哈哈哈~~~嘿嘿嘿嘿嘿~~---呵呵呵呵呵！";
    String enc = RSAUtil.encrypt(src, kp.getPublicKey(), "UTF-8");
    String dec = RSAUtil.decrypt(enc, kp.getPrivateKey(), "UTF-8");
    assertEquals(src, dec);
}

測試通過，核心流程打通。完整代碼結構見文中截圖。