findCommonPrimes.py

from Crypto.PublicKey import RSA

# pem = open('private.pem','r').read()
# key = RSA.importKey(pem)

# cyphertext = open('message.bin','r').read()
# print key.decrypt(cyphertext)


def gcd(a,b):
	if b > a:
		temp = b
		b = a
		a = temp
	
	if b == 0:
		#success
		return a
	if b == 1:
		return 1
	return gcd(a%b, b)

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    gcd, x, y = egcd(a, m)
    if gcd != 1:
        return None  # modular inverse does not exist
    else:
        return x % m


for i in range(1,101):
	pem = open('../%d.pem' % i,'r').read()
	cyphertext = open('../%d.bin' % i,'r').read()
	n = long(RSA.importKey(pem).n)
	e = long(RSA.importKey(pem).e)
	for j in range(1,101):
		if i == j:
			continue
		pem2 = open('../%d.pem' % j,'r').read()
		n2 = long(RSA.importKey(pem2).n)
		modulus = gcd(n,n2)
		if modulus != 1:
			p = long(modulus)
			q = long(n/modulus)
			phi = (p-1)*(q-1)
			d = modinv(e, phi) #(1/e)%phi
			pem3 = RSA.construct((n,e,d))
			print pem3.decrypt(cyphertext)

There are not as many weak RSA keys available as the bug that was causing a faulty number generator on some systems has long since been patched. But it was only a few years ago that many keypairs across the Internet were vulnerable to this simple script.