ASIS CTF Finals 2017: Interested Message

solve.py

from scryptos import *
import hashlib
import gmpy
'''
References: 
[1] Hitachi, Ltd. 2001. Specification of HIME(R) CryptoSystem - http://www.hitachi.com/rd/yrl/crypto/hime/HIME_R_specE.pdf
'''
SECRET = 'ASISCTF-17'

C0 = [ hashlib.sha1(SECRET[i:] + SECRET[:i]).digest()[:16] for i in xrange(10) ]
C1 = (''.join([ hashlib.sha1(SECRET[i:] + SECRET[:i]).hexdigest()[24:] for i in xrange(8) ])).decode('hex')

def xor_str(x, y):
    if len(x) > len(y):
        return ''.join([chr(ord(z) ^ ord(p)) for (z, p) in zip(x[:len(y)], y)])
    else:
        return ''.join([chr(ord(z) ^ ord(p)) for (z, p) in zip(x, y[:len(x)])])

def hashi(x):
    if len(x) < 16:
        x = (16 - len(x)) * chr(0) + x
    return hashlib.sha1(xor_str(x + x, C1)).digest()[:16]

def G(x):
    a = 2 ** 127 - 1
    g = ''.join([ long_to_bytes(bytes_to_long(hashi(x + C0[0])) & a) ] + [hashi(x + C0[i]) for i in range(1, 9)] + [hashi(x + C0[9])[:8]])
    if len(g) < 152:
        g = (152 - len(g)) * chr(0) + g
    return g

def H(x):
    if len(x) < 152:
        x = (152 - len(x)) * chr(0) + x
    x = x + chr(0) * 8
    X = [x[i*16:(i+1)*16] for i in xrange(10)]
    res = hashi(X[0] + C0[0])
    for i in xrange(1, 10):
        res = xor_str(res, hashi(X[i] + C0[i]))
    if len(res) < 16:
        res = (152 - len(res)) * chr(0) + res
    return res

n = 198215811254578914143528679853394516943487191887133602719421229002835939155691362962056570747961133502365266191144307866755524824103871505056373013932585133835543321312227889313102212621888049039915064642604244253420464918662950537321433526102958541961921321562189585754292234269540520254519467706456342129214007611726103951423784590140561773123755857400629545080504437281815096797288082474978240553370503
enc = 90202671282140726938772231828532543465876394733342802972061264758729938518019431881534956868790097577690987026821010559147302121811579117273065376510961140002317015599909541782531328674281365144484724526798519803467240235138261486140279631210452738702091365452358994702604159240518573590663651781917664308109701267670633780136142501057454596418073159035730758145508658399991034098716891323263302795445575

# Guess: |p - q| is very small
x = nth_root(n, 3)
while True:
  x = gmpy.next_prime(x)
  if n % x == 0:
    q = int(x)
    print '[+] q = %d' % q
    break

# Actually, q = 583059350840498322495293827270996268277814817261340572149557041850334201169979322271355385635285998430821171194131461175804739754635847

p = isqrt(n / q)
pq = p*q
assert gmpy.is_prime(p) == 1
assert p**2 * q == n

a, b = (p+1)/4, (q+1)/4
z = modinv(p, q)

phi = p*(p-1)*(q-1)

# x = pow(enc, (phi + 4) / 8, n)
# -> not worked (maybe legendre symbol of p and q are -1)

# We write decryption code referenced [1] pp.14 - 16.

assert pow(enc, (p-1)/2, p) == 1
assert pow(enc, (q-1)/2, q) == 1

a1 = pow(enc % p, a, p)
a2 = p - a1
assert pow(a1, 2, p) == enc % p
assert pow(a2, 2, p) == enc % p
b1 = pow(enc % q, b, q)
b2 = q - b1
assert pow(b1, 2, q) == enc % q
assert pow(b2, 2, q) == enc % q

y = ((b1 - a1) * z) % q
x1 = a1 + y*p

y = ((b1 - a2) * z) % q
x2 = a2 + y*p

y = ((b2 - a1) * z) % q
x3 = a1 + y*p

y = ((b2 - a2) * z) % q
x4 = a2 + y*p

for x in [x1, x2, x3, x4]:
  if (x**2 - enc) % pq == 0:
    s = (x ** 2 - enc) / pq
    t = p - (s % p)
    Y = (t * modinv(2*x, p)) % p
    x = (x + Y * pq) % n
    assert pow(x, 2, n) == enc
    mp = long_to_bytes(x)

    if len(mp) < 168:
      mp = (168 - len(mp)) * chr(0) + mp

    s, t = mp[:152], mp[-16:]

    r = xor_str(t, H(s))
    M = xor_str(s, G(r))
    m, w = M[:136], M[136:]

    if w == '\x00' * 16:
      print repr(m)
      print repr(w)
      break

solve_log

Mon Sep 11 02:43:26 JST 2017 ~/Downloads/oracle 100%
> time python solve.py 
[+] q = 583059350840498322495293827270996268277814817261340572149557041850334201169979322271355385635285998430821171194131461175804739754635847
'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00ASIS{Highly_Interested_Message_Encryption_System_IS_HIME!!!}'
'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'

real    0m6.168s
user    0m6.128s
sys     0m0.008s