picoCTF

Rsa Pop Quiz [200 pts]

Challenge Description

Challenge Description:

Class, take your seats! It’s PRIME-time for a quiz… nc jupiter.challenges.picoctf.org 18821

Connect to the service. The first problem should be as follows (may have different numbers):

#### NEW PROBLEM ####
q : 60413
p : 76753
##### PRODUCE THE FOLLOWING ####
n
IS THIS POSSIBLE and FEASIBLE? (Y/N):

Every following problem is similarly formatted.
This one is simple enough. In RSA encryption, \(n=pq\). Thus, our answer is 4636878989. Answer Y and then 4636878989 to move on.

#### NEW PROBLEM ####
p : 54269
n : 5051846941
##### PRODUCE THE FOLLOWING ####
q

Same equation, but we’re finding q = 93089.

#### NEW PROBLEM ####
e : 3
n : 12738162802910546503821920886905393316386362759567480839428456525224226445173031635306683726182522494910808518920409019414034814409330094245825749680913204566832337704700165993198897029795786969124232138869784626202501366135975223827287812326250577148625360887698930625504334325804587329905617936581116392784684334664204309771430814449606147221349888320403451637882447709796221706470239625292297988766493746209684880843111138170600039888112404411310974758532603998608057008811836384597579147244737606088756299939654265086899096359070667266167754944587948695842171915048619846282873769413489072243477764350071787327913
##### PRODUCE THE FOLLOWING ####
q
p

This appears to use the same equation, however, now we’re finding p and q from n. That means we would need to prime factorize n, and there is no currently known classical algorithm to prime factorize large numbers in polynomial time. Hence, the answer is Not Possible.

#### NEW PROBLEM ####
q : 66347
p : 12611
##### PRODUCE THE FOLLOWING ####
totient(n)

Euler’s totient function is essentially the equation \(\phi(n)=(p-1)(q-1)\) so the answer is 836623060.

#### NEW PROBLEM ####
plaintext : 6357294171489311547190987615544575133581967886499484091352661406414044440475205342882841236357665973431462491355089413710392273380203038793241564304774271529108729717
e : 3
n : 29129463609326322559521123136222078780585451208149138547799121083622333250646678767769126248182207478527881025116332742616201890576280859777513414460842754045651093593251726785499360828237897586278068419875517543013545369871704159718105354690802726645710699029936754265654381929650494383622583174075805797766685192325859982797796060391271817578087472948205626257717479858369754502615173773514087437504532994142632207906501079835037052797306690891600559321673928943158514646572885986881016569647357891598545880304236145548059520898133142087545369179876065657214225826997676844000054327141666320553082128424707948750331
##### PRODUCE THE FOLLOWING ####
ciphertext

Here, we’re given the plaintext m, public exponent e, and modulus n, and have to compute the ciphertext c. \(c\equiv m^{e}\;(mod\;n)\), so we can write a simple python program to calculate this.

m = 6357294171489311547190987615544575133581967886499484091352661406414044440475205342882841236357665973431462491355089413710392273380203038793241564304774271529108729717
e = 3
n = 29129463609326322559521123136222078780585451208149138547799121083622333250646678767769126248182207478527881025116332742616201890576280859777513414460842754045651093593251726785499360828237897586278068419875517543013545369871704159718105354690802726645710699029936754265654381929650494383622583174075805797766685192325859982797796060391271817578087472948205626257717479858369754502615173773514087437504532994142632207906501079835037052797306690891600559321673928943158514646572885986881016569647357891598545880304236145548059520898133142087545369179876065657214225826997676844000054327141666320553082128424707948750331

print(int(pow(m, e, n)))

This program returns the value

256931246631782714357241556582441991993437399854161372646318659020994329843524306570818293602492485385337029697819837182169818816821461486018802894936801257629375428544752970630870631166355711254848465862207765051226282541748174535990314552471546936536330397892907207943448897073772015986097770443616540466471245438117157152783246654401668267323136450122287983612851171545784168132230208726238881861407976917850248110805724300421712827401063963117423718797887144760360749619552577176382615108244813  

#### NEW PROBLEM ####
ciphertext : 107524013451079348539944510756143604203925717262185033799328445011792760545528944993719783392542163428637172323512252624567111110666168664743115203791510985709942366609626436995887781674651272233566303814979677507101168587739375699009734588985482369702634499544891509228440194615376339573685285125730286623323
e : 3
n : 27566996291508213932419371385141522859343226560050921196294761870500846140132385080994630946107675330189606021165260590147068785820203600882092467797813519434652632126061353583124063944373336654246386074125394368479677295167494332556053947231141336142392086767742035970752738056297057898704112912616565299451359791548536846025854378347423520104947907334451056339439706623069503088916316369813499705073573777577169392401411708920615574908593784282546154486446779246790294398198854547069593987224578333683144886242572837465834139561122101527973799583927411936200068176539747586449939559180772690007261562703222558103359
##### PRODUCE THE FOLLOWING ####
plaintext

This problem provides us the ciphertext c, public exponent e, and modulus n. This is what is usually given for RSA encrypted messages, and given how large n is, it is unlikely we’d be able to factor n and determine d. (read the PicoPrimer section on RSA to understand this better). Thus, the answer is Not Possible.

#### NEW PROBLEM ####
q : 92092076805892533739724722602668675840671093008520241548191914215399824020372076186460768206814914423802230398410980218741906960527104568970225804374404612617736579286959865287226538692911376507934256844456333236362669879347073756238894784951597211105734179388300051579994253565459304743059533646753003894559
p : 97846775312392801037224396977012615848433199640105786119757047098757998273009741128821931277074555731813289423891389911801250326299324018557072727051765547115514791337578758859803890173153277252326496062476389498019821358465433398338364421624871010292162533041884897182597065662521825095949253625730631876637
e : 65537
##### PRODUCE THE FOLLOWING ####
d

Here, we’re given primes p and q and public exponent e, and are tasked with finding the private exponent d. Since \(\phi(n)=(p-1)(q-1)\) and \(ed=1\;(mod\;\phi)\), we can create another python program to solve this.

q = 92092076805892533739724722602668675840671093008520241548191914215399824020372076186460768206814914423802230398410980218741906960527104568970225804374404612617736579286959865287226538692911376507934256844456333236362669879347073756238894784951597211105734179388300051579994253565459304743059533646753003894559
p = 97846775312392801037224396977012615848433199640105786119757047098757998273009741128821931277074555731813289423891389911801250326299324018557072727051765547115514791337578758859803890173153277252326496062476389498019821358465433398338364421624871010292162533041884897182597065662521825095949253625730631876637
e = 65537

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
print(d)

d = 1405046269503207469140791548403639533127416416214210694972085079171787580463776820425965898174272870486015739516125786182821637006600742140682552321645503743280670839819078749092730110549881891271317396450158021688253989767145578723458252769465545504142139663476747479225923933192421405464414574786272963741656223941750084051228611576708609346787101088759062724389874160693008783334605903142528824559223515203978707969795087506678894006628296743079886244349469131831225757926844843554897638786146036869572653204735650843186722732736888918789379054050122205253165705085538743651258400390580971043144644984654914856729

p : 153143042272527868798412612417204434156935146874282990942386694020462861918068684561281763577034706600608387699148071015194725533394126069826857182428660427818277378724977554365910231524827258160904493774748749088477328204812171935987088715261127321911849092207070653272176072509933245978935455542420691737433
ciphertext : 13433290949680532374013867441263154634705815037382789341947905025573905974395028146503162155477260989520870175638250366834087929309236841056522311567941474209163559687755762232926539910909326834168973560610986090744435081572047926364479629414399701920441091626046861493465214197526650146669009590360242375313096062285541413327190041808752295242278877995930751460977420696964385608409717277431821765402461515639686537904799084682553530460611519251872463837425068958992042166507373556839377045616866221238932332390930404993242351071392965945718308504231468783743378794612151028803489143522912976113314577732444166162766
e : 65537
n : 23952937352643527451379227516428377705004894508566304313177880191662177061878993798938496818120987817049538365206671401938265663712351239785237507341311858383628932183083145614696585411921662992078376103990806989257289472590902167457302888198293135333083734504191910953238278860923153746261500759411620299864395158783509535039259714359526738924736952759753503357614939203434092075676169179112452620687731670534906069845965633455748606649062394293289967059348143206600765820021392608270528856238306849191113241355842396325210132358046616312901337987464473799040762271876389031455051640937681745409057246190498795697239
##### PRODUCE THE FOLLOWING ####
plaintext

This problem provides us the prime p, ciphertext c, public exponent e, and modulus n. This combines all the previous equations we have used.

\[n=pq\] \[\phi(n)=(p-1)(q-1)\] \[ed=1\;(mod\;\phi)\] \[c^{d}\equiv m\;(mod\;n)\] 
p = 153143042272527868798412612417204434156935146874282990942386694020462861918068684561281763577034706600608387699148071015194725533394126069826857182428660427818277378724977554365910231524827258160904493774748749088477328204812171935987088715261127321911849092207070653272176072509933245978935455542420691737433
c = 13433290949680532374013867441263154634705815037382789341947905025573905974395028146503162155477260989520870175638250366834087929309236841056522311567941474209163559687755762232926539910909326834168973560610986090744435081572047926364479629414399701920441091626046861493465214197526650146669009590360242375313096062285541413327190041808752295242278877995930751460977420696964385608409717277431821765402461515639686537904799084682553530460611519251872463837425068958992042166507373556839377045616866221238932332390930404993242351071392965945718308504231468783743378794612151028803489143522912976113314577732444166162766
e = 65537
n = 23952937352643527451379227516428377705004894508566304313177880191662177061878993798938496818120987817049538365206671401938265663712351239785237507341311858383628932183083145614696585411921662992078376103990806989257289472590902167457302888198293135333083734504191910953238278860923153746261500759411620299864395158783509535039259714359526738924736952759753503357614939203434092075676169179112452620687731670534906069845965633455748606649062394293289967059348143206600765820021392608270528856238306849191113241355842396325210132358046616312901337987464473799040762271876389031455051640937681745409057246190498795697239

q = n // p
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)

print(m)

That’s the last question! Last thing we need to do is convert the plaintext message to hex and then to ascii for our flag. Add the last two lines to the program:

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

picoCTF{wA8_th4t$_ill3aGal..oa2d2239b}