SECCON 2014 - crypto200

solver.py

def mul_inv(a, b):
    b0 = b
    x0, x1 = 0, 1
    if b == 1: return 1
    while a > 1:
        q = a / b
        a, b = b, a%b
        x0, x1 = x1 - q * x0, x0
    if x1 < 0: x1 += b0
    return x1

# n list of modulus, a list of coefficients
def chinese_remainder(n, a, lena):
    p = i = prod = 1; sm = 0
    for i in range(lena): prod *= n[i]
    for i in range(lena):
        p = prod / n[i]
        sm += a[i] * mul_inv(p, n[i]) * p
    return sm % prod


def decrypt(b, c, p, q):
    m_p = []
    m_q = []
    for i in xrange(p):
        m = i
        if (m * (m + b)) % p == c % p:
            print "Found m mod p =", m
            m_p.append(m)

    for i in xrange(q):
        m = i
        if (m * (m + b)) % q == c % q:
            print "Found m mod q =", m
            m_q.append(m)

    print "Possible candidates: "
    for a in m_p:
        for b in m_q:
            print hex(chinese_remainder([p, q], [a, b], 2))[2:].decode('hex')
    print ""

if __name__ == "__main__":
    decrypt(0xffeee, 0x8d5051562b, 868019, 913799)
    decrypt(0xfffee, 0x5ffa0ac1a2, 875543, 904727)
    decrypt(0xfefef, 0x6008ddf867, 597263, 890459)