Suppose an RSA algorithm created private key on two machines. Is there any possibility that both keys are the same?
What does this have to do with the pigeonhole principle?
averell
2010-06-14 06:34:12
Given a sufficient (massive) number of generated keys, it is not only possible, but guaranteed that there will be a collision.
Matthew Flaschen
2010-06-14 06:40:39
Point taken. Since the key length is limited, the number of possible keys is limited, that's obvious. Still, in practice there is no practical way to generate a sufficient number of keys - it would be equivalent to brute-forcing a key. The key to understanding your answer it is important to understand that "creating a key" actually means "picking one randomly" in practice. And also that the number of possible keys is so big that picking the same one twice will never happen in practice.
averell
2010-06-14 07:01:51
+2
A:
Short answer: No. There is a theoretical possibility, but even if you create a key every second you aren't likely to get the same one twice before the sun explodes.
averell
2010-06-14 06:31:27
I may add that since the question was posed as a "programming" question, you actually meant to say "will it happen to me, in my programming problem"? The answer to that is a strong no. Or rather the answer is that if this happens to you, you're doing it wrong.See the other answer(s) to learn about the theoretical possibility. As a matter of fact, you may want to read up a bit on cryptography before using this for any real application.
averell
2010-06-14 07:05:27
+2
A:
Normally, you create RSA keys by randomly selecting extremely large numbers and checking whether they're prime.
Given the sizes of the numbers involved (100+ digits), the only reasonable possibility of a collision is if there's a problem in the random number generator, so that (at least under some circumstances) the numbers it picks aren't very random.
This was exactly the sort of problem that led to a break in the SSL system in Netscape (~4.0, if memory serves). In this particular case, the problem was in generating a session key, but the basic idea was the same -- a fair amount of the "random" bits that were used were actually pretty predictable, so an attacker who knew the sources of the bits could fairly quickly generate the same "random" number, and therefore the same session key.
Jerry Coffin
2010-06-14 07:26:59
A:
In the RSA cryptosystem with public key (n,e), the private key (n,d) is generated such that n = p * q, where p, q are large N-bit primes and ed − 1 can be evenly divided by the totient (p − 1)(q − 1).
To generate the same private key, you essentially need to generate the same p,q,e so it is an abysmally small probability.
Manas
2010-07-09 20:37:25