RSA加密算法

本文最后更新于：2025年8月26日 上午

一、非对称加密（asymmetric encryption）

RSA 是 非对称加密 中十分经典的加密算法，相较于 AES 一类的 对称加密（symmetric encryption） ，非对称加密 中往往是多个 发送方（加密者） 对应着一个 接收方（解密者） 。非对称加密 的密钥分 私钥 和 公钥 ，前者只负责解密，后者只负责加密。因此，公钥可以任意分发，哪怕泄露也无法从中推算出解密的方法，而私钥往往只掌握在值得信任的解密者手中。

非对称加密的优点显而易见，不用担心密钥分发被拦截或是在客户端被破解，整体更加 安全。

而由于非对称加密背后的数学原理，和为了安全性而不得不选择更长的密钥，它的计算效率要比对称加密 慢百倍甚至千倍 。同时，由于非对称加密的密钥只有单一功能，无法像对称加密一样同时可以加密解密，而私钥往往不进行分发，如果想双向加密数据通信，单靠非对称加密是不够的。

由于其安全但效率低，非对称加密通常被用于 数字签名 ， 证书 ， 密钥 等一类数据体量小但对安全性要求更高的内容。

二、加密解密步骤

1.生成密钥

  • 步骤 1：选择质数 随机选择两个非常大且不同的质数 p 和 q。
  • 步骤 2：计算模数 n n = p * q。这个 n 将同时用于加密和解密，并且是公开的。
  • 步骤 3：计算欧拉函数 φ(n) φ(n) = (p - 1) * (q - 1)。这个值必须严格保密！ 如果泄露，私钥就很容易被计算出来。
  • 步骤 4：选择公钥指数 e 选择一个整数 e，满足：
    • 1 < e < φ(n)
    • gcd(e, φ(n)) = 1 (即 e 和 φ(n) 互质)
  • 步骤 5：计算私钥指数 d 计算 e 关于模 φ(n) 的模反元素 d。即找到整数 d 满足： e * d ≡ 1 (mod φ(n)) 这等价于 e * d = k * φ(n) + 1 (其中 k 是某个整数)。
  • 密钥对:
    • 公钥 (Public Key): (n, e)
    • 私钥 (Private Key): (n, d) 或 (p, q, d)。通常只保存 (n, d)，但生成过程需要 p 和 q 来计算 φ(n)。

2. 加密

  • 将明文消息转换为一个整数 m，满足 0 ≤ m < n (如果消息很长，需要分块处理)。
  • 使用公钥 (n, e) 计算密文 c： c ≡ me (mod n)
  • 数学逻辑: 这里利用了模幂运算的容易性。即使 m 和 e 很大，计算 me mod n 也有高效算法（如快速幂算法）。

3.解密

  • 收到密文 c。

  • 使用私钥 (n, d) 计算还原的明文 m'：

    m’ = cd mod n

4.加密解密后数据不变证明

数学逻辑（核心证明）: 我们需要证明 m' = m。

首先，通过明文的获取公式我们可以得知： $$ \begin{aligned} m' \equiv c^d \pmod{n} \end{aligned} $$

将加密公式代入得到： $$ \begin{aligned} m' \equiv c^d \equiv (m^e)^d \equiv m^{ed} \pmod{n} \end{aligned} $$

根据密钥生成步骤 5，我们知道 e*d ≡ 1 (mod φ(n))，即 e*d = k * φ(n) + 1 (其中 k 是某个整数)。所以： $$ \begin{aligned} m' &\equiv m^{k \cdot \varphi(n) + 1} \pmod{n} \\ m' &\equiv (m^{\varphi(n)})^k \cdot m \pmod{n} \\ m' &\equiv (1)^k \cdot m \pmod{n} \\ m' &\equiv m \pmod{n} \end{aligned} $$

又因为 0 ≤ m < n 且 0 ≤ m' < n ，所以 m = m'

上述公式推导涉及 欧拉定理 (Euler’s Theorem)

RSA不易被破解涉及 大整数分解难题 (Integer Factorization Problem)

公钥的计算获取方法可查找 求模逆元方法 ，例如 扩展欧几里得算法

三、JAVA代码实现

密钥对生成可以使用 java.security.* 中的工具：

import java.security.*;  // 密钥对的生成可以使用该包下的工具

// 公钥-私钥对生成
KeyPair keyPair;
KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("RSA/ECB/PKCS1Padding"); // 指定RSA加密以及填充方式
keyPairGenerator.initialize(2048); // 该整数实际上是模数n的位数，2048为目前适用性较广的选择，
														// 并不可随意选择，牵涉安全性和性能等，建议查阅“RSA密钥长度”相关文章
keyPair = keyPairGenerator.generateKeyPair(); // keyPair 中便存储了生成的密钥对
PublicKey publicKey = keyPair.getPublic(); // 获取公钥
PrivateKey privateKey = keyPair.getPrivate(); // 获取私钥

解密：

import javax.crypto.Cipher;
import java.nio.charset.StandardCharsets;
import java.security.GeneralSecurityException;
import java.security.PrivateKey;
import java.util.Base64;
// 解密的示例代码
public String decrypt(String encryptedData, PrivateKey privateKey) {
    try {
        Cipher cipher = Cipher.getInstance("RSA/ECB/PKCS1Padding");
        cipher.init(Cipher.DECRYPT_MODE, privateKey);

        // Base64 解码
        byte[] encryptedBytes = Base64.getDecoder().decode(encryptedData);

        // 解密
        byte[] decryptedBytes = cipher.doFinal(encryptedBytes);

        // 转换为 UTF-8 字符串
        return new String(decryptedBytes, StandardCharsets.UTF_8);

    } catch (GeneralSecurityException e) {
        logger.error("RSA 解密失败", e);
        throw new IllegalStateException("RSA 解密失败", e);
    }
}

加密：

public static String encrypt(String plainText, PublicKey publicKey) {
        try {
            // 使用 RSA 算法（显式指定填充方式）
            Cipher cipher = Cipher.getInstance("RSA/ECB/PKCS1Padding");
            cipher.init(Cipher.ENCRYPT_MODE, publicKey);

            // 执行加密
            byte[] encryptedBytes = cipher.doFinal(plainText.getBytes(StandardCharsets.UTF_8));

            // Base64 编码后返回
            return Base64.getEncoder().encodeToString(encryptedBytes);
        } catch (GeneralSecurityException e) {
            throw new IllegalStateException("RSA 加密失败", e);
        }
    }