对于密码安全素数，我应该使用多少次 Rabin-Miller 迭代? [英] How many iterations of Rabin-Miller should I use for cryptographic safe primes?

问题描述

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

I am generating a 2048-bit safe prime for a Diffie-Hellman-type key, p such that p and (p-1)/2 are both prime.

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

How few iterations of Rabin-Miller can I use on both p and (p-1)/2 and still be confident of a cryptographically strong key? In the research I've done I've heard everything from 6 to 64 iterations for 1024-bit ordinary primes, so I'm a little confused at this point. And once that's established, does the number change if you are generating a safe prime rather than an ordinary one?

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

Computation time is at a premium, so this is a practical question - I'm basically wondering how to find out the lowest possible number of tests I can get away with while at the same time maintaining pretty much guaranteed security.

推荐答案

假设你通过选择随机值来选择一个素数 p，直到你找到一个 Miller-Rabin 说的:那个看起来像一个素数.Miller-Rabin 测试最多使用 n 轮.(对于所谓的安全素数"，除了运行两个嵌套测试之外，事情没有改变.)

Let's assume that you select a prime p by selecting random values until you hit one for which Miller-Rabin says: that one looks like a prime. You use n rounds at most for the Miller-Rabin test. (For a so-called "safe prime", things are are not changed, except that you run two nested tests.)

随机 1024 位整数是素数的概率约为 1/900.现在，您不想做任何愚蠢的事情，因此您只生成 odd 值(保证偶数 1024 位整数不是素数)，更一般地说，您只运行 Miller-Rabin 测试如果该值不是显然"非质数，即可以被一个小质数除.因此，在达到素数(平均)之前，您最终会使用 Miller-Rabin 尝试大约 300 个值.当该值是非质数时，Miller-Rabin 将在每轮以 3/4 的概率检测到它，因此对于单个非质数，您将运行的 Miller-Rabin 轮数平均为 1+(1/4)+(1/16)+... = 4/3.对于 300 个值，这意味着大约 400 轮 Miller-Rabin，无论您为 n 选择什么.

The probability that a random 1024-bit integer is prime is about 1/900. Now, you do not want to do anything stupid so you generate only odd values (an even 1024-bit integer is guaranteed non-prime), and, more generally, you run the Miller-Rabin test only if the value is not "obviously" non-prime, i.e. can be divided by a small prime. So you end up with trying about 300 values with Miller-Rabin before hitting a prime (on average). When the value is non-prime, Miller-Rabin will detect it with probability 3/4 at each round, so the number of Miller-Rabin rounds you will run on average for a single non-prime value is 1+(1/4)+(1/16)+... = 4/3. For the 300 values, this means about 400 rounds of Miller-Rabin, regardless of what you choose for n.

因此，如果您选择 n 为例如 40，则 n 隐含的成本小于总计算成本的 10%.随机素数选择过程以对非素数的测试为主，不受您选择的 n 值的影响.我在这里谈到了 1024 位整数；对于更大的数字，n 的选择就更不重要了，因为随着大小的增加，质数变得越来越稀疏(对于 2048 位整数，上面的10%"变成5%").

So if you select n to be, e.g., 40, then the cost implied by n is less than 10% of the total computational cost. The random prime selection process is dominated by the test on non-primes, which are not impacted by the value of n you choose. I talked here about 1024-bit integers; for bigger numbers the choice of n is even less important since primes become sparser as size increases (for 2048-bit integers, the "10%" above become "5%").

因此您可以选择 n=40 并对此感到满意(或者至少知道减少 n 无论如何也不会给您带来太多好处).另一方面，使用大于 40 的 n 是没有意义的，因为这会使您获得的概率低于简单错误计算的风险.计算机是硬件，它们可能会出现随机故障.例如，素数测试函数可以为非素数返回真"，因为宇宙射线(一种高速穿过宇宙的高能粒子)碰巧在正确的时间击中了正确的晶体管，翻转了返回值从 0(假")到 1(真").这是非常不可能的——但不亚于概率2^-80.有关更多详细信息，请参阅this stackoverflow answer.底线是，无论您如何确保整数是素数，您仍然有一个不可避免的概率元素，并且 40 轮 Miller-Rabin 已经为您提供了您所希望的最佳结果.

Hence you can choose n=40 and be happy with it (or at least know that reducing n will not buy you much anyway). On the other hand, using a n greater than 40 is meaningless, because this would get you to probabilities lower than the risk of a simple miscomputation. Computers are hardware, they can have random failures. For instance, a primality test function could return "true" for a non-prime value because a cosmic ray (a high-energy particle hurtling through the Universe at high speed) happens to hit just the right transistor at the right time, flipping the return value from 0 ("false") to 1 ("true"). This is very unlikely -- but no less likely than probability 2^-80. See this stackoverflow answer for a few more details. The bottom line is that regardless of how you make sure that an integer is prime, you still have an unavoidable probabilistic element, and 40 rounds of Miller-Rabin already give you the best that you can hope for.

总之，使用 40 轮.

To sum up, use 40 rounds.

这篇关于对于密码安全素数，我应该使用多少次 Rabin-Miller 迭代?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！