picoCTF 密码学方向RSA算法做题记录

RSA算法原理：

https://blog.csdn.net/qq_45894840/article/details/128204460?spm=1001.2014.3001.5502

Mind your Ps and Qs

题目描述：In RSA, a small e value can be problematic, but what about N? Can you decrypt this?

下载题目

在这里可以看到三个值，c，n和e，关于原理，可以去看我之前写的这个文章

https://blog.csdn.net/qq_45894840/article/details/128204460

python模块安装

pip3 install factordb-pycli
pip3 install gmpy2

现在我们写一个小脚本来破解

from factordb.factordb import FactorDB
import gmpy2

c = 240986837130071017759137533082982207147971245672412893755780400885108149004760496
n = 831416828080417866340504968188990032810316193533653516022175784399720141076262857
e = 65537
//导入c，n，e的值

f = FactorDB(n)   //因为n不大，这里直接分解q和p的值
f.connect()
p, q = f.get_factor_list()  //获取因素列表
ph = (p-1)*(q-1)  //获取φ(n)值，之后计算私钥值
d = gmpy2.invert(e, ph) //有了e值和φ(n)值，可以计算私钥值
plaintext = pow(c, d, n)  //解密
print(bytearray.fromhex(format(plaintext, 'x')).decode())  //将十六进制字符串转换为字节后解密

运行脚本，得到flag值

picoCTF{sma11_N_n0_g0od_23540368}

Mini RSA

题目描述：What happens if you have a small exponent? There is a twist though, we padded the plaintext so that (M ** e) is just barely larger than N. Let’s decrypt this:

下载题目

这里有三个值，n，e和c值，根据题目描述提示M ^ e刚比N大，意思是：

M^3 mod n = c

t值可以写成：

M^3 = tn + c

根据以上推理，可以得出：

M = iroot(tn+c, 3) //iroot是gmpy2模块的一个函数，作用是给a开b次方

现在我们写一个小脚本来获得flag

import gmpy2

n = 1615765684321463054078226051959887884233678317734892901740763321135213636796075462401950274602405095138589898087428337758445013281488966866073355710771864671726991918706558071231266976427184673800225254531695928541272546385146495736420261815693810544589811104967829354461491178200126099661909654163542661541699404839644035177445092988952614918424317082380174383819025585076206641993479326576180793544321194357018916215113009742654408597083724508169216182008449693917227497813165444372201517541788989925461711067825681947947471001390843774746442699739386923285801022685451221261010798837646928092277556198145662924691803032880040492762442561497760689933601781401617086600593482127465655390841361154025890679757514060456103104199255917164678161972735858939464790960448345988941481499050248673128656508055285037090026439683847266536283160142071643015434813473463469733112182328678706702116054036618277506997666534567846763938692335069955755244438415377933440029498378955355877502743215305768814857864433151287
e = 3
c = 1220012318588871886132524757898884422174534558055593713309088304910273991073554732659977133980685370899257850121970812405700793710546674062154237544840177616746805668666317481140872605653768484867292138139949076102907399831998827567645230986345455915692863094364797526497302082734955903755050638155202890599808154521995312832362835648711819155169679435239286935784452613518014043549023137530689967601174246864606495200453313556091158637122956278811935858649498244722557014003601909465057421728834883411992999408157828996722087360414577252630186866387785481057649036414986099181831292644783916873710123009473008639825720434282893177856511819939659625989092206115515005188455003918918879483234969164887705505900695379846159901322053253156096586139847768297521166448931631916220211254417971683366167719596219422776768895460908015773369743067718890024592505393221967098308653507944367482969331133726958321767736855857529350486000867434567743580745186277999637935034821461543527421831665171525793988229518569050
//导入n，e，c的值

for i in range(10000):   //遍历循环，找到m值
    m, t = gmpy2.iroot(i*n + c, e)
    if t:
        print(bytearray.fromhex(format(m, 'x')).decode()) //将十六进制字符串转换为字节后解密
        break

运行脚本，获得flag

picoCTF{e_sh0u1d_b3_lArg3r_a166c1e3}

Dachshund Attacks

题目描述：What if d is too small? Connect with nc mercury.picoctf.net 41508

可以得到e，n和c的值，根据题目提示，Wiener’s attack是一个针对RSA密码的攻击

https://en.wikipedia.org/wiki/Wiener%27s_attack

直接用rsactftool脚本跑

https://github.com/RsaCtfTool/RsaCtfTool

python3 RsaCtfTool.py -n 73858245204393269120598772974257218874289179816258533748548954836353808000542909731398449660121424717248079724923923284922221800385870164798744402737063530114487159042350959711492581286948377310386675916734743955708759421607349585475823504183537132290212235481788134354234151518170214048887523664730897405647 -e 40185337488228965483088768689361237580655397969352079774015797079626751211817603607155962600219370112069853693506378621129705581863959239984871073674637310005220323695488701830477574210150173980203084059519439551150923764323395592278383658383525721471839777239932693638775164411928659371101425091253226312809 --uncipher 11279019002658132246395680583012680197641520463055015905954159065596263829466315684813964601637222796742820040947867106250604831640789683230174556440623073026811900236014477245382133062014821631152893829897692611106964558955134460480794092202226246351625569961925929573208935964302390747204250124554416009841 --attack wiener

得到flag

picoCTF{proving_wiener_1146084}

No Padding, No Problem

题目描述：Oracles can be your best friend, they will decrypt anything, except the flag’s ciphertext. How will you break it? Connect with nc mercury.picoctf.net 33780

可以得到n，e和c值，他可以帮我们解密一些东西，除了这个密文

根据题目提示，未填充的RSA是同态加密

https://en.wikipedia.org/wiki/Homomorphic_encryption

意思是：

encrypt(m1) * encrypt(m2) = ((m1^e) * (m2^e)) mod n = (m1 * m2)^e mod n = encrypt(m1 * m2)

我们写一个小脚本，对它进行加密，然后让服务器给我们解密

n = 51257263015582188197648371474129549390905726426257438448153816359702362365658508334422660676137191608574589301862860723036048910648313371474365316649888203989162930646519011433136231329260451213231902920703710354241532734042339059649207865410951756937740333312020743615116676965217774179610963694893894058993
e = 65537
c = 4630900525813217788908324506108030714601444705261980401094718094759603138876572869225585464832937171107712654868912146981974620187638194979958086597403998901460677636640013168017847942623819676132193036153903064536382635689292213133256195449181769142311263486211152780709880862212814932262615707105931438936


x = pow(2, e, n)
print(c * x)

运行脚本，得到加密后的值

根据官方文档，c * x = encrypt(m) * encrypt(2) = encrypt(m * 2)，现在我们去服务器上解密

得到了m * 2的值，将这个值除以2得到m

m = 580550060391700078946913236734911770139931497702556153513487440893406629034802718534645538074938502890769425795379846471930 // 2

print(bytearray.fromhex(format(m, 'x')).decode())

运行脚本，得到flag

picoCTF{m4yb3_Th0se_m3s54g3s_4r3_difurrent_5052620}

Scrambled: RSA

题目描述：Description
Hmmm I wonder if you have learned your lesson… Let’s see if you understand RSA and how the encryption works. Connect with nc mercury.picoctf.net 50075

连接之后，它会问你一些很基础的问题

给了你q和p值，叫我们求n值，并且还问我们n值能求出来吗

n = pq

q = 60413
p = 76753
n = p*q

print(n)
//4636878989

成功通过第一关，第二关给了我们p和n值，需要求q值

q = n // p

p = 54269
n = 5051846941
q = n // p

print(q)
//93089

第三关给了我们e和n值，叫我们求p和q的值，因为条件不够(没有t的值)，这里选n

来到第四关，这里给了我们q和p的值，叫我们求toitent(n)的值

totient(n) = (p – 1) * (q – 1)

def totient(p, q):
    return (p - 1)*(q - 1)
 
q = 66347
p = 12611

print(totient(q, p))
//836623060

成功通过第四关，第五关给了我们plaintest和e，n的值，叫我们加密，直接加密即可

def encryption(plaintext, e, n):
    return (plaintext**e) % n
plaintext = 6357294171489311547190987615544575133581967886499484091352661406414044440475205342882841236357665973431462491355089413710392273380203038793241564304774271529108729717
e = 3
n = 29129463609326322559521123136222078780585451208149138547799121083622333250646678767769126248182207478527881025116332742616201890576280859777513414460842754045651093593251726785499360828237897586278068419875517543013545369871704159718105354690802726645710699029936754265654381929650494383622583174075805797766685192325859982797796060391271817578087472948205626257717479858369754502615173773514087437504532994142632207906501079835037052797306690891600559321673928943158514646572885986881016569647357891598545880304236145548059520898133142087545369179876065657214225826997676844000054327141666320553082128424707948750331

print(encryption(plaintext,e, n)) 
//256931246631782714357241556582441991993437399854161372646318659020994329843524306570818293602492485385337029697819837182169818816821461486018802894936801257629375428544752970630870631166355711254848465862207765051226282541748174535990314552471546936536330397892907207943448897073772015986097770443616540466471245438117157152783246654401668267323136450122287983612851171545784168132230208726238881861407976917850248110805724300421712827401063963117423718797887144760360749619552577176382615108244813

第六关给了我们c，n和e值，叫我们解密我们不知道p和q值，这里选n

第七关给了我们q、p和e值，需要计算出d值

d ≡ e^−1 (mod φ(n))

from Crypto.Util.number import inverse

q = 92092076805892533739724722602668675840671093008520241548191914215399824020372076186460768206814914423802230398410980218741906960527104568970225804374404612617736579286959865287226538692911376507934256844456333236362669879347073756238894784951597211105734179388300051579994253565459304743059533646753003894559
p = 97846775312392801037224396977012615848433199640105786119757047098757998273009741128821931277074555731813289423891389911801250326299324018557072727051765547115514791337578758859803890173153277252326496062476389498019821358465433398338364421624871010292162533041884897182597065662521825095949253625730631876637
e = 65537

print(inverse(e, (p-1)*(q-1)))
//1405046269503207469140791548403639533127416416214210694972085079171787580463776820425965898174272870486015739516125786182821637006600742140682552321645503743280670839819078749092730110549881891271317396450158021688253989767145578723458252769465545504142139663476747479225923933192421405464414574786272963741656223941750084051228611576708609346787101088759062724389874160693008783334605903142528824559223515203978707969795087506678894006628296743079886244349469131831225757926844843554897638786146036869572653204735650843186722732736888918789379054050122205253165705085538743651258400390580971043144644984654914856729

第八关给了p，c，e和n的值，叫我们求明文的值，我们写个小脚本直接跑

from Crypto.Util.number import inverse
p = 153143042272527868798412612417204434156935146874282990942386694020462861918068684561281763577034706600608387699148071015194725533394126069826857182428660427818277378724977554365910231524827258160904493774748749088477328204812171935987088715261127321911849092207070653272176072509933245978935455542420691737433
ciphertext = 18031488536864379496089550017272599246134435121343229164236671388038630752847645738968455413067773166115234039247540029174331743781203512108626594601293283737392240326020888417252388602914051828980913478927759934805755030493894728974208520271926698905550119698686762813722190657005740866343113838228101687566611695952746931293926696289378849403873881699852860519784750763227733530168282209363348322874740823803639617797763626570478847423136936562441423318948695084910283653593619962163665200322516949205854709192890808315604698217238383629613355109164122397545332736734824591444665706810731112586202816816647839648399
e = 65537
n = 23952937352643527451379227516428377705004894508566304313177880191662177061878993798938496818120987817049538365206671401938265663712351239785237507341311858383628932183083145614696585411921662992078376103990806989257289472590902167457302888198293135333083734504191910953238278860923153746261500759411620299864395158783509535039259714359526738924736952759753503357614939203434092075676169179112452620687731670534906069845965633455748606649062394293289967059348143206600765820021392608270528856238306849191113241355842396325210132358046616312901337987464473799040762271876389031455051640937681745409057246190498795697239

r = (p-1)*(n//p-1)
d = inverse(e,r)
m = pow(ciphertext, d, n)

print(m)
//14311663942709674867122208214901970650496788151239520971623411712977120586163535880168563325

然后它说，这个明文就是flag，我们转换即可

m = 14311663942709674867122208214901970650496788151239520971623411712977120586163535880168563325
print(bytearray.fromhex(format(m, 'x')).decode())

得到flag

picoCTF{wA8_th4t$_ill3aGal..ode01e4bb}

转载：https://blog.csdn.net/qq_45894840/article/details/128283475