# Does it necessarily mean that an RSA moduli generated with poor randomness is not random?

In 2012 a group of researchers collected a large amount of RSA moduli and calculated their greatest common divisor in order to find common factors between them. By finding a common factor they could the divide and completely factorize the key. They concluded that the vulnerable moduli where generated by PRNGs with inadequate randomness. Does it necessarily mean that those key are not random?

• Short answer is yes : If the PRNGs had been properly seeded it would have been very unlikely that two moduli share a non-trivial factor. Said otherwise the moduli generated with in that way are a particular subset (understand here non-random) of the semi-primes of a given size Commented Aug 5, 2013 at 0:53
• Ok then assume that these primes are not random. How can they be distinguished from a truly random sequence? Commented Aug 5, 2013 at 1:04
• By doing exactly what they did in the paper you're talking about : calculating their gcd. In a truly random sequence of semiprimes the gcd found would be 1 with high probability... Commented Aug 5, 2013 at 1:10
• @hask: To see if something is "random", context is everything. No number itself is random or not random. Rather, it is the process that generates the number that is random or not. And even then we can't prove something is random, just we can only say that it looks good under certain analysis. However, there are many ways to distinguish output as coming from a bad source. This study did one, namely, find output thats the same between sources, as that should happen with very low probability. Commented Aug 5, 2013 at 3:59