Challenge

from Crypto.Util.number import getPrime, bytes_to_long
from sympy import nextprime

flag, p, q, e = bytes_to_long(b""), getPrime(512), getPrime(512), 65537
p = nextprime(p * (2 ** 840))
N = p * q

phi = (q - 1) * (p - 1)
enc = pow(flag, e, N)

# e = 65537

# N = 511061712869767254923417507708423566803587315951215744449715075615600701047527924141476176383285842212764671714878553227904486876838449407090326662539121771195590789506492786725908969361846038999891448563132484756305963560020748224396889868246112626585991730693152916596916258781645175611422063584010852787918679803261851512170183777523636296830312045781078778334599688408884607340571781540596691301386077465581205326172070513668547044144082731824293675892955243136842882119833580668130487007241250369099906401716899567532432029182305803683674638323872526000339

# enc = 442516549992046590742354265430567787742076116371462359871598249156593979722239545390613965802267944443785286367153629953707131062130367303713855475944891719951679062496424522913904939663851195810804513924326023862775908778542384730368742069138909181385364394754722929066775095351588491586955107005659286304863011557079782809742343736760308855362337751476097669678111854856839187880902291870067305610897318135069459082558886485431757600836358977744846029167379481777168618976412708460632888974886614707087388015310711863092199326193977360729885331325121772220993

Solve

Vulnerability: Partial knowledge of $p$

Since $p$ is generated as $\text{next_prime}(\text{p} \cdot 2^{840})$, it’s very close to $p \cdot 2^{840}$.
This means $p$ can be written as:

\[p = a \times 2^{840} + x\]

Since $x$ is small, the polynomial $f(a) = \text{a} \cdot 2^{840} + x$ has a small root modulo $N$, which allows us to apply Coppersmith’s Attack to efficiently recover $p$.

from Crypto.Util.number import *

N = 511061712869767254923417507708423566803587315951215744449715075615600701047527924141476176383285842212764671714878553227904486876838449407090326662539121771195590789506492786725908969361846038999891448563132484756305963560020748224396889868246112626585991730693152916596916258781645175611422063584010852787918679803261851512170183777523636296830312045781078778334599688408884607340571781540596691301386077465581205326172070513668547044144082731824293675892955243136842882119833580668130487007241250369099906401716899567532432029182305803683674638323872526000339

PR.<a> = PolynomialRing(Zmod(N))
for x in range(200):
    f = (a*(2**840)+x)
    roots = f.monic().small_roots(X=2**512, beta=0.4)
    if roots == []:
        continue
    pp = roots[0]
    if pp == 0:
        continue
    p = int(f(a=pp))


    c = 442516549992046590742354265430567787742076116371462359871598249156593979722239545390613965802267944443785286367153629953707131062130367303713855475944891719951679062496424522913904939663851195810804513924326023862775908778542384730368742069138909181385364394754722929066775095351588491586955107005659286304863011557079782809742343736760308855362337751476097669678111854856839187880902291870067305610897318135069459082558886485431757600836358977744846029167379481777168618976412708460632888974886614707087388015310711863092199326193977360729885331325121772220993
    
    q = N//p
    d = pow(65537, -1, (p-1)*(q-1))
    print(long_to_bytes(int(pow(c, d, N))))

    if is_prime(p):
        break


#ctfjo{9d1ff022330f0aaaec1bc28c3523f620}

Reference