I did not manage to solve this challenge. The private key is composed by some $f, g$, both smaller than $\sqrt{\frac{q}{2}}$, with the relation that $fh - g = 0 \mod q$
This means that there exists a $k$ such that $fh = qk + g$, since $h$ is about the same size of $q$, we have that $k$ is the same size of $f$.
We have the observation that $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}$, and $f$ is approximately $k$). Also note that $f > k$, hence $f - k > 0$.
We can use Gauss reduction to find the lattice generated by $(h, 1), (q, 1)$ has a chance to give us $g$.
Sage Implementation: (kudos to Drago)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
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)))
|