Take the 2-minute tour ×
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
1  
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? –  hask Aug 5 '13 at 1:04
2  
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
1  
@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

1 Answer 1

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

Your Answer

 
discard

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.