Crypto - Copperbox

Cedric found a mysterious box made of pure copper in the old archive. He is convinced that it contains the secrets he is looking for, but he is unable to penetrate the metal case. Can you help?

Challenge

import secrets

p = 0x31337313373133731337313373133731337313373133731337313373133732ad
a = 0xdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef
b = 0xdeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0de

def lcg(x, a, b):
    while True:
        yield (x := a*x + b)

x = int.from_bytes(flag + secrets.token_bytes(30-len(flag)), 'big')
gen = lcg(x, a, b)

h1 = next(gen) * pow(next(gen), -1, p) % p
h2 = next(gen) * pow(next(gen), -1, p) % p

with open('output.txt', 'w') as o:
    trunc = 48
    # oops, i forgot the last part
    o.write(f'hint1 = {h1 >> trunc}\n')
    o.write(f'hint2 = {h2 >> trunc}\n')

This looks like a Truncated LCG question, and the challenge name hints at us to use Coppersmith's method.

The hints that are given to us are not directly truncated outputs, rather a pair of the product of the state and inverse of the next state.

To find the flag, we need to find the seed of the LCG, first we need to see the equations given. Let $s_i$ denote the states, then

$$s_1 = ax + b \\ s_2 = a^2x + ab + b \\ s_3 =a^3x + a^2b + ab + b \\ s_4 = a^4x + a^3b + a^2b + ab + b \\ h_1 = s_1/s_2 \mod p \\ h_2 = s_3/s_4 \mod p$$

The hints given to us are $f(x) = x * e^{2 pi i \xi x}$h1>>48 and h2>> 48, since h1 and h2 are given modulus p, we can recover h1 and h2 using Coppersmith's method. Let's try forming the equations

We need to form an equation with h1 and h2 such that it is 0 mod p.

One approach that we can try is trying to find an approximation to x from h1 and substituting it in h2.

$$h_1 = (ax+b)/(a^2x+ab+b) \mod p \\ a^2h_1x+abh_1+bh_1 -ax -b = 0\mod p \\ x = (b - abh_1-bh_1)/(a^2h_1-a) \ mod p$$

The problem here is that Coppersmith's method doesn't take inverse polynomials. Even if it did, we need to calculate $(a^2h_1-a)^{-1}$, which is a problem, because inverse calculation needs to precise, even a small change can cause a large change in the inverse, which virtually gives us no information about the approximation of x, even though we have an approximation of $h_1$.

We can consider another approach which doesn't use $x$ . To do this, we need to find some relation between $h1$ and $h2$. We can do this using Groebner basis.

R.<a,b,x,h1,h2> = PolynomialRing(ZZ)
gen = lcg(x, a, b)
f = next(gen) - h1*next(gen)
g = next(gen) - h2*next(gen)
I = Ideal(f,g)
I.elimination_ideal(x)
#Ideal (a^2*b*h1*h2 - a^2*b*h2 + a*b*h1*h2 - a*b*h1 - a*b*h2 + a*b - b*h2 + b) of Multivariate Polynomial Ring in a, b, x, h1, h2 over Integer Ring

Now that we have an equation using $h_1$ and $h_2$ , we can use this implementation of Coppersmith's bivariate method and solve the for the complete $h_1$ and $h_2$.

Let $l_1$ and $l_2$ be the 48-bits of LSB of $h_1$ and $h_2$

R.<l1,l2> = PolynomialRing(GF(p))
hint1 = 77759147870011250959067600299812670660963056658309113392093130
hint2 = 50608194198883881938583003429122755064581079722494357415324546
h1 = l1 + int(hint1<<48)
h2 = l2 + int(hint2<<48)
h = (a^2*b*h1*h2 - a^2*b*h2 + a*b*h1*h2 - a*b*h1 - a*b*h2 + a*b - b*h2 + b)
roots = coppersmith_multivariate_heuristic(h,[2^48,2^48],1)
k11 = roots[0][0] + int(hint1<<48)
x = GF(p)((-a*b*k11-b*k11+b)*(a^2*k11-a)^-1)
long_to_bytes(int(x))
#b'HTB{sm1th1ng_mY_c0pp3r_fl4G}L\xc6'