Cryptographic keys must be generated using true randomness, and a lot of entropy worth of it, say 2000 bits worth.
If there are n possible birthdays of equal probability, then the number of people required for there to be a reasonable probability of shared birthdays is O(sqrt(n)) -- for reasons based on Stirling's formula. Hence, if we have Np² possible prime numbers that a random number generator could produce, where N is a reasonably large number (10^6, or so) and p is the number of people using this system, then there should be no intersection. Based on the current word population, 90 bits of randomness should be ample to avoid collisions, not 2000. Also, 2^90 operations is out of the computational capacity of any organisation I am aware of (NSA was around 2^56 operations when 56-bit DES was invented, so they were the only organisation capable of cracking it), rendering a brute-force search infeasible. If we want to keep it secure for another century or so, then (using Moore's Law), 160 bits of randomness would suffice. Sincerely, Adam P. Goucher