1

With the RSA encryption algorithm, is there any guarantee that two different entities will not be given the same private keys?

  • The things that generate and store users' private keys. – user49075 Oct 7 '14 at 16:20
9

Probability.

When generating a 1024-bit RSA keypair, one of the first jobs is to pick a pair of primes p and q such that the product of those numbers (i.e. p multiplied by q) is 1024 bits in size. The simplest way to do this is to pick both values to be somewhere around 512 bits in size each, as 2512 × 2512 = 21024. Note that I'm picking 1024-bit as it's now considered to be the lowest acceptable key size, in which you're going to have the highest likelihood of prime collision.

Now, if we assume that only 512-bit values are used for p and q, we can now estimate how many primes there are in that range. I discussed this in an answer to another question about RSA, but I'll re-iterate here. The prime counting function allows us to estimate the number of primes in a given range. It isn't really defined, as it's just an estimation, and there are various ways to compute it. The simplest and roughest way is simply π(x) = x / ln(x), where π is the PCF and ln() is natural log. As I explained in the linked answer, there are likely somewhere around 1.885×10151 prime numbers in the range 2512 < n < 2513.

This means that, assuming an ideal implementation, the chance of picking equal p or q values in two independently generated RSA key pairs is roughly one in...

18,850,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000

That's slightly less likely than winning the jackpot on the UK national lottery 21 draws in a row (13,983,81521 = 1.143×10150).


This is all assuming that the implementation is ideal. However, this isn't always the case. For example, there used to be a bug in OpenSSL that caused uninitialised stack data to be used as the random pool for generating RSA primes, which meant that the actual number of possible outputs from the RNG was quite small. The resulting key pairs are now blacklisted from most implementations to prevent exploitation. Another example is that in many embedded devices (e.g. firewall appliances, routers, etc.) certain cryptographic values, such as SSH session keys, are generated early on in the system boot process, when there isn't much entropy available. This leads to a situation where the number of possible generated keys is significantly lower than you might expect, potentially leading to prediction attacks.


The tl;dr is that the key space is so large that randomly selecting two equal primes (p or q) when independently computing two RSA key pairs is phenomenally unlikely.

  • Note that in most cases, the RNG is actually a PRNG over a random seed, so the risk of collision is much bigger -- though still overwhelmingly small (if it is not, then your RNG is using a very poor or way too small seed). – Thomas Pornin Oct 7 '14 at 16:49
  • 1
    The prime counting function is "really defined", it just isn't really defined as x/ln(x). – user49075 Oct 7 '14 at 16:59
  • 1
    We just don't have an efficient algorithm for calculating it for arbitrary x. :) – Stephen Touset Oct 7 '14 at 23:57
  • + for embedded/etc ref factorable.net . But you have the bug backwards: upstream OpenSSL (then) seeded partly from "leftover" stack data and worked decently, but a Debian packager commented out the use of uninit var because analysis tools complained (and in most programs it is indeed a bug) leaving almost no entropy. debian.org/security/2008/dsa-1571 schneier.com/blog/archives/2008/05/random_number_b.html – dave_thompson_085 Oct 10 '14 at 7:42
  • @RickyDemer That is true, though when I said "isn't really defined" I was referring to the fact that (as Stephen pointed out) we don't have a defined, agreed upon function for calculating its true value, short of actually counting all the primes, which defeats the point of the PCF in the first place. – Polynomial Oct 10 '14 at 16:20
1

Basically, statistics. The chances of generating two identical private keys in an environment with good randomness are effectively nil.

  • I think "good randomness" should be underlined, in bold, and in a 120pt font. :p – cloudfeet Oct 7 '14 at 16:32
  • Even with only "fair randomness" or just "randomness" not only would one have to discover they have the same key as someone else, they have to realize they have the same key as someone else. It's essentially the same thing as with keys to bike locks. There are probably over 100 people in the US alone that have the same exact keys to their bike locks, but the manufacturers ship them to different regions and states and the odds of someone in Florida realizing and exploiting the fact that they have the same key as someone in California even more astronomical. Could it happen? Yes, anything COULD. – JekwA Oct 7 '14 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.