如果你的训练量常人都能接受，冠军凭什么是你
[SWPUCTF 2021 新生赛]crypto1
附件
from Crypto.Util.number import *
flag = ‘****************************’
flag = {“asfajgfbiagbwe”}
m1 = bytes_to_long(bytes(flag.encode()))
print(‘flag1= ‘+str(flag1))
print(‘flag2= ‘+str(flag2))
#flag1= 463634070971821449698012827631572665302589213868521491855038966879005784397309389922926838028598122795187584361359142761652619958273094398420314927073008031088375892957173280915904309949716842152249806486027920136603248454946737961650252641668562626310035983343018705370077783879047584582817271215517599531278507300104564011142229942160380563527291388260832749808727470291331902902518196932928128107067117198707209620169906575791373793854773799564060536121390593687449884988936522369331738199522700261116496965863870682295858957952661531894477603953742494526632841396338388879198270913523572980574440793543571757278020533565628285714358815083303489096524318164071888139412436112963845619981511061231001617406815056986634680975142352197476024575809514978857034477688443230263761729039797859697947454810551009108031457294164840611157524719173343259485881089252938664456637673337362424443150013961181619441267926981848009107466576314685961478748352388452114042115892243272514245081604607798243817586737546663059737344687130881861357423084448027959893402445303299089606081931041217035955143939567456782107203447898345284731038150377722447329202078375870541529539840051415759436083384408203659613313535094343772238691393447475364806171594
#flag2= 130959534275704453216282334815034647265875632781798750901627773826812657339274362406246297925411291822193191483409847323315110393729020700526946712786793380991675008128561863631081095222226285788412970362518398757423705216112313533155390315204875516645459370629706277876211656753247984282379731850770447978537855070379324935282789327428625259945250066774049650951465043700088958965762054418615838049340724639373351248933494355591934236360506778496741051064156771092798005112534162050165095430065000827916096893408569751085550379620558282942254606978819033885539221416335848319082054806148859427713144286777516251724474319613960327799643723278205969253636514684757409059003348229151341200451785288395596484563480261212963114071064979559812327582474674812225260616757099890896900340007990585501470484762752362734968297532533654846190900571017635959385883945858334995884341767905619567505341752047589731815868489295690574109758825021386698440670611361127170896689015108432408490763723594673299472336065575301681055583084547847733168801030191262122130369687497236959760366874106043801542493392227424890925595734150487586757484304609945827925762382889592743709682485229267604771944535469557860120878491329984792448597107256325783346904408
#n= 609305637099654478882754880905638123124918364116173050874864700996165096776233155524277418132679727857702738043786588380577485490575591029930152718828075976000078971987922107645530323356525126496562423491563365836491753476840795804040219013880969539154444387313029522565456897962200817021423704204077133003361140660038327458057898764857872645377236870759691588009666047187685654297678987435769051762120388537868493789773766688347724903911796741124237476823452505450704989455260077833828660552130714794889208291939055406292476845194489525212129635173284301782141617878483740788532998492403101324795726865866661786740345862631916793208037250277376942046905892342213663197755010315060990871143919384283302925469309777769989798197913048813940747488087191697903624669415774198027063997058701217124640082074789591591494106726857376728759663074734040755438623372683762856958888826373151815914621262862750497078245369680378038995425628467728412953392359090775734440671874387905724083226246587924716226512631671786591611586774947156657178654343092123117255372954798131265566301316033414311712092913492774989048057650627801991277862963173961355088082419091848569675686058581383542877982979697235829206442087786927939745804017455244315305118437
思路
首先可以看到e1e2的积很小，那么e1,e2都很小，3087可以直接分解，可以循环分解的组合去爆破出e1和e2，也可以直接2到3087去循环，我采用的是后者（代码好写），然后就是最简单的共模攻击，可以直接套用脚本，然后再把求出的m开gcd(e1,e2)次方就可以了
exp
from gmpy2 import *
from Crypto.Util.number import *
c1= 463634070971821449698012827631572665302589213868521491855038966879005784397309389922926838028598122795187584361359142761652619958273094398420314927073008031088375892957173280915904309949716842152249806486027920136603248454946737961650252641668562626310035983343018705370077783879047584582817271215517599531278507300104564011142229942160380563527291388260832749808727470291331902902518196932928128107067117198707209620169906575791373793854773799564060536121390593687449884988936522369331738199522700261116496965863870682295858957952661531894477603953742494526632841396338388879198270913523572980574440793543571757278020533565628285714358815083303489096524318164071888139412436112963845619981511061231001617406815056986634680975142352197476024575809514978857034477688443230263761729039797859697947454810551009108031457294164840611157524719173343259485881089252938664456637673337362424443150013961181619441267926981848009107466576314685961478748352388452114042115892243272514245081604607798243817586737546663059737344687130881861357423084448027959893402445303299089606081931041217035955143939567456782107203447898345284731038150377722447329202078375870541529539840051415759436083384408203659613313535094343772238691393447475364806171594
c2= 130959534275704453216282334815034647265875632781798750901627773826812657339274362406246297925411291822193191483409847323315110393729020700526946712786793380991675008128561863631081095222226285788412970362518398757423705216112313533155390315204875516645459370629706277876211656753247984282379731850770447978537855070379324935282789327428625259945250066774049650951465043700088958965762054418615838049340724639373351248933494355591934236360506778496741051064156771092798005112534162050165095430065000827916096893408569751085550379620558282942254606978819033885539221416335848319082054806148859427713144286777516251724474319613960327799643723278205969253636514684757409059003348229151341200451785288395596484563480261212963114071064979559812327582474674812225260616757099890896900340007990585501470484762752362734968297532533654846190900571017635959385883945858334995884341767905619567505341752047589731815868489295690574109758825021386698440670611361127170896689015108432408490763723594673299472336065575301681055583084547847733168801030191262122130369687497236959760366874106043801542493392227424890925595734150487586757484304609945827925762382889592743709682485229267604771944535469557860120878491329984792448597107256325783346904408
n= 609305637099654478882754880905638123124918364116173050874864700996165096776233155524277418132679727857702738043786588380577485490575591029930152718828075976000078971987922107645530323356525126496562423491563365836491753476840795804040219013880969539154444387313029522565456897962200817021423704204077133003361140660038327458057898764857872645377236870759691588009666047187685654297678987435769051762120388537868493789773766688347724903911796741124237476823452505450704989455260077833828660552130714794889208291939055406292476845194489525212129635173284301782141617878483740788532998492403101324795726865866661786740345862631916793208037250277376942046905892342213663197755010315060990871143919384283302925469309777769989798197913048813940747488087191697903624669415774198027063997058701217124640082074789591591494106726857376728759663074734040755438623372683762856958888826373151815914621262862750497078245369680378038995425628467728412953392359090775734440671874387905724083226246587924716226512631671786591611586774947156657178654343092123117255372954798131265566301316033414311712092913492774989048057650627801991277862963173961355088082419091848569675686058581383542877982979697235829206442087786927939745804017455244315305118437
e1e2 = 3087
for e1 in range(2,3087):
if e1e2%e1==0:
e2 = e1e2//e1
r,s1,s2 = gmpy2.gcdext(e1, e2)
m = (pow(c1,s1,n)*pow(c2,s2,n)) % n
e=gmpy2.gcd(e1,e2)
m=gmpy2.iroot(m,e)[0]
print(long_to_bytes(m))
#NSSCTF{d64dba66-b608-4255-b888-0b0f25c2f90e}
[BJDCTF 2020]rsa_output
附件
{21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111,2767}
{21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111,3659}
message1=20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599
message2=11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227
思路
首先给的就是两组enc，先把他分开，然后直接共模攻击就可以了
exp
from Crypto.Util.number import *
n = 21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111
n1 = 21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111
c1 = 20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599
n2 = 21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111
c2 = 11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227
def rsa_mod_same_N(e1, c1, e2, c2, n):
r, s1, s2 = gmpy2.gcdext(e1, e2)
m = gmpy2.mod(gmpy2.powmod(c1, s1, n)*gmpy2.powmod(c2,s2,n), n)
m = rsa_mod_same_N(e1, c1, e2, c2, n)
[BJDCTF 2020]EasyRSA
附件
from Crypto.Util.number import getPrime,bytes_to_long
from sympy import Derivative
from fractions import Fraction
from secret import flag
p=getPrime(1024)
q=getPrime(1024)
e=65537
n=p*q
z=Fraction(1,Derivative(arctan(p),p))-Fraction(1,Derivative(arth(q),q))
m=bytes_to_long(flag)
c=pow(m,e,n)
print(c,z,n)
”’
output:
7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035
32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482
15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441
”’
思路
大概试了一下n是可以直接分解的，所以可以直接求出来，当然也可以用正规做法，题目中的z就可以看成p**2+q**2（怎么推的靠自己），那么z+n=(p+q)²,z-n=(p-q)²,那么我们就可以求出来p和q了
exp
from gmpy2 import *
from Crypto.Util.number import long_to_bytes
c = 7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035
z = 32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482
n = 15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441
e = 0x10001
ppq = iroot(z+2*n, 2)[0]
psq = iroot(z-2*n, 2)[0]
p = (ppq + psq) // 2
q = (ppq – psq) // 2
d = invert(e, (p-1)*(q-1))
print(long_to_bytes(pow(c, int(d), n)))
[闽盾杯 2021]decode
附件
n1:
15228664629164509105936278301396170708905691970126305196584505186788860519598413718493859625462561931380632032431490419378905593909771649295663481782473029836321132574188559245931660756414915507930357509270674460219615256962333464689419869130366867401404262606367700782040693275068101244535880649261286041921882470460606034302142183971677715439862839410834231609821777031530457674591868138859358815039755085358568037032478394036448363183057305077227769673701227083943898736796552550712057417053897722979700329662099072959306298177351997084389916443815546425080826441671985030755256185725913397986385179516049927425591
n2:
28182418532443955655250943929828439725377604572088962537896240628709829618999901367131159759359513146864646169253348651905865895468151210748207509325666501438590382812326109260537618829438786609626137074778638549998280533912080708785604673270460635181275360847313985764185991865570533815651261638439461846512012164531330949433517277559149828806588070421852157781670188281908625986974579194819272643409859915715455134433970119584552350648013116998668938513347083566970423327936691885137812528912263666957628197241313496232397910546498542303925205356813548741679943691886217742767778075067797422624969714343428365022749
n3:
18355811159408154065817199279776805621878757240392366715869421799780946779485225342662736231980532326015283372375030686507311099745671828649419794838611580909610100636296701054995302819692794479292794716441442731393027118795245239019609474743841061251498233337758043553376098591254587406941205804917663153256036922860462415387926973551020540123742773938055950168965005226319984869124543783579240130888344231027912143592472823564266887957101575622993773291455143915263715932280728961208233983782906070719786115187115449430196335973764600533097718947377609348244073036523422892353195107093782201003551217830556519184839
e1:
65537
e2:
27751
e3:
65537
c1:
5368342382489380107251269030258282008067103595899117880173297169710980852124379736420135829984131832023988667774795223808420069001078159756328642298736759964890517323144475742861501409284299556459601222657540302786301791897975932176538612601162552795835603779910738886150925504885639254302406755008796950704938463132687940418772021406619622090999564746948113296328739593309200238996686945891130656599419832796482095787039339269564880847130379179831744694000940207887150388411084465949903406848727641093033681144598595895383689139227400553234701993087147186292040330589331703587405822925483701667354935313494938769206
c2:
21521672635651854919517759696514027081496995002884626306313384597771682621826437868933822942195279941318573525337109548152966094293276717095298929811895186384560362917891928656637913236676702009205642367801075592458101830488916914437754803979953027152373619293870115731171449223105986403604973873007338969000153480949617700626516389419935352576014084068271819009465242491467427642787306345049280205827574043586767133396458785487959251540831856187380154825027964867977651727983254127239427622549059938701125498520279503972702883327594442747467858234391945790597844344295786118320620376681461727686876948563884520137741
c3:
13940747781246179701167820858098775936269078279837839169409057305686612176371099274767269714494905207551971162649902129137425806839867713157472497469542260664882313041602553845621113546259276402534229231780532278276697961222319054833980226978574905974878218905613341365260453461080117407529132948986104191917111000811731784483944945364091757083949827612260904757837644538366763161154611658652020868326985526984718638276184626634240096213703958275241215175054246685206226179114590838833694648062135027841593419815101363262701960507235056752424778384286627997500871204804629047307688466887868894491042058198480775705486
思路
就是一个三组的共模攻击，直接写就行，当然，如果你和我一样闲，就可以发现n1和n3可以分解，而n2恰好是由他们俩的因子相乘得到的，所以全都可以分解！！
exp
from Crypto.Util.number import *
import gmpy2
n1 = 15228664629164509105936278301396170708905691970126305196584505186788860519598413718493859625462561931380632032431490419378905593909771649295663481782473029836321132574188559245931660756414915507930357509270674460219615256962333464689419869130366867401404262606367700782040693275068101244535880649261286041921882470460606034302142183971677715439862839410834231609821777031530457674591868138859358815039755085358568037032478394036448363183057305077227769673701227083943898736796552550712057417053897722979700329662099072959306298177351997084389916443815546425080826441671985030755256185725913397986385179516049927425591
n2 = 28182418532443955655250943929828439725377604572088962537896240628709829618999901367131159759359513146864646169253348651905865895468151210748207509325666501438590382812326109260537618829438786609626137074778638549998280533912080708785604673270460635181275360847313985764185991865570533815651261638439461846512012164531330949433517277559149828806588070421852157781670188281908625986974579194819272643409859915715455134433970119584552350648013116998668938513347083566970423327936691885137812528912263666957628197241313496232397910546498542303925205356813548741679943691886217742767778075067797422624969714343428365022749
n3 = 18355811159408154065817199279776805621878757240392366715869421799780946779485225342662736231980532326015283372375030686507311099745671828649419794838611580909610100636296701054995302819692794479292794716441442731393027118795245239019609474743841061251498233337758043553376098591254587406941205804917663153256036922860462415387926973551020540123742773938055950168965005226319984869124543783579240130888344231027912143592472823564266887957101575622993773291455143915263715932280728961208233983782906070719786115187115449430196335973764600533097718947377609348244073036523422892353195107093782201003551217830556519184839
e1 = 65537
e2 = 27751
e3 = 65537
c1 = 5368342382489380107251269030258282008067103595899117880173297169710980852124379736420135829984131832023988667774795223808420069001078159756328642298736759964890517323144475742861501409284299556459601222657540302786301791897975932176538612601162552795835603779910738886150925504885639254302406755008796950704938463132687940418772021406619622090999564746948113296328739593309200238996686945891130656599419832796482095787039339269564880847130379179831744694000940207887150388411084465949903406848727641093033681144598595895383689139227400553234701993087147186292040330589331703587405822925483701667354935313494938769206
c2 = 21521672635651854919517759696514027081496995002884626306313384597771682621826437868933822942195279941318573525337109548152966094293276717095298929811895186384560362917891928656637913236676702009205642367801075592458101830488916914437754803979953027152373619293870115731171449223105986403604973873007338969000153480949617700626516389419935352576014084068271819009465242491467427642787306345049280205827574043586767133396458785487959251540831856187380154825027964867977651727983254127239427622549059938701125498520279503972702883327594442747467858234391945790597844344295786118320620376681461727686876948563884520137741
c3 = 13940747781246179701167820858098775936269078279837839169409057305686612176371099274767269714494905207551971162649902129137425806839867713157472497469542260664882313041602553845621113546259276402534229231780532278276697961222319054833980226978574905974878218905613341365260453461080117407529132948986104191917111000811731784483944945364091757083949827612260904757837644538366763161154611658652020868326985526984718638276184626634240096213703958275241215175054246685206226179114590838833694648062135027841593419815101363262701960507235056752424778384286627997500871204804629047307688466887868894491042058198480775705486
p = gmpy2.gcd(n1,n2)
q = gmpy2.gcd(n2,n3)
def attack(p,q,e,c):
n = p * q
phi = (p – 1) * (q – 1)
d = gmpy2.invert(e,phi)
m = long_to_bytes(pow(c,d,n))
print(m)
attack(p,n1 // p,e1,c1)
attack(p,n2 // p,e2,c2)
attack(q,n3 // q,e3,c3)
#flag{G00d_w4y_tO_cR4ck_RS4}
[HGAME 2022 week3]RSA attack 3
附件
from Crypto.Util.number import getPrime
from gmpy2 import invert
from libnum import s2n
from secret import flag
p = getPrime(2048)
q = getPrime(2048)
n = p * q
d = getPrime(64)
e = invert(d, (p – 1) * (q – 1))
c = pow(s2n(flag), e, n)
print(f”n = {n}”)
print(f”e = {e}”)
print(f”c = {c}”)
思路
给了nec，但是d是一个很小的数且e比较大，所以我们就可以推断出来是wiener攻击，可以直接去套模板。
exp
import gmpy2
from Crypto.Util.number import long_to_bytes
n = 507419170088344932990702256911694788408493968749527614421614568612944144764889717229444020813658893362983714454159980719026366361318789415279417172858536381938870379267670180128174798344744371725609827872339512302232610590888649555446972990419313445687852636305518801236132032618350847705234643521557851434711389664130274468354405273873218264222293858509477860634889001898462547712800153111774564939279190835857445378261920532206352364005840238252284065587291779196975457288580812526597185332036342330147250312262816994625317482869849388424397437470502449815132000588425028055964432298176942124697105509057090546600330760364385753313923003549670107599757996810939165300581847068233156887269181096893089415302163770884312255957584660964506028002922164767453287973102961910781312351686488047510932997937700597992705557881172640175117476017503918294534205898046483981707558521558992058512940087192655700351675718815723840568640509355338482631416345193176708501897458649841539192993142790402734898948352382350766125000186026261167277014748183012844440603384989647664190074853086693408529737767147592432979469020671772152652865219092597717869942730499507426269170189547020660681363276871874469322437194397171763927907099922324375991793759
e = 77310199867448677782081572109343472783781135641712597643597122591443011229091533516758925238949755491395489408922437493670252550920826641442189683907973926843505436730014899918587477913032286153545247063493885982941194996251799882984145155733050069564485120660716110828110738784644223519725613280140006783618393995138076030616463398284819550627612102010214315235269945251741407899692274978642663650687157736417831290404871181902463904311095448368498432147292938825418930527188720696497596867575843476810225152659244529481480993843168383016583068747733118703000287423374094051895724494193455175131120243097065270804457787026492578916584536863548445813916819417857064037664101684455000184987531252344582899589746272173970083733130106407810619258077266603898529285634495710846838011858287024329514491058790557305041389614650730267774482954666726949886313386881066593946789460028399523245777171320319444673551268379126203862576627540177888290265714418064334752499940587750374552330008143708562065940245637685833371348603338834447212248648869514585047871442060412622164276894766238383894693759347590977926306581080390685360615407766600573527565016914830132066428454738135380178959590692145577418811677639050929791996313180297924833690095
c = 165251729917394529793163344300848992394021337429474789711805041655116845722480301677817165053253655027459227404782607373107477419083333844871948673626672704233977397989843349633720167495862807995411682262559392496273163155214888276398332204954185252030616473235814999366132031184631541209554169938146205402400412307638567132128690379079483633171535375278689326189057930259534983374296873110199636558962144635514392282351103900375366360933088605794654279480277782805401749872568584335215630740265944133347038070337891035560658434763924576508969938866566235926587685108811154229747423410476421860059769485356567301897413767088823807510568561254627099309752215808220067495561412081320541540679503218232020279947159175547517811501280846596226165148013762293861131544331444165070186672186027410082671602892508739473724143698396105392623164025712124329254933353509384748403154342322725203183050328143736631333990445537119855865348221215277608372952942702104088940952142851523651639574409075484106857403651453121036577767672430612728022444370874223001778580387635197325043524719396707713385963432915855227152371800527536048555551237729690663544828830627192867570345853910196397851763591543484023134551876591248557980182981967782409054277224
#将分数x/y展开为连分数的形式
def transform(x,y):
arr=[]
while y:
arr+=[x//y]
x,y=y,x%y
return arr
#求解渐进分数
def sub_fraction(k):
x=0
y=1
for i in k[::-1]:
x,y=y,x+i*y
return (y,x)
data=transform(e,n)
for x in range(1,len(data)+1):
data1=data[:x]
d = sub_fraction(data1)[1]
m = pow(c,d,n)
flag = long_to_bytes(m)
if b’hgame{‘ in flag:
print(flag)
break
[CISCN 2022 西南]rsa
附件
from Crypto.Util.number import *
import gmpy2
flag = b’XXXXXXXX’
p1 = getPrime(700)
r1 = getPrime(700)
for i in range(10):
q1 = 5*p1+i
n = p1*q1*r1
p3 = pow(p1,3,n)
q3 = pow(q1,3,n)
print(p3)
print(q3)
”’
p3 = 29914513810588158800677413177910972738704129106546850855032986405861482276089830788972187432277517348644647399654780884571794069905291936470934226328931651386658328163535027343107140438177837479649822914209171476632450951930287641742344330471734177295804718555774395704231261550376220154493373703096062950390869299905383682611063374747752091585836452902373843865043412096365874638466683035848817858586173172058756256354758712684819253211761289032789542371351760915771791997388241121078055468403109260493642435791152671979552597191217179672328555740595434990908530985477314228867209314472001848844089467987561661918366232980944933533
q3 = 66208618374366130551979192465001581263127328176551695213970812805980115496523825511250542987452691413485117902772315362811067501379171731387904074565035353566976164797769439898266222919741874340315356585585077141595328441423323822407738375537476582506440045835592730211502035261968878999959340204806442390319739977816872969200022096331677277225467021553564212725120939434924481787524609852608476848761521446441776154400518315701988027274150425936061679275540502720782853648148897480117033152064922234451671636288396704170234613549011854618414776342798740690128675106027908639984431432591397555541420243824539205614036979987830125678
”’
P = getPrime(1024)
Q = getPrime(1024)
N = P * Q
E = 65537
lcm = gmpy2.lcm(P-1, Q-1)
e1 = gmpy2.invert(p1, lcm)
e2 = gmpy2.invert(r1, lcm)
m = bytes_to_long(flag)
c = pow(m, E, N)
print(lcm)
print(c)
print(N)
”’
lcm = 4292158730589770192682795435047249488185453170529228019750042608688907718268448193363838203887391025871515871000364259326343790645215256385842265899206372365402431198699714374850409466996627163968391249416054093529090485677808301343590811445080871279796162536469847469761747058736980603093722710824453312207182881241846080117790728778291633761198069016865260030288832065807438020772711645648333908622890343009942617559434851450007195025869850769670769715654662127278293639938359741401336592219730356884542179574372134014927006215640945952229142436595334916765255426954857520777553915330597952622785359222832224632624
c = 4288727484183191191687364666620023549392656794153112764357730676861570386983002380982803054964588111708662498647767438881892355599604826306427809017097724346976778230464708540600157055782723189971534549543664668430013171469625043063261219462210251726207552819381767396148632877168530609902046293626355744288863460554297860696918890189350721960355460410677203131993419723440382095665713164422367291153108363066159712951217816814873413423853338021627653555202253351957999686659021298525147460016557904084617528199284448056532965033560516083489693334373695545423561715471204868795248569806148395196572046378679014697206
N = 17168634922359080770731181740188997952741812682116912079000170434755630873073792773455352815549564103486063484001457037305375162580861025543369063596825489461609724794798857499401637867986508655873564997664216374116361942711233205374363245780323485119184650145879389879046988234947922412374890843297813248828996855478005656041814919367820336728271583686844991928889831691815821365423570311291064846736832327637944358854661523107817781673029406341843040857813841671405147146887291204140157388049394514390098066284975682117038362207142272098796924412602725857521665773622056312191400612944442008222587867782281556388669
”’
思路
看了一大会，然后就在想lcm是p-1和q-1的最小公倍数，那么有没有可能lcm就是φn，那我是不是可以直接求出来flag了，结果还真是（）。
exp
p3 = 29914513810588158800677413177910972738704129106546850855032986405861482276089830788972187432277517348644647399654780884571794069905291936470934226328931651386658328163535027343107140438177837479649822914209171476632450951930287641742344330471734177295804718555774395704231261550376220154493373703096062950390869299905383682611063374747752091585836452902373843865043412096365874638466683035848817858586173172058756256354758712684819253211761289032789542371351760915771791997388241121078055468403109260493642435791152671979552597191217179672328555740595434990908530985477314228867209314472001848844089467987561661918366232980944933533
q3 = 66208618374366130551979192465001581263127328176551695213970812805980115496523825511250542987452691413485117902772315362811067501379171731387904074565035353566976164797769439898266222919741874340315356585585077141595328441423323822407738375537476582506440045835592730211502035261968878999959340204806442390319739977816872969200022096331677277225467021553564212725120939434924481787524609852608476848761521446441776154400518315701988027274150425936061679275540502720782853648148897480117033152064922234451671636288396704170234613549011854618414776342798740690128675106027908639984431432591397555541420243824539205614036979987830125678
from Crypto.Util.number import *
import gmpy2
p1=gmpy2.iroot(p3,3)[0]
q1=gmpy2.iroot(q3,3)[0]
lcm = 4292158730589770192682795435047249488185453170529228019750042608688907718268448193363838203887391025871515871000364259326343790645215256385842265899206372365402431198699714374850409466996627163968391249416054093529090485677808301343590811445080871279796162536469847469761747058736980603093722710824453312207182881241846080117790728778291633761198069016865260030288832065807438020772711645648333908622890343009942617559434851450007195025869850769670769715654662127278293639938359741401336592219730356884542179574372134014927006215640945952229142436595334916765255426954857520777553915330597952622785359222832224632624
c = 4288727484183191191687364666620023549392656794153112764357730676861570386983002380982803054964588111708662498647767438881892355599604826306427809017097724346976778230464708540600157055782723189971534549543664668430013171469625043063261219462210251726207552819381767396148632877168530609902046293626355744288863460554297860696918890189350721960355460410677203131993419723440382095665713164422367291153108363066159712951217816814873413423853338021627653555202253351957999686659021298525147460016557904084617528199284448056532965033560516083489693334373695545423561715471204868795248569806148395196572046378679014697206
N = 17168634922359080770731181740188997952741812682116912079000170434755630873073792773455352815549564103486063484001457037305375162580861025543369063596825489461609724794798857499401637867986508655873564997664216374116361942711233205374363245780323485119184650145879389879046988234947922412374890843297813248828996855478005656041814919367820336728271583686844991928889831691815821365423570311291064846736832327637944358854661523107817781673029406341843040857813841671405147146887291204140157388049394514390098066284975682117038362207142272098796924412602725857521665773622056312191400612944442008222587867782281556388669
e=65537
d=inverse(e,lcm)
m=pow(c,d,N)
print(long_to_bytes(m))
ok，今天的到此结束，下机。
（2020.4.5）