JCC*_*CyC 12 primes cryptography rsa pki
好吧,我对RSA数学运算的理解可能不会那么深,所以如果这是愚蠢的话,请随意拍我的头:
要生成私钥,我们需要两个随机的大素数.没有算法可以精确有效地做到这一点,但是有些算法可以生成大数字,这些数字具有99.99999 ...(数十亿9s)... 999%的概率.
我的问题是:如果通过一个惊人的运气,当你生成你的密钥时,素数生成算法产生了一个非素数会发生什么？这对于使用这个不幸的密钥的软件有何影响？
编辑:我知道其他因素更可能是这个问题的不良结果来源; 这只是纯粹的书呆子数学好奇心.
Tho*_*nin 28
1.关于概率素性测试
计算机是一个可靠的确定性系统:对于相同的输入,它将对相同的输出运行相同的算法.它会一直这样吗？几乎.有一种高能粒子在宇宙中漫游,通常被称为宇宙射线.当这样的粒子撞击隐藏在CPU深处的晶体管时,它可能使其打嗝 - 基本上以非常短暂的方式改变其输出电压,使得在一个时钟周期中,晶体管输出所代表的位被翻转.
现在考虑一些计算机运行一个素数生成器算法,它创建随机数并测试它们的素数.素数测试是一个返回布尔值的函数.在某些时候,结果(对于非素数的true"素数" 的布尔值false)是复制到寄存器中的常量值.因此,存在几个时钟周期的窗口,在此期间,结果是单个位,包含在触发器结构(包含6个晶体管)中.
那么宇宙射线在"正确"的时钟周期翻转那个关键位的概率是多少,这使得程序认为非素数实际上是素数？这个概率非常低.正如我所说,计算机是可靠的系统.然而,可以粗略估计该概率.通常认为给定的CPU每三个月经历一次宇宙射线位翻转.Core2 Duo处理器包含大约291百万个晶体管,并以(例如)2.4 GHz运行.如果存在单个"关键"晶体管,并且该晶体管对于单个时钟周期至关重要,则宇宙射线将非素数转换为明显素数的概率约为1.8*10 -24.这是一个非常乐观的下界; 在实践中,许多转换器可以被翻转并暗示素性测试失败,并且目标定时覆盖几个周期,并且素发生器将检查每个素数生成的几十个非素数.但我们认为我们很幸运.
1.8*10 -24概率影响每个素性测试,无论它是否是确定性的.
通常的素发生器将运行Miller-Rabin测试,其"确定性"为2 -100(测试执行50次,并且每次错过非素数的概率不超过0.25)."100"是任意的但很常见.这个概率略低于10 -30.所以你有它:米勒 - 拉宾测试宣布素数为非素数的概率小于宇宙射线撞击晶体管的概率的百万分之一,并使应用假设一个数是素数而米勒 -拉宾测试说它不是.
简而言之,如果从质数生成器中得到非素数,那么这是由于诸如宇宙射线之类的硬件问题,而不是由于素数测试的概率性质.
由于宇宙射线导致的质量不好实际上是一个非常好运的中风.小行星穿过太空最终落在你的房子上的可能性是在你生成钥匙的第一秒内焚烧你的可能性要高得多.我不了解你,但就我个人而言,我更喜欢使用糟糕的RSA钥匙,而不是被摔倒的岩石压碎.
一把坏钥匙
如果在RSA密钥中使用非素数,则会得到错误的密钥.坏密钥将生成错误签名:签名生成器将生成正确长度的字节流,但签名验证程序将声明签名无效.注意:实际上,签名可能是有效的,概率很小.在RSA中使用"素数" p和q类似于概率素性测试,就像Miller-Rabin测试一样.然而,很可能很快就会发现钥匙行为不端.对于非对称加密,将观察到类似的行为.
应该注意的是,由于另一个宇宙射线,或者甚至更糟糕的坏RAM发生,也会产生不良签名或者未能解密RSA加密的消息.
最重要的是,如果你担心有一个糟糕的RSA密钥,而不是关于更可能的硬件故障事件(由于宇宙射线这是不可避免的,但幸好不是很常见),那么你的优先级就是错误的.