Instantly share code, notes, and snippets.

@193s /solve.py
Last active Oct 19, 2015

Embed
What would you like to do?
HITCON CTF Quals 2015 rsabin
#!/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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment