我正在为 Diffie-Hellman 类型的密钥 p 生成一个 2048 位安全素数，使得 p 和 (p-1)/2 都是素数。
我可以在 p 和 (p-1)/2 上使用多少次 Rabin-Miller 迭代，并且仍然对加密强密钥充满信心？在我所做的研究中，我听说过 1024 位普通素数的 6 到 64 次迭代，所以在这一点上我有点困惑。一旦确定了，如果你生成的是一个安全的素数而不是一个普通的素数，这个数字会改变吗？
计算时间非常宝贵，所以这是一个实际问题——我基本上想知道如何找出我可以摆脱的尽可能少的测试，同时保持几乎有保证的安全性。
让我们假设您通过选择随机值来选择一个素数p，直到您找到一个 Miller-Rabin 所说的：那个看起来像一个素数。Miller-Rabin 测试最多使用n轮。（对于所谓的“安全素数”，除了运行两个嵌套测试之外，事情没有改变。）
一个随机的 1024 位整数是素数的概率约为 1/900。现在，您不想做任何愚蠢的事情，因此您只生成奇数值（偶数 1024 位整数保证非素数），并且更一般地说，仅当该值不是“明显" 非素数，即可以被一个小素数整除。因此，在达到素数（平均）之前，您最终会使用 Miller-Rabin 尝试大约 300 个值。当该值是非质数时，Miller-Rabin 将在每轮以 3/4 的概率检测到它，因此对于单个非质数，您将运行的 Miller-Rabin 轮数平均为 1+(1/4 )+(1/16)+... = 4/3。对于 300 个值，这意味着大约 400 轮 Miller-Rabin，无论您为n选择什么。
因此，如果您选择n为例如 40，则n隐含的成本小于总计算成本的 10%。随机素数选择过程由对非素数的测试控制，这些测试不受您选择的n值的影响。我在这里谈到了 1024 位整数；对于更大的数字，n的选择就更不重要了，因为随着大小的增加，素数变得越来越稀疏（对于 2048 位整数，上面的“10%”变成“5%”）。
因此，您可以选择n=40并对此感到满意（或者至少知道减少n无论如何都不会给您带来太多好处）。另一方面，使用大于 40 的n是没有意义的，因为这会使您获得的概率低于简单计算错误的风险。计算机是硬件，它们可能会出现随机故障。例如，素数测试函数可以为非素数返回“真”，因为宇宙射线（一种高速穿过宇宙的高能粒子）碰巧在正确的时间击中了正确的晶体管，翻转了返回值从 0（“假”）到 1（“真”）。这是非常不可能的——但不亚于概率2 -80。看到这个stackoverflow答案了解更多详情。底线是，无论您如何确保整数是素数，您仍然有一个不可避免的概率元素，并且 40 轮 Miller-Rabin 已经为您提供了您所希望的最佳结果。
总而言之，使用 40 发子弹。
Damgard-Landrock-Pomerance的论文“强可能素数检验的平均案例误差估计”指出，如果您随机选择k-bit 奇数n并连续应用t独立的 Rabin-Miller 检验，n则复合概率具有更强的界限.
实际上对于3 <= t <= k/9和k >= 21,
对于k=1024一点素数，t=6迭代给你的错误率小于10^(-40).
Rabin-Miller 的每次迭代都会将数字复合的几率降低 1/4。
所以在 64 次迭代之后，在 2^128 中只有 1 次机会是复合数。
假设您将这些用于公钥算法（例如 RSA），并假设您将其与使用（例如）128 位密钥的对称算法相结合，对手可以以该概率猜测您的密钥。
底线是选择迭代次数以将该概率置于您为算法选择的其他大小的范围内。
[更新，详细]
答案完全取决于您要将这些数字用于什么算法，以及针对这些算法的最知名的攻击是什么。
例如，根据维基百科：
截至 2003 年，RSA Security 声称 1024 位 RSA 密钥的强度等同于 80 位对称密钥、2048 位 RSA 密钥等同于 112 位对称密钥以及 3072 位 RSA 密钥等同于 128 位对称密钥。
因此，如果您打算使用这些素数来生成（例如）1024 位 RSA 密钥，那么没有理由运行超过 40 次左右的 Rabin-Miller 迭代。为什么？因为当您遇到故障时，攻击者无论如何都可以破解您的一个密钥。
当然，如果时间允许，没有理由不执行更多的迭代。这样做没有多大意义。
另一方面，如果您要生成 2048 位 RSA 密钥，那么 Rabin-Miller 的 56 次（左右）迭代更合适。
密码学通常构建为原语的组合，如素数生成、RSA、SHA-2 和 AES。如果你想让其中一个原语比其他原语强 2^900 倍，你可以，但这有点像在小木屋上放一扇 10 英尺高的钢拱门。
你的问题没有固定的答案。这取决于进入您的加密系统的其他部分的强度。
综上所述，2^-128 的概率非常小，所以我可能只使用 64 次迭代 :-)。
来自 libgcrypt 源：
/* We use 64 Rabin-Miller rounds which is better and thus
sufficient. We do not have a Lucas test implementaion thus we
can't do it in the X9.31 preferred way of running a few
Rabin-Miller followed by one Lucas test. */
cipher/primegen.c line# 1295
我会运行两到三次 Miller-Rabin（即强费马可能素数）测试，确保其中一个基数是 2。
然后我会运行一个强大的卢卡斯可能素数测试，使用此处描述的方法选择 D、P 和 Q： https ://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test
没有已知的复合材料可以通过这种费马和卢卡斯测试的组合。
这比进行 40 次 Rabin-Miller 迭代要快得多。此外，正如 Pomerance、Selfridge 和 Wagstaff 在https://math.dartmouth.edu/~carlp/PDF/paper25.pdf中指出的那样，多重费马检验的收益递减：如果 N 是 1 的伪素数碱基，那么它比平均数更有可能成为其他碱基的伪素数。这就是为什么，例如，我们看到很多 psp 的 base 2 也是 psp 的 base 3。
较小的概率通常更好，但我会对实际的概率值持保留态度。Albrecht et al Prime and Prejudice: Primality Testing Under Adversarial Conditions打破了密码库中的一些素数测试例程。在一个例子中，公布的概率是 1/2^80，但他们构造的数字被宣布为 16 次中的质数。
在其他几个示例中，它们的数量通过 100% 的时间。
有关系吗？为什么不运行 1000 次迭代？在搜索素数时，无论如何您在第一次失败时都停止应用 Rabin-Miller 测试，因此对于找到素数所需的时间，迭代次数的上限是多少并不重要。您甚至可以在这 1000 次迭代之后运行确定性素数检查算法来完全确定。
也就是说，一个数在 n 次迭代后是素数的概率是 4^-n。