Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
SECCON 2014 - crypto200
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)
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.