Tags: approximation crypto python

Rating: 2.5

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)
print('a', a)
cr = cr - a**3
b = root(cr // 3, 2) + 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 = bytes_to_long(cr)
print('crow', cr)
pq, qr, rp = rev_crow(cr)
pqr = root(pq*qr*rp, 2)
_enc = pqr // qr
_hash = pqr // pq
pk = pqr // rp
print('enc', _enc)
print('hash', _hash)
print('pk', pk)
p, q, r = rev_crow(pk, 1)
e, n = 31337, p * q * r
phi = (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}