MAKECERT and duplicate Public Keys

Question

I hope this question makes sense. But let's say I create a Certificate with MAKECERT.EXE like this:

makecert -r -sr LocalMachine -ss my -a sha256 -sky exchange -n "CN=Hello World"

Now let's say I run this on two different (Windows) machines. Statistically what are the chances the certificates on the two different machines will have the same Public Key?

If this question does not make sense, I'd appreciate an explanation as to why it doesn't.

Thanks.

Answer 1

• makecert defaults to a 1024-bit RSA key.
• It defaults to a fixed e=65537.
• A 1024-bit RSA key has two primes, each 512 bits long.
• The Prime Number Theorem says that there are more than 2^511/ln(2^511) primes of that size, and if we subtract all the 511-and-smaller bit primes we're left with about 10^151.
• So across two runs, the odds of the smaller of the two primes being the same is about 1 in 1e151.
• Running that through the formula for the birthday problem we see that all the magic really happens around the 1e75 mark.
  • 1% chance of collision: 4.5e74
  • 10%: 1.5e75
  • 25%: 2.4e75
  • 50%: 3.7e75
  • 75%: 5.3e75
  • 99%: 9.6e75
• All of that was for one of the two primes. If we factor in the other (and, without-loss-of-generality, assume that we always declare that p < q) then we get:
  • 5e150 * 1e151 ~= 5e301 different 1024-bit values of RSA n.
  • 1% collision chance after 1e150 runs.
  • 10% collision chance after 3e150
  • 25% collision chance after 5e150
  • 50% collision chance after 8e150
  • 75% collision chance after 1e151
  • 99% collision chance after 2e151

At 1 million keys per second (1e6) for all ~86000 seconds per day you get 8.6e10 keys per day. To have a "millionth of a percent" chance (1/1e8) of a collision you'll need over 1e136 days of computation. That's 3e133 years. The universe, currently, is believed to be 1.4e10 years old. So, you need about 2.3e123 universes to have even that high of a chance (give or take a couple universes).

BTW, my computer can only do ~100 1024-bit keys per core-second (right around 10ms per), so I'm assuming you have about 10,000 of them chugging away at this problem.

Unless we model in CSPRNG state collision and VM rollback (to cause CSPRNG state collision), the answer is: effectively impossible.