This challenge came with two files:
As with some of the other CryptoCTF challenges, the idea here is that we have a python script that encrypts a secret which is imported from a file that was not provided. We have been provided with some constants $X$, $Y$, and $N$ and the ciphertext $c$, along with some asserts in the python code that imply there is some non-standard mathematical property of the primes $p$ and $q$ that were used to generate $N$. The known quantities are
X = 153801856029563198525204130558738800846256680799373350925981555360388985602786501362501554433635610131437376183630577217917787342621398264625389914280509
Y = 8086061902465799210233863613232941060876437002894022994953293934963170056653232109405937694010696299303888742108631749969054117542816358078039478109426
N = 161010103536746712075112156042553283066813155993777943981946663919051986586388748662616958741697621238654724628406094469789970509959159343108847331259823125490271091357244742345403096394500947202321339572876147277506789731024810289354756781901338337411136794489136638411531539112369520980466458615878975406339
c = 64166146958225113130966383399465462600516627646827654061505253681784027524205938322376396685421354659091159523153346321216052274404398431369574383580893610370389016662302880230566394277969479472339696624461863666891731292801506958051383432113998695237733732222591191217365300789670291769876292466495287189494
And from clever_girl.py we know that the following statements are true: $$isprime(p) = 1$$
$$isprime(q) = 1$$$$n = pq$$$$\frac{p}{p+1} + \frac{q+1}{q} = \frac{2s - x}{s + Y}$$The last one is the interesting one, which we can reduce as follows:
$$\frac{p}{p+1} + \frac{q+1}{q} - 2 = \frac{2s - x}{s + Y} - 2$$$$\frac{p - p - 1}{p+1} + \frac{q+1 - q}{q} = \frac{2s - X - 2s - 2Y}{s + Y}$$$$ \frac{1}{q} - \frac{1}{p+1} = - \frac{X + 2Y}{s + Y}$$$$ \frac{1}{p+1} - \frac{1}{q} = \frac{X + 2Y}{s + Y}$$$$ \frac{q-p-1}{q(p+1)} = \frac{X + 2Y}{s + Y}$$The key here is that because $q$ is prime the left hand side is an irreducible fraction, and the top of the right hand side is a constant. Now it turns out the the right hand side is also irreducible, but even if it wasn't we could factor $X+2Y$ and brute force it. Because the right hand side is irreducible, we know that $q-p-1 = X + 2Y$ and it is easy to solve from here because we also know that $q=N/p$
import gmpy2
from fractions import Fraction
from sympy import Symbol, solve
from Crypto.Util.number import long_to_bytes
# First, we solve for p and
p = Symbol('p')
result = solve(N/p - p - 1 - (X+2*Y), p)
p = max(result)
print('p =',p)
q = N/p
print('q =', q)
assert N == p*q
phi = int((p-1)*(q-1))
e = 0x20002
assert 2 == gmpy2.gcd(e,phi)
d = gmpy2.powmod(int(e/2), -1, phi)
m_squared = gmpy2.powmod(c, d, N)
Now, we have to apply a little trick that relies on the fact that the flag was encrypted without padding. Because the exponent $e$ used to encrypt the flag is even, it cannot be inverted mod phi and thus we cannot directly decrypt the message.
Thankfully, $\frac{e}{2}$ can be inverted. So to extract the flag first we take the ciphertext $m^{e}$ and partially decrypt it using the inverse $d \equiv (\frac{e}{2})^{-1} (\mod phi)$:
$$(m^{e})^{d} \equiv ((m^{2})^{\frac{e}{2}})^{d} \equiv (m^{2})^{d(\frac{e}{2})} \equiv m^{2} \mod n$$From here, all we need to do to get the flag is take the square root of the partially decrypted message.
assert gmpy2.is_square(m_squared)
m = gmpy2.isqrt(m_squared)
flag = str(long_to_bytes(m))
print(flag)