Challenge

from Crypto.Util.number import *
p = getPrime(512)
q = getPrime(512)
Z = p + q
e = 65537
n = p*q
phi = (p - 1) * (q - 1)
d = pow(e,-1,phi)
flag = b'AliensCTF{XXXXXXXXXXXXXXX}'
flag = bytes_to_long(flag)
ct = pow(flag,e,n)
print("Z = " , Z)
print("ct = " , ct)
print("e = " , e)
print("d = " . d)
'''
Z =  16820737097353712199008885189308993240062786445532266527638053380922378774616476382163247194937072305014746509504145047878443638872497494118908269570032268
c =  479071499146375975938322489301482293703390637168677812333128679564097095268226244517563983793769084733694521865492794622837160726397932788602732027510921529236034519758543370535127503081504645209677730499880169790853613312632519658763093707467213480497322022033842076428439183228571516341469788182850999977
e =  65537
d =30457311326725662835214016666844881462445051263981028375137823295574368019980007635319500981574067252775053081714539957668696316970001308548888552486734579219472425821075186464709552910556541803654932577396437902891944339629571939336444030765475727284297080520163293154113609913839011602974796247723401571353
'''

Solve

we have $Z = p + q$ from this hint we can calculate $\phi$ in this way

\(\phi = (p-1) \times (q-1) = pq - p - q + 1 = n - z + 1\)

and we know that:

\(ed - 1 = K \times \phi \quad \Rightarrow \quad ed - 1 = K (n - z + 1)\)

Now rearrange the equation for $N$ and brute force $k$

\[N = \frac{ed - 1}{K} + Z - 1\] 


from Crypto.Util.number import *
from tqdm import *

e = 65537
Z =  16820737097353712199008885189308993240062786445532266527638053380922378774616476382163247194937072305014746509504145047878443638872497494118908269570032268
ct =  479071499146375975938322489301482293703390637168677812333128679564097095268226244517563983793769084733694521865492794622837160726397932788602732027510921529236034519758543370535127503081504645209677730499880169790853613312632519658763093707467213480497322022033842076428439183228571516341469788182850999977
e =  65537
d = 30457311326725662835214016666844881462445051263981028375137823295574368019980007635319500981574067252775053081714539957668696316970001308548888552486734579219472425821075186464709552910556541803654932577396437902891944339629571939336444030765475727284297080520163293154113609913839011602974796247723401571353

for k in trange(28_000, e):
    n = ((e*d-1)//k) + Z - 1
    flag = long_to_bytes(pow(ct, d, n))
    if b"Alien" in flag:
        print(flag)
        break

#AliensCTF{partialKeyIsNiceIdia}