理解 RSA：公钥数学简明指南

I’m happy to translate the article for you, but I’ll need the full text you’d like translated. Could you please paste the content (excluding the source line you already provided) here? Once I have the article text, I’ll translate it into Simplified Chinese while preserving the original formatting, markdown, and any code blocks or URLs.

Source: …

RSA 基础

RSA（Rivest–Shamir–Adleman）是一种公钥密码算法。它使用 公钥 加密数据，使用相应的 私钥 解密，从而实现安全传输和数字签名。

密钥生成

1. 选择两个大的素数 p 和 q。

2. 计算 n = p × q。

3. 求 n 的欧拉函数（totient）：

   [ \phi(n) = (p-1)(q-1) ]

   欧拉函数计数小于 n 且与 n 互质的整数。

   示例：

   • (\phi(11) = 10)，因为 1‑10 都与 11 互质。
   • (\phi(12) = 4)，因为只有 1、5、7、11 与 12 互质。

4. 选择一个整数 e（公用指数），满足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1。

5. 计算私有指数 d，它是 e 在模 φ(n) 下的乘法逆元：

   [ d \equiv e^{-1} \pmod{\phi(n)} ]

加密与解密

如果明文消息是 m，密文是 c：

• 加密：

  c = m^e mod n

• 解密：

  m = c^d mod n

示例

设 p = 7 和 q = 17，则 n = 7 × 17 = 119。

[ \phi(n) = (7-1)(17-1) = 96 ]

选择 e = 53（与 96 互质）。

• 加密消息 m = 7（ASCII 为 “H”）：

  c = 7^53 mod 119 = 28

• 解密：

  m = 28^29 mod 119 = 7

解密后的值与原始明文相匹配。

为什么 RSA 是安全的

在实际使用中，素数 p 和 q 通常有数百位（例如，2048 位 RSA）。仅知道 e 和 n 不能 在不将 n 分解为 p 和 q 的情况下得到 φ(n)，而对足够大的密钥进行因式分解在计算上是不可行的。

“2048‑bit RSA” 密钥意味着 n 是一个 2048 位的整数（最大值约为 (2^{2048} - 1)），在当前技术条件下，因式分解几乎不可能实现。

实现

提供了一个简单的 Java 实现供实验使用。下面是一个最小示例（完整的源代码和 README 位于原始仓库中）。

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

public class RSAExample {
    public static void main(String[] args) {
        // Generate two large prime numbers
        SecureRandom rnd = new SecureRandom();
        BigInteger p = BigInteger.probablePrime(1024, rnd);
        BigInteger q = BigInteger.probablePrime(1024, rnd);

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

        // Choose public exponent e
        BigInteger e = BigInteger.valueOf(65537); // common choice
        while (!phi.gcd(e).equals(BigInteger.ONE)) {
            e = e.add(BigInteger.TWO);
        }

        // Compute private exponent d
        BigInteger d = e.modInverse(phi);

        // Example message
        BigInteger m = new BigInteger("123456789");
        BigInteger c = m.modPow(e, n); // encryption
        BigInteger decrypted = c.modPow(d, n); // decryption

        System.out.println("Original: " + m);
        System.out.println("Encrypted: " + c);
        System.out.println("Decrypted: " + decrypted);
    }
}

常见风险与缓解措施

通过遵循这些最佳实践——选择大素数、使用适当的填充以及采用足够的密钥长度——RSA 仍然是安全通信的坚实基础。