Crypto - uf

🙄 - Laika

Full Implementation

Challenge

def encrypt(m: int, n: int = 512) -> int:
    x = 0
    for i in range(n):
        x <<= 1
        x += m * randbits(1)
        if i >= n // 2:
            x ^= randbits(1)
    return x

Solved after the CTF ended.

The for loop multiplies by the sum by 2 each time and maybe adds 1 to the product of m. The other condition only concerned with adding a constant, as it only changes the last bit, it may add 1 to the sum at the end of each loop

The output can be generalized as

$$x_i = q_i\times m + r_i$$

Where pi and ri are unknown. Solving this can be generalized to solving the Approximate GCD problem

We use the solution given here

Page 41, Practical lattice reductions for CTF challenges

pad = 2^300
M = Matrix(ZZ,[[pad,x1,x2,x3],[0,-x0,0,0],[0,0,-x0,0],[0,0,0,-x0]])
M1 = M.LLL()
q0 = M1[0][0] //pad

Finding q0 is actually enough to solve for m because

$$x_o = q_o \times m + r_0 \\ x_0 = r_o \pmod{q_0}$$

After finding r0 we get

$$\frac{(x_0 -r_0) }{q} = m$$

r0 = x0 % q0
ans = (x0-r0) // q0
print(long_to_bytes(ans))
#FLAG{hope_this_chal_is_not_automatically_solved_by_AI_c14ef1732e87a6c}