RSA和素生成算法 [英] RSA and prime-generator algorithms
问题描述
好吧，我对RSA的数学运算的理解可能不像它应该的那么深，所以如果这是愚蠢的话，请随意拍打我：
要生成私钥，我们需要两个随机大的素数。没有可以精确有效地做到的算法，但是有算法可以产生具有99.99999 ...（bazillion 9s）... 999％的概率的大数字。
我的问题是：如果由于运气不佳，当你生成你的密钥时，主生成算法生成非素数，会发生什么？
编辑：我知道其他因素是对这个问题的可能的不良结果的来源。这只是纯粹的书呆子数学好奇心。
1。对于概率性原始性测试
计算机是一个可靠的确定性系统：对于同一个输入，它将对同一个输出运行相同的算法。它会永远这样做吗？ 几乎。有一种东西，如通过宇宙漫游的高能粒子，通常被称为宇宙射线。当这样的粒子撞击深深地隐藏在CPU内的晶体管时，其可以以非常短暂的方式使其打嗝 - 基本上改变其输出电压，使得在一个时钟周期，晶体管输出表示的位被翻转。 / p>
现在考虑一些计算机运行素数生成器算法，它创建随机数并测试它们的原始性。原始性测试是返回布尔值的函数。在某些时候，结果（对于prime为 true 的布尔值，对于非素数为 false 的布尔值）一个常数值复制到寄存器中。因此，存在几个时钟周期的窗口，其中该结果是包含在触发器结构（包括6个晶体管）中的单个位。
什么是宇宙射线在正确时钟周期翻转这个关键位的概率，使得程序认为非素数实际上是素数？那个概率非常低。正如我所说，计算机是可靠的系统。然而，该概率可以粗略估计。通常认为给定的CPU每三个月经历一次宇宙射线比特翻转。 Core2 Duo处理器包含约291百万个晶体管，并且运行在（例如）2.4GHz。如果存在单个关键晶体管，并且该晶体管对于单个时钟周期是关键的，则宇宙射线将非素数转变为表观质数的概率为大约1.8×10 -24 。这是一个非常乐观的下界;在实践中，许多转换器可以被翻转并且意味着原始测试失败，并且目标定时覆盖几个周期，并且素生成器将针对每个初级生成检查几十个非素数。
1.8 * 10 -24 概率影响每个素数测试，无论它是确定性的
通常的素数生成器将运行Miller-Rabin测试，其确定性为2 -100 （测试执行50次，并且具有不大于0.25的概率每次错过非素数）。 100是任意的，但是常见。该概率有点小于10 -30 。所以你有它：米勒拉宾测试声明素数非素数的概率小于宇宙射线击中晶体管的概率的百万分之一部分，并使应用程序假设数字是素数，而米勒 - 拉宾测试表示它不是。
简而言之，如果你从质数生成器中得到一个非素数，是由于硬件问题，例如宇宙射线，不是对原始性测试的概率性质。
由于宇宙射线实际上是一个非常好运气的冲击。小行星通过空间破坏的可能性最终落在你的房子上焚烧你在第一秒，之后你生成你的钥匙是高得多。我不知道你，但我个人更喜欢有一个坏的RSA密钥，而不是被坠落的岩石压碎。
2。坏密钥
如果您在RSA密钥中使用非密钥，那么您将得到一个坏密钥。坏密钥将生成坏的签名：签名生成器将产生正确长度的字节流，但是签名验证器将声明签名无效。注意：实际上，签名可能有效，具有较小的概率。在RSA中使用primes 和 q 类似于概率性素质测试，就像Miller-Rabin测试。然而，很可能会很快发现钥匙行为不当。对于非对称加密，将观察到类似的行为。
应当注意，产生坏的签名或未能解密RSA加密的消息也可能由于但另一个宇宙射线，甚至更糟糕的RAM的更平凡的事情。
底线是，如果你担心有一个坏的RSA密钥，但不是更多硬件故障的可能事件（由于宇宙射线，这是不可避免的，但幸运的是不是很常见），那么你的优先级错误。
OK, my understanding of the mathematical workings of RSA may not be as deep as it should, so feel free to slap me over the head if this is stupid:
To generate a private key, we need two random big primes. There is no algorithm that can do that precisely and efficiently, but there are algorithms that can generate big numbers that have a 99.99999...(a bazillion 9s)...999% probability of being prime.
My question is: what happens if, by a phenomenal stroke of bad luck, when you were generating your key, the prime generating algorithm generated a non-prime? How does that impact software using that unlucky key?
EDIT: I know other factors are much more probable sources of bad results on this matter; this is just pure nerdy math curiosity.
1. On probabilistic primality tests
A computer is a reliable, deterministic system: for the same input, it will run the same algorithm to the same output. Will it always do that ? Almost. There is such a thing as high energy particles roaming through the universe, usually known as cosmic rays. When such a particle hits a transistor hidden deep within a CPU, it may make it hiccup -- basically alter its output voltage, in a very transient way, such that for one clock cycle, the bit which the transistor output represent is flipped.
Now consider some computer running a prime generator algorithm, which creates random numbers and tests them for primality. The primality test is a function which returns a boolean value. At some point, the result (the boolean which is true for "prime", false for non-prime) is a constant value copied into a register. So there is a window of a few clock cycles during which that result is a single bit, contained in a flip-flop structure (which consists in 6 transistors).
What is then the probability that a cosmic ray flips that critical bit at just the "right" clock cycle, making the program consider a non-prime to be actually prime ? That probability is very low. As I said, computers are reliable systems. Nevertheless, that probability can be roughly estimated. It is usually considered that a given CPU experiences a cosmic ray bit flip once every three months. A Core2 Duo processor contains about 291 millions of transistors, and runs at (for instance) 2.4 GHz. If there is a single "critical" transistor, and that transistor is critical for a single clock cycle, then the probability of cosmic ray turning a non-prime into an apparent prime is about 1.8*10-24. This is a very optimistic lower bound; in practice, many transitors could be flipped and imply the primality test failure, and the target timing covers several cycles, and a prime generator will examine several dozen non-primes for each prime generation. But let's consider that we are lucky.
The 1.8*10-24 probability affects every primality test, regardless of whether it is deterministic or not.
A usual prime generator will run a Miller-Rabin test with a "certainty" of 2-100 (the test is executed 50 times, and has a probability of no more than 0.25 to miss a non-prime each time). The "100" is arbitrary but common. That probability is a bit less than 10-30. So there you have it: the probability of a Miller-Rabin test declaring prime a non-prime is less than a millionth part of the probability of a cosmic ray hitting a transistor and making the application assume that a number is prime whereas the Miller-Rabin test said that it was not.
In shorter words, if you get a non-prime out of a prime number generator, then this is due to a hardware issue such as a cosmic ray, not to the probabilistic nature of the primality test.
Having a bad prime due to a cosmic ray is actually a stroke of very good luck. The probability that an asteroid hurtling through space finally falls on your house an incinerates you during the first second after which you generated your key is much higher. I do not know about you, but personally I much prefer having a bad RSA key than being crushed by a falling rock.
2. A bad key
If you use a non-prime in a RSA key then you get a bad key. A bad key will generate bad signatures: the signature generator will produce a stream of bytes of the right length, but the signature verifier will declare the signature invalid. Note: actually, the signature may be valid, with a small probability. Using the "primes" p and q in RSA is akin to a probabilistic primality test, just like a Miller-Rabin test. Chances are, however, that the key will soon be found to misbehave. A similar behavior will be observed for asymmetric encryption.
It shall be noted that producing a bad signature, or failing to decrypt a RSA-encrypted message, can also occur due to yet another cosmic ray, or even the much more mundane occurrence of bad RAM.
Bottom line is that if you worry about having a bad RSA key but not about the much more probable event of a hardware failure (which is unavoidable because of cosmic rays, but thankfully not very common anyway), then you are getting your priorities wrong.
这篇关于RSA和素生成算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
