PROBLEM
We ran into some weird puzzles we think may mean something, can you help me solve one? Connect with nc 2018shell1.picoctf.com 40440
HINT
SOLUTION
First question is
q : 93187 p : 94603
n IS THIS POSSIBLE and FEASIBLE? (Y/N):
Yes it is possible.
n=p*q so just multiple the given numbers - n= p*q = 8815769761
Second question:
p : 81203 n : 6315400919
q IS THIS POSSIBLE and FEASIBLE? (Y/N):
YES that is possible. As we saw above n=p*q so obviously q=n/p and we get q=77773
Next question:
e : 3 n : 12738162802910546503821920886905393316386362759567480839428456525224226445173031635306683726182522494910808518920409019414034814409330094245825749680913204566832337704700165993198897029795786969124232138869784626202501366135975223827287812326250577148625360887698930625504334325804587329905617936581116392784684334664204309771430814449606147221349888320403451637882447709796221706470239625292297988766493746209684880843111138170600039888112404411310974758532603998608057008811836384597579147244737606088756299939654265086899096359070667266167754944587948695842171915048619846282873769413489072243477764350071787327913
q p IS THIS POSSIBLE and FEASIBLE? (Y/N):
n->No that is not possible. Why? well just read about RSA, if you'll make this possible you'll break RSA.
Next Question;
q : 78203 p : 79999
totient(n) IS THIS POSSIBLE and FEASIBLE? (Y/N):
Y->yes that is possible.
totient(n) is also given by phi(n) and we can see on the wikipedia page that phi(n)=(p-1)*(q-1) so calculating that we get 6256003596
Next question:
plaintext : 1815907181716474805136452061793917684000871911998851410864797078911161933431337632774829806207517001958179617856720738101327521552576351369691667910371502971480153619360010341709624631317220940851114914911751279825748 e : 3 n : 29129463609326322559521123136222078780585451208149138547799121083622333250646678767769126248182207478527881025116332742616201890576280859777513414460842754045651093593251726785499360828237897586278068419875517543013545369871704159718105354690802726645710699029936754265654381929650494383622583174075805797766685192325859982797796060391271817578087472948205626257717479858369754502615173773514087437504532994142632207906501079835037052797306690891600559321673928943158514646572885986881016569647357891598545880304236145548059520898133142087545369179876065657214225826997676844000054327141666320553082128424707948750331
ciphertext IS THIS POSSIBLE and FEASIBLE? (Y/N):
Y->Yes that is possible.
We know that c=m^e mod n and we are given all the components so just pass all these 3 decimal values into python's pow function like pow(m,e,n).
we'll get 26722917505435451150596710555980625220524134812001687080485341361511207096550823814926607028717403343344600191255790864873639087129323153797404989216681535785492257030896045464472300400447688001563694767148451912130180323038978568872458130612657140514751874493071944456290959151981399532582347021031424096175747508579453024891862161356081561032045394147561900547733602483979861042957169820579569242714893461713308057915755735700329990893197650028440038700231719057433874201113850357283873424698585951160069976869223244147124759020366717935504226979456299659682165757462057188430539271285705680101066120475874786208053
P.S - you can import pow like from math import pow
Next question
ciphertext : 10752401345107934853994451075614360420392571726218503379932844501179276054552894499371978339254216342863717232351225262 456711111066616866474311520379151098570994236660962643699588778167465127223356630381497967750710116858773937569900973458898548236970 2634499544891509228440194615376339573685285125730286623323 e : 3 n : 27566996291508213932419371385141522859343226560050921196294761870500846140132385080994630946107675330189606021165260590147068785 820203600882092467797813519434652632126061353583124063944373336654246386074125394368479677295167494332556053947231141336142392086767 742035970752738056297057898704112912616565299451359791548536846025854378347423520104947907334451056339439706623069503088916316369813 499705073573777577169392401411708920615574908593784282546154486446779246790294398198854547069593987224578333683144886242572837465834 139561122101527973799583927411936200068176539747586449939559180772690007261562703222558103359
plaintext IS THIS POSSIBLE and FEASIBLE? (Y/N):
N->No that is not possible. Why? well to get plaintext from ciphertext we need d, from wiki page we can see m=c^d mod n and we are not given any required value to calculate d and again we don't want to break RSA 😉
Next question
q : 92092076805892533739724722602668675840671093008520241548191914215399824020372076186460768206814914423802230398410980218741906960527104568970225804374404612617736579286959865287226538692911376507934256844456333236362669879347073756238894784951597211105734179388300051579994253565459304743059533646753003894559 p : 97846775312392801037224396977012615848433199640105786119757047098757998273009741128821931277074555731813289423891389911801250326299324018557072727051765547115514791337578758859803890173153277252326496062476389498019821358465433398338364421624871010292162533041884897182597065662521825095949253625730631876637 e : 65537
d IS THIS POSSIBLE and FEASIBLE? (Y/N):
Y->Yes that is possible.
We need d. For this we use Euclid's Extended GCD algorithm.
For this I took code that was written by dufferzafar.
You can see the code in calculate-d.py. Just put the values of p, q and e and you'll get d.
1405046269503207469140791548403639533127416416214210694972085079171787580463776820425965898174272870486015739516125786182821637006600742140682552321645503743280670839819078749092730110549881891271317396450158021688253989767145578723458252769465545504142139663476747479225923933192421405464414574786272963741656223941750084051228611576708609346787101088759062724389874160693008783334605903142528824559223515203978707969795087506678894006628296743079886244349469131831225757926844843554897638786146036869572653204735650843186722732736888918789379054050122205253165705085538743651258400390580971043144644984654914856729
Next question:
p : 153143042272527868798412612417204434156935146874282990942386694020462861918068684561281763577034706600608387699148071015194725533394126069826857182428660427818277378724977554365910231524827258160904493774748749088477328204812171935987088715261127321911849092207070653272176072509933245978935455542420691737433 ciphertext : 5315135537182226856134532843338546481354659841681272223692273789930341302489189252395544040217036010025492161730920090820789264419456405499853943420863961834511620167348215712366219204972198527365477630427263725627920265227612760416678425823843187407675643742844283110052895704455415142735463486037912801307917634230788549540802477270278755052542590491708620341889689884020271200598596327430790861785538107067664504281508756159305916221674161062222221931717498244841323828452111473034440447694160917521358885718436832783214139059379459896493819067235346238816701274408935126796953373891399167497687512301978797146598 e : 65537 n : 23952937352643527451379227516428377705004894508566304313177880191662177061878993798938496818120987817049538365206671401938265663712351239785237507341311858383628932183083145614696585411921662992078376103990806989257289472590902167457302888198293135333083734504191910953238278860923153746261500759411620299864395158783509535039259714359526738924736952759753503357614939203434092075676169179112452620687731670534906069845965633455748606649062394293289967059348143206600765820021392608270528856238306849191113241355842396325210132358046616312901337987464473799040762271876389031455051640937681745409057246190498795697239
plaintext IS THIS POSSIBLE and FEASIBLE? (Y/N):
Y->yes that is possible.
We are given p,c,e and n. Okay so first we q so calculate it by q=n/p then again we put the value of p,q and e in the code mentioned above and get the value of d.
Now we have c,d and n i.e all the value required to get plaintext(m) by using m=c^d mod n so again use the python's pow function, pow(c,d,n).
Finally we get 240109877286251840533272915662757983981706320845661471802585807564915966910384301849411666983334013
Change the last value to hex and then to ascii.
After doing some maths you'll get the flag.
🎉 FLAG - picoCTF{d0_u_kn0w_th3_w@y_2_RS@_5d383e10}