一直在抄脚本，终于想着来看看原理了。
dp是什么？
dp = d mod (p-1)
基本前备知识
e*d = 1 mod ϕ(n)
那么开推吧
dp = d mod (p-1)
–> dp * e = e*d mod (p-1)
–> e*d = dp * e mod (p-1)
–> e*d = dp *e + k1*(p-1)
–> dp * e + k1*(p-1) = 1 mod ϕ(n)
–> dp * e + k1*(p-1) = 1 + k2*ϕ(n)
–> dp * e + k1*(p-1) = 1 + k2*(p-1)*(q-1)
–> dp * e = 1 + (k2*(q-1) – k1) * (p-1)
由于
dp < (p-1)
所以
0 < (k2*(q-1) – k1) < e
对(p-1)进行爆破即可
脚本
for i in range(1,e):
if (dp*e-1)%i==0:
if n%(((dp*e-1)//i)+1)==0:
p=(dp*e-1)//i+1
q=n//p
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c,d,n)
例题
[FSCTF 2023]RSA 3
附件：
from Crypto.Util.number import bytes_to_long
m=bytes_to_long(flag)
n= 12308543373374311860115195114269947739026255098864232126071500623399852788903738569949462616714391748269539072128882946132686996592089735285396762634029371785959865779256901123369306119124563405765293657606975290441243965513640680841871955014230301486214824204887945375140818283280272607903500556306646445508386218951500563603482945071727344737690804338144982687000734071274618240408238519378280819162796749148066754028700125846348589164721591354555019608871411236973606149388257533629388508942271702742078883636357856776193846813894734271905070538713351614750057245897158615891962167410053552739441195871000310777649
e= 65537
dp= 28196759050232165736649945458463681080421101473761579424309687746007021074159564720195299959516638110870101025657932732247788828322476803386736345945717104030991724584628153257976163663460034720811420324255626233108130037584679035250792445830510130682783638394418531763109219293027733347554816808577799709553
c= 1855798257044238280327042455832785889763141234883180404158555071443088630113034033050409259513632343742665544043437830959750873431928980910236398026670945184328950692568113819821699696418438157336263799808404698795433243968536256780396910914692949484556950491722527661706255009863481905590371725089587377065000354109396062360440021447607401687082247775453369117424848927386857425051097931983703966253652921113920387008048024308793686643944404541941182997963873579988680965558581885273185721576668001462817150245955628293258512024323515581063235248627223179117549540541642185815489978089367061102920114395871329023208
思路：
dp泄露，脚本解即可
exp：
from Crypto.Util.number import *
n= 12308543373374311860115195114269947739026255098864232126071500623399852788903738569949462616714391748269539072128882946132686996592089735285396762634029371785959865779256901123369306119124563405765293657606975290441243965513640680841871955014230301486214824204887945375140818283280272607903500556306646445508386218951500563603482945071727344737690804338144982687000734071274618240408238519378280819162796749148066754028700125846348589164721591354555019608871411236973606149388257533629388508942271702742078883636357856776193846813894734271905070538713351614750057245897158615891962167410053552739441195871000310777649
e= 65537
dp= 28196759050232165736649945458463681080421101473761579424309687746007021074159564720195299959516638110870101025657932732247788828322476803386736345945717104030991724584628153257976163663460034720811420324255626233108130037584679035250792445830510130682783638394418531763109219293027733347554816808577799709553
c= 1855798257044238280327042455832785889763141234883180404158555071443088630113034033050409259513632343742665544043437830959750873431928980910236398026670945184328950692568113819821699696418438157336263799808404698795433243968536256780396910914692949484556950491722527661706255009863481905590371725089587377065000354109396062360440021447607401687082247775453369117424848927386857425051097931983703966253652921113920387008048024308793686643944404541941182997963873579988680965558581885273185721576668001462817150245955628293258512024323515581063235248627223179117549540541642185815489978089367061102920114395871329023208
for i in range(1,e):
if (dp*e-1)%i==0:
if n%(((dp*e-1)//i)+1)==0:
p=(dp*e-1)//i+1
q=n//p
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))
