每日算法 — 使用java实现RSA加密：非对称密钥体系与模幂运算

概述

RSA算法是当今互联网安全的基石，广泛应用于HTTPS、数字签名和密钥交换。与AES等对称加密不同，RSA使用一对数学上关联但不同的密钥：公钥用于加密，私钥用于解密。本文将用Java实现完整的RSA算法，涵盖大整数运算、素数生成、密钥生成、加密解密和数字签名。

数学原理

RSA的安全性基于大整数分解难题：将两个大素数的乘积分解回原来的素数，在计算上极其困难。

密钥生成步骤

1. 随机选择两个大素数 p 和 q
2. 计算 n = p × q（模数）
3. 计算欧拉函数 φ(n) = (p-1)(q-1)
4. 选择公钥指数 e，满足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1
5. 计算私钥指数 d，满足 e × d ≡ 1 (mod φ(n))

加密与解密

• 加密：c = m^e mod n
• 解密：m = c^d mod n

Java实现

大整数工具类

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

public class RSA {
    // 密钥长度（比特）
    private static final int KEY_SIZE = 1024;
    private static final SecureRandom random = new SecureRandom();

    private BigInteger n;      // 模数
    private BigInteger e;      // 公钥指数
    private BigInteger d;      // 私钥指数
    private BigInteger p, q;   // 素数因子
    private BigInteger phi;    // 欧拉函数

    public RSA() {
        generateKeys();
    }

    /**
     * 生成RSA密钥对
     */
    public void generateKeys() {
        // 1. 生成两个大素数
        p = generatePrime(KEY_SIZE / 2);
        q = generatePrime(KEY_SIZE / 2);

        // 确保 p != q
        while (p.equals(q)) {
            q = generatePrime(KEY_SIZE / 2);
        }

        // 2. 计算模数 n = p * q
        n = p.multiply(q);

        // 3. 计算欧拉函数 φ(n) = (p-1)(q-1)
        phi = p.subtract(BigInteger.ONE)
               .multiply(q.subtract(BigInteger.ONE));

        // 4. 选择公钥指数 e（常用 65537 = 2^16 + 1）
        e = new BigInteger("65537");
        while (phi.gcd(e).intValue() > 1) {
            e = e.add(BigInteger.TWO);
        }

        // 5. 计算私钥指数 d = e^(-1) mod φ(n)
        d = e.modInverse(phi);
    }

    /**
     * Miller-Rabin素性测试生成大素数
     */
    private BigInteger generatePrime(int bitLength) {
        while (true) {
            BigInteger candidate = new BigInteger(bitLength, random);
            // 确保是奇数且最高位为1
            candidate = candidate.setBit(0).setBit(bitLength - 1);
            if (isProbablePrime(candidate, 20)) {
                return candidate;
            }
        }
    }

    /**
     * Miller-Rabin素性测试
     * @param n 待测试的数
     * @param k 测试轮数，错误概率 < 4^(-k)
     */
    public boolean isProbablePrime(BigInteger n, int k) {
        if (n.compareTo(BigInteger.TWO) < 0) return false;
        if (n.equals(BigInteger.TWO) || n.equals(BigInteger.valueOf(3))) return true;
        if (n.mod(BigInteger.TWO).equals(BigInteger.ZERO)) return false;

        // 将 n-1 分解为 2^r * d
        BigInteger d = n.subtract(BigInteger.ONE);
        int r = 0;
        while (d.mod(BigInteger.TWO).equals(BigInteger.ZERO)) {
            d = d.divide(BigInteger.TWO);
            r++;
        }

        // 进行k轮测试
        for (int i = 0; i < k; i++) {
            BigInteger a = randomBigInteger(BigInteger.TWO, n.subtract(BigInteger.TWO));
            BigInteger x = a.modPow(d, n);

            if (x.equals(BigInteger.ONE) || x.equals(n.subtract(BigInteger.ONE))) {
                continue;
            }

            boolean continueOuter = false;
            for (int j = 0; j < r - 1; j++) {
                x = x.modPow(BigInteger.TWO, n);
                if (x.equals(n.subtract(BigInteger.ONE))) {
                    continueOuter = true;
                    break;
                }
            }

            if (continueOuter) continue;
            return false;
        }

        return true;
    }

    private BigInteger randomBigInteger(BigInteger min, BigInteger max) {
        BigInteger range = max.subtract(min).add(BigInteger.ONE);
        BigInteger result;
        do {
            result = new BigInteger(range.bitLength(), random);
        } while (result.compareTo(range) >= 0);
        return result.add(min);
    }

加密解密与签名

    /**
     * 公钥加密：c = m^e mod n
     * @param message 明文（必须小于n）
     */
    public BigInteger encrypt(BigInteger message) {
        if (message.compareTo(n) >= 0) {
            throw new IllegalArgumentException("Message must be less than n");
        }
        return message.modPow(e, n);
    }

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

    /**
     * 使用中国剩余定理(CRT)加速解密
     * 速度比直接 modPow 快约4倍
     */
    public BigInteger decryptCRT(BigInteger ciphertext) {
        // dp = d mod (p-1), dq = d mod (q-1)
        BigInteger dp = d.mod(p.subtract(BigInteger.ONE));
        BigInteger dq = d.mod(q.subtract(BigInteger.ONE));

        // qInv = q^(-1) mod p
        BigInteger qInv = q.modInverse(p);

        // m1 = c^dp mod p, m2 = c^dq mod q
        BigInteger m1 = ciphertext.modPow(dp, p);
        BigInteger m2 = ciphertext.modPow(dq, q);

        // h = qInv * (m1 - m2) mod p
        BigInteger h = qInv.multiply(m1.subtract(m2)).mod(p);

        // m = m2 + h * q
        return m2.add(h.multiply(q));
    }

    /**
     * 数字签名：使用私钥对消息哈希签名
     */
    public BigInteger sign(byte[] message) {
        BigInteger hash = hashToBigInteger(message);
        return hash.modPow(d, n);
    }

    /**
     * 签名验证：使用公钥验证签名
     */
    public boolean verify(byte[] message, BigInteger signature) {
        BigInteger hash = hashToBigInteger(message);
        BigInteger decryptedHash = signature.modPow(e, n);
        return hash.equals(decryptedHash);
    }

    /**
     * 简单哈希函数（实际应使用SHA-256）
     */
    private BigInteger hashToBigInteger(byte[] message) {
        long hash = 0;
        for (byte b : message) {
            hash = ((hash << 5) - hash) + (b & 0xFF);
            hash = hash & 0x7FFFFFFFFFFFFFFFL;
        }
        return BigInteger.valueOf(hash).mod(n);
    }

    // Getters
    public BigInteger getN() { return n; }
    public BigInteger getE() { return e; }
    public BigInteger getD() { return d; }

完整测试

    public static void main(String[] args) {
        System.out.println("=== RSA算法演示 ===");

        // 生成密钥
        RSA rsa = new RSA();
        System.out.println("模数 n 位数: " + rsa.getN().bitLength());
        System.out.println("公钥 e: " + rsa.getE());

        // 加密测试
        String original = "Hello RSA!";
        BigInteger message = new BigInteger(original.getBytes());
        System.out.println("原始消息: " + original);

        BigInteger encrypted = rsa.encrypt(message);
        System.out.println("加密后: " + encrypted.toString(16).substring(0, 32) + "...");

        // 解密测试
        BigInteger decrypted = rsa.decrypt(encrypted);
        String recovered = new String(decrypted.toByteArray());
        System.out.println("解密后: " + recovered);

        // CRT加速对比
        long start = System.nanoTime();
        for (int i = 0; i < 100; i++) {
            rsa.decrypt(encrypted);
        }
        long normalTime = System.nanoTime() - start;

        start = System.nanoTime();
        for (int i = 0; i < 100; i++) {
            rsa.decryptCRT(encrypted);
        }
        long crtTime = System.nanoTime() - start;

        System.out.println("\n=== 性能对比（100次解密）===");
        System.out.println("标准解密: " + (normalTime / 1000000) + " ms");
        System.out.println("CRT加速:  " + (crtTime / 1000000) + " ms");
        System.out.println("加速比: " + String.format("%.2fx", (double)normalTime / crtTime));

        // 数字签名测试
        String contract = "我同意该条款";
        BigInteger signature = rsa.sign(contract.getBytes());
        boolean valid = rsa.verify(contract.getBytes(), signature);
        System.out.println("\n=== 数字签名 ===");
        System.out.println("签名验证: " + (valid ? "通过" : "失败"));
    }
}

算法分析

安全性参数

时间复杂度

实际应用注意事项

1. 填充方案： never使用裸RSA，必须配合OAEP或PKCS#1 v1.5填充
2. 消息长度：RSA直接加密的消息长度不能超过密钥长度减去填充开销
3. 实际用法：通常用RSA加密AES密钥，再用AES加密实际数据（混合加密）
4. 随机数安全：素数生成依赖高质量的随机数源

总结

RSA是现代密码学的里程碑算法。本文从素数生成、密钥派生到加密解密和CRT优化，完整呈现了RSA的Java实现。理解RSA有助于把握非对称密码学的本质：利用数学难题构建单向函数，从而实现安全的密钥分发和数字签名。