Find the Lattice

I did not manage to solve this challenge. The private key is composed by some $f,g$$f, g$, both smaller than $\sqrt{\frac{q}{2}}$$\sqrt{\frac{q}{2}}$, with the relation that $fh-g=0\mathrm{mod}q$$fh - g = 0 \mod q$

This means that there exists a $k$$k$ such that $fh=qk+g$$fh = qk + g$, since $h$$h$ is about the same size of $q$$q$, we have that $k$$k$ is the same size of $f$$f$.

We have the observation that $f\cdot (h,1)+(-k)\cdot (q,1)=(g,f-k)$$f \cdot (h, 1) + (-k) \cdot (q, 1) = (g, f - k)$, where both components of the result are small (g is around the square root of $\frac{q}{2}$$\frac{q}{2}$, and $f$$f$ is approximately $k$$k$). Also note that $f>k$$f > k$, hence $f-k>0$$f - k > 0$.

We can use Gauss reduction to find the lattice generated by $(h,1),(q,1)$$(h, 1), (q, 1)$ has a chance to give us $g$$g$.

Sage Implementation: (kudos to Drago)

xxxxxxxxxx
from Crypto.Util.number import long_to_bytes

def decrypt(q, h, f, g, e):
    a = (f*e) % q
    m = (a*inverse_mod(f, g)) % g
    return m

def gauss(v1, v2):
    while True:
        if v2.norm() < v1.norm():
            v1, v2 = v2, v1
        m = round(v1*v2/(v1*v1))
        if m == 0:
            return v1, v2
        v2 = v2-m*v1

h, q = (2163268902194560093843693572170199707501787797497998463462129592239973581462651622978282637513865274199374452805292639586264791317439029535926401109074800, 7638232120454925879231554234011842347641017888219021175304217358715878636183252433454896490677496516149889316745664606749499241420160898019203925115292257)
enc_flag = 5605696495253720664142881956908624307570671858477482119657436163663663844731169035682344974286379049123733356009125671924280312532755241162267269123486523

g = gauss(vector([q,1]),vector([h,1]))[0][0]
F = IntegerModRing(q)
f = int(g / F(h))
print(long_to_bytes(decrypt(q,h,f,g,enc_flag)))