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

问题描述

我为Diffie-Hellman类型键生成一个2048位的安全素数，p使得p和（p-1）/ 2都是素数。

我可以在p和（p-1）/ 2上使用Rabin-Miller多少次迭代，仍然对加密密钥有信心？在我做的研究中，我听说过对于1024位普通素数的6到64次迭代，所以我在这一点上有点困惑。一旦建立，如果你生成一个安全的素数而不是一个普通的数字，数字是否改变？

计算时间是一个溢价，所以这是一个实际问题 - 我基本上想知道如何找出尽可能少的测试数量，同时保持安全性。

解决方案

让我们假设你选择一个素数 p ，通过选择随机值，直到你打一个为米勒拉宾说：一个看起来像素数。您最多可以使用Miller-Rabin测试的 n 个回合。 （对于所谓的安全素数，事情不会改变，除非你运行两个嵌套测试。）

随机1024位整数是素数约为1/900。现在，你不想做任何蠢事，所以你只生成奇数值（一个偶数的1024位整数是保证非素数），更一般地，你运行米勒 - 拉宾测试如果值不是明显非素数，即可以除以小素数。所以你最终在尝试一个黄金（平均）之前尝试300个值与米勒拉宾。当值是非素数时，Miller-Rabin将在每个回合中以3/4的概率检测它，因此，对于单个非素数值，平均运行的Miller-Rabin回合数为1+（1/4 ）+（1/16）+ ... = 4/3。对于300个值，这意味着大约400轮Miller-Rabin，无论您选择 n 。

em> n 为例如40，那么由 n 隐含的成本小于总计算成本的10％。随机素数选择过程由对非素数的测试支配，不受您选择的 n值的影响。我在这里谈论了1024位整数;对于更大的数字， n 的选择甚至更不重要，因为随着大小增加，素数变得更稀疏（对于2048位整数，上面的10％变为5％ b
$ b

因此，您可以选择 n = 40 并满意它（或至少知道减少 n ）。另一方面，使用大于40的 n 是无意义的，因为这将使您的概率低于简单错误计算的风险。计算机是硬件，它们可能有随机故障。例如，素性测试函数可以为非素数值返回真，因为宇宙射线（高能量粒子在高速下穿过宇宙）恰好在正确的时间碰到正确的晶体管，翻转返回值从0（false）到1（true）。这是不太可能的，但不比概率 2 ^-80 小。有关更多详细信息，请参见此stackoverflow答案。底线是，无论你如何确保整数是素数，你仍然有一个不可避免的概率元素，和40轮米勒拉宾已经给你最好的，你可以希望。

总而言之，使用40轮。

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.

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.

解决方案

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.)

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.

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%").

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.

To sum up, use 40 rounds.

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