Public key encryption is heavily utilized in modern implementations of SSH. By leveraging public key cryptography, administrators can generate both a public key and a private key to encrypt and decrypt data in transit.

Using this method is favored over logging in with passwords that are vulnerable to dictionary attacks. Unfortunately, many SSH implementations use RSA encryption with keys generated using broken random key generators.

Many times, this is because keys are generated on systems with very limited computational capabilities that cannot generate a truly random seed value. This weakness is vulnerable to exploitation if an attacker can compute the two large prime factors that make up the private key.

We at Abricto Security have a database of over a million public RSA keys that we regularly use to scan new found public keys for possible matching keys. If two keys are found that share a greatest common divisor which is greater than one, it becomes trivial to extract the private keys from both public keys.

Once a pair of keys has been isolated that were generated using a broken random key generator (RNG), the P and Q factors are computed and the extended Euclidean algorithm is applied to extract the private keys.

Our team utilized python to generate a proof-of-concept:

We got a match!
Here's n1: 122674739778129708019456870792787852322257642052768260843903499494 *snip*
Here's n2: 121608081932595682903629533946680032876291571480782666632715329128 *snip*
Here's q1: 116772543328001894737302319443835471919682668655679362877647838428 *snip*
Here's q2: 115757205127904234183163270712766816043460104337326463103219584235 *snip*
Here's p: 1050544385537181964579003532131441162619124527593161073805885887146 *snip*
Here's a plain number: 1234567890
Here's the encrypted number using key ending in 12267: 9834035888265848507862 *snip*
Here's the encrypted number using key ending in 12160: 9025361503458246598693 *snip*
Here's the decrypted number using key ending in 12160: 1234567890
Successfully found at least one match.

This flawed implementation phenomena has been heavily researched and documented in Heninger, Durumetric, Wustrow and Halderman’s research paper “Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices”.