RSA: How effective is this keypair-trash attack [duplicate]

Question

A question that could very well be part of xkcd's "what if?":

Let's say Monica made a piece of software that sends all RSA keypairs to a central database after they're not used anymore. Something like a keypair-trash. Let's say Monica has convinced everyone in the world to use this piece of software. Monica starts collecting keypairs on January 2015 and waits X years and collects all keypairs.

1) Given the current evolution of electronics and use of RSA, how many years would Monica have to wait so that a new keypair created has a 10% chance of being in the database? (you can apply certain limits like key length never changing)

2) If Monica had a DB that has 10% of all the possible RSA keypairs (within certain limits like length). Will the database be so big that searching a match is still too hard?

3) Would the attack be any more effective if Monica managed to put a keygenerating program in every consumer-grade device (with internet connection) of a country the size of the USA? The program uses all the devices spare time to generate keys and send them to her DB.

Answer 1

Without waiting to get a collision, there is a more annoying scenario : compute the gcd of all public keys you can scan over the net. Experience did show that a lot of systems do not generate enough unique entropy (Lenstra, A., et al., "Ron was wrong, Whit is right", Cryptology ePrint Archive Report 2012/064, February 2012). Based on that scenario where everyone in a pool of 2000000 public keys use the same 4000 primes, the probability that 2 users get the very same combination of 2 primes is not so remote (the birthday paradox ....), and the response to your question is : yesterday, at latest. It did occur.

Let's assume that pseudoprimes from probabilistic testing do not interfere (they do, with a jackpot lottery probability!) ... when randomness is weak for integer generation, it is weaker for probabilistic tests.

Let's assume that you don't care about safe prime, strong primes, extra strong safe primes, and all the paranoid method of prime generation which might exclude all of them, because none is really strong and safe enough ....

Assuming your integer selection does not strictly follow some standards which only check the first prime candidate at the end of a prime gap, thus excluding all primes at the start of a prime gap.

Considering the evolution of software and electronics, Elliptic Curve is approximately 10 times faster at equivalent security levels and equivalent source code optimization levels. Monica's database will never fill.

Assuming Cloud Quantum Computing is approximately 60-70 years ahead and Wiki leaks reveals in 30 years that NSA already has a 2048 quBit computer in a vault, this gives a end-of-life of 30 years to Monica database.

Assuming ....

Now, assuming that key generation is fair, everyone is using RSA2048 with 2 x 1Kbit primes and these prime numbers are evenly distributed in the range $[\sqrt{2} \cdot 2^{1023}, 2^{1024}]$, and are safe prime, i.e. $(p-1)/2$ is also prime. There are approximately c =

10474478420880630540417976938987964186481756527689107725320293990926166280934544
54955114259503095991159974600201604222625579123974838523076493430916373173064804
47871510202082442494709247560640274359031066510018408132368005212283030654515197
893087986785888352332881597122452139709939124879383308130303597 

such 1 Kbit primes.

Assuming you like to play the national lottery and are familiar with a low probability $10^{-10}$ to see the first fateful collision event ( http://en.wikipedia.org/wiki/Birthday_problem ) and using a birthday paradox formula, then $10^{-10} = 1 - \exp(-d^2/(2c))$.

You would need this number of keys:

$$d = \sqrt{ \ln(1.0000000001)\cdot 2c)}$$

d = 552129915947348069547969241673542619236474053
1711023498369601774599992268056593071378343449425
9320014789158954279395322381058948290665165722107332

At a rate of 1 new key per nanosecond, your key storage cloud solution must absorb 1 terabit of continuous throughput, plus the little 600% overhead of https connections, disconnections, you might require a computer the size of the universe (including the 99% of it which is supposed to exist amd has not been formally proved, and there will be no energy left to generate enough keys). But let's assume ....

The response is : you need

34195165591218423336373586540577052517638203484900091229
87420239096781423943440303949716847304675114278446095972
125316749920908117079065 years 92 days 3 h. 23 m. 10 s. 

for a 0.000000001 % chance to witness a RSA key collision in your database.