This is my favourite chall in this CTF, it is solvable without too much advanced knowledge.
We are given the `crow` function, which is applied on `(p, q, r)` then `(_enc * pk, pk * _hash, _hash * _enc)` to encrypt the message```def crow(x, y, z):	return (x**3 + 3*(x + 2)*y**2 + y**3 + 3*(x + y + 1)*z**2 + z**3 + 6*x**2 + (3*x**2 + 12*x + 5)*y + (3*x**2 + 6*(x + 1)*y + 3*y**2 + 6*x + 2)*z + 11*x) // 6```The only approach here is to find a way to get back `(x, y, z)` from `crow`. Although this function looks complicated, it can be simplified to a much nicer version.
Let `a = x + y + z + 1`, `b = x + y + 1`.  With our knowledge learned in highschool, `crow` can be simplified as:```crow = (a**3 + 3*b**2 + 2*b - 6*y - z - 6) // 6```Now because x, y, z are big numbers we can get them back with approximation:- `a` approximates to `cuberoot(6*crow)`- `b` approximates to `sqrt((6*crow - a**3) / 3)` (when x, y, z are not big enough, this value is off by one)- Then we can calculate the rest to get back `(x, y, z)`
Full solver code:```from Crypto.Util.number import *
def crow(x, y, z):	print('x', x)	print('y', y)	print('z', z)	return (x**3 + 3*(x + 2)*y**2 + y**3 + 3*(x + y + 1)*z**2 + z**3 + 6*x**2 + (3*x**2 + 12*x + 5)*y + (3*x**2 + 6*(x + 1)*y + 3*y**2 + 6*x + 2)*z + 11*x) // 6
def root(n, k):      low = 0      high = n + 1      while high > low + 1:         mid = (low + high) >> 1         mr = mid**k         if mr == n:            return (mid, 1)         if mr < n:            low = mid         if mr > n:            high = mid      return (low, 0)
def rev_crow(cr, delta = 0):        cr *= 6        a = root(cr, 3)[0]        print('a', a)        cr = cr - a**3        b = root(cr // 3, 2)[0] + delta        print('b', b)        cr = 3*b*b + 2*b - cr        r = a - b        cr = cr - r - 6        q = cr // 6        p = b - q - 1        print('p', p)        print('q', q)        print('r', r)        print('crow', crow(p, q, r))        return p, q, r
cr = open('flag.enc', "rb").read()cr = bytes_to_long(cr)print('crow', cr)pq, qr, rp = rev_crow(cr)pqr = root(pq*qr*rp, 2)[0]_enc = pqr // qr_hash = pqr // pqpk = pqr // rpprint('enc', _enc)print('hash', _hash)print('pk', pk)p, q, r = rev_crow(pk, 1)e, n = 31337, p * q * rphi = (p - 1)*(q - 1) * (r - 1)d = inverse(e, phi)pt = pow(_enc, d, n)print(long_to_bytes(pt))```
Flag: `ASIS{I7s__Fueter-PoLy4__c0nJ3c7UrE_iN_p4Ir1n9_FuNCT10n}`