BUUCTF RSA（二）

1.[BJDCTF2020]RSA

两个加密的n共用一个q，对n1,n2求最大公约数，进而分解n1,n2，分别求得p，q。
假设c3 = pow(294,e,n1)
,利用其进行枚举求得e,此时的e应该满足三个条件：
1.e<100000
2.(e,n1) = 1
3.pow(294,e,n1) = c3
解是解出来了，不过另一个明文加密的过程好像没有用到，仅仅只是提示了两个模数有共同因数。

c1 = 12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120
n1 = 13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037
q = 99855353761764939308265951492116976798674681282941462516956577712943717850048051273358745095906207085170915794187749954588685850452162165059831749303473106541930948723000882713453679904525655327168665295207423257922666721077747911860159181041422993030618385436504858943615630219459262419715816361781062898911
p = 135283423427545651023916134156519717109709399113553907832988770259402226695880524199087896377303631866790192008529658716376684328032075836094156150811025163336681163420875451747389868549203081743561907379260240665153166927504059379076555558704275659133135906827306189040804323574468819553401905127999523676067
phi = (q-1)*(p-1)c3 = 381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018
e = 2
while e<100000:if int(gmpy2.gcd(e,n1)) == 1:if pow(294,e,n1) == c3:print(e)breake += 1
d = int(gmpy2.invert(e,phi))
m = pow(c1,d,n1)
print(libnum.n2s(m))n2 = 12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047

2.[BJDCTF2020]rsa_output

可以看出第一二行是（n,e），两个n相同，属于共模攻击。那么只要利用扩展欧几里得算法求出s,t使得s * e1+t * e2 = 1即可。

#共模攻击
import libnum
e1 = 2767
c1 = 20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599
e2 = 3659
c2 = 11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227
n = 21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111 def ext_euclid(a, b):     if b == 0:         return 1, 0, a     else:         x, y, q = ext_euclid(b, a % b) # q = gcd(a, b) = gcd(b, a%b) x, y = y, (x - (a // b) * y)         return x, y, q
r,s,q = ext_euclid(e1,e2)
m = (pow(c1,r,n)*pow(c2,s,n))%n
print(libnum.n2s(m))

3.SameMod

可以看出来是共模攻击，不过最后用libnum.n2s等方法解出来的不对。后面尝试了将m的前几个数根据情况分开，进行chr()转换，出现了flag。于是就想着有没有什么函数可以一次性将这串数字转成字符，找了老半天了，后面才知道要自己手动完成！！！

import libnume1 = 773 
c1 = 3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349
e2 = 839 
c2 = 5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535
n = 6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249  def ext_euclid(a, b):     if b == 0:         return 1, 0, a     else:         x, y, q = ext_euclid(b, a % b)        x, y = y, (x - (a // b) * y)         return x, y, q
r,s,q = ext_euclid(e1,e2)   #r=gmpy2.gcdext(e1,e2)[1],s=gmpy2.gcdext(e1,e2)[2]
m = (pow(c1,r,n)*pow(c2,s,n))%n
print(m)
print(libnum.n2s(m))#b'\x86\x8e~\xd9\x1f\x06\xe6\x9f\xd2\x9b\xd3\xa2j\xa8\xaf4"\xc9\x90\xe2\x81TI>J\xf2\x89\xa9^>\x93\xd4P\xba\x05'ming = str(m)
i = 0
while i < len(ming):if ming[i] == '1' :print(chr(int(ming[i:i+3])),end = '')i += 3else :print(chr(int(ming[i:i+2])),end = '')i += 2

4.[BJDCTF2020]easyrsa

这个n可以用网站进行分解就得到了。不过按照题目的意思来吧。通过求导并化简得z = p² + q²

已知n = p*q，可以求出p+q，再构造方程x²-(p+q) * x +p * q = 0，分别求出p,q。

'''#分数 #导数 #arctan() #反双曲正切arth() z=Fraction(1,Derivative(arctan(p),p))-Fraction(1,Derivative(arth(q),q)) #z = 1/(1/(1+p**2)) - 1/(1/(1-q**2)) = p**2+q**2 '''import gmpy2,libnum
c = 7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035
z = 32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482
n = 15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441
#解方程 x*x-(p+q)*x+p*q=0
paq = int(gmpy2.iroot(z+2*n,2)[0])
pd = int(gmpy2.iroot(paq**2-4*n,2)[0])
p = (paq + pd)//2
q = (paq - pd)//2
e = 65537
phi = (p-1)*(q-1)
d = int(gmpy2.invert(e,phi))
m = pow(c,d,n)
print(libnum.n2s(m))

5.[NCTF2019]babyRSA

因为phi = (p-1) * (q-1)，又q是p的后一个素数，所以p² < phi < q²,即sqrt(phi)永远在p和q之间，求前后素数即可得到p和q。
已知e * d = 1 mod (phi) ==> ed - 1 = t * phi
因为(e*d-1)是2064bit，p和q是素数，(p-1)和(q-1)是1024bit，乘起来是2048 ~ 2049bit，那么t是15 ~ 16bit。枚举t并验算p,q。

'''文件内容 from Crypto.Util.number import * from flag import flagdef nextPrime(n):n += 2 if n & 1 else 1while not isPrime(n):n += 2return np = getPrime(1024) q = nextPrime(p) #返回下一个素数 n = p * q e = 0x10001 d = inverse(e, (p-1) * (q-1)) c = pow(bytes_to_long(flag.encode()), e, n) '''import gmpy2,libnum,sympy,binascii
from Crypto.Util.number import long_to_bytes
d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804
e = 65537
pd = e*d-1
#print(len(bin(pd)[2:])) # 2064bit p*q至少2048bit t最多16bit
start = pow(2,15)
end = pow(2,16)
for t in range(start,end):if pd%t == 0:phi = pd//tp = sympy.prevprime(int(gmpy2.iroot(phi,2)[0])) #phi近似于p**2,#prevprime返回上一个素数q = sympy.nextprime(p)#这里的p,q并无大小之分，可以任取前后素数，但必须是一前一后if (p-1)*(q-1) == phi:break
n = p*q
m = pow(c,d,n)
print(long_to_bytes(m))#print(binascii.unhexlify(hex(m)[2:]))

6.[ACTF新生赛2020]crypto-rsa3

已知n,e,c，利用fatordb网站分解n，得到p,q。

'''文件内容 from flag import FLAG from Cryptodome.Util.number import * import gmpy2 import randome=65537 p = getPrime(512) q = int(gmpy2.next_prime(p)) n = p*q m = bytes_to_long(FLAG) c = pow(m,e,n) print(n) print(c) '''
import libnum,gmpy2
n = 177606504836499246970959030226871608885969321778211051080524634084516973331441644993898029573612290095853069264036530459253652875586267946877831055147546910227100566496658148381834683037366134553848011903251252726474047661274223137727688689535823533046778793131902143444408735610821167838717488859902242863683
c = 1457390378511382354771000540945361168984775052693073641682375071407490851289703070905749525830483035988737117653971428424612332020925926617395558868160380601912498299922825914229510166957910451841730028919883807634489834128830801407228447221775264711349928156290102782374379406719292116047581560530382210049
e = 65537
p = 13326909050357447643526585836833969378078147057723054701432842192988717649385731430095055622303549577233495793715580004801634268505725255565021519817179231
q = 13326909050357447643526585836833969378078147057723054701432842192988717649385731430095055622303549577233495793715580004801634268505725255565021519817179293
d = int(gmpy2.invert(e,(p-1)*(q-1)))
m = pow(c,d,n)
print(libnum.n2s(m))

7.[AFCTF2018]你能看出这是什么加密么

解出的结果是一堆’\x ‘的东西就懒得看后面的了，看到这个我以为转换的方法不对，用了其他方法，还是这样。可恶，到最后网络上一搜发现flag就在最后面。不过当时写的一些题目解出来是’\x '的东西，网上查了一些，不知道为什么会产生这种结果，而且有的貌似还没找到解决方法，曾一度崩溃，所以看到这个的时候真没有心情往下看。

import libnum,gmpy2
from Crypto.Util.number import long_to_bytes 
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
p = int('0x928fb6aa9d813b6c3270131818a7c54edb18e3806942b88670106c1821e0326364194a8c49392849432b37632f0abe3f3c52e909b939c91c50e41a7b8cd00c67d6743b4f',16)
q = int('0xec301417ccdffa679a8dcc4027dd0d75baf9d441625ed8930472165717f4732884c33f25d4ee6a6c9ae6c44aedad039b0b72cf42cab7f80d32b74061',16)
e = int('0x10001',16)
c = int('0x70c9133e1647e95c3cb99bd998a9028b5bf492929725a9e8e6d2e277fa0f37205580b196e5f121a2e83bc80a8204c99f5036a07c8cf6f96c420369b4161d2654a7eccbdaf583204b645e137b3bd15c5ce865298416fd5831cba0d947113ed5be5426b708b89451934d11f9aed9085b48b729449e461ff0863552149b965e22b6',16)
n = p * q
phi = (p-1)*(q-1)
d = int(gmpy2.invert(e,phi))
m = pow(c,d,n)
print(m)
print(libnum.n2s(m))

8.[RoarCTF2019]babyRSA

明知道不行，我还是去算 B！。网上别人用Wilson定理来解。看到Wilson定理，这才恍然大悟。

• Wilson定理
  设p是一个素数，则(p-1)! = -1 (mod p)

因为A是素数，所以(A-1)! = -1(mod A)，又因为B<A，所以有B！ = -1 * (A-1)^-1 * (A-2)^-1 * … * (B+1)^-1 (mod A)，至此(B!)%A 就解决了，从而能求出p和q。
不过这里要注意的是n = p * q * r，所以phi = (p-1) * (q-1) * (r-1)。为什么n = p * q * r ？为什么不是 n = p * q?

''' import sympy import randomdef myGetPrime():A= getPrime(513)print(A)B=A-random.randint(1e3,1e5)print(B)return sympy.nextPrime((B!)%A)'''import gmpy2,libnum
import sympy
#p=myGetPrime()
A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596#q=myGetPrime()
A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026#r=myGetPrime()#Wilson定理 p为素数,(p-1)! = -1 mod p
def getpq(B,A):result = -1for i in range(B+1,A):pd = int(gmpy2.invert(i,A))result = (result*pd)%Areturn result#n=p*q*r
n = 85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
#c=pow(flag,e,n)
e = int('0x1001',16)
c = 75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
p = sympy.nextprime(getpq(B1,A1))
q = sympy.nextprime(getpq(B2,A2))
r = n//p//q
phi = (p-1)*(q-1)*(r-1)
d = int(gmpy2.invert(e,phi))
m = pow(c,d,n)
print(libnum.n2s(m))

9.[RoarCTF2019]RSA

用factordb网站分解n，得到p和q。e通过爆破来求得。因为e模phi不可能都有逆元，所以用try except来处理异常。

import gmpy2,libnum,sympy,binascii
from Crypto.Util.number import long_to_bytes,bytes_to_long
#A = (((y%x)**5)%(x%y))**2019+y**316+(y+1)/x
#p = gmpy2.nextprime(z*x*y)
#q = gmpy2.nextprime(z)
# p > qA = 2683349182678714524247469512793476009861014781004924905484127480308161377768192868061561886577048646432382128960881487463427414176114486885830693959404989743229103516924432512724195654425703453612710310587164417035878308390676612592848750287387318129424195208623440294647817367740878211949147526287091298307480502897462279102572556822231669438279317474828479089719046386411971105448723910594710418093977044179949800373224354729179833393219827789389078869290217569511230868967647963089430594258815146362187250855166897553056073744582946148472068334167445499314471518357535261186318756327890016183228412253724
n = 117930806043507374325982291823027285148807239117987369609583515353889814856088099671454394340816761242974462268435911765045576377767711593100416932019831889059333166946263184861287975722954992219766493089630810876984781113645362450398009234556085330943125568377741065242183073882558834603430862598066786475299918395341014877416901185392905676043795425126968745185649565106322336954427505104906770493155723995382318346714944184577894150229037758434597242564815299174950147754426950251419204917376517360505024549691723683358170823416757973059354784142601436519500811159036795034676360028928301979780528294114933347127
c = 41971850275428383625653350824107291609587853887037624239544762751558838294718672159979929266922528917912189124713273673948051464226519605803745171340724343705832198554680196798623263806617998072496026019940476324971696928551159371970207365741517064295956376809297272541800647747885170905737868568000101029143923792003486793278197051326716680212726111099439262589341050943913401067673851885114314709706016622157285023272496793595281054074260451116213815934843317894898883215362289599366101018081513215120728297131352439066930452281829446586562062242527329672575620261776042653626411730955819001674118193293313612128#factordb
p = 842868045681390934539739959201847552284980179958879667933078453950968566151662147267006293571765463137270594151138695778986165111380428806545593588078365331313084230014618714412959584843421586674162688321942889369912392031882620994944241987153078156389470370195514285850736541078623854327959382156753458569
q = 139916095583110895133596833227506693679306709873174024876891023355860781981175916446323044732913066880786918629089023499311703408489151181886568535621008644997971982182426706592551291084007983387911006261442519635405457077292515085160744169867410973960652081452455371451222265819051559818441257438021073941183
phi =(p-1)*(q-1)
e = 2
while e < 100000:try:d = int(gmpy2.invert(e,phi))m = pow(c,d,n)m = str(long_to_bytes(m))if 'CTF' in m:print(m)except:passe = sympy.nextprime(e)

10.[HDCTF2019]together

公钥解析求出两个加密的e和n，发现n相同，是共模攻击。另外两个文件里面是base64编码，应该是密文，只通过base64解码只能得到一串’\x '的东西，需要进行bytes_to_long()转换成数字，毕竟写过的题目里面的c都是大数，所以把它转成数字，

import libnum,gmpy2,base64
from Crypto.Util.number import long_to_bytes,bytes_to_long
e1 = 2333
e2 = 23333
n = 14853081277902411240991719582265437298941606850989432655928075747449227799832389574251190347654658701773951599098366248661597113015221566041305501996451638624389417055956926238595947885740084994809382932733556986107653499144588614105694518150594105711438983069306254763078820574239989253573144558449346681620784979079971559976102366527270867527423001083169127402157598183442923364480383742653117285643026319914244072975557200353546060352744263637867557162046429886176035616570590229646013789737629785488326501654202429466891022723268768841320111152381619260637023031430545168618446134188815113100443559425057634959299
c1 = base64.b64decode('R3Noy6r3WLItytAmb4FmHEygoilucEEZbO9ZYXx5JN03HNpBLDx7fXd2fl+UL5+11RCs/y0qlTGURWWDtG66eNLzGwNpAKiVj6I7RtUJl2Pcm3NvFeAFwI9UsVREyh7zIV6sI9ZP8l/2GVDorLAz5ULW+f0OINGhJmZm8FL/aDnlfTElhQ87LPicWpXYoMtyr6WrxjK6Ontn8BqCt0EjQ7TeXZhxIH9VTPWjDmFdmOqaqdVIT+LZemTgLNESwM5nn4g5S3aFDFwj1YiDYl0/+8etvKfOrfoKOwR0CxsRHagwdUUTES8EcHLmMGCxCkDZn3SzmmA6Nb3lgLeSgG8P1A==')
c2 = base64.b64decode('O+rRCXI3aTB6P1rYIOPUdalUp6ujpwEq4I20CoWA+HIL8xxGtqY6N5gpr0guZv9ZgOEAMFnBxOqMdVNnB9GgnhmXtt1ZWydPqIcHvlfwpd/Lyd0XSjXnjaz3P3vOQvR71cD/uXyBA0XPzmnTIMgEhuGJVFm8min0L/2qI7wg/Z7w1+4mOmi655JIXeCiG23ukDv6l9bZuqfGvWCa1KKXWDP31nLbp0ZN2obUs6jEAa1qVTaX6M4My+sks+0VvHATrAUuCrmMwVEivqIJ/nS6ymGVERN6Ohnzyr168knEBKOVj0FAOx3YLfppMM+XbOGHeqdKJRLpMvqFXDMGQInT3w==')
c1,c2 = bytes_to_long(c1),bytes_to_long(c2)
gcd = gmpy2.gcdext(e1,e2)
s,t = int(gcd[1]),int(gcd[2])
m = pow(c1,s,n)*pow(c2,t,n)%n
print(libnum.n2s(m))