TDUCTF 2015 Crypto500 My RSA

myrsa.py

A = 2**127 - 1
B = 2**521 - 1
M = 2**607 - 1
e = 2 ** 16 + 1
N = 63818680202675589216815967315756339566489246779116223051722243409259352306082269405584940079271925323037734694881017657210693291225811959344097136283943773119253977386753351100049200282621303479907450098708525270143513533970091975470643256818850535284677109438825447301648598261836252545636152169068763895406856318437232759172916712871952129664784095465920918889209

# Mathematica
# X = Mod[FindInstance[Reduce[A*x^2 + B*x - NN + k*M == 0, {x, k}, Integers], {x, k}][[1]][[1]][[2]], M]
X = 191381205906541365810282593776863206661156657204872893015293939948869850881931905283828875884014270971209197231695869794928684848246961454267088835714426435068255775651115299873104893

# from http://rosettacode.org/wiki/Modular_inverse#Python
def extended_gcd(aa, bb):
    lastremainder, remainder = abs(aa), abs(bb)
    x, lastx, y, lasty = 0, 1, 1, 0
    while remainder:
        lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
        x, lastx = lastx - quotient*x, x
        y, lasty = lasty - quotient*y, y
    return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)

def modinv(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise ValueError
    return x % m


p = X
q = (A * X + B) % M
assert(p * q == N)

d = modinv(e, (p-1) * (q-1))

print 'p:', p
print 'q:', q
print 'd:', d

C = int(open('./encrypted.dat', 'rb').read().encode('hex'), 16)
Plain = pow(C, d, N)

print hex(Plain)
print hex(Plain)[2:-1].decode('hex')