PicoCTF2018 Cryptography RSA-Madlibs

PicoCTF2018 Cryptography RSA-Madlibs


Objective:
We ran into some weird puzzles we think may mean something, can you help me solve one? Connect with nc 2018shell.picoctf.com 50652

Solution:


Hello, Welcome to RSA Madlibs
Keeping young children entertained, since, well, nev3r
Tell us how to fill in the blanks, or if it's even possible to do so
Everything, input and output, is decimal, not hex
#### NEW MADLIB ####
q : 93187
p : 94603
##### WE'RE GONNA NEED THE FOLLOWING ####
n
IS THIS POSSIBLE and FEASIBLE? (Y/N):y

This is possible because n = pq
so we just simply multiply the numbers to get q

#### TIME TO FILL IN THE MADLIB! ###
n: 8815769761
YAHHH! That one was a great madlib!!!


#### NEW MADLIB ####
p : 81203
n : 6315400919
##### WE'RE GONNA NEED THE FOLLOWING ####
q
IS THIS POSSIBLE and FEASIBLE? (Y/N):y

This is also possible since n=pq  transitively we know that q=n/p

#### TIME TO FILL IN THE MADLIB! ###
q: 77773
YAHHH! That one was a great madlib!!!



#### NEW MADLIB ####
e : 3
n : 12738162802910546503821920886905393316386362759567480839428456525224226445173031635306683726182522494910808518920409019414034814409330094245825749680913204566832337704700165993198897029795786969124232138869784626202501366135975223827287812326250577148625360887698930625504334325804587329905617936581116392784684334664204309771430814449606147221349888320403451637882447709796221706470239625292297988766493746209684880843111138170600039888112404411310974758532603998608057008811836384597579147244737606088756299939654265086899096359070667266167754944587948695842171915048619846282873769413489072243477764350071787327913
##### WE'RE GONNA NEED THE FOLLOWING ####
q
p
IS THIS POSSIBLE and FEASIBLE? (Y/N):n
YAHHH! That one was a great madlib!!!


This is not possible be cause we would have no information about the two numbers that were multiplied to make n




#### NEW MADLIB ####
q : 78203
p : 79999
##### WE'RE GONNA NEED THE FOLLOWING ####
totient(n)

so n = pq:   n=78203*79999 n = 6256161797
Thanks to this website for the totient
http://www.javascripter.net/math/calculators/eulertotientfunction.htm

totient of 6256161797 is 6256003596



#### NEW MADLIB ####
plaintext : 1815907181716474805136452061793917684000871911998851410864797078911161933431337632774829806207517001958179617856720738101327521552576351369691667910371502971480153619360010341709624631317220940851114914911751279825748
e : 3
n : 29129463609326322559521123136222078780585451208149138547799121083622333250646678767769126248182207478527881025116332742616201890576280859777513414460842754045651093593251726785499360828237897586278068419875517543013545369871704159718105354690802726645710699029936754265654381929650494383622583174075805797766685192325859982797796060391271817578087472948205626257717479858369754502615173773514087437504532994142632207906501079835037052797306690891600559321673928943158514646572885986881016569647357891598545880304236145548059520898133142087545369179876065657214225826997676844000054327141666320553082128424707948750331
##### WE'RE GONNA NEED THE FOLLOWING ####
#### TIME TO FILL IN THE MADLIB! ###
ciphertext: 26722917505435451150596710555980625220524134812001687080485341361511207096550823814926607028717403343344600191255790864873639087129323153797404989216681535785492257030896045464472300400447688001563694767148451912130180323038978568872458130612657140514751874493071944456290959151981399532582347021031424096175747508579453024891862161356081561032045394147561900547733602483979861042957169820579569242714893461713308057915755735700329990893197650028440038700231719057433874201113850357283873424698585951160069976869223244147124759020366717935504226979456299659682165757462057188430539271285705680101066120475874786208053
YAHHH! That one was a great madlib!!!


Wrote small python script to bang this part out
following the encrypt Message to power of e mod n
n=29129463609326322559521123136222078780585451208149138547799121083622333250646678767769126248182207478527881025116332742616201890576280859777513414460842754045651093593251726785499360828237897586278068419875517543013545369871704159718105354690802726645710699029936754265654381929650494383622583174075805797766685192325859982797796060391271817578087472948205626257717479858369754502615173773514087437504532994142632207906501079835037052797306690891600559321673928943158514646572885986881016569647357891598545880304236145548059520898133142087545369179876065657214225826997676844000054327141666320553082128424707948750331
e=3
PT=1815907181716474805136452061793917684000871911998851410864797078911161933431337632774829806207517001958179617856720738101327521552576351369691667910371502971480153619360010341709624631317220940851114914911751279825748


temp = PT**3
print("temp: ",temp)
CT = temp%n
print("cipher: ",CT)




#### NEW MADLIB ####
ciphertext : 107524013451079348539944510756143604203925717262185033799328445011792760545528944993719783392542163428637172323512252624567111110666168664743115203791510985709942366609626436995887781674651272233566303814979677507101168587739375699009734588985482369702634499544891509228440194615376339573685285125730286623323
e : 3
n : 27566996291508213932419371385141522859343226560050921196294761870500846140132385080994630946107675330189606021165260590147068785820203600882092467797813519434652632126061353583124063944373336654246386074125394368479677295167494332556053947231141336142392086767742035970752738056297057898704112912616565299451359791548536846025854378347423520104947907334451056339439706623069503088916316369813499705073573777577169392401411708920615574908593784282546154486446779246790294398198854547069593987224578333683144886242572837465834139561122101527973799583927411936200068176539747586449939559180772690007261562703222558103359
##### WE'RE GONNA NEED THE FOLLOWING ####
plaintext

This is not possible to decrypt because we don't have the private key 




#### NEW MADLIB ####
q : 92092076805892533739724722602668675840671093008520241548191914215399824020372076186460768206814914423802230398410980218741906960527104568970225804374404612617736579286959865287226538692911376507934256844456333236362669879347073756238894784951597211105734179388300051579994253565459304743059533646753003894559
p : 97846775312392801037224396977012615848433199640105786119757047098757998273009741128821931277074555731813289423891389911801250326299324018557072727051765547115514791337578758859803890173153277252326496062476389498019821358465433398338364421624871010292162533041884897182597065662521825095949253625730631876637
e : 65537
##### WE'RE GONNA NEED THE FOLLOWING ####
d


I used this site to solve this one
https://www.cryptool.org/de/cto-highlights/rsa-schritt-fuer-schritt


1405046269503207469140791548403639533127416416214210694972085079171787580463776820425965898174272870486015739516125786182821637006600742140682552321645503743280670839819078749092730110549881891271317396450158021688253989767145578723458252769465545504142139663476747479225923933192421405464414574786272963741656223941750084051228611576708609346787101088759062724389874160693008783334605903142528824559223515203978707969795087506678894006628296743079886244349469131831225757926844843554897638786146036869572653204735650843186722732736888918789379054050122205253165705085538743651258400390580971043144644984654914856729



#### NEW MADLIB ####
p : 153143042272527868798412612417204434156935146874282990942386694020462861918068684561281763577034706600608387699148071015194725533394126069826857182428660427818277378724977554365910231524827258160904493774748749088477328204812171935987088715261127321911849092207070653272176072509933245978935455542420691737433
ciphertext : 14699632914289984358210582075909309608817619615764122409514577850253033131275996955127394794512801987443786025277031557775238937388086632327611216460613138074110905840487213116627139558528011448028813522809156509374602431319619052803531008581645459969997969897966475478980398396687104746302415391434104278327526947341073215599683555703818611403510483832532921625745935543818100178607417658929607435582550913918895885596025822532531372429301293588416086854338617700672628239475365045267537032531973594689061842791028000992635092519215619497247452814483357403667400283975070444902253349175045305073603687442947532925780
e : 65537
n : 23952937352643527451379227516428377705004894508566304313177880191662177061878993798938496818120987817049538365206671401938265663712351239785237507341311858383628932183083145614696585411921662992078376103990806989257289472590902167457302888198293135333083734504191910953238278860923153746261500759411620299864395158783509535039259714359526738924736952759753503357614939203434092075676169179112452620687731670534906069845965633455748606649062394293289967059348143206600765820021392608270528856238306849191113241355842396325210132358046616312901337987464473799040762271876389031455051640937681745409057246190498795697239
##### WE'RE GONNA NEED THE FOLLOWING ####
plaintext

1st need to solve for q
q= n/p
q=156408916769576372285319235535320446340733908943564048157238512311891352879208957302116527435165097143521156600690562005797819820759620198602417583539668686152735534648541252847927334505648478214810780526425005943955838623325525300844493280040860604499838598837599791480284496210333200247148213274376422459183

Solved for D using this site again

https://www.cryptool.org/de/cto-highlights/rsa-schritt-fuer-schritt
d=22034129334251191532436631052427142022088744911087428294376533303549714947731798818325604737385904031714383011477708757017443918217594934051491731465975983129741023155187658874730504062262863677059204116473042418196655483682312571059072267891580301964167098006533984400230039789561227549336513668349914598133972091774519248676772440875769025772999278219313806132022105603602125065517276257780089695487263525233311631530270816107086663522684249560931634897706468898520986823978521565593553989544219514141658868117625286137870896148765109851519254459305427251830096270116145359667655034114642356864731801259263519426097


so now we have d and n we can solve for the plain text. I used Python again
p=153143042272527868798412612417204434156935146874282990942386694020462861918068684561281763577034706600608387699148071015194725533394126069826857182428660427818277378724977554365910231524827258160904493774748749088477328204812171935987088715261127321911849092207070653272176072509933245978935455542420691737433
n=23952937352643527451379227516428377705004894508566304313177880191662177061878993798938496818120987817049538365206671401938265663712351239785237507341311858383628932183083145614696585411921662992078376103990806989257289472590902167457302888198293135333083734504191910953238278860923153746261500759411620299864395158783509535039259714359526738924736952759753503357614939203434092075676169179112452620687731670534906069845965633455748606649062394293289967059348143206600765820021392608270528856238306849191113241355842396325210132358046616312901337987464473799040762271876389031455051640937681745409057246190498795697239
q=156408916769576372285319235535320446340733908943564048157238512311891352879208957302116527435165097143521156600690562005797819820759620198602417583539668686152735534648541252847927334505648478214810780526425005943955838623325525300844493280040860604499838598837599791480284496210333200247148213274376422459183
e=65537
d=22034129334251191532436631052427142022088744911087428294376533303549714947731798818325604737385904031714383011477708757017443918217594934051491731465975983129741023155187658874730504062262863677059204116473042418196655483682312571059072267891580301964167098006533984400230039789561227549336513668349914598133972091774519248676772440875769025772999278219313806132022105603602125065517276257780089695487263525233311631530270816107086663522684249560931634897706468898520986823978521565593553989544219514141658868117625286137870896148765109851519254459305427251830096270116145359667655034114642356864731801259263519426097
ct=14699632914289984358210582075909309608817619615764122409514577850253033131275996955127394794512801987443786025277031557775238937388086632327611216460613138074110905840487213116627139558528011448028813522809156509374602431319619052803531008581645459969997969897966475478980398396687104746302415391434104278327526947341073215599683555703818611403510483832532921625745935543818100178607417658929607435582550913918895885596025822532531372429301293588416086854338617700672628239475365045267537032531973594689061842791028000992635092519215619497247452814483357403667400283975070444902253349175045305073603687442947532925780

dt = pow(ct,d,n)
print("dt: = ",dt) 

dt: =  240109877286251840533272915662757983981706320845661471802585807564915966910385147086109038271870589




#### TIME TO FILL IN THE MADLIB! ###
plaintext: 240109877286251840533272915662757983981706320845661471802585807564915966910385147086109038271870589
YAHHH! That one was a great madlib!!!


If you convert the last plaintext to a hex number, then ascii, you'll find what you're searching for ;)

just manipulated the last python to covert to hex then ascii

p=153143042272527868798412612417204434156935146874282990942386694020462861918068684561281763577034706600608387699148071015194725533394126069826857182428660427818277378724977554365910231524827258160904493774748749088477328204812171935987088715261127321911849092207070653272176072509933245978935455542420691737433
n=23952937352643527451379227516428377705004894508566304313177880191662177061878993798938496818120987817049538365206671401938265663712351239785237507341311858383628932183083145614696585411921662992078376103990806989257289472590902167457302888198293135333083734504191910953238278860923153746261500759411620299864395158783509535039259714359526738924736952759753503357614939203434092075676169179112452620687731670534906069845965633455748606649062394293289967059348143206600765820021392608270528856238306849191113241355842396325210132358046616312901337987464473799040762271876389031455051640937681745409057246190498795697239
q=156408916769576372285319235535320446340733908943564048157238512311891352879208957302116527435165097143521156600690562005797819820759620198602417583539668686152735534648541252847927334505648478214810780526425005943955838623325525300844493280040860604499838598837599791480284496210333200247148213274376422459183
e=65537
d=22034129334251191532436631052427142022088744911087428294376533303549714947731798818325604737385904031714383011477708757017443918217594934051491731465975983129741023155187658874730504062262863677059204116473042418196655483682312571059072267891580301964167098006533984400230039789561227549336513668349914598133972091774519248676772440875769025772999278219313806132022105603602125065517276257780089695487263525233311631530270816107086663522684249560931634897706468898520986823978521565593553989544219514141658868117625286137870896148765109851519254459305427251830096270116145359667655034114642356864731801259263519426097
ct=14699632914289984358210582075909309608817619615764122409514577850253033131275996955127394794512801987443786025277031557775238937388086632327611216460613138074110905840487213116627139558528011448028813522809156509374602431319619052803531008581645459969997969897966475478980398396687104746302415391434104278327526947341073215599683555703818611403510483832532921625745935543818100178607417658929607435582550913918895885596025822532531372429301293588416086854338617700672628239475365045267537032531973594689061842791028000992635092519215619497247452814483357403667400283975070444902253349175045305073603687442947532925780

dt = pow(ct,d,n)
print("dt: = ",dt) 

dectohex = hex(dt).lstrip("0x").rstrip("L")
print("dectohex : ",dectohex)

dectoascii = bytes.fromhex(dectohex).decode('utf-8')
print("decoded: ",dectoascii)

dt: =  240109877286251840533272915662757983981706320845661471802585807564915966910385147086109038271870589
dectohex :  7069636f4354467b64305f755f6b6e30775f7468335f7740795f325f5253405f63363732343931367d
decoded:  picoCTF{d0_u_kn0w_th3_w@y_2_RS@_c6724916}