我应该使用多少次Rabin-Miller迭代加密安全素数？

Question

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

我可以在p和(p-1)/ 2上使用几次Rabin-Miller迭代,并且仍然对加密密钥有信心吗？在我做过的研究中,我已经听到了1024位普通素数的6到64次迭代的所有内容,所以我在这一点上有点困惑.一旦确定,如果您正在生成一个安全的素数而不是普通素数,那么数字是否会改变？

计算时间非常宝贵,所以这是一个实际的问题 - 我基本上想知道如何找到尽可能少的测试数量,同时保持非常有保障的安全性.

Answer 1

让我们假设您通过选择随机值来选择素数p,直到您达到Miller-Rabin所说的那个:那个看起来像素数.你最多使用n轮进行Miller-Rabin测试.(对于所谓的"安全素数",除了运行两个嵌套测试外,事情不会改变.)

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

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

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

总而言之,使用40轮.

Answer 2

论文Damgard-Landrock-Pomerance 对强可能初等检验的平均病例误差估计指出,如果你随机选择k-bit奇数n并t连续应用独立的Rabin-Miller检验,那么n复合的概率有更大的界限.

事实上,3 <= t <= k/9和k >= 21,

对于k=1024位素数,t=6迭代会给出小于的错误率10^(-40).