cryptography - 对于密码安全素数，我应该使用多少次 Rabin-Miller 迭代？

Question

我正在为 Diffie-Hellman 类型的 key p 生成一个 2048 位安全素数，使得 p 和 (p-1)/2 都是素数。

我可以在 p 和 (p-1)/2 上使用多少次 Rabin-Miller 迭代，并且仍然对加密强 key 充满信心？在我所做的研究中，我听说过 1024 位普通素数的 6 到 64 次迭代，所以在这一点上我有点困惑。一旦确定了，如果你生成的是一个安全的素数而不是一个普通的素数，这个数字会改变吗？

计算时间非常宝贵，所以这是一个实际问题——我基本上想知道如何找出我可以摆脱的尽可能少的测试，同时保持几乎有保证的安全性。

Answer 1

我会运行两到三次米勒拉宾(即强费马可能素数)测试，确保其中一个基数是 2。

然后我会运行一个强大的 Lucas 可能素数检验，使用此处描述的方法选择 D、P 和 Q:
https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test

没有已知的复合 Material 可以通过这种费马和卢卡斯测试的组合。

这比进行 40 次 Rabin-Miller 迭代要快得多。此外，正如 Pomerance、Selfridge 和 Wagstaff 在 https://math.dartmouth.edu/~carlp/PDF/paper25.pdf 中指出的那样, 多重费马检验的 yield 递减:如果 N 是一个碱基的伪素数，那么它比平均数更有可能是其他碱基的伪素数。这就是为什么，例如，我们看到很多 psp 的 base 2 也是 psp 的 base 3。