附件：
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
p1 = getPrime(512)
q1 = getPrime(512)
p2 = p1 + 1
q2 = q1 + 1
while not isPrime(p2):
p2 += 1
while not isPrime(q2):
q2 += 1
n = p1 * q1 * p2 * q2
e = 0x10001
flag = b"flag{********************}"
cipher = pow(bytes_to_long(flag), e, n)
print(n, cipher)
"""
16043540260711155677255538751089366052043709595227783852052656066597002774407800122418007523362396728183266465761392565042428599355725500826143539420140456329895849730908022450275066086440965293522897107194146134290754743462502643795143263235203956531033501481970113556323667497120218175024737224022249204376993498195979835136345239487464596152504444779379295276044877361199024987337843924242871234441022266042777175260303907206315473401337359800612700541755058981449179303221570098930479897624992090983015909248329973983829662506812701491729279714342396205919529925242196142897730112916106987201487845243489306705801 2066115663525746527006627359468128590893825280358396250104208720689490275374897638123457041234796490924868928927502724180110038497520643860784458150587807106541897109745721030614711936742403635641095902699269742164975578028469069698973292309477453808933330564169489658364371933906178410011496479652100451402540714190682735935110606874460167002975309353684815782160263967640258741617713920964735873147902859161068038608313491537620215756103436033073775233266496545167522336487886276048486169352197432827513155409694413942465378979586580718575345608052451570799077424423767881137206427719277073748039170388976335980108
"""
题目生成了两个素数 p1 和 q1，分别求出它们的下一个素数 p2 和 q2，给定 p1 * p2 * q1 * q2，求分解。
@Sceleri 给出了思路：
n开根后跟(p1*q2+p2*q1)/2很近，然后解方程得出p2*q1的近似值，然后coppersmith得到p2*q1的准确值，后面随便枚举一下p2-p1
实测下来，根号 n 与 (p1 * q2 + p2 * q1) / 2 确实很接近，所以可以枚举。枚举时，就可以求出 p1 * q2 和 p2 * q1，再根据 p1 和 p2 很接近，q1 和 q2 很接近的性质，枚举它们之间的差值，最终可以找到正确的分解。
攻击代码：
from Crypto.Util.number import *
import math
from pwn import *
import tqdm
if args.TEST:
p1 = getPrime(512)
q1 = getPrime(512)
p2 = p1 + 1
q2 = q1 + 1
while not isPrime(p2):
p2 += 1
while not isPrime(q2):
q2 += 1
n = p1 * q1 * p2 * q2
print("avg - sqrt", (p1 * q2 + p2 * q1) // 2 - math.isqrt(n))
print("p2 - p1", p2 - p1)
print("q2 - q1", q2 - q1)
e = 0x10001
flag = b"flag{fake_flag_for_testing}"
cipher = pow(bytes_to_long(flag), e, n)
else:
e = 0x10001
n = 16043540260711155677255538751089366052043709595227783852052656066597002774407800122418007523362396728183266465761392565042428599355725500826143539420140456329895849730908022450275066086440965293522897107194146134290754743462502643795143263235203956531033501481970113556323667497120218175024737224022249204376993498195979835136345239487464596152504444779379295276044877361199024987337843924242871234441022266042777175260303907206315473401337359800612700541755058981449179303221570098930479897624992090983015909248329973983829662506812701491729279714342396205919529925242196142897730112916106987201487845243489306705801
cipher = 2066115663525746527006627359468128590893825280358396250104208720689490275374897638123457041234796490924868928927502724180110038497520643860784458150587807106541897109745721030614711936742403635641095902699269742164975578028469069698973292309477453808933330564169489658364371933906178410011496479652100451402540714190682735935110606874460167002975309353684815782160263967640258741617713920964735873147902859161068038608313491537620215756103436033073775233266496545167522336487886276048486169352197432827513155409694413942465378979586580718575345608052451570799077424423767881137206427719277073748039170388976335980108
# observation: math.isqrt(n) is very close to (p1 * q2 + p2 * q1) // 2
for diff in tqdm.trange(1000000):
# guess (p1 * q2 + p2 * q1) // 2
avg = math.isqrt(n) + diff
sum = avg * 2
# given:
# p1 * q2 + p2 * q1 = sum
# p1 * q2 * p2 * q1 = n
# solve p1 * q2:
# x^2 - sum * x + n = 0
delta = sum**2 - 4 * n
if delta < 0:
continue
# got p1 * q2, p2 * q1
x1 = (sum + math.isqrt(delta)) // 2
x2 = (sum - math.isqrt(delta)) // 2
if x1 * x2 != n or x1 + x2 != sum:
continue
print("Found possible x1, x2")
# p2 - p1, q2 - q1 are both small
# p2 = p1 + i
# q2 = q1 + j
# enumerate i+j
for sum in tqdm.trange(0, 100000, 2):
for j in range(2, sum, 2):
i = sum - j
# p1 * (q1 + j) = x1
# q1 * (p1 + i) = x2
# p1 * j - q1 * i = x1 - x2
# p1 * j = x1 - x2 + q1 * i
# (x1 - x2 + q1 * i) * (q1 + j) = x1 * j
# i * q1 ** 2 + (x1 - x2 + i * j) * q1 + (x1 - x2) * j - x1 * j = 0
delta = (x1 - x2 + i * j) ** 2 - 4 * i * ((x1 - x2) * j - x1 * j)
if delta < 0:
continue
q1_recover = (-(x1 - x2 + i * j) + math.isqrt(delta)) // (2 * i)
if q1_recover <= 0:
continue
q2_recover = q1_recover + j
p1_recover = x1 // q2_recover
p2_recover = p1_recover + i
if p1_recover * p2_recover * q1_recover * q2_recover == n:
print("Success")
print("p1", p1_recover)
print("p2", p2_recover)
print("q1", q1_recover)
print("q2", q2_recover)
d = pow(
e,
-1,
(p1_recover - 1)
* (p2_recover - 1)
* (q1_recover - 1)
* (q2_recover - 1),
)
flag = long_to_bytes(pow(cipher, d, n))
print(flag)
exit(0)
输出：
22%|█████████████████████████ | 224132/1000000 [00:01<00:04, 171879.47it/s]Found possible x1, x2
22%|█████████████████████████ | 224132/1000000 [00:20<00:04, 171879.47it/sSuccess████████████████████████████████████████████████▋ | 20864/50000 [12:40<35:34, 13.65it/s]
p1 11625804744635154350371950732800383322411952133939525583724573459942114636120987807547656193712145536570486366194633820156730838351920778775000255332893323
p2 11625804744635154350371950732800383322411952133939525583724573459942114636120987807547656193712145536570486366194633820156730838351920778775000255332914187
q1 10894996110141523785973254710653587130206370977430192463414696444537186690532925612365891389623700928168375231738096236398363290305482179680063492895631913
q2 10894996110141523785973254710653587130206370977430192463414696444537186690532925612365891389623700928168375231738096236398363290305482179680063492895652777
b'flag{c7b9f4e1-8b42-4df0-9a9d-1d2b3e4c9f76}'
42%|█████████████████████████████████████████████████▋ | 20864/50000 [12:40<17:42, 27.43it/s]
23%|██████████████████████████▍ | 229437/1000000 [12:42<42:39, 301.09it/s]