题目如下
点击查看代码
from Crypto.Util.number import *
import sympy
from secrets import flag
def get_happy_prime():
p = getPrime(512)
q = sympy.nextprime(p ^ ((1 << 512) - 1))
return p, q
m = bytes_to_long(flag)
p, q = get_happy_prime()
n = p * q
e = 65537
print(n)
print(pow(m, e, n))
# 24852206647750545040640868093921252282805229864862413863025873203291042799096787789288461426555716785288286492530194901130042940279109598071958012303179823645151637759103558737126271435636657767272703908384802528366090871653024192321398785017073393201385586868836278447340624427705360349350604325533927890879
# 14767985399473111932544176852718061186100743117407141435994374261886396781040934632110608219482140465671269958180849886097491653105939368395716596413352563005027867546585191103214650790884720729601171517615620202183534021987618146862260558624458833387692782722514796407503120297235224234298891794056695442287
题目给了n，c，e的值，要得到flag就得先解m的值。又因为m = pow(c, d, n), 且给了e值，所以利用p，q的生成规则求phi_n的值成为了问题的关键！
观察p， q生成的规则，发现p是随机取的512位的素数；
sympy.nextprime() 函数接受一个整数作为参数，并返回大于该整数的下一个素数；
1 << 512 是一个位运算，表示将1左移512位，即得到一个只有第513位为1的数，其他位都为0的数；
（1 << 512） - 1 是将上述结果减去1，得到一个二进制表示全为1的512位数；
所以q的结果就是p与512位的1进行异或的结果，再进行nextprime。
因为phi_n = n - (p + q) + 1 ,且n位数与全1按位异或等于取反，原码 + 反码 = 2 ** n - 1
我们先不计q在nextprime函数后的差值，所以p + q = 2 ** 512 - 1
又因为素数性质（除2之外都是奇数），因此，p + q = 2 ** 512 - 1 + t
所以，爆破！这里的t从1开始，每次爆完t + 2，满足奇数条件，直到有符合的怕p + q的值便可得到flag
代码呈上
点击查看代码
import gmpy2
from Crypto.Util.number import *
n = 24852206647750545040640868093921252282805229864862413863025873203291042799096787789288461426555716785288286492530194901130042940279109598071958012303179823645151637759103558737126271435636657767272703908384802528366090871653024192321398785017073393201385586868836278447340624427705360349350604325533927890879
c = 14767985399473111932544176852718061186100743117407141435994374261886396781040934632110608219482140465671269958180849886097491653105939368395716596413352563005027867546585191103214650790884720729601171517615620202183534021987618146862260558624458833387692782722514796407503120297235224234298891794056695442287
e = 65537
t = 1
# 因为q是p的取反后取比其值大的最近的一个素数，所以p + q = 2**512 - 1 + t
for i in range(400):
phi = n - (2**512 - 1 + t) + 1
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
t += 2