思路
已知e,P,Euler(Q),c,n.求m.
P = p**3
分解P,得到p
Q = q**2
根据欧拉函数性质,可知
Euler(Q) = q*(q-1)
分解phi_Q得到一个大因数,这个数比剩下的因数乘积大很多,所以可以推断这个大因数应该不是q,但是是q的倍数。
n = p*q*r
q*r = n/p
可知q*r的值,对phi_Q求公约数,可以得到q,进而得到r.
计算得到phi_n,对e取模反元素得到d.
至此,私钥对(n,d)已经取得,对消息解密,得到原文。
Exp如下:
from Crypto.Util.number import *
import gmpy2
from hashlib import md5
e = 65537
n = 1069981867450019752454430625015273180922733107799929958042241890002915414684562764186875387471850290817321430141222917656674447229697676236077201897275059270515637506529666384968535578683380559782336910645306992981172862940944536463561840412558764760962107958365575095435157363812028759723055357681895134974760386884254380189603418912937553755099672511307377054933171384741715642510754214768859689909974996095149155241791151425031489280537907842378844226410097051
P = 1686761823519516525084824311416810253107853832929411677237594989001281261421956188747941222367576127569696216513071075733130132251383529469095077597202999362675041210639065389821237728348981344440193122126487447235175127680730304754656661704596111547454161716607787386914764780833658069534913186485846587027674567133467341836048413431174183101579802349498153899249182793495245916757355079598668221097821452488627067390724198617676379698358212167618567704428433303
p = 11903771663059518341912645066042582267678745214691121272332269847512624178064427789028954264701292914161793272471217879550653909080475237446747964043276487
# p**3==P
# phi_Q = q*(q-1)
phi_Q = 54800501457630149544580145188029519076092032026436445384163914536965196942938808746487258773679836358732387355329080483568564046906919385574994390974732491368590525875801103056613954297623835159311237599961507385582029709732950222118171961946571285930711702624160354541459438994349318149872111029043942485620
r_q = n//p # q*r
q = gmpy2.gcd(r_q, phi_Q)
r = r_q//q
phi_n = (p-1)*(q-1)*(r-1)
c = 568846080701555049788706647255668980211679838950729382006912035332305772256748203239331545262283165739670330060735508231578298253855583985677482008855909565463834639005910652510802915373310537390293061001384655286359323437737989289787972131460392977341024828530868508329336263146882773903176326250063921456707975853839017504122823304303509269793133132036479219404842827556015566627129747816769486873563843578029479179692030808518925753268233301452280242586076493
d = gmpy2.invert(e, phi_n)
m = pow(c, d, n)
flag = long_to_bytes(m)
print(flag)
flag =flag[5:-1]
m = md5()
m.update(flag)
digest = m.hexdigest()
print("flag{"+digest+"}")