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?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ 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 $\endgroup$– Alexandre YamajakoCommented Aug 5, 2013 at 0:53
-
$\begingroup$ Ok then assume that these primes are not random. How can they be distinguished from a truly random sequence? $\endgroup$– alexandrosCommented Aug 5, 2013 at 1:04
-
2$\begingroup$ 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... $\endgroup$– Alexandre YamajakoCommented Aug 5, 2013 at 1:10
-
3$\begingroup$ @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. $\endgroup$– B-ConCommented Aug 5, 2013 at 3:59
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
answered Oct 16, 2015 at 7:11
$\begingroup$
$\endgroup$
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
