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)

Code to solve puzzle on:
http://www.loyalty.org/~schoen/rsa/

The concept is that not all random number generators are truly random.

The first step of generating a RSA keypair is to generate two prime numbers (p and q). If the random number generator fails and reuses the same primes, then the public key can be compared to other keys to determine the two prime numbers, and therefore, recreate the private key.

It works like this:

Imagine we have 100 keypairs, some of which happen to share a prime number. The public key reveals the n value (p * q). If we compare the n values from different public keys, we can use the greatest common denominator to determine if there is a shared prime number. If we determine that they share a common prime number through GCD, then the other prime number (for each keypair) can be determined by dividing n by the first prime number.

For example:

• Two n values may be 55 and 77 (the n value will be a much larger number in reality)
• GCD(55, 77) = 11
• 77/11 = 5 and 55/11 = 7
• We now know that the two sets of prime numbers for each keypair are (5, 11) and (7, 11) and can use these numbers to re-generate the private key.

The greatest common denominator is relatively easy for a computer to determine. Through iteration of the GCD function, we can continue to use the modulus to determine the next number to test. Refer to my code below:

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)

• First, order the parameters so that the a is the larger number.
• Next, check if the smaller number (b) is zero or one. If so, we are finished and have determined the gcd. If b == 0 then a is the GCD. If b == 1 then the GCD is equal to one and we can continue on to the next n to compute.
• If neither of these are true, then we perform the next iteration of the GCD where a can be replaced with a%b. I will not go into the mathematical proof for this here.

Using the same numbers as before: gdc(77, 55)

Iteration 1:
77%55 = 22 => compute gcd(22, 55)

Iteration 2:
55%22 = 11 => compute gcd(11, 22)

Iteration 4:
22%11 = 0 => 11 IS A PRIME

Since 11 is a known prime, we can compute the other two primes: 77/11 = 7, 55/11 = 5

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.