Instantly share code, notes, and snippets.

hellman/crypto_backdoor.py

Last active June 15, 2019 07:00
Show Gist options
• Save hellman/8c189eea51da76da0acfe4ab70cfd585 to your computer and use it in GitHub Desktop.
Google CTF 2017 Quals - Crypto Backdoor
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 def I(s): val = 0 for i in range(len(s)): digit = ord(s[len(s) - i - 1]) val <<= 8 val |= digit return val def Sn(i, length): s = '' while i != 0: digit = i & 0xff i >>= 8; s += chr(digit) return s 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, p): a %= p g, x, y = egcd(a, p) if g != 1: raise Exception('No inverse exists for %d mod %d' % (a, p)) else: return x % p def add(a, b, p): if a == -1: return b if b == -1: return a x1, y1 = a x2, y2 = b x3 = ((x1*x2 - x1*y2 - x2*y1 + 2*y1*y2)*modinv(x1 + x2 - y1 - y2 - 1, p)) % p y3 = ((y1*y2)*modinv(x1 + x2 - y1 - y2 - 1, p)) % p return (x3, y3) def double(a, p): return add(a, a, p) def mul(m, g, p): r = -1 while m != 0: if m & 1: r = add(r, g, p) m >>= 1 g = double(g, p) return r def encrypt(message, key): return message ^ key # Modulus p = 606341371901192354470259703076328716992246317693812238045286463 # g is the generator point. g = (160057538006753370699321703048317480466874572114764155861735009, 255466303302648575056527135374882065819706963269525464635673824) # Alice's public key A: A = (460868776123995205521652669050817772789692922946697572502806062, 263320455545743566732526866838203345604600592515673506653173727) # Bob's public key B: B = (270400597838364567126384881699673470955074338456296574231734133, 526337866156590745463188427547342121612334530789375115287956485) if __name__ == "__main__": from secret_data import aliceSecret, bobSecret, flag assert A == mul(aliceSecret, g, p) assert B == mul(bobSecret, g, p) aliceMS = mul(aliceSecret, B, p) bobMS = mul(bobSecret, A, p) assert aliceMS == bobMS masterSecret = aliceMS[0]*aliceMS[1] length = len(flag) encrypted_message = encrypt(I(flag), masterSecret) print "length = %d, encrypted_message = %d" % (length, encrypted_message) # length = 31, encrypted_message = 137737300119926924583874978524079282469973134128061924568175107915062758827931077214500356470551826348226759580545095568667325
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 ''' The arithmetic is probably some masked Elliptic Curve arithmetic. p is factored into many small primes so Pohlig-Hellman method should work (with Baby-Step-Giant-Step inside). Probably it is easy to unmask arithmetic to get the usual equations. Then Sage can do discrete_log nicely automatically. Otherwise, we can reuse the arithmetic functions and code PH and BSGS ourselves. This is done in this script. One tricky point is determining order of g modulo prime factors of p: For elliptic curves the order is close to P (the error is about sqrt(P)), so we can check it exhaustively. Interestingly, all orders are (p-1). Maybe the arithmetic is actually masked multiplication in GF(P), no elliptic curves? ''' from sage.all import * from crypto_backdoor import add, mul # Modulus p = 606341371901192354470259703076328716992246317693812238045286463 # g is the generator point. g = (160057538006753370699321703048317480466874572114764155861735009, 255466303302648575056527135374882065819706963269525464635673824) # Alice's public key A: A = (460868776123995205521652669050817772789692922946697572502806062, 263320455545743566732526866838203345604600592515673506653173727) # Bob's public key B: B = (270400597838364567126384881699673470955074338456296574231734133, 526337866156590745463188427547342121612334530789375115287956485) def discrete_log(g, v, mod, order): lim = int(sqrt(mod)) + 10 table = {} g = g[0] % mod, g[1] % mod v0 = v = v[0] % mod, v[1] % mod cur = g cure = 1 table[-1] = 0 for x in xrange(lim): table[cur] = cure cure += 1 cur = add(cur, g, mod) step = mul(order-1, cur, mod) stepe = cure for e2 in xrange(lim): if v in table: e1 = table[v] ans = (e1 + e2 * stepe) % order assert mul(ans, g, mod) == v0 return ans v = add(step, v, mod) assert 0 def calc_order(g, mod): g = g[0] % mod, g[1] % mod lim = int(sqrt(mod)) + 10 cur = mul(mod - lim, g, mod) cure = mod - lim for test in xrange(2*lim): try: cure += 1 cur = add(cur, g, mod) except Exception as err: assert mul(cure+1, g, mod) == g return cure assert 0 def n2s(n): s = hex(n)[2:].rstrip("L") if len(s) % 2 != 0: s = "0" + s return s.decode("hex") rems = [] mods = [] for (mod, mod_e) in factor(p): assert mod_e == 1 order = calc_order(g, mod) assert mul(order+1, g, mod) == (g[0] % mod, g[1] % mod) print "order", factor(order) cofactor = 1 for pp, e in factor(order): for de in reversed(xrange(1, e + 1)): if mul(order//pp**de + 1, g, mod) == (g[0] % mod, g[1] % mod): order //= pp**de cofactor *= pp**de break print "reduced", factor(order), "cofactor", cofactor x = discrete_log(g, A, mod, order) print "X", x, "ORD", order, "MOD", mod rems.append([x + i * order for i in xrange(cofactor)]) mods.append(order) print from itertools import product for rems in product(*rems): rems = list(rems) try: secret = crt(rems, mods) print "SECRET", secret ms = mul(secret, B, p) ms = ms[0] * ms[1] msg = 137737300119926924583874978524079282469973134128061924568175107915062758827931077214500356470551826348226759580545095568667325 ^ ms print `n2s(msg)[::-1]` except ValueError: pass ''' SECRET 6621005115841589341021728146593578127178145692816888878 'CTF{Anyone-can-make-bad-crypto}' '''