If there are n possible birthdays of equal probability,... Based on the current word population, 90 bits of randomness should be ample to avoid collisions, not 2000.
--no. You are missing the point. The collisions were not the problem, they were the symptom of the problem. The problem was, generating too few keys. This means the KGB (or whoever planted that bogus not-very-random generator in NETSCAPE or whatever) can break your RSA "secrets" easily by searching a small space, whose definition is known to them. Way smaller than they were supposed to need to search. Unfortunately for the KGB, the world pop of 10^10 would mean to avoid birthdays they would need to make the space be 10^20, which would be too large for them to crack. So they made it smaller than 10^20, causing their plots to become revealable thanks to the Birthday effect. If you trust linux's alleged true-random bits and Intel's alleged true random bits, then fine, problem solved. I think in the case of Intel you really should trust them... probably... because a cheat engineered by the KGB in cooperation with Intel would be revealed by collision tests -- which they pass. Intel+KGB could be cleverer and weaken their randoms only when their hardware hack detected they were being used by a keygen code. This would be harder to detect, but still detectable, by the writers of the keygen code. If they tried.