This is a (multi) RSA-type of challenge, in which we are given some relationships between the prime numbers used, and we have to recover them to decrypt the flag. This is the code:

def keygen(nbit):
	p, q, r = [getPrime(nbit + (nbit >> 3) * _) for _ in range(3)]
	return p, q, r

m = bytes_to_long(os.urandom(len(flag)) + flag + os.urandom(len(flag)))
nbit = 512
p, q, r = keygen(nbit)
n, s, e = p * q * r, inverse(p, q * r) + p, 1234567891

while True:
    pr(f"{border} Options: \n{border}\t[E]ncrypt the flag! \n{border}\t[P]ublic information \n{border}\t[Q]uit")
    ans = sc().decode().strip().lower()
    if ans == 'e':
        assert m < n
        c = pow(m, e, n)
        pr(f'{c = }')
    elif ans == 'p':
        pr(border, f'{n = }')
        pr(border, f'{s = }')
        pr(border, f'{q % p = }')

So, the server generates three prime numbers, $r, s$ and $t$, of 512, 576 and 640 bits, respectively. Then, we are given $n = pqr$, $s$, which is computed as s = inverse(p, q*r) + p and q % p. First, note that as $qr$ is quite bigger than $p$, we can take the sum of $p$ into the modular expression and say that

$$s = p^{-1} + p \ (mod \ qr)$$

Then, let

$$t = q \ (mod \ p)$$

The goal is, having $n, s$ and $t$, recover $p, q$ and $r$. To handle better the expression for $s$, multiply it by $p$, getting:

$$sp \equiv 1 + p^2 \ (mod \ qr)$$

which means

$$\exists k_1 \in \mathbb{Z} : sp = 1 + p^2 + k_1qr$$

and multiplying both sides by $p$, we get:

$$sp^2 = p + p^3 + k_1n \iff p^3 - sp^2 + p + k_1n = 0 \implies p^3 - sp^2 + p \equiv 0 \ (mod \ n)$$

In different words, let $f \in \mathbb{Z}_n[x]$ be the polynomaial given by $f(x) = x^3 - sx^2 + x$. Then, $p$ is a root of $f$.

Now, how can we obtain the roots of $f$? Well, note that $n$ is 1728 bits long and $p$ is 512 bits, which is small compared to the size of $n$. This hints us at using the small_roots function that sagemath implements to recover $p$:

r = process("./phoney.py")
r.sendlineafter(b"[Q]uit\n", b"p")
r.recvuntil(b"n = ")
n = int(r.recvline().strip())
r.recvuntil(b"s = ")
s = int(r.recvline().strip())
r.recvuntil(b"q % p = ")
t = int(r.recvline().strip())

P = PolynomialRing(Zmod(n), 'x')
x = P.gen()
f = x**3 - s*x**2 + x
roots = f.small_roots(X=2**512, epsilon=0.03)
p = int(roots[1] if roots[1] != 0 else roots[0])

When using small_roots, the approximate size of $p$ is passed as the argument X, and a small epsilon is also passed. The epsilon parameter is used in the lattice construction. Bigger epsilon implies bigger lattice and more time to apply the LLL algorithm on it. Usually gets better results, at slower performance. In this case, it takes around a minute to get the root.

Now that we have $p$, we can recover $pq$ simply by diving $n$ by $p$.In order to recover $q$ and $r$, we need to use the other relationship: $t \equiv q \ (mod \ p)$. This means

$$\exists k_2 \in \mathbb{Z} : t = q + k_2p$$

As $t$ has (approximately) the same size as $p$, $k_2p$ needs to have the same size as $q$, so that $k_2$ is around 64 bits.

From this last relation we get that $t - k_2p = q$, so that $t - k_2p$ divides $qr$. We would like to recover $k_2$, which leads to recovering $q$. We can use again the small_roots method to do so, because $k_2$ is pretty small (64 bits) compared to $qr$ (1216 bits). We can do that with this piece of code:

qr = n // p
P2 = PolynomialRing(Zmod(qr), 'y')
y = P2.gen()
g = t - p*y
k2 = g.monic().small_roots(X=2**70, beta=0.4)[0]
q = int(t - k2*p)

Note that beta value passed to small_roots. This is because small_roots also looks for roots of the polynomaial in divisors of the modulus. In this case, we want it to look for roots in $\mathbb{Z}_q$ ($q$ divides $qr$). The beta value specifies sage to find integers $x_0$ such that

$$f(x_0) \equiv 0 \ (mod \ b), \quad \text{for some} \ b, \text{divisor of} \ qr \ \text{with} b \geq N^\beta$$

In our case, $q \geq (qr)^{0.4736}$, so setting beta=0.4 does the trick. Actually, setting it to anything lower than that value does the trick as well.

Once we have recovered $q$, we recover $r$ trivially and decrypt the flag as usual:

_r = qr // q
assert q*_r*p == n

phi = (p-1)*(q-1)*(_r-1)
e = 1234567891
d = inverse_mod(e, phi)
r.sendlineafter(b"[Q]uit\n", b"e")
r.recvuntil(b"c = ")
c = int(r.recvline().strip())
m = pow(c, d, n)
flag = long_to_bytes(m)
print(flag)

Fun chall!