Google CTF 2017 Quals - Crypto Backdoor

crypto_backdoor.py

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

ph_bsgs.py

'''
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}'
'''