Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
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 – Alexandre Yamajako Aug 5 '13 at 0:53
Ok then assume that these primes are not random. How can they be distinguished from a truly random sequence? – AlexH Aug 5 '13 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... – Alexandre Yamajako Aug 5 '13 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. – B-Con Aug 5 '13 at 3:59

2 Answers 2

Pretty much.

The prime numbers for those keys were generated from random number sources with bad entropy. Entropy is really just a human measurement of how unpredictable something is. Entropy sources responsible for the common RSA factors hadn't had enough "random stuff" input to them to get mixed around, so they output data that tended to be the same across many devices. Some more info

share|improve this answer

If each key was generated by selecting two random primes of the desired length then the chance of two keys with a common prime would be incredibly small. If i'm reading How are primes generated for RSA? correctly there are about 2^502 possible 512 bit primes (prime length is half modulus length, so a 1024 bit RSA key would use 512 bit primes).

Since keys have been found which share a prime and the chance of that happening with randomly selected primes is so incredibly small the only reasonable conclusion is that the primes were not selected randomly.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.