RSA and prime-generator algorithms

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:

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.

回答2:

You will notice it immediatelly: the secret key will be wrong.

If p or q is composite, you choose public key (65537 typically) compute your secret key using the extended euclidean algorithm: 65537*x mod n = 1. (where n=(p-1)*(q-1))

But using the x secret key decrypt(encrypt(m)) != m In formula: (m^65537)^x mod n != m

回答3:

ive learned that you can use rsa as this :

p = prime
q = prime
n = p * q

phi(n) = phi(p) * phi(q) = p-1 * q-1

But ive heard if you do phi of an none prime its not prime -1 so it would crash at the step above (but i cant say why)

回答4:

If you have true primes, then there are no shortcuts but brute force. If you are are not 100% sure, the attacker won't be either. Also, you can be enough confident with prime number test algoritms, that the risk of having a non prime nunber is less than 1 to the entire key space. Basically you can statistically be sure that your number is prime. In other words, the odds for guessing it's not a prime should be higher than guessing the right key. It just requires some patience at key generation time.

回答5:

There is a simple algorithm to factor a large composite -(as has always been suspected). This has been known by US and allies since 1989. It also identifies primes easily.

Also RSA is in the know.