Multi Prime RSA solver

multi_prime_rsa.py

# Solves multi prime rsa given n, e, and c. Need to factor n into primes first (recommend yafu)
# Reference https://crypto.stackexchange.com/questions/31109/rsa-enc-decryption-with-multiple-prime-modulus-using-crt
# From https://github.com/diogoaj/ctf-writeups/tree/master/2018/Timisoara/crypto/NotYourAverageRSA

# Params
e = 65537
c = 48761539940486768790697951968441053167086423529120379009399989923982917278530780108524481919294548305561552133247376067350664771674488982501980538923179804440135482761541868213581098181220801732284669971107195377327445661261746882474615837238429855596647745621191046720648860759474615170945636435027382702345930153884587334870109990234396501579
n = 81736943705459767985288486167314099164146317197040392194768161097750074479540025761100109449092862009195976097250151609584294118669228141027624354052423638509988705830737675936098155468596924772948252465412194715615408850250410310761063399013426728554729053139453019049285162533445627620506060381552244023004446417793032764776342793336374803699
# primes are factored from n
primes = [13791271931, 14045354431, 9135653437, 13351818269, 12139150253, 16755272693, 12624207653, 17085139931, 10173449261, 14433479449, 9864787187, 16512953389, 11924202263, 15640499503, 11824459483, 16610374789, 10802213987, 14984854631, 13227411217, 16593548737, 13898961539, 8883963797, 16733116537, 12405130123, 13370635781, 10965930293, 11279137189, 9312576787, 15410839123, 14616587107, 15424024453, 9190503997, 15975600409, 12580269851]

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):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

ts = []
xs = []
ds = []

for i in range(len(primes)):
	ds.append(modinv(e, primes[i]-1))

m = primes[0]

for i in range(1, len(primes)):
	ts.append(modinv(m, primes[i]))
	m = m * primes[i]

for i in range(len(primes)):
	xs.append(pow((c%primes[i]), ds[i], primes[i]))

x = xs[0]
m = primes[0]

for i in range(1, len(primes)):
	x = x + m * ((xs[i] - x % primes[i]) * (ts[i-1] % primes[i]))
	m = m * primes[i]


print hex(x%n)[2:-1].decode("hex")

FYI-- as of Python 3.8, modular-inverse is in stdlib:

	ds.append(pow(e, -1, primes[i]-1))