An RSA public key (e,N) consists of an exponent e and a modulus N. The modulus is the product of two randomly chosen prime numbers p and, q. If p and q are known, it is straightforward to derive the private key. However, if they are unknown, one must factor N into p and q, which requires intensive computing resources. However, let’s assume that two keys with modulus N₁ and N₂ share one of the factors: N₁ = p₁ x q and N₂ = p₂ x q. In this case, finding the greatest common divisor of N₁ and N₂, which is q, is sufficient to factor these two moduli. The task of finding the greatest common divisor of two 1024-bit integers is much simpler than factoring and can be done in microseconds…

This well known vulnerability of RSA can be exploited in the context of low entropy keys. Poor random number generation can indeed lead to multiple keys sharing one of their factors. Heninger found that more than 60’000 keys (approximately 0.5%) they had collected could be factored in this way.

via Quantis Newsletter – September 2012.