TLDR
Abuse weak prime generation to factorize a rsa modulus and recover the private key.
Recon
It takes only a few seconds to notice that the prime generation is homemade, which is usually a bad idea. From this point the objective is simple : we need to find a way to abuse this homemade prime generation to recover the rsa private key.
Problem formalization
Let’s have a closer look at the prime generation in the function fastPrime(), called twice in our case to produce two 1024-bit primes.
def fastPrime(bits, eps = 32):
while True:
a, e, u = getrandbits(eps), getrandbits(eps), getrandbits(4 * eps)
p = a * (2 ** bits - e) + u
if isPrime(p):
return p
So this is a two-step generation, first 3 numbers $a,e,u$ respectively of size 32,32 and 128 bits are randomly generated, and then we check the primality of the value $p = a(2^{1024} - e) + u$. If it is prime, return p as the generated prime, otherwise start again. So starting from the public modulus definition which is $N=p \times q$, we can write:
$$ \begin{aligned} N &= (a_p(2^{1024} - e_p) + u_p)(a_q(2^{1024} - e_q) + u_q) \\ N &= (2^{1024}a_p)((2^{1024}a_q) - (2^{1024}a_p)(a_qe_q) + (2^{1024}a_p)u_q - (a_pe_p)(2^{1024}a_q) + (a_pe_p) (a_qe_q) \\ & - (a_pe_p)u_q + u_p(2^{1024}a_q) - u_p(a_qe_q) + u_pu_q \end{aligned} $$
which can be summarized as:
$$ \begin{aligned} N = 2^{2048}A + 2^{1024}B + C \end{aligned} $$
where:
$$ \begin{aligned} A &= a_pa_q & (32 + 32 = 64 \text{bits}) \\ B &= -(a_pa_qe_q) + a_pu_q - a_pa_qe_p + u_pa_q \\ &= a_p(u_q - a_qe_q) + a_q(u_p - a_pe_p) & (\approx 161 \text{bits})\\ C &= (a_pe_p)(a_qe_q) - (a_pe_p)u_q - u_p(a_qe_q) + u_pu_q \\ &= (a_pe_p - u_p)(a_qe_q - u_q) & (\approx 256 \text{bits}) \end{aligned} $$
By taking $U_p = (u_p - a_pe_p)$ and $U_q = (u_q - a_qe_q)$ we get:
$$ \begin{aligned} A &= a_pa_q \\ B &= a_pU_q + a_qU_p \\ C &= U_pU_q \end{aligned} \tag{1}$$
To be honest during the CTF at this point I just plugged the polynomial $$f = (a_p 2^{1024} + Up)(a_q 2^{1024} + Uq) \text{ over } \mathbb{Z}/N\mathbb{Z}$$ which has two small roots $U_p$ and $U_q$ modulo $N$ into Coppersmith bivariate and recovered $U_p$ and $U_q$. That was a bit overkill so let’s do this properly without lattice magic. From $(1)$ we get:
$$B = a_p\frac{C}{U_p} + a_qU_p $$ and then: $$a_qU_p^2 - U_pB + a_pC = 0. $$
Solving
Printing the modulus $N$ in hexadecimal we confirm our hypothesis:
>>> hex(n)
'0xbf0a8dd7d8f16cad000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001002c0b6fc6c3c2949b0a1e097f3c51eff2e89198000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000526e422445cbd24c429d60a4a3d75cfd20d09708a2945d9ad2d3b65a55f110eb'
And we can easily recover $A,B,C$. Then we can trivially recover $a_p$ and $a_q$ from $A$ factors, and solve the quadratic equation just below to recover $U_p$ and then $U_q$. Finally recover
$$\begin{aligned} p &= a_p 2^{1024} + Up \ q &= a_q 2^{1024} + Uq \end{aligned}$$
and from the factorization of $N$ recover the private key to decrypt the flag. Here is my solving script:
from gmpy2 import iroot
from Crypto.Util.number import isPrime,long_to_bytes,inverse
e = 65537
N = 444874973852804286630293120525019547982392964519934608680681255396764239795499482860997657663742247333836933457910503642061679607999128792657151145831533603267962151902191791568052924623477918783346790554917615006885807262798511378178431356140169891510484103567017335784087168191133679976921108092647227149255338118895695993606854195408940572577899625236666854544581041490770396755583819878794842828965377818593455075306655077757834318066860484956428681524881285058664687568640627516452658874124048546780999256640377399347893644988620246748059490751348919880389771785423781356133657866769589669296191804649195706447605778549172906037483
c = 95237912740655706597869523108017194269174342313145809624317482236690453533195825723998662803480781411928531102859302761153780930600026069381338457909962825300269319811329312349030179047249481841770850760719178786027583177746485281874469568361239865139247368477628439074063199551773499058148848583822114902905937101832069433266700866684389484684637264625534353716652481372979896491011990121581654120224008271898183948045975282945190669287662303053695007661315593832681112603350797162485915921143973984584370685793424167878687293688079969123983391456553965822470300435648090790538426859154898556069348437896975230111242040448169800372469
A = N >> 2048
B = (N >> 1024) % (2 ** 161)
C = N % (2 ** 256)
## A = 5 * 2203 * 1665479 * 750383357
a_p = 5 * 750383357
a_q = A//a_p
##a_qX^2 - BX + a_pC = 0
discr = B ** 2 - 4*a_q*a_p*C
U_p = (B + iroot(discr,2)[0])//(2 * a_q)
U_q = C//U_p
p = a_p * 2**1024 + U_p
q = a_q * 2**1024 + U_q
assert(p*q == N)
phi = N - p - q + 1
d = inverse(e,phi)
flag = long_to_bytes(pow(c,d,N))
print(flag)
$in