RSA 生成公私钥时质数是怎么选的？

RSA 算法生成公私钥的核心是选择两个大质数，我们通常将它们命名为 $p$ 和 $q$。这两个质数的选择是整个 RSA 加密流程中最关键、最需要细致处理的环节。下面我将详细地解释质数的选择过程，以及为什么选择大质数以及如何选择它们。

1. RSA 的核心数学原理回顾

在深入质数选择之前，我们先快速回顾一下 RSA 的数学基础：

模运算和欧拉定理 (Euler's Theorem)：RSA 的安全性依赖于大整数的模幂运算的计算难度。欧拉定理是其理论基础之一：对于互质的正整数 $a$ 和 $n$，有 $a^{phi(n)} equiv 1 pmod{n}$，其中 $phi(n)$ 是欧拉函数。
欧拉函数 $phi(n)$：当 $n = pq$ 是两个不同质数的乘积时，$phi(n) = (p1)(q1)$。这是 RSA 中一个非常重要的值，它决定了公钥和私钥之间的关系。
模逆元 (Modular Multiplicative Inverse)：RSA 的公钥指数 $e$ 和私钥指数 $d$ 必须满足 $ed equiv 1 pmod{phi(n)}$。也就是说，$d$ 是 $e$ 模 $phi(n)$ 的乘法逆元。

2. 为什么需要选择质数？

选择质数而不是合数，主要有以下几个原因：

简化欧拉函数计算：如上所述，当 $n = pq$ 是两个不同质数的乘积时，$phi(n)$ 的计算非常简单：$phi(n) = (p1)(q1)$。如果 $p$ 或 $q$ 是合数，计算 $phi(n)$ 会变得非常复杂，因为需要对 $n$ 进行完全的素因数分解，这正是 RSA 要依赖的计算难题。
安全性：RSA 的安全性依赖于整数分解的困难性。如果 $n = pq$ 的因数（$p$ 和 $q$）很容易被找到，那么攻击者就可以轻易计算出 $phi(n)$，进而推导出私钥 $d$。选择质数保证了在没有 $p$ 和 $q$ 的情况下，分解 $n$ 是一个计算上非常困难的问题。
确保模逆元存在：为了使 $ed equiv 1 pmod{phi(n)}$ 有解，需要 $e$ 和 $phi(n)$ 互质。如果 $p$ 和 $q$ 是质数，并且我们选择 $e$ 和 $(p1)(q1)$ 互质，那么就能找到 $d$。

3. 为什么需要选择“大”质数？

“大”是 RSA 安全性的关键。

对抗暴力破解和已知的分解算法：如果质数 $p$ 和 $q$ 很小，那么将它们的乘积 $n = pq$ 进行因数分解将变得非常容易。例如，如果 $n$ 只有几十位，使用普通的计算器或一些简单的算法就可以在短时间内找到 $p$ 和 $q$。
“费马分解法” (Fermat's Factorization Method)：对于一个数 $N$，费马分解法的思想是尝试找到两个整数 $x$ 和 $y$，使得 $N = x^2 y^2 = (xy)(x+y)$。如果 $N = pq$，那么令 $x = (p+q)/2$ 和 $y = (qp)/2$。$p$ 和 $q$ 的差值越小，找到 $x$ 和 $y$ 就越容易。选择大质数，并且让它们相差尽可能大（但又不能太小），可以增加分解的难度。
“二次筛法” (Quadratic Sieve)：这是目前最快的已知通用整数分解算法之一，其运行时间大致与 $e^{sqrt{ln n ln ln n}}$ 成正比。这个算法对 $n$ 的大小非常敏感。
当前的标准和推荐：为了抵御现代计算机和已有算法的攻击，RSA 密钥的长度（即 $n$ 的位数）需要足够大。目前，2048 位的密钥长度是行业标准，3072 位或 4096 位也越来越常见，并且被认为是更安全的。这意味着 $p$ 和 $q$ 的长度通常在 1024 位到 2048 位之间，它们是极其巨大的数字。

4. 如何选择大质数 $p$ 和 $q$？

选择大质数是一个严谨的概率性过程，无法直接“列举”出来。具体步骤如下：

步骤 1：生成一个随机的大整数

1. 确定密钥长度 (key length)：首先需要确定 RSA 的密钥长度，例如 2048 位。这意味着乘积 $n = pq$ 的长度约为 2048 位。
2. 确定 $p$ 和 $q$ 的长度：为了使 $n$ 约为 2048 位，通常选择 $p$ 和 $q$ 的长度大致为密钥长度的一半，即约 1024 位。这样可以保证 $p e q$，并且它们的乘积接近预期的长度。
3. 生成一个随机的 1024 位数：使用密码学安全的伪随机数生成器 (CSPRNG) 来生成一个随机的 1024 位整数。确保这个随机数生成器具有足够的熵（随机性）。

步骤 2：检查生成的随机数是否为质数（素性测试）

刚生成的随机数很可能不是质数。因此，需要对其进行素性测试，以确定它是否是质数。这又分为两个子步骤：

简单的试除法（可选但常见）：
首先，可以进行一些简单的试除法来快速排除一些合数。例如，检查这个数是否能被小的质数（如 2, 3, 5, 7, 11, 13 等）整除。
如果一个 1024 位数能被 2 整除，那它肯定是偶数，不是质数（除非是 2 本身，但我们不需要这么小的数）。
检查这个数是否以 1, 3, 7, 9 结尾（排除能被 2 和 5 整除的情况）。
可以对一些小的质数进行试除。这个过程可以快速筛掉一部分合数，但对于大数而言效率不高。

概率性素性测试 (Probabilistic Primality Tests)：
米勒拉宾测试 (MillerRabin Test) 是目前最常用和最有效的概率性素性测试算法之一。
工作原理简介：米勒拉宾测试基于费马小定理的推广和平方剩余的性质。对于一个待测的奇数 $n > 2$，测试会选择一个随机的基数 $a$ (1 < $a$ < $n$)。如果 $n$ 是质数，那么在某些条件下，一个特定的测试会通过。如果测试失败，那么 $n$ 肯定不是质数（是一个合数）。如果测试通过，那么 $n$ 很有可能是一个质数，但不能 100% 保证。
提高确定性：为了提高概率性测试的确定性，算法会重复进行多次（通常选择一个合适的迭代次数 $k$）。每次都选择一个新的随机基数 $a$ 并执行测试。
错误概率：如果一个合数通过了 $k$ 次独立的米勒拉宾测试，那么它实际上是质数的概率非常低。具体来说，如果一个合数通过了单次测试，其“伪装”成质数的概率小于 1/4。那么，如果它连续通过了 $k$ 次测试，是合数的概率就小于 $(1/4)^k$。
实际应用中的选择：对于密码学应用，通常会选择一个足够大的 $k$ 值（例如 $k=40$ 或 $k=64$），使得一个合数通过所有测试的概率低于 $2^{80}$ 或 $2^{128}$，这在实际应用中已经可以接受了。

步骤 3：重复直到找到两个质数

1. 生成第一个随机数，进行素性测试。如果不是质数，丢弃，重新生成。直到找到第一个质数 $p$。
2. 为了确保 $p e q$，通常会对 $p$ 和 $q$ 的选取做一些额外的限制，例如要求它们大于某个阈值，或者保证它们的差值大于某个最小值。虽然通过随机性生成不同质数的概率很高，但这样做可以进一步加强安全性。
3. 生成第二个随机数，进行素性测试。如果不是质数，丢弃，重新生成。直到找到第二个质数 $q$。
4. 再次进行素性测试：确认 $q$ 确实是质数，并且 $q e p$。
5. 确保 $p$ 和 $q$ 的大小差异不会过大：虽然不要求 $p$ 和 $q$ 完全相等，但为了避免某些分解算法的攻击，通常会避免 $p$ 和 $q$ 的值相差太悬殊。例如，可以限制 $max(p, q) / min(p, q) < 2$。

步骤 4：计算 $n$ 和 $phi(n)$

1. 计算 $n = pq$：将找到的两个大质数相乘，得到模数 $n$。$n$ 的位数决定了 RSA 密钥的长度。
2. 计算 $phi(n) = (p1)(q1)$：这是欧拉函数的值，用于后续计算私钥指数 $d$。

步骤 5：选择公钥指数 $e$

1. 选择 $e$ 的要求：
$e$ 必须是奇数（通常为了效率，避免 $e$ 是偶数，因为这意味着 $p1$ 或 $q1$ 中有一个是偶数，如果 $e$ 是偶数，则 $gcd(e, phi(n))$ 可能大于 1）。
$e$ 必须与 $phi(n)$ 互质 (即 $gcd(e, phi(n)) = 1$)。
2. 常见的 $e$ 值：
$e = 3$：这是一个非常小的素数。如果使用 $e=3$，加密操作 $m^3 pmod n$ 会非常快。但是，如果信息 $m$ 足够小（例如 $m < n^{1/3}$），那么 $m^3 < n$，加密结果就是 $m^3$，这会带来安全隐患（例如在批量加密或已知明文攻击中）。因此，使用 $e=3$ 时，需要谨慎处理明文填充。
$e = 65537$ ($2^{16} + 1$)：这是最常用的公钥指数。它是费马数 $F_4$（也称为费马素数），它是一个素数。使用 $e=65537$ 有几个好处：
它很小，可以加快加密速度。
它与任何合理的 $phi(n)$ 互质的概率非常高（除非 $phi(n)$ 恰好是 65537 的倍数）。
它的二进制表示只有两个 1，这使得计算 $m^e pmod n$ 的效率很高（通过平方乘法算法）。
3. 如何选择 $e$：通常会从一组预设的常用 $e$ 值（如 $3, 17, 65537$）中选择一个，然后检查它是否与计算出的 $phi(n)$ 互质。如果互质，就使用该 $e$ 值。如果选定的 $e$ 与 $phi(n)$ 不互质，则尝试下一个预设值，或者生成一个新的 $phi(n)$（即重新生成 $p$ 和 $q$）。

步骤 6：计算私钥指数 $d$

1. 一旦确定了 $e$ 和 $phi(n)$，就可以使用扩展欧几里得算法 (Extended Euclidean Algorithm) 来计算 $d$。
2. 扩展欧几里得算法可以找到满足 $ed + kphi(n) = 1$ 的整数 $d$ 和 $k$。该算法保证了如果 $gcd(e, phi(n)) = 1$，则一定能找到唯一的 $d$ 使得 $ed equiv 1 pmod{phi(n)}$。

总结：关键点回顾

质数选择的目的是为了安全性：依赖于大整数分解的困难性。
质数必须足够大：以抵御现有和潜在的攻击算法。现代标准是至少 2048 位密钥长度，意味着质数 $p$ 和 $q$ 至少是千位级别的大数。
选择过程是概率性的：使用密码学安全的随机数生成器生成大整数，然后用高概率的素性测试（如米勒拉宾）来验证其素性。
重复是必须的：直到找到满足条件的两个不同的、足够大的质数。
公钥指数 $e$ 的选择很重要：常见的 $e=65537$ 是一个好选择。

通过上述详细步骤，RSA 算法能够生成一组强大的公钥和私钥对，为安全通信奠定基础。质数的选择是整个流程中至关重要的一步，直接关系到 RSA 的安全强度。

具体的说比如openssl keygen时，是怎么找质数的？假设个人计算机能力算不出太大的质数，是不是可以穷举已知的大质数形成攻击呢？