PKI Crumbles A Bit More
The RSA public key encryption method uses two prime numbers: p and q, and then calculates a modulus (N=p*q). If we can find one of the random prime numbers, we can easily find the other one, and then can determine the private key from the public key value. We thus need to make sure we have a completely random prime number, and one which is not easily guessable. But Keyfactor scanned over 75 million RSA certificates certficates on the Internet and found that 1 in 172 digital certificates share a common factor [here].
The work is not new in its methodology and uses a GCD (Greatest Common Denominator) method in order to determine if a modulus (N) shares a factor with others. With GCD, we take two numbers, such as 15 and 21, and then determine if they share a common factor. In this case the largest common factor is 3. With an RSA modulus we should always get a GCD of 1 for two modulus’ that we try, and especially where we have completely random prime numbers. Here is an outline of how RSA is cracked if we can factor the modulus:
The Keyfactor work follows the work of Lensta et al [1] and Heninger et al [2]:
