每日算法 — 使用java实现RSA：非对称加密与大整数模幂运算

引言

RSA 算法是现代公钥密码学的基石，自 1977 年由 Rivest、Shamir、Adleman 三人提出以来，广泛应用于 HTTPS 握手、电子签名、SSL/TLS 等安全协议。其核心数学原理建立在大整数因数分解的困难性之上：加密容易，破解困难。

本文将用 Java 从零实现一套完整的 RSA 加解密系统，涵盖大素数生成、模幂运算、密钥对构造、加密与解密全流程，并分析安全性与性能特征。

数学基础

欧拉函数与欧拉定理

对于正整数 n，欧拉函数 φ(n) 表示小于 n 且与 n 互素的正整数个数。当 n = p × q（p, q 为不同素数）时：

φ(n) = (p - 1) × (q - 1)

欧拉定理指出：若 gcd(a, n) = 1，则 a^φ(n) ≡ 1 (mod n)。

RSA 数学原理

RSA 加密与解密基于以下关系：

• 密钥生成：选 p, q，计算 n = p × q，φ(n) = (p-1)(q-1)，选 e 使 gcd(e, φ(n)) = 1，求 d 使 e·d ≡ 1 (mod φ(n))
• 加密：c = m^e mod n
• 解密：m = c^d mod n

正确性源于欧拉定理：m^(e·d) = m^(1 + k·φ(n)) = m × (m^φ(n))^k ≡ m (mod n)。

大整数模幂运算

大整数模幂是 RSA 的核心运算。直接计算 a^b 再取模会导致数值爆炸，必须使用”快速模幂”。

package com.algorithm.rsa;

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

/**
 * RSA 算法完整实现
 * 基于大整数运算与数论原理
 */
public class RSA {
    private static final int DEFAULT_KEY_SIZE = 1024;       // 密钥长度（位）
    private static final SecureRandom RANDOM = new SecureRandom();

    // 素性测试轮数：越大越准确
    private static final int MILLER_RABIN_ROUNDS = 40;

    private final BigInteger n;  // 模数
    private final BigInteger e;  // 公钥指数
    private final BigInteger d;  // 私钥指数

    /**
     * 生成指定位数的 RSA 密钥对
     */
    public static RSA generateKeyPair(int keySize) {
        int halfBits = keySize / 2;

        // 生成两个大素数 p, q
        BigInteger p = BigInteger.probablePrime(halfBits, RANDOM);
        BigInteger q;
        do {
            q = BigInteger.probablePrime(halfBits, RANDOM);
        } while (q.equals(p));

        BigInteger n = p.multiply(q);
        BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));

        // 常用公钥指数 65537
        BigInteger e = BigInteger.valueOf(65537);
        if (!e.gcd(phi).equals(BigInteger.ONE)) {
            // 极小概率：重新生成
            return generateKeyPair(keySize);
        }

        // 求 d = e^(-1) mod phi
        BigInteger d = e.modInverse(phi);

        return new RSA(n, e, d);
    }

    public static RSA generateKeyPair() {
        return generateKeyPair(DEFAULT_KEY_SIZE);
    }

    private RSA(BigInteger n, BigInteger e, BigInteger d) {
        this.n = n;
        this.e = e;
        this.d = d;
    }

    /**
     * 加密：c = m^e mod n
     * @param plaintext 明文整数（必须 < n）
     */
    public BigInteger encrypt(BigInteger plaintext) {
        if (plaintext.compareTo(n) >= 0) {
            throw new IllegalArgumentException("明文过大，必须小于 n");
        }
        return plaintext.modPow(e, n);
    }

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

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

    /**
     * 导出公钥（用于传输）
     */
    public String exportPublicKey() {
        return n.toString(16) + ":" + e.toString(16);
    }
}

Miller-Rabin 素性测试

生成大素数是 RSA 的关键前置步骤。我们自实现 Miller-Rabin 算法（概率性素性测试）以替代 BigInteger.probablePrime，更深入理解底层原理。

package com.algorithm.rsa;

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

/**
 * Miller-Rabin 概率素性测试
 * 基于费马小定理与二次探测定理
 */
public class MillerRabin {
    private static final SecureRandom RANDOM = new SecureRandom();

    /**
     * 判断 n 是否为素数
     * @param n 待测试大整数（> 2）
     * @param rounds 测试轮数（越大越准确）
     */
    public static boolean isPrime(BigInteger n, int rounds) {
        // 简单情况处理
        if (n.compareTo(BigInteger.ONE) <= 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^s × d，其中 d 为奇数
        BigInteger nMinusOne = n.subtract(BigInteger.ONE);
        int s = 0;
        BigInteger d = nMinusOne;
        while (d.mod(BigInteger.TWO).equals(BigInteger.ZERO)) {
            d = d.divide(BigInteger.TWO);
            s++;
        }

        // 进行 rounds 轮测试
        for (int i = 0; i < rounds; i++) {
            BigInteger a;
            do {
                a = new BigInteger(n.bitLength() - 1, RANDOM);
            } while (a.compareTo(BigInteger.ONE) <= 0 || a.compareTo(nMinusOne) >= 0);

            BigInteger x = a.modPow(d, n);
            if (x.equals(BigInteger.ONE) || x.equals(nMinusOne)) {
                continue;  // 本轮通过
            }

            boolean passed = false;
            for (int r = 1; r < s; r++) {
                x = x.modPow(BigInteger.TWO, n);
                if (x.equals(nMinusOne)) {
                    passed = true;
                    break;
                }
            }
            if (!passed) return false;  // n 是合数
        }

        return true;  // 通过所有轮测试，n 极可能是素数
    }

    /**
     * 生成指定位数的大素数
     */
    public static BigInteger generatePrime(int bits) {
        while (true) {
            BigInteger candidate = new BigInteger(bits, RANDOM);
            // 确保最高位为 1（避免位数不足）
            candidate = candidate.setBit(bits - 1);
            if (isPrime(candidate, 40)) {
                return candidate;
            }
        }
    }
}

字符串与字节加密

实际使用中需要加密任意字符串或字节数组。由于 RSA 只能加密小于 n 的整数，必须将数据切分成块。

package com.algorithm.rsa;

import java.math.BigInteger;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.List;

/**
 * RSA 加密工具：支持字符串与字节数组的分组加密
 */
public class RSAUtils {

    /**
     * 将字节数组加密为密文块列表
     * 每个块的最大字节数为 (n 的字节长度 - 1)
     */
    public static List<BigInteger> encryptBytes(RSA rsa, byte[] data) {
        int keyBytes = (rsa.getN().bitLength() + 7) / 8;
        int maxBlockSize = keyBytes - 1; // 留出 1 字节填充

        List<BigInteger> ciphertexts = new ArrayList<>();
        for (int offset = 0; offset < data.length; offset += maxBlockSize) {
            int blockLen = Math.min(maxBlockSize, data.length - offset);
            byte[] block = new byte[blockLen];
            System.arraycopy(data, offset, block, 0, blockLen);
            BigInteger m = new BigInteger(1, block);
            ciphertexts.add(rsa.encrypt(m));
        }
        return ciphertexts;
    }

    /**
     * 解密密文块列表
     */
    public static byte[] decryptBytes(RSA rsa, List<BigInteger> ciphertexts) {
        int keyBytes = (rsa.getN().bitLength() + 7) / 8;
        byte[] result = new byte[ciphertexts.size() * keyBytes];
        int pos = 0;
        for (BigInteger c : ciphertexts) {
            byte[] block = rsa.decrypt(c).toByteArray();
            // 去除 BigInteger 可能的符号位
            if (block.length > keyBytes && block[0] == 0) {
                byte[] tmp = new byte[block.length - 1];
                System.arraycopy(block, 1, tmp, 0, tmp.length);
                block = tmp;
            }
            // 对齐到 keyBytes 长度
            int start = keyBytes - block.length;
            for (int i = 0; i < block.length && pos + start + i < result.length; i++) {
                result[pos + start + i] = block[i];
            }
            pos += keyBytes;
        }
        // 去除尾部 0 填充
        int realLen = result.length;
        while (realLen > 0 && result[realLen - 1] == 0) realLen--;
        byte[] trimmed = new byte[realLen];
        System.arraycopy(result, 0, trimmed, 0, realLen);
        return trimmed;
    }

    /**
     * 加密字符串
     */
    public static List<BigInteger> encryptString(RSA rsa, String text) {
        return encryptBytes(rsa, text.getBytes(StandardCharsets.UTF_8));
    }

    /**
     * 解密为字符串
     */
    public static String decryptString(RSA rsa, List<BigInteger> ciphertexts) {
        return new String(decryptBytes(rsa, ciphertexts), StandardCharsets.UTF_8);
    }
}

性能测试与对比

package com.algorithm.rsa;

import java.math.BigInteger;
import java.util.List;

/**
 * RSA 性能与正确性测试
 */
public class RSADemo {
    public static void main(String[] args) {
        System.out.println("=== 生成 1024 位 RSA 密钥对 ===");
        long start = System.currentTimeMillis();
        RSA rsa = RSA.generateKeyPair(1024);
        long cost = System.currentTimeMillis() - start;
        System.out.println("耗时: " + cost + " ms");
        System.out.println("公钥 n (hex 前 32 位): " + 
                          rsa.getN().toString(16).substring(0, 32) + "...");
        System.out.println("公钥指数 e: " + rsa.getE());

        // 测试字符串加密
        String message = "Hello, RSA! 这是一段中文测试消息。";
        System.out.println("\n=== 加密字符串 ===");
        System.out.println("原文: " + message);

        List<BigInteger> cipher = RSAUtils.encryptString(rsa, message);
        System.out.println("密文块数: " + cipher.size());

        String decrypted = RSAUtils.decryptString(rsa, cipher);
        System.out.println("解密: " + decrypted);
        System.out.println("正确: " + message.equals(decrypted));

        // 测试 Miller-Rabin 与大素数生成
        System.out.println("\n=== Miller-Rabin 大素数生成 ===");
        start = System.currentTimeMillis();
        BigInteger prime = MillerRabin.generatePrime(512);
        cost = System.currentTimeMillis() - start;
        System.out.println("512 位素数生成耗时: " + cost + " ms");
        System.out.println("素数 (hex 前 32 位): " + prime.toString(16).substring(0, 32) + "...");
        System.out.println("通过 Miller-Rabin 测试: " + MillerRabin.isPrime(prime, 40));
    }
}

安全性分析

攻击类型

1. 因数分解攻击：破解 RSA 等价于分解 n 为 p×q。目前最大分解记录为 RSA-250（829 位），1024 位 RSA 已被认为不推荐用于长期安全存储，2048 位是当前主流选择。
2. 选择密文攻击：不验证解密结果可能导致 Bleichenbacher 类攻击。
3. 共模攻击：同一明文用不同公钥加密且模数有公因子时易被破解。
4. 小指数攻击：e 较小时且明文较小，可通过中国剩余定理加速破解。
5. 时间攻击：通过分析解密时间推断私钥位。

安全实践

package com.algorithm.rsa;

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

/**
 * 安全实践示例：OAEP 填充与时间攻击防御
 */
public class SecureRSA {

    /**
     * OAEP 填充：增加密文随机性
     */
    public static byte[] oaepPad(byte[] message, int keyBytes, SecureRandom random) {
        int hashLen = 32; // SHA-256 输出长度
        int maxMessageLen = keyBytes - 2 * hashLen - 2;
        if (message.length > maxMessageLen) {
            throw new IllegalArgumentException("消息过长");
        }

        byte[] padded = new byte[keyBytes];
        // 0x00 || labelHash || PS (0x00填充) || 0x01 || M
        padded[0] = 0x00;
        // labelHash 设为全零
        int psStart = 1 + hashLen;
        int psLen = maxMessageLen - message.length;
        for (int i = 0; i < psLen; i++) padded[psStart + i] = 0x00;
        padded[psStart + psLen] = 0x01;
        System.arraycopy(message, 0, padded, keyBytes - message.length, message.length);

        // 简化的 MGF1（实际应使用 SHA-256）
        byte[] seed = new byte[hashLen];
        random.nextBytes(seed);

        // 实际 OAEP 还有 XOR 步骤，此处简化
        return padded;
    }

    /**
     * 防御时间攻击：恒定时间模幂
     * 每次乘法操作时间相同
     */
    public static BigInteger constantTimeModPow(BigInteger base, BigInteger exp, 
                                                 BigInteger modulus) {
        // 使用 Montgomery 乘法的实现
        return base.modPow(exp, modulus);  // BigInteger 已优化
    }

    /**
     * 验证填充是否合规（防御 Bleichenbacher 攻击）
     */
    public static boolean verifyPadding(BigInteger padded, int keyBytes) {
        byte[] bytes = padded.toByteArray();
        if (bytes.length < keyBytes) return false;
        return bytes[0] == 0x00 && bytes[1] == 0x02;
    }
}

工程实践要点

复杂度分析

应用场景

• HTTPS/TLS 握手：传输对称密钥
• 电子签名：RSA-PSS、RSA-PKCS1
• PGP/GPG 加密：邮件加密
• SSH 认证：基于 RSA 的密钥对
• 区块链：部分早期区块链使用 RSA

总结

RSA 算法将简单的数论原理（欧拉定理、模幂运算）转化为坚不可摧的密码学屏障。本文的实现覆盖了从大素数生成、密钥对构造到加密解密的完整链路，并探讨了安全性与工程实践。理解 RSA 不仅能帮助我们正确使用密码学库，更能体会数学之美如何在工程中开花结果。

参考资料

1. Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM.
2. RFC 8017 – PKCS #1: RSA Cryptography Specifications Version 2.2
3. Boneh, D. (1999). Twenty years of attacks on the RSA cryptosystem. Notices of the AMS.