RSA e与phi不互质（AMM算法进行有限域开根）

e与phi不互质

这一部分学习来自trup师傅的博客

针对CTFer的e与phi不互素的问题 - 跳跳糖

1：m^t<n

from Crypto.Util.number import *
from secret import flag
flag = b'flag{*********}'
m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 114
c = pow(m,e,n)
print(c)
print(p >> 200)
print(n)# 4981370648841772812759645290740849305394680703208798679296466901875830602835273402860232301263281323578956193947979697234640828088984992529165349436050379602381023059635247562226192384089521639938396211636613132291696135696985578958227320544060232615333466684704244997055833821133086665356126147182204658744167431612986909752009485714137028204041440181653812250548914729617593568901044728464293232061709058144788756823288190386071071979728390993033661221130338943191220680445314588574185565138844949934691183548291792150029676489045342419826189506616272247940278820931530398810621850374268800818970515221497093852109
# 62037304914409314363888940906845820031382619388386590204815535497699521033644001814874589864676342418539729790446530529473631795496696578029445470682035483391568820927435567100377626022924900710513454770616746573110984342344183967600234091673261776
# 10315159385090642346129000730749042701431892949303034712476198921384639021767097119992198421632142955005047146294210952031882321038272269972695714084199530336742619691272883151455898061330316812891004827724782855036289498818157782936179413509824274682055131552093071749522986951202502017564120645520386407170556413591537187759567563157956331577316042296031033014710853038209000676314440817362756989634719336973373719581572614119144998829076893422175956726616346716072744575347893245428145235967836165207095908913238287634122873060994828380614739915448587956681845973466847711337763120292734433687845920176310499582951

显然第一部分是一个copper，先解一下p

from Crypto.Util.number import *
from libnum import *
e=114
c=4981370648841772812759645290740849305394680703208798679296466901875830602835273402860232301263281323578956193947979697234640828088984992529165349436050379602381023059635247562226192384089521639938396211636613132291696135696985578958227320544060232615333466684704244997055833821133086665356126147182204658744167431612986909752009485714137028204041440181653812250548914729617593568901044728464293232061709058144788756823288190386071071979728390993033661221130338943191220680445314588574185565138844949934691183548291792150029676489045342419826189506616272247940278820931530398810621850374268800818970515221497093852109
pl=62037304914409314363888940906845820031382619388386590204815535497699521033644001814874589864676342418539729790446530529473631795496696578029445470682035483391568820927435567100377626022924900710513454770616746573110984342344183967600234091673261776
n=10315159385090642346129000730749042701431892949303034712476198921384639021767097119992198421632142955005047146294210952031882321038272269972695714084199530336742619691272883151455898061330316812891004827724782855036289498818157782936179413509824274682055131552093071749522986951202502017564120645520386407170556413591537187759567563157956331577316042296031033014710853038209000676314440817362756989634719336973373719581572614119144998829076893422175956726616346716072744575347893245428145235967836165207095908913238287634122873060994828380614739915448587956681845973466847711337763120292734433687845920176310499582951
bit=200
PR.<x> = PolynomialRing(Zmod(n))
f=pl*2^200+x
f=f.monic()
root=f.small_roots(2**bit,beta=0.4)
if root:p=int(root[0])+pl*2^200print(p)p=99690105430259549732952386298363416480730988331578091065948950836198178325904426675017504756348563688521763268566954512895974110780822714951824351709232320913381679046309934991336770483285399157355308073567950907088479972767984569322594411195698421500521401221792581871025328456951904596576566123729811756413

第二部分根据e‘接着求解即可

p=99690105430259549732952386298363416480730988331578091065948950836198178325904426675017504756348563688521763268566954512895974110780822714951824351709232320913381679046309934991336770483285399157355308073567950907088479972767984569322594411195698421500521401221792581871025328456951904596576566123729811756413
q=n//p
phi=(p-1)*(q-1)
t=gcd(e,phi)
ee=e//t
d=invmod(ee,phi)
mt=int(pow(c,d,n))
flag=iroot(mt,t)[0]
print(long_to_bytes(flag))

2：m^t>n，但e比较小，结合CRT求解

from Crypto.Util.number import bytes_to_long
from secrets import p,q,r,s,t,flagn = p * q * r * s * t
e = 2
m = bytes_to_long(os.urandom(500) + flag)
c = pow(m,e,n)print(p,q,r,s,t,sep='\n')
print(c)'''
145332367700944303747548912160113939198078051436029477960348968315913956664143693347226702600438608693933768134575289286283267810723137895903153829001826223446477799895493265422562348917012216790077395795861238257357035152687833639085415763850743538206986781418939737511715957738982536382066693822159860701263
116660458253067608044065523310547233337730583902133756095473339390057738510707447906971188577217274861047379404014140178165569604404468897712846876108444468370709141219302291601408652742006268186059762087155933131837323952675627966299810891805398890428420575425160696531236660480933905879208166090591482794763
157931722402853245421436270609912823260313730941283152856444641969403238646482562190531038393124087232554754746464603598717356255570166081501573727336977292059427220330169044611674973569766966838498453232642731737958791706086957762244686953294662693939604300864961637325536379321027705854708492453330690705531
100973451687449518854742673778783266158999451072058606348222018797891147675959983616210003484476577612134482311993701677242007759556951494382833070563369964294544839433671087037596159753825249018950693369209927951667775267086896180395776150188902057785214767230658487267587289809918132337927575673868568976679
93960345071948255233882121683650797512129333868351496468898834736770441398743300745703393838320587998953678254272245400344928586394089488734271897540051673996675973642347859306921527430850673334243441180183460927865980713929789963587608547554858491264614271309608925634272282292964002897650355047792764365447
9144597920381774885442906257311149465702295057238600973973598305004391534618770363098565074541384771979931799878381439264848137810353858418200992191234142740194489573540381681161219332611454834544291634628456257670178843484698324641739324687497388018406214041657278323855749902661752448796122517061920880552011343608609622885787617238758769398972009949575526258430282648817039091284796330585349957724522615105102735930258969562103112238020133587096826386028128471852377225525357348919204333121695432662339443004327748973224423132988376298843862056631045488285859621661802413201793962883794915513510467912312842687601478117040419013468059983777273699192408773551806581458197324620065210523913467414181480875280203580147077789063808832356486197271376615883221558265591069223727607585313240243619515521180600435114131162272519949101464089935441251751426683447701142156416866113627126765919641034042927519834229168536331952275698122511502745177547569813354280565828372968703810158857859460406828090199683324760956105682902577189283246483314689365570862217407333103243336691401424548702387876409228977278498691200028282744239512091373110111792177228979867318546462714521296256938374618636206565791541769138267080789842400796973226733816939794717596194090232425688504890234304977612220790858557639246367437740975495450011676714198668471438814299689325208882261918460708833888406187912527346628912894921059735420931656953236560178909180587372589456926690219114173193202048332172538564489660440225377822914097420807957784201785024166011709377791129
'''

稍微测一测，就会发现m是一个极大的数，且e与phi的公因数是2，而m^t>n

from Crypto.Util.number import *
import os
from random import  *p=145332367700944303747548912160113939198078051436029477960348968315913956664143693347226702600438608693933768134575289286283267810723137895903153829001826223446477799895493265422562348917012216790077395795861238257357035152687833639085415763850743538206986781418939737511715957738982536382066693822159860701263
q=116660458253067608044065523310547233337730583902133756095473339390057738510707447906971188577217274861047379404014140178165569604404468897712846876108444468370709141219302291601408652742006268186059762087155933131837323952675627966299810891805398890428420575425160696531236660480933905879208166090591482794763
r=157931722402853245421436270609912823260313730941283152856444641969403238646482562190531038393124087232554754746464603598717356255570166081501573727336977292059427220330169044611674973569766966838498453232642731737958791706086957762244686953294662693939604300864961637325536379321027705854708492453330690705531
s=100973451687449518854742673778783266158999451072058606348222018797891147675959983616210003484476577612134482311993701677242007759556951494382833070563369964294544839433671087037596159753825249018950693369209927951667775267086896180395776150188902057785214767230658487267587289809918132337927575673868568976679
t=93960345071948255233882121683650797512129333868351496468898834736770441398743300745703393838320587998953678254272245400344928586394089488734271897540051673996675973642347859306921527430850673334243441180183460927865980713929789963587608547554858491264614271309608925634272282292964002897650355047792764365447
c=9144597920381774885442906257311149465702295057238600973973598305004391534618770363098565074541384771979931799878381439264848137810353858418200992191234142740194489573540381681161219332611454834544291634628456257670178843484698324641739324687497388018406214041657278323855749902661752448796122517061920880552011343608609622885787617238758769398972009949575526258430282648817039091284796330585349957724522615105102735930258969562103112238020133587096826386028128471852377225525357348919204333121695432662339443004327748973224423132988376298843862056631045488285859621661802413201793962883794915513510467912312842687601478117040419013468059983777273699192408773551806581458197324620065210523913467414181480875280203580147077789063808832356486197271376615883221558265591069223727607585313240243619515521180600435114131162272519949101464089935441251751426683447701142156416866113627126765919641034042927519834229168536331952275698122511502745177547569813354280565828372968703810158857859460406828090199683324760956105682902577189283246483314689365570862217407333103243336691401424548702387876409228977278498691200028282744239512091373110111792177228979867318546462714521296256938374618636206565791541769138267080789842400796973226733816939794717596194090232425688504890234304977612220790858557639246367437740975495450011676714198668471438814299689325208882261918460708833888406187912527346628912894921059735420931656953236560178909180587372589456926690219114173193202048332172538564489660440225377822914097420807957784201785024166011709377791129
phi=(p-1)*(q-1)*(r-1)*(s-1)*(t-1)
m=bytes_to_long(os.urandom(500))
n=p*q*r*s*t
if m**2<n:print(1)
else:print(0)
print(gcd(2,phi))

即使用CRT找到一个m，而这样的m可以满足所有的res，那么它就极有可能是原本的m

这里也是因为变量命名不规范的问题，弄了一晚上的报错，最终还是顺利解决了

from Crypto.Util.number import *
from libnum import *
from gmpy2 import *
p=145332367700944303747548912160113939198078051436029477960348968315913956664143693347226702600438608693933768134575289286283267810723137895903153829001826223446477799895493265422562348917012216790077395795861238257357035152687833639085415763850743538206986781418939737511715957738982536382066693822159860701263
q=116660458253067608044065523310547233337730583902133756095473339390057738510707447906971188577217274861047379404014140178165569604404468897712846876108444468370709141219302291601408652742006268186059762087155933131837323952675627966299810891805398890428420575425160696531236660480933905879208166090591482794763
r=157931722402853245421436270609912823260313730941283152856444641969403238646482562190531038393124087232554754746464603598717356255570166081501573727336977292059427220330169044611674973569766966838498453232642731737958791706086957762244686953294662693939604300864961637325536379321027705854708492453330690705531
s=100973451687449518854742673778783266158999451072058606348222018797891147675959983616210003484476577612134482311993701677242007759556951494382833070563369964294544839433671087037596159753825249018950693369209927951667775267086896180395776150188902057785214767230658487267587289809918132337927575673868568976679
t=93960345071948255233882121683650797512129333868351496468898834736770441398743300745703393838320587998953678254272245400344928586394089488734271897540051673996675973642347859306921527430850673334243441180183460927865980713929789963587608547554858491264614271309608925634272282292964002897650355047792764365447
c=9144597920381774885442906257311149465702295057238600973973598305004391534618770363098565074541384771979931799878381439264848137810353858418200992191234142740194489573540381681161219332611454834544291634628456257670178843484698324641739324687497388018406214041657278323855749902661752448796122517061920880552011343608609622885787617238758769398972009949575526258430282648817039091284796330585349957724522615105102735930258969562103112238020133587096826386028128471852377225525357348919204333121695432662339443004327748973224423132988376298843862056631045488285859621661802413201793962883794915513510467912312842687601478117040419013468059983777273699192408773551806581458197324620065210523913467414181480875280203580147077789063808832356486197271376615883221558265591069223727607585313240243619515521180600435114131162272519949101464089935441251751426683447701142156416866113627126765919641034042927519834229168536331952275698122511502745177547569813354280565828372968703810158857859460406828090199683324760956105682902577189283246483314689365570862217407333103243336691401424548702387876409228977278498691200028282744239512091373110111792177228979867318546462714521296256938374618636206565791541769138267080789842400796973226733816939794717596194090232425688504890234304977612220790858557639246367437740975495450011676714198668471438814299689325208882261918460708833888406187912527346628912894921059735420931656953236560178909180587372589456926690219114173193202048332172538564489660440225377822914097420807957784201785024166011709377791129
R.<x>=Zmod(p)[]
f=x^2-c
f=f.monic()
res1=f.roots()
print(res1)R.<x>=Zmod(q)[]
f=x^2-c
f=f.monic()
res2=f.roots()
print(res2)R.<x>=Zmod(r)[]
f=x^2-c
f=f.monic()
res3=f.roots()
print(res3)R.<x>=Zmod(s)[]
f=x^2-c
f=f.monic()
res4=f.roots()
print(res4)R.<x>=Zmod(t)[]
f=x^2-c
f=f.monic()
res5=f.roots()
print(res5)

 不要问为什么写了两个脚本（处理报错处理到怀疑自己了）

from tqdm import trange
import time 
res1=[(105759306796604458734616988025041070894254086177961955152266241983599552436038417164589781800548170263137744573303899679801944648323570236444662118586389843689723523559621259451179955280920984411241370317372577352603546061045989233542252380860541664590826871711240796449926428967356180623320755399312333855914, 1), (39573060904339845012931924135072868303823965258067522808082726332314404228105276182636920799890438430796023561271389606481323162399567659458491710415436379756754276335872005971382393636091232378836025478488660904753489091641844405543163382990201873616159909707698941061789528771626355758745938422847526845349, 1)]
res2=[(61271467210118412966724984292095335317733695256090878426560686891756079924997989716821358995235922204013829340494037064720729099316872761029080019202081517084920407823716674786308109091176385109278967641331532338629650874309430534283470953619914746783509470375167910894276568010726761673444218996017135114156, 1), (55388991042949195077340539018451898019996888646042877668912652498301658585709458190149829581981352657033550063520103113444840505087596136683766856906362951285788733395585616815100543650829883076780794445824400793207673078366197432016339938185484143644911105049992785636960092470207144205763947094574347680607, 1)]
res3=[(81494645874260988911158916071880589359987692444861294147300186590570368369310500749798165469954243389790515045742691754565984336157619549494162814548778978629336604244757475768337171648672659348063737408489515868219005399374680983335675188997145621903581258458582232536740517461870029388465524596256244426733, 1), (76437076528592256510277354538032233900326038496421858709144455378832870277172061440732872923169843842764239700721911844151371919412546532007410912788198313430090616085411568843337801921094307490434715824153215869739786306712276778909011764297517072036023042406379404788795861859157676466242967857074446278798, 1)]
res4=[(51144823034893467516049830013634908954947282240108395637750270980709555996962447979999247978745025424678021661508447789536796050829892155378538642362300766072138752230839087308843963081621082317370683937461997061050952181636902197426079036843036405576746588315389276602207691439303029900209974821989735900029, 1), (49828628652556051338692843765148357204052168831950210710471747817181591678997535636210755505731552187456460650485253887705211708727059339004294428201069198222406087202831999728752196672204166701580009431747930890616823085449993982969697113345865652208468178915269210665379598370615102437717600851878833076650, 1)]
res5=[(56637279121653393183765926394036757622063751326302092068920147262287397466384343814073144226967254272339029262947175891947262297560109802237295059464880607159848782193114481656026708061277319588698540513237321988174311640122032153576262583677645331084360321934219426057528705181800937189748999636758570257615, 1), (37323065950294862050116195289614039890065582542049404399978687474483043932358956931630249611353333726614648991325069508397666288833979686496976838075171066836827191449233377650894819369573353745544900666946138939691669073807757810011345963877213160180253949375389499576743577111163065707901355411034194107832, 1)]
p=int(145332367700944303747548912160113939198078051436029477960348968315913956664143693347226702600438608693933768134575289286283267810723137895903153829001826223446477799895493265422562348917012216790077395795861238257357035152687833639085415763850743538206986781418939737511715957738982536382066693822159860701263)
q=int(116660458253067608044065523310547233337730583902133756095473339390057738510707447906971188577217274861047379404014140178165569604404468897712846876108444468370709141219302291601408652742006268186059762087155933131837323952675627966299810891805398890428420575425160696531236660480933905879208166090591482794763)
r=int(157931722402853245421436270609912823260313730941283152856444641969403238646482562190531038393124087232554754746464603598717356255570166081501573727336977292059427220330169044611674973569766966838498453232642731737958791706086957762244686953294662693939604300864961637325536379321027705854708492453330690705531)
s=int(100973451687449518854742673778783266158999451072058606348222018797891147675959983616210003484476577612134482311993701677242007759556951494382833070563369964294544839433671087037596159753825249018950693369209927951667775267086896180395776150188902057785214767230658487267587289809918132337927575673868568976679)
t=int(93960345071948255233882121683650797512129333868351496468898834736770441398743300745703393838320587998953678254272245400344928586394089488734271897540051673996675973642347859306921527430850673334243441180183460927865980713929789963587608547554858491264614271309608925634272282292964002897650355047792764365447)
def CRT(m,a,n):M = 1ans = 0for i in range(n):M *= m[i]for i in range(n):Mi = M // m[i]g,x,y=extend_gcd(Mi,m[i])x=x%m[i]#通过扩展欧几里得算法求Mi的逆元xans+=x*Mi*a[i]ans%=Mreturn ans;
#扩展欧几里得算法ax+by=gcd(a,b),该函数可求gcd(a,b),x,y
def extend_gcd(a,b):if b==0:return (a,1,0)else:g,x,y=extend_gcd(b,a%b)return (g,y,x-(a//b)*y)
for i in res1:for j in res2:for k in res3:for l in res4:for ss in res5:a=[int(i[0]),int(j[0]),int(k[0]),int(l[0]),int(ss[0])]m=[p,q,r,s,t]flag=long_to_bytes(CRT(m,a,5))if b'ctfshow' in flag:print(flag)

3：m^t>n，但e很大，采取AMM算法

AMM算法是在有限域上开根求解的算法，论文实现细节可以去看trup师傅的博客，写的更加详细，而我比较急于求成，没有关注原理，只搞懂了这个东西怎么用

以下是AMM的代码，它的作用是在模p的有限域上，给出o的开r次根

def AMM(o, r, q):start = time.time()print('\n----------------------------------------------------------------------------------')print('Start to run Adleman-Manders-Miller Root Extraction Method')print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))g = GF(q)o = g(o)p = g(random.randint(1, q))while p ^ ((q-1) // r) == 1:p = g(random.randint(1, q))print('[+] Find p:{}'.format(p))t = 0s = q - 1while s % r == 0:t += 1s = s // rprint('[+] Find s:{}, t:{}'.format(s, t))k = 1while (k * s + 1) % r != 0:k += 1alp = (k * s + 1) // rprint('[+] Find alp:{}'.format(alp))a = p ^ (r**(t-1) * s)b = o ^ (r*alp - 1)c = p ^ sh = 1for i in range(1, t):d = b ^ (r^(t-1-i))if d == 1:j = 0else:print('[+] Calculating DLP...')j = - discrete_log(d, a)print('[+] Finish DLP...')b = b * (c^r)^jh = h * c^jc = c^rresult = o^alp * hend = time.time()print("Finished in {} seconds.".format(end - start))print('Find one solution: {}'.format(result))return result

同样，sympy库也有这样的库函数，作用是一样的，给出模p下对a的开n次方

from sympy.ntheory.residue_ntheory import nthroot_mod
nthroot_mod(a,n,p)

接下来进入一道实战题练习

e = 12742153496769814072596
p = 65211247300401312530078141569304950676358489059623557848188896752173856845051471066071652073612337629832155846984721797768267868868902023383604553319793550396610085424563231688918357710337401138108050205457200940158475922063279384491022916790549837379548978141370347556053597178221402425212594060342213485311
c = 45326527081735095684632585216508484943819720696878842043540554720229674414296707918873385105075387912310299691748216658256439485784388880803922134863731374059731970174794936075890019917038396488161530769759774808480182049272235808430693365496648819656078275683885130420969875204155207145247880895891885126527
phi = p - 1
assert pow(m,e,p) == c

做一些简单的测试，发现gcd(e,phi)=7438, 问题的关键就在于e//7438后，与phi仍有公因数2（只有两个数都除以最大公因数才会一定互质）

所以接下来要做的就是一步步脱去外壳，但是开二次方还好说，拿正根就行，如果是开7438次方，AMM算法只能找到一个根，所以需要接下来这个函数来找到所有根

def findAllPRoot(p, e):print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p))start = time.time()proot = set()while len(proot) < e:proot.add(pow(random.randint(2, p-1), (p-1)//e, p))end = time.time()print("Finished in {} seconds.".format(end - start))return proot

 这个函数会返回一个m1列表，用AMM求出的m0*m1得到的即是所有根的组合情况。到此已经没有什么问题了，可以开始尝试写解密脚本了

import time,random
from sympy import discrete_log
from Crypto.Util.number import *
from libnum import *
from gmpy2 import *
def AMM(o, r, q):start = time.time()print('\n----------------------------------------------------------------------------------')print('Start to run Adleman-Manders-Miller Root Extraction Method')g = GF(q)o = g(o)p = g(random.randint(1, q))while p ^ ((q-1) // r) == 1:p = g(random.randint(1, q))print('[+] Find p:{}'.format(p))t = 0s = q - 1while s % r == 0:t += 1s = s // rprint('[+] Find s:{}, t:{}'.format(s, t))k = 1while (k * s + 1) % r != 0:k += 1alp = (k * s + 1) // rprint('[+] Find alp:{}'.format(alp))a = p ^ (r**(t-1) * s)b = o ^ (r*alp - 1)c = p ^ sh = 1for i in range(1, t):d = b ^ (r^(t-1-i))if d == 1:j = 0else:print('[+] Calculating DLP...')j = - discrete_log(d, a)print('[+] Finish DLP...')b = b * (c^r)^jh = h * c^jc = c^rresult = o^alp * hend = time.time()print("Finished in {} seconds.".format(end - start))print('Find one solution: {}'.format(result))return result
e = 12742153496769814072596
p = 65211247300401312530078141569304950676358489059623557848188896752173856845051471066071652073612337629832155846984721797768267868868902023383604553319793550396610085424563231688918357710337401138108050205457200940158475922063279384491022916790549837379548978141370347556053597178221402425212594060342213485311
c = 45326527081735095684632585216508484943819720696878842043540554720229674414296707918873385105075387912310299691748216658256439485784388880803922134863731374059731970174794936075890019917038396488161530769759774808480182049272235808430693365496648819656078275683885130420969875204155207145247880895891885126527
phi = p - 1
c1=AMM(c,2,p)
d=invmod(e//2//7438,phi)
c2=pow(int(c1),int(d),int(p))
m0=AMM(c2,7438,p)
def findAllPRoot(p, e):start = time.time()proot = set()while len(proot) < e:proot.add(pow(random.randint(2, p-1), int((p-1)//e), int(p)))end = time.time()return proot
m1=findAllPRoot(p,7438)
for i in m1:flag=m0*i%pflag=long_to_bytes(flag)if b'flag' in flag:print(flag)

再看一道例题，来自2022SUSCTF

from Crypto.Util.number import *
from secret import e,messagedef pad(s):if len(s)<3*L:s+=bytes(3*L-len(s))return sL=128
p = 127846753573603084140032502367311687577517286192893830888210505400863747960458410091624928485398237221748639465569360357083610343901195273740653100259873512668015324620239720302434418836556626441491996755736644886234427063508445212117628827393696641594389475794455769831224080974098671804484986257952189021223
q = 145855456487495382044171198958191111759614682359121667762539436558951453420409098978730659224765186993202647878416602503196995715156477020462357271957894750950465766809623184979464111968346235929375202282811814079958258215558862385475337911665725569669510022344713444067774094112542265293776098223712339100693
r = 165967627827619421909025667485886197280531070386062799707570138462960892786375448755168117226002965841166040777799690060003514218907279202146293715568618421507166624010447447835500614000601643150187327886055136468260391127675012777934049855029499330117864969171026445847229725440665179150874362143944727374907
n = p * q * rassert isPrime(GCD(e,p-1)) and isPrime(GCD(e,q-1)) and isPrime(GCD(e,r-1)) and e==GCD(e,p-1)*GCD(e,q-1)*GCD(e,r-1)
assert len(message)>L and len(message)<2*L
assert b'SUSCTF' in message
m=bytes_to_long(pad(message))c=pow(m,e,n)
print(c)
'''
2832775557487418816663494645849097066925967799754895979829784499040437385450603537732862576495758207240632734290947928291961063611897822688909447511260639429367768479378599532712621774918733304857247099714044615691877995534173849302353620399896455615474093581673774297730056975663792651743809514320379189748228186812362112753688073161375690508818356712739795492736743994105438575736577194329751372142329306630950863097761601196849158280502041616545429586870751042908365507050717385205371671658706357669408813112610215766159761927196639404951251535622349916877296956767883165696947955379829079278948514755758174884809479690995427980775293393456403529481055942899970158049070109142310832516606657100119207595631431023336544432679282722485978175459551109374822024850128128796213791820270973849303929674648894135672365776376696816104314090776423931007123128977218361110636927878232444348690591774581974226318856099862175526133892
'''

这里看到e由三个数的因子组成，那么就可以尝试用yafu分解素数，将因数组合，而因数不可能太大（不然在短时间里根本不可能解出来），后续用p，q换模再进行CRT组合也是同理，但即使减短了求解的时间也仍需要较长时间

p = 127846753573603084140032502367311687577517286192893830888210505400863747960458410091624928485398237221748639465569360357083610343901195273740653100259873512668015324620239720302434418836556626441491996755736644886234427063508445212117628827393696641594389475794455769831224080974098671804484986257952189021223
q = 145855456487495382044171198958191111759614682359121667762539436558951453420409098978730659224765186993202647878416602503196995715156477020462357271957894750950465766809623184979464111968346235929375202282811814079958258215558862385475337911665725569669510022344713444067774094112542265293776098223712339100693
r = 165967627827619421909025667485886197280531070386062799707570138462960892786375448755168117226002965841166040777799690060003514218907279202146293715568618421507166624010447447835500614000601643150187327886055136468260391127675012777934049855029499330117864969171026445847229725440665179150874362143944727374907
pp=[2,7,757,1709,85015583,339028665499]
qq=[2,2,3,3,66553,81768440203, 84405986771]
rr=[2,5156273,10012111,11607389]

同时，注意到c的后128位来自填充，那么可以将它去掉

p = 127846753573603084140032502367311687577517286192893830888210505400863747960458410091624928485398237221748639465569360357083610343901195273740653100259873512668015324620239720302434418836556626441491996755736644886234427063508445212117628827393696641594389475794455769831224080974098671804484986257952189021223
q = 145855456487495382044171198958191111759614682359121667762539436558951453420409098978730659224765186993202647878416602503196995715156477020462357271957894750950465766809623184979464111968346235929375202282811814079958258215558862385475337911665725569669510022344713444067774094112542265293776098223712339100693
r = 165967627827619421909025667485886197280531070386062799707570138462960892786375448755168117226002965841166040777799690060003514218907279202146293715568618421507166624010447447835500614000601643150187327886055136468260391127675012777934049855029499330117864969171026445847229725440665179150874362143944727374907
pp=[2,7,757,1709,85015583,339028665499]
qq=[2,3,66553,81768440203, 84405986771]
rr=[2,5156273,10012111,11607389]
pe=757
qe=66553
re=5156273
c=2832775557487418816663494645849097066925967799754895979829784499040437385450603537732862576495758207240632734290947928291961063611897822688909447511260639429367768479378599532712621774918733304857247099714044615691877995534173849302353620399896455615474093581673774297730056975663792651743809514320379189748228186812362112753688073161375690508818356712739795492736743994105438575736577194329751372142329306630950863097761601196849158280502041616545429586870751042908365507050717385205371671658706357669408813112610215766159761927196639404951251535622349916877296956767883165696947955379829079278948514755758174884809479690995427980775293393456403529481055942899970158049070109142310832516606657100119207595631431023336544432679282722485978175459551109374822024850128128796213791820270973849303929674648894135672365776376696816104314090776423931007123128977218361110636927878232444348690591774581974226318856099862175526133892
n=p*q*r
phi=(p-1)*(q-1)*(r-1)
e1=pe*qe*re*1024
s=pow(2,e1,n)
c=c*inverse(s,n)%n
c=280255407228236757409815887816839305916013793019016233556655881177084422973195335022587512823438603244476043620827618294521590422727109511126415701233621433629240428867472167324658030697632936334280396757560948574122348115659399270054958107088934452614887088952896264179020173433953077103667481291070508539455758662089418673467059205006535938089060238423612896891987917999584958061136036905447992065531255981463313994015042735163816799075348821119889190340460982992279626227831798343223551589026122303723190113833517871336399306996954589023298254133748866058614684423538364147817066529477497132575245720700870565926266788795913995176704128093239281548107568333922105485755437756178962461996506944599470241130124718452661102076116228019710853593988020056387355430180299354138576803527595019867293888047502553256446787799726850487133374683211529254614387387388363258745961934823313987871646019723020739519484511573598334592780

准备工作做好了，接下来移步sageamth，下面的代码也可以当作AMM算法的板子来使用

import time,random
from sympy import discrete_log
from Crypto.Util.number import *
from libnum import *
from gmpy2 import *
from tqdm import *
def AMM(o, r, q):start = time.time()print('\n----------------------------------------------------------------------------------')print('Start to run Adleman-Manders-Miller Root Extraction Method')g = GF(q)o = g(o)p = g(random.randint(1, q))while p ^ ((q-1) // r) == 1:p = g(random.randint(1, q))print('[+] Find p:{}'.format(p))t = 0s = q - 1while s % r == 0:t += 1s = s // rprint('[+] Find s:{}, t:{}'.format(s, t))k = 1while (k * s + 1) % r != 0:k += 1alp = (k * s + 1) // rprint('[+] Find alp:{}'.format(alp))a = p ^ (r**(t-1) * s)b = o ^ (r*alp - 1)c = p ^ sh = 1for i in range(1, t):d = b ^ (r^(t-1-i))if d == 1:j = 0else:print('[+] Calculating DLP...')j = - discrete_log(d, a)print('[+] Finish DLP...')b = b * (c^r)^jh = h * c^jc = c^rresult = o^alp * hend = time.time()print("Finished in {} seconds.".format(end - start))print('Find one solution: {}'.format(result))return resultdef onemod(p,r): t=p-2 while pow(t,(p-1) // r,p)==1: t -= 1 return pow(t,(p-1) // r,p) def solution(p,root,e):  g = onemod(p,e) may = set() for i in range(e): may.add(root * pow(g,i,p)%p) return mayp = 127846753573603084140032502367311687577517286192893830888210505400863747960458410091624928485398237221748639465569360357083610343901195273740653100259873512668015324620239720302434418836556626441491996755736644886234427063508445212117628827393696641594389475794455769831224080974098671804484986257952189021223
q = 145855456487495382044171198958191111759614682359121667762539436558951453420409098978730659224765186993202647878416602503196995715156477020462357271957894750950465766809623184979464111968346235929375202282811814079958258215558862385475337911665725569669510022344713444067774094112542265293776098223712339100693
r = 165967627827619421909025667485886197280531070386062799707570138462960892786375448755168117226002965841166040777799690060003514218907279202146293715568618421507166624010447447835500614000601643150187327886055136468260391127675012777934049855029499330117864969171026445847229725440665179150874362143944727374907
pe=757
qe=66553
re=5156273
c=280255407228236757409815887816839305916013793019016233556655881177084422973195335022587512823438603244476043620827618294521590422727109511126415701233621433629240428867472167324658030697632936334280396757560948574122348115659399270054958107088934452614887088952896264179020173433953077103667481291070508539455758662089418673467059205006535938089060238423612896891987917999584958061136036905447992065531255981463313994015042735163816799075348821119889190340460982992279626227831798343223551589026122303723190113833517871336399306996954589023298254133748866058614684423538364147817066529477497132575245720700870565926266788795913995176704128093239281548107568333922105485755437756178962461996506944599470241130124718452661102076116228019710853593988020056387355430180299354138576803527595019867293888047502553256446787799726850487133374683211529254614387387388363258745961934823313987871646019723020739519484511573598334592780
cp=pow(c,invmod(qe*re,p-1),p)
cq=pow(c,invmod(pe*re,q-1),q)
pm=AMM(cp,pe,p)
qm=AMM(cq,qe,q)
pms=solution(p,pm,pe)
qms=solution(q,qm,qe)
print(pms)
for i in tqdm(pms):for j in qms:a=[int(i),int(j)]m=[p,q]res=crt(a,m)flag=long_to_bytes(res)if b'SUSCTF' in flag:print(flag)

费马小定理推导

这道题有点意思，适合新生赛的时候出题

from Crypto.Util.number import *
from secret import flag
m=bytes_to_long(flag)
p=getPrime(1024)
q=getPrime(1024)
n=p*q
phi=(p-1)*(q-1)
e=0x10001
c=pow(m,e,n)
leak1=pow(p,q,n)
leak2=pow(q,p,n)print(f'leak1={leak1}')
print(f'leak2={leak2}')
print(f'c={c}')"""
leak1=149127170073611271968182576751290331559018441805725310426095412837589227670757540743929865853650399839102838431507200744724939659463200158012469676979987696419050900842798225665861812331113632892438742724202916416060266581590169063867688299288985734104127632232175657352697898383441323477450658179727728908669
leak2=116122992714670915381309916967490436489020001172880644167179915467021794892927977272080596641785569119134259037522388335198043152206150259103485574558816424740204736215551933482583941959994625356581201054534529395781744338631021423703171146456663432955843598548122593308782245220792018716508538497402576709461
c=10529481867532520034258056773864074017027019578041866245400647840230251661652999709715919620810933437191661180003295923273655675729588558899592524235622728816065501918076120812236580344991140980991532347991252705288633014913479970610056845543523591324177567061948922552275235486615514913932125436543991642607028689762693617305246716492783116813070355512606971626645594961850567586340389705821314842096465631886812281289843132258131809773797777049358789182212570606252509790830994263132020094153646296793522975632191912463919898988349282284972919932761952603379733234575351624039162440021940592552768579639977713099971
"""

代码就懒得写了，求解一个常规RSA即可