3、RSA密钥对生成：素数选取策略、模数n与指数e/d的计算、密钥长度与安全强度对应关系

RSA 密钥对生成，说白了就是找两个大素数，然后做一堆数学运算。听起来简单，但这里面的坑，我踩过不少。今天咱们就把它彻底聊透。

3.1 素数选取策略：不是随便找个质数就行

RSA 的安全性，根基就在大整数分解的困难性上。如果 p 和 q 选得不好，攻击者就能轻松分解 n，私钥也就形同虚设了。

3.1.1 随机性与不可预测性

素数必须通过密码学安全的伪随机数生成器（CSPRNG）产生。不能用 rand() 这种普通函数，否则攻击者可能预测出你的素数。

3.1.2 素数间隔与分布要求

p 和 q 不能太接近。如果 |p - q| 很小，那么 n 的平方根附近就能快速找到因子。我个人的习惯是，p 和 q 的比特长度相差至少 10 位以上。

举个例子：

• 如果 n 是 2048 位，p 取 1024 位，q 取 1024 位，但 p 和 q 的高位要不同。
• 避免 p 和 q 是连续的素数，或者有简单的数学关系。

3.1.3 强素数（Strong Prime）的概念

虽然现代标准（如 PKCS#1）不再强制要求强素数，但我建议你还是了解一下：

3.2 模数 n 与指数 e/d 的计算

这部分是纯数学，但理解它有助于你排查问题。我记得有一次调试一个签名验签失败的问题，最后发现是 e 和 d 的关系没算对。

3.2.1 模数 n 的计算

n = p × q。就这么简单。n 的比特长度就是 RSA 的密钥长度。比如 2048 位 RSA，n 就是 2048 位。

这里有个细节：n 的二进制表示中，最高位必须是 1。否则密钥长度就缩水了。我见过一些实现，生成的 n 最高位是 0，实际有效长度只有 2047 位，安全强度直接降了一档。

3.2.2 欧拉函数 φ(n) 的计算

φ(n) = (p-1) × (q-1)。这个值在计算私钥指数 d 时要用到。注意，φ(n) 必须保密，泄露了它，私钥也就等于公开了。

3.2.3 公钥指数 e 的选择

e 必须满足：1 < e < φ(n)，且 gcd(e, φ(n)) = 1。常见的 e 值有：

• 65537 (0x10001)：最常用。它是一个费马素数，二进制只有两个 1，加密速度快。
• 3：虽然计算更快，但存在安全隐患（小指数攻击），不推荐。
• 17：偶尔见到，但不如 65537 普遍。

3.2.4 私钥指数 d 的计算

d ≡ e⁻¹ mod φ(n)。也就是 e 关于 φ(n) 的模逆元。用扩展欧几里得算法就能算出来。

代码示例（Python 示意）：

def rsa_keygen(p, q, e=65537):
    n = p * q
    phi = (p - 1) * (q - 1)
    # 计算 d，使得 e * d ≡ 1 (mod phi)
    d = pow(e, -1, phi)  # Python 3.8+ 支持
    return (n, e), (n, d)

3.3 密钥长度与安全强度对应关系

密钥越长越安全，但性能也越差。怎么选？我根据 NIST 和 ENISA 的建议，结合自己的工程经验，整理了一张表：

你想想看，为什么 2048 位 RSA 只相当于 112 位安全强度？因为 RSA 的安全性依赖于大整数分解的难度，而对称加密依赖于穷举搜索。攻击 RSA 的算法（如数域筛法）比穷举密钥更高效。所以 RSA 需要的比特数远多于对称密钥。

3.4 核心流程总览

下面这张图，把 RSA 密钥对生成的整个流程串起来了。我画这张图的时候，特意把容易出错的环节标红了。

3.5 工程实践中的几个关键检查点

生成完密钥对，别急着用。我习惯做以下几项检查：

1. 验证 n 的比特长度：确保 n 的二进制最高位是 1，长度符合预期。
2. 验证 e × d ≡ 1 (mod φ(n))：用这个等式确认 e 和 d 的关系正确。
3. 测试加解密：选一个随机消息 m，计算 c = m^e mod n，再计算 m' = c^d mod n，确认 m == m'。
4. 检查私钥文件格式：确保 PKCS#8 或 PKCS#1 格式正确，没有多余的空格或换行。

嗯，RSA 密钥对生成的核心内容就这些。记住，数学是基础，但工程细节才是决定成败的关键。选对素数、算对指数、检查到位，你的密钥对才能经得起考验。