HITCON CTF Quals 2015 rsabin

solve.py

#!/usr/bin/env python
# author: 193s
from modular_sqrt import modular_sqrt
from scryptos.math.arithmetic import modinv, chinese_remainder_theorem, egcd
import string
from sys import exit

bytes_to_long = lambda s: int(s.encode('hex'), 16)
long_to_bytes = lambda l: ('%x'%l).decode('hex')

n = 20313365319875646582924758840260496108941009482470626789052986536609343163264552626895564532307
e = 31415926535897932384
c = 19103602508342401901122269279664114182748999577286972038123073823905007006697188423804611222902
p = 164184701914508585475304431352949988726937945291
q = 123722643358410276082662590855480232574295213977
assert n == p*q

## enumerate all possible m = FLAG % n

list_m = set() # list of all possible m's

_d = modinv(e / (2**5), (p-1)*(q-1))

def dec(t, i):
  if i == 5:
    mm = pow(t, _d, n)
    if pow(mm, e, n) == c: list_m.add(mm)
  else:
    mp = modular_sqrt(t, p)
    mq = modular_sqrt(t, q)
    _, yp, yq = egcd(p, q)
    r = (yp*p*mq + yq*q*mp) % n
    s = (yp*p*mq - yq*q*mp) % n
    m1, m2, m3, m4 = r, s, n-r, n-s

    dec(m1, i+1)
    dec(m2, i+1)
    dec(m3, i+1)
    dec(m4, i+1)
dec(c, 0)

charset = string.printable

for m in list_m:
  print '#', m
  sr = (bytes_to_long('hitcon{')<<(8*43)) / n
  v_flag = False
  las_g = ''
  x = sr + 210000000
  while x <= sr + 900000000:
    r = long_to_bytes(m + n*x)
    if not v_flag and r[-1] == '}':
      v_flag = True
    if r.startswith('hitcon{'):
      g = r[7:11]
      # hitcon{(g)...
      if g[0] != las_g:
        print repr(g)
        las_g = g[0]
      if all([c in charset for c in r]):
        # found flag ! hitcon{[:print:]+}
        print '***************************************************'
        print r
        exit(0)
    x += 256 if v_flag else 1