1、n与p的关系

题目

('n=', 288990088827100766680640490138486855101396196362885475612662192799072729620922966280891529295418086760877864145641240773774844610436051331306946338447987578274717185638059894743079958222428285199328796227699729755905906693841390517397968838979989187937765197009779831853782677148778833145391472483838410348187851940691573340443869780062542939942374320161963733291697585221383236756651125859306190611469903757185440175993363742018028809952801247846742033092984755533015067691332105526414972647382492862838910121236931498154729282070633749340622741556189535964547876244515672975306477660510791252904365137930260201368678082714836609782629541945700299956150734915268018652247423889358580950207466855040229003192308083531802714903385087417356434589306892888679309614923529675726467403933384636928018988851880153857796741120106443942767510880882869047315219885712389114991426210349790111241522116230105084964008967100552072784232695481018329040160132729906613461492188324496134449714224077399892244195702892564301367979224008861187860872226748641058472580561639257018145326272111688770894219937657825160193141745581367365405561724485260621462608988652159867916009465022291576279442397617091954522421449924662838224659158273250901130749121L)
('e=', 65537)
('c=', 137779053430049038434216593290618874948270200405399256269581378223281016900970652718848813337302671790604519081916876544192809184345327660912429768032693176503712428533118856746085101104530004384957878944306712448749988496680310178630490784192543750138162129344588248045230306419533817167822335810463544443187846127211253432794996440212197855199829148459690714008745033082890861457636322467364543567930633647015286211438515604345302463094804730828792938997761910285052058358568926162211399619255066215361304899897417756093402335995371832711502872437222512001157985528518717742208913450911897520543227613018962674806657657794649288850627452188012334771673285026593343941925348598797901401883986370253828688950287301471120024830787649255742214626285600948267746659887690844720659848203176190617138006403190722263638569661414450881185857994056115115153097909046365223008051874366779117102760347630728800614449748348771220711988694991053148346720284163230564679943853428714970819836241190140660788978119501945023060842021831844356818641202498764351298545672779480524641463732128037763042975104375933047678750844329826766152652487655163730244337514529371558702619207820731799113790535682515957476301736026894861608980444780607729321721653L)

我的解答

只给这点信息因此n必可分解。n和c都是长整型数据，直接转十进制超出范围，因此尝试把末尾L删去分解n可得某个数的四次方，看作p

有了p就正常思路解就行。

已知n = p * q 以及 n = p ** 4  => q = p ** 3

=> phi = (p - 1) * (p ** 3 - 1)

但尝试发现用此phi解不出来最终flag。

phi展开后省略了一些小数据尝试几遍发现使用 phi = p ** 4 - p ** 3 （即p ** 3(p - 1)）可行

（这里不知道是为什么？可能是因为p**3-1太大了完全可以忽略掉-1？）

最终exp:

from Crypto.Util.number import *
import gmpy2
from gmpy2 import iroot
c = 137779053430049038434216593290618874948270200405399256269581378223281016900970652718848813337302671790604519081916876544192809184345327660912429768032693176503712428533118856746085101104530004384957878944306712448749988496680310178630490784192543750138162129344588248045230306419533817167822335810463544443187846127211253432794996440212197855199829148459690714008745033082890861457636322467364543567930633647015286211438515604345302463094804730828792938997761910285052058358568926162211399619255066215361304899897417756093402335995371832711502872437222512001157985528518717742208913450911897520543227613018962674806657657794649288850627452188012334771673285026593343941925348598797901401883986370253828688950287301471120024830787649255742214626285600948267746659887690844720659848203176190617138006403190722263638569661414450881185857994056115115153097909046365223008051874366779117102760347630728800614449748348771220711988694991053148346720284163230564679943853428714970819836241190140660788978119501945023060842021831844356818641202498764351298545672779480524641463732128037763042975104375933047678750844329826766152652487655163730244337514529371558702619207820731799113790535682515957476301736026894861608980444780607729321721653
n = 288990088827100766680640490138486855101396196362885475612662192799072729620922966280891529295418086760877864145641240773774844610436051331306946338447987578274717185638059894743079958222428285199328796227699729755905906693841390517397968838979989187937765197009779831853782677148778833145391472483838410348187851940691573340443869780062542939942374320161963733291697585221383236756651125859306190611469903757185440175993363742018028809952801247846742033092984755533015067691332105526414972647382492862838910121236931498154729282070633749340622741556189535964547876244515672975306477660510791252904365137930260201368678082714836609782629541945700299956150734915268018652247423889358580950207466855040229003192308083531802714903385087417356434589306892888679309614923529675726467403933384636928018988851880153857796741120106443942767510880882869047315219885712389114991426210349790111241522116230105084964008967100552072784232695481018329040160132729906613461492188324496134449714224077399892244195702892564301367979224008861187860872226748641058472580561639257018145326272111688770894219937657825160193141745581367365405561724485260621462608988652159867916009465022291576279442397617091954522421449924662838224659158273250901130749121
e = 65537
p = iroot(n,4)[0]
phi = p**4 - p**3
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))
#flag{5a9d88e1-e588-11ed-a829-907841e2ffbc}