如果你的训练量常人都能接受，冠军凭什么是你
[CISCN 2021初赛]rsa
附件
from flag import text,flag
import md5
from Crypto.Util.number import long_to_bytes,bytes_to_long,getPrime
assert md5.new(text).hexdigest() == flag[6:-1]
msg1 = text[:xx]
msg2 = text[xx:yy]
msg3 = text[yy:]
msg1 = bytes_to_long(msg1)
msg2 = bytes_to_long(msg2)
msg3 = bytes_to_long(msg3)
p1 = getPrime(512)
q1 = getPrime(512)
N1 = p1*q1
e1 = 3
print pow(msg1,e1,N1)
print (e1,N1)
p2 = getPrime(512)
q2 = getPrime(512)
N2 = p2*q2
e2 = 17
e3 = 65537
print pow(msg2,e2,N2)
print pow(msg2,e3,N2)
print (e2,N2)
print (e3,N2)
p3 = getPrime(512)
q3 = getPrime(512)
N3 = p3*q3
print pow(msg3,e3,N3)
print (e3,N3)
print p3>>200
思路
首先可以很容易的发现这题分成三段去进行加密，第一段e=3就可以直接判断出来是小明文加密，直接对c1开三次方就好，第二段共用一个e和n去进行加密，就是最经典的共模加密，直接套用脚本()，第三段p右移200位，那就是已知p高位，直接写就可以了，然后把三段m1转化后相加再用md5加密就可以求出来最后的flag。
exp
c1=19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893
e1=3
n1=123814470394550598363280518848914546938137731026777975885846733672494493975703069760053867471836249473290828799962586855892685902902050630018312939010564945676699712246249820341712155938398068732866646422826619477180434858148938235662092482058999079105450136181685141895955574548671667320167741641072330259009
c2=54995751387258798791895413216172284653407054079765769704170763023830130981480272943338445245689293729308200574217959018462512790523622252479258419498858307898118907076773470253533344877959508766285730509067829684427375759345623701605997067135659404296663877453758701010726561824951602615501078818914410959610
c3=91290935267458356541959327381220067466104890455391103989639822855753797805354139741959957951983943146108552762756444475545250343766798220348240377590112854890482375744876016191773471853704014735936608436210153669829454288199838827646402742554134017280213707222338496271289894681312606239512924842845268366950
e2=17
e3=65537
n2=111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977
c4=59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646
n3=113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
ph=7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902
from Crypto.Util.number import*
import gmpy2
from hashlib import md5
m1=gmpy2.iroot(c1,3)[0]
print(long_to_bytes(m1))
r,s1,s2 = gmpy2.gcdext(e2, e3)
m2 = (pow(c2,s1,n2)*pow(c3,s2,n2)) % n2
print(long_to_bytes(m2))
”’
用sage跑
n = 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
p4 =7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902
pbits = 512
kbits = pbits – p4.nbits()
print(p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits, beta=0.4)
if roots:
p = p4 + int(roots[0])
q = n//p
print(f’n: {n}’)
print(f’p: {p}’)
print(f’q: {q}’)
”’
p3=11437038763581010263116493983733546014403343859218003707512796706928880848035239990740428334091106443982769386517753703890002478698418549777553268906496423
q3= 9918033198963879798362329507637256706010562962487329742400933192721549307087332482107381554368538995776396557446746866861247191248938339640876368268930589
d3=inverse(e3,(p3-1)*(q3-1))
m3=pow(c4,d3,n3)
print(long_to_bytes(m3))
flag=long_to_bytes(m1)+long_to_bytes(m2)+long_to_bytes(m3)
print(md5(flag).hexdigest())
#3943e8843a19149497956901e5d98639
[GWCTF 2019]babyRSA
附件
import hashlib
import sympy
from Crypto.Util.number import *
flag = ‘GWHT{******}’
secret = ‘******’
assert(len(flag) == 38)
half = len(flag) / 2
flag1 = flag[:half]
flag2 = flag[half:]
secret_num = getPrime(1024) * bytes_to_long(secret)
p = sympy.nextprime(secret_num)
q = sympy.nextprime(p)
N = p * q
e = 0x10001
F1 = bytes_to_long(flag1)
F2 = bytes_to_long(flag2)
c1 = F1 + F2
c2 = pow(F1, 3) + pow(F2, 3)
assert(c2 < N)
m1 = pow(c1, e, N)
m2 = pow(c2, e, N)
output = open(‘secret’, ‘w’)
output.write(‘N=’ + str(N) + ‘\n’)
output.write(‘m1=’ + str(m1) + ‘\n’)
output.write(‘m2=’ + str(m2) + ‘\n’)
output.close()
思路
首先尝试分解n，发现直接可以得到p和q，那么就可以求出来c1和c2，这个时候要是头铁的可以直接推关系去求出f1和f2，当然，sympy和z3库可以直接去解方程，如果不会的可以去学一下，十分方便好用。
exp
N=636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
m1=90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
m2=487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546
e = 0x10001
from Crypto.Util.number import *
import gmpy2
import sympy
p=797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377747699
q=797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377748737
phi=(p-1)*(q-1)
d=inverse(e,phi)
c1=pow(m1,d,N)
c2=pow(m2,d,N)
f1,f2=sympy.symbols(‘f1 f2’)
a=sympy.solve([f1+f2-c1,pow(f1,3)+pow(f2,3)-c2],[f1,f2])
print(a)
f1=1590956290598033029862556611630426044507841845
f2=1141553212031156130619789508463772513350070909
print(long_to_bytes(f1)+long_to_bytes(f2))
#GWHT{f709e0e2cfe7e530ca8972959a1033b2}
[LitCTF 2023]yafu (中级)
附件
from Crypto.Util.number import *
from secret import flag
m = bytes_to_long(flag)
n = 1
for i in range(15):
n *=getPrime(32)
e = 65537
c = pow(m,e,n)
print(f’n = {n}’)
print(f’c = {c}’)
”’
n = 15241208217768849887180010139590210767831431018204645415681695749294131435566140166245881287131522331092026252879324931622292179726764214435307
c = 12608550100856399369399391849907846147170257754920996952259023159548789970041433744454761458030776176806265496305629236559551086998780836655717
”’
思路
题目都明示让我去分解了，那就按照他的意思来，用了风二西佬的工具，直接出来了。
[RoarCTF 2019]babyRSA
附件
import sympy
import random
def myGetPrime():
A= getPrime(513)
print(A)
B=A-random.randint(1e3,1e5)
print(B)
return sympy.nextPrime((B!)%A)
p=myGetPrime()
#A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
#B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
q=myGetPrime()
#A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
#B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
r=myGetPrime()
n=p*q*r
#n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
c=pow(flag,e,n)
#e=0x1001
#c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
#so,what is the flag?
思路
这个题中的n是可以去分解的，恰好就可以出来pqr，当然这个是非预期的做法，预期做法应该是威尔逊定理，可以去了解一下，那么题目中的B! mod A就可以去写成Z=(A-1)*(A-2)*…(B!),然后可以进一步去写Z=-1(mod A)，进一步化简为(A-2)*…(B!)=1(mod A)，那么这个题就出来了。
exp
from Crypto.Util.number import long_to_bytes
from gmpy2 import *
from sympy import nextprime
def get_p_q(A,B):
tmp = 1
for i in range(B+1,A-1):
tmp *= i
tmp %= A
tmp_inv = invert(tmp,A)
result = nextprime(tmp_inv)
return result
A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
n = 85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
e = 0x1001
c = 75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
p = get_p_q(A1,B1)
q = get_p_q(A2,B2)
r = n // p // q
phi = (p – 1) * (q – 1) * (r – 1)
d = invert(e, phi)
print(long_to_bytes(powmod(c, d, n)))
#RoarCTF{wm-CongrAtu1ation4-1t4-ju4t-A-bAby-R4A}
[LitCTF 2023]P_Leak
附件
from Crypto.Util.number import *
e=65537
m=bytes_to_long(b’xxxx’)
p=getPrime(512)
q=getPrime(512)
n=p*q
phi=(p-1)*(q-1)
d=inverse(e,phi)
dp=d%(p-1)
c=pow(m,e,n)
print(“dp=”,dp)
print(“n=”,n)
print(“c=”,c)
#dp= 5892502924236878675675338970704766304539618343869489297045857272605067962848952532606770917225218534430490745895652561015493032055636004130931491316020329
#n= 50612159190225619689404794427464916374543237300894011803225784470008992781409447214236779975896311093686413491163221778479739252804271270231391599602217675895446538524670610623369953168412236472302812808639218392319634397138871387898452935081756580084070333246950840091192420542761507705395568904875746222477
#c= 39257649468514605476432946851710016346016992413796229928386230062780829495844059368939749930876895443279723032641876662714088329296631207594999580050131450251288839714711436117326769029649419789323982613380617840218087161435260837263996287628129307328857086987521821533565738409794866606381789730458247531619
思路
很明显的最简单的dp泄露，直接写脚本就好了，如果不知道什么是dp泄露的话可以去nss上面看看。
exp
dp= 5892502924236878675675338970704766304539618343869489297045857272605067962848952532606770917225218534430490745895652561015493032055636004130931491316020329
n= 50612159190225619689404794427464916374543237300894011803225784470008992781409447214236779975896311093686413491163221778479739252804271270231391599602217675895446538524670610623369953168412236472302812808639218392319634397138871387898452935081756580084070333246950840091192420542761507705395568904875746222477
c= 39257649468514605476432946851710016346016992413796229928386230062780829495844059368939749930876895443279723032641876662714088329296631207594999580050131450251288839714711436117326769029649419789323982613380617840218087161435260837263996287628129307328857086987521821533565738409794866606381789730458247531619
e=65537
from Crypto.Util.number import *
for i in range(1,e):
if (dp*e-1)%i==0:
if n%(((dp*e-1)//i)+1)==0:
p=(dp*e-1)//i+1
q=n//p
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))
[HUBUCTF 2022 新生赛]RSAaaa
附件
就你小子是黑客？
我忘记怎么解密了！
靠你了，大黑阔！
(536970330703, 65537)
message: 473878130775 40132555282 40132555282 94619939727 72818765591 208015808884 42561234694 159353248388 27748063975 159353248388 159353248388 278953790403 410746718603 496849210942 27748063975 142521857906 103632267191 17774494147 328684046745 278953790403 129956887006 129956887006 366275425558 328684046745 142521857906 410746718603 142521857906 129956887006 379067009467 328684046745 159353248388 366275425558 129956887006 103632267191 27748063975 27748063975 17774494147 160623996897 278953790403 182341799525
思路
给了n，e和一堆c，直接先把n分解，那么phi有了，只需要去遍历每一个c就可以去求出flag了
exp
n=536970330703
e=65537
p=540961
q=992623
m=[473878130775, 40132555282 ,40132555282 ,94619939727 ,72818765591, 208015808884, 42561234694 ,159353248388, 27748063975, 159353248388 ,159353248388 ,278953790403, 410746718603 ,496849210942, 27748063975, 142521857906, 103632267191, 17774494147 ,328684046745 ,278953790403, 129956887006, 129956887006, 366275425558 ,328684046745 ,142521857906 ,410746718603 ,142521857906 ,129956887006, 379067009467, 328684046745 ,159353248388 ,366275425558, 129956887006, 103632267191, 27748063975 ,27748063975 ,17774494147, 160623996897 ,278953790403, 182341799525]
import gmpy2
from Crypto.Util.number import *
phi=(p-1)*(q-1)
d=inverse(e,phi)
flag=”
for i in m:
flag+=str(long_to_bytes(pow(int(i),d,n)).decode())
print(flag)
[HGAME 2022 week2]RSA Attack2
附件
import re
from math import ceil
from Crypto.Util.number import getPrime
from libnum import s2n
from secret import flag
flag_parts = list(map(s2n, re.findall(rf”.{{,{ceil(len(flag) / 3)}}}”, flag)))
print(“# task1”)
m = flag_parts[0]
e = 65537
p = getPrime(1024)
q = getPrime(1024)
r = getPrime(1024)
n1 = p * q
c1 = pow(m, e, n1)
n2 = r * q
c2 = pow(m, e, n2)
print(“e =”, e)
print(“n1 =”, n1)
print(“c1 =”, c1)
print(“n2 =”, n2)
print(“c2 =”, c2)
print(“# task2”)
m = flag_parts[1]
e = 7
p = getPrime(1024)
q = getPrime(1024)
n = p * q
c = pow(m, e, n)
print(“e =”, e)
print(“n =”, n)
print(“c =”, c)
print(“# task3”)
m = flag_parts[2]
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e1 = getPrime(32)
e2 = getPrime(32)
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)
print(“n =”, n)
print(“e1 =”, e1)
print(“c1 =”, c1)
print(“e2 =”, e2)
print(“c2 =”, c2)
思路
很明显这是三段加密，第一段就是n1和n2有个公因子q，所以p也得到了，m1就出来了，第二段e为7是小明文加密，尝试直接开7次方，得到m2，第三段两组ec公用一个n，直接就是共模攻击直接写，得到m3，一块输出得到完整的flag。
exp
# task1
e = 65537
n1 = 14611545605107950827581005165327694782823188603151768169731431418361306231114985037775917461433925308054396970809690804073985835376464629860609710292181368600618626590498491850404503443414241455487304448344892337877422465715709154238653505141605904184985311873763495761345722155289457889686019746663293720106874227323699288277794292208957172446523420596391114891559537811029473150123641624108103676516754449492805126642552751278309634846777636042114135990516245907517377320190091400729277307636724890592155256437996566160995456743018225013851937593886086129131351582958811003596445806061492952513851932238563627194553
c1 = 965075803554932988664271816439183802328812013694203741320763105376036912584995031647672348468111310423680858101990670067065306237596121664884353679987689532305437801346923070145524106271337770666947677115752724993307387122132705797012726237073550669419110046308257408484535063515678066777681017211510981429273346928022971149411064556225001287399141306136081722471075032423079692908380267160214143720516748000734987068685104675254411687005690312116824966036851568223828884335112144637268090397158532937141122654075952730052331573980701136378212002956719295192733955673315234274064519957670199895100508623561838510479
n2 = 20937478725109983803079185450449616567464596961348727453817249035110047585580142823551289577145958127121586792878509386085178452171112455890429474457797219202827030884262273061334752493496797935346631509806685589179618367453992749753318273834113016237120686880514110415113673431170488958730203963489455418967544128619234394915820392908422974075932751838012185542968842691824203206517795693893863945100661940988455695923511777306566419373394091907349431686646485516325575494902682337518438042711296437513221448397034813099279203955535025939120139680604495486980765910892438284945450733375156933863150808369796830892363
c2 = 11536506945313747180442473461658912307154460869003392732178457643224057969838224601059836860883718459986003106970375778443725748607085620938787714081321315817144414115589952237492448483438910378865359239575169326116668030463275817609827626048962304593324479546453471881099976644410889657248346038986836461779780183411686260756776711720577053319504691373550107525296560936467435283812493396486678178020292433365898032597027338876045182743492831814175673834198345337514065596396477709839868387265840430322983945906464646824470437783271607499089791869398590557314713094674208261761299894705772513440948139429011425948090
# task2
e = 7
n3 = 14157878492255346300993349653813018105991884577529909522555551468374307942096214964604172734381913051273745228293930832314483466922529240958994897697475939867025561348042725919663546949015024693952641936481841552751484604123097148071800416608762258562797116583678332832015617217745966495992049762530373531163821979627361200921544223578170718741348242012164115593777700903954409103110092921578821048933346893212805071682235575813724113978341592885957767377587492202740185970828629767501662195356276862585025913615910839679860669917255271734413865211340126544199760628445054131661484184876679626946360753009512634349537
c3 = 10262871020519116406312674685238364023536657841034751572844570983750295909492149101500869806418603732181350082576447594766587572350246675445508931577670158295558641219582729345581697448231116318080456112516700717984731655900726388185866905989088504004805024490513718243036445638662260558477697146032055765285263446084259814560197549018044099935158351931885157616527235283229066145390964094929007056946332051364474528453970904251050605631514869007890625
# task3
n4 = 18819509188106230363444813350468162056164434642729404632983082518225388069544777374544142317612858448345344137372222988033366528086236635213756227816610865045924357232188768913642158448603346330462535696121739622702200540344105464126695432011739181531217582949804939555720700457350512898322376591813135311921904580338340203569582681889243452495363849558955947124975293736509426400460083981078846138740050634906824438689712748324336878791622676974341814691041262280604277357889892211717124319329666052810029131172229930723477981468761369516771720250571713027972064974999802168017946274736383148001865929719248159075729
e1 = 2519901323
c4 = 3230779726225544872531441169009307072073754578761888387983403206364548451496736513905460381907928107310030086346589351105809028599650303539607581407627819797944337398601400510560992462455048451326593993595089800150342999021874734748066692962362650540036002073748766509347649818139304363914083879918929873577706323599628031618641793074018304521243460487551364823299685052518852685706687800209505277426869140051056996242882132616256695188870782634310362973153766698286258946896866396670872451803114280846709572779780558482223393759475999103607704510618332253710503857561025613632592682931552228150171423846203875344870
e2 = 3676335737
c5 = 940818595622279161439836719641707846790294650888799822335007385854166736459283129434769062995122371073636785371800857633841379139761091890426137981113087519934854663776695944489430385663011713917022574342380155718317794204988626116362865144125136624722782309455452257758808172415884403909840651554485364309237853885251876941477098008690389600544398998669635962495989736021020715396415375890720335697504837045188626103142204474942751410819466379437091569610294575687793060945525108986660851277475079994466474859114092643797418927645726430175928247476884879817034346652560116597965191204061051401916282814886688467861
from Crypto.Util.number import*
import gmpy2
#1
q1=gmpy2.gcd(n1,n2)
p1=n1//q1
phi1=(p1-1)*(q1-1)
d1=inverse(65537,phi1)
m1=pow(c1,d1,n1)
print(long_to_bytes(m1))
#2
m2=gmpy2.iroot(c3,7)[0]
print(long_to_bytes(m2))
#3
r,s1,s2 = gmpy2.gcdext(e1, e2)
m3 = (pow(c4,s1,n4)*pow(c5,s2,n4)) % n4
print(long_to_bytes(m3))
print(long_to_bytes(m1)+long_to_bytes(m2)+long_to_bytes(m3))
今天就到此结束了，有一些纯纯分解的题就没有拉上来，下机！
（2024.4.6）