Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Multi Prime RSA solver
# 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")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.