CTFZone 2021 WriteUp —— CSALab_Sec
Welcome Task:
flag:
ctfzone{w3lc0m3_t0_th3_n3w_3r}Kupferschmied:
rsa给出了去掉了低256位的p，利用已知高位攻击：
sage脚本如下：
n=17408501387761496422571387531255186395594822625427018891931944274948424531840216804087406016201792609748639929234296711971006012525921492918677094417191621332330736111601665865736555524248675576283234365640108546272991072207602044576112932673004330047590294978687908382405473010869244156261269605749387676770380679964792778882683915037857456922851572226870054273144693323373449850410871470997876341208204079943211614798111409509469703286696609862614115550797655677627165801785377057385818348554957219344657509473038869337457657726576119314363978080667672646829814723388079633788309158417386736009981786671111112505803p4=0xaa0f7afd50596b48004229329331258e7a3508e16898b76b134d6f5a2b009873b8a863ed506fa55a6a3140db3b1c9eec46cab0ce6608d56026cb62dad05f5ead1a6a6ebb26421621632c5e7b647124b0e9d016f395e139fada264628202f7af5e=65537pbits=1024 #P原本的位数kbits = pbits - p4.nbits()p4.nbits()p4 = p4 << kbitsPR.<x> = PolynomialRing(Zmod(n))f = x + p4roots = f.small_roots(X=2^kbits,beta=0.4)# 经过以上一些函数处理后，n和p已经被转化为10进制if roots:p = p4 + int(roots[0])print ("p",p)print ("q",n/p)#p = 119420523510623090846833793146222404943223285889905397168353912719187632695735948651401226047990503394729751314186553881321576118296503852722223763684189725197775635180409932855355015210533150489165617903913700213161301171347867072150249238127415724079733797238630408776703514960152445701873599721261206430401#q = 145774787080153082868047117797147268461414574587849978224739443341799752161105851314801720474592840202972362161463697336621078360431351937301009018700401475017115594434629937870750548863469584724485884588099790402070054463556504669977882300829443680604954474369500514425404137431833382351548196370382665374603
得到 p q之后即可解密：
import gmpy2p = 119420523510623090846833793146222404943223285889905397168353912719187632695735948651401226047990503394729751314186553881321576118296503852722223763684189725197775635180409932855355015210533150489165617903913700213161301171347867072150249238127415724079733797238630408776703514960152445701873599721261206430401q = 145774787080153082868047117797147268461414574587849978224739443341799752161105851314801720474592840202972362161463697336621078360431351937301009018700401475017115594434629937870750548863469584724485884588099790402070054463556504669977882300829443680604954474369500514425404137431833382351548196370382665374603e = 65537c = 13379049231117532190657453732616073467792859161985883227181972507288510795162724703440583569549454207533110491760618847771838821216322814621290028928001947821505573944034675857472874883203679148854891438911854405538005691430502229662893665845524700146320897213036827063648644226906564140678401342163126370500363614868513470016023732653611112525057113030386163104323085429601812094775062497285554446279651447305571612018449904401222576586054803969482102683062018183392582432901510221006910302847026799209146553472024321478232424369745325324045939637623758793410313304754800395675157502461205254266210454626140853239295n = 17408501387761496422571387531255186395594822625427018891931944274948424531840216804087406016201792609748639929234296711971006012525921492918677094417191621332330736111601665865736555524248675576283234365640108546272991072207602044576112932673004330047590294978687908382405473010869244156261269605749387676770380679964792778882683915037857456922851572226870054273144693323373449850410871470997876341208204079943211614798111409509469703286696609862614115550797655677627165801785377057385818348554957219344657509473038869337457657726576119314363978080667672646829814723388079633788309158417386736009981786671111112505803d = gmpy2.invert(e,(p-1)*(q-1))print (hex(pow(c,d,n)))
flag:
cftzone{w4rmup_f0r_scr1pt_k1dd13s}