Little Case - * CTF

Overview

known values:-

• n1
• e1
• c ciphertext of mesg (taken as arguement by little_tricks())
• n
• encrypted flag returned by real_trick()

n1 = 21669699875387343975765484834175962461348837371447024695458479154615348697330944566714587217852888702291368306637977095490953192701450127798670425959768118384915082017373951315699899009631834471691811815393784748930880954114446745814058132752897827717077886547911476575751254872623927783670252969995075629255541621917767501261249192653546875104532649043219697616464205772025267019328364349763854659490144531087349974469079255236823096415094552037488277752927579909539401311624671444833332618177513356173537573280352724384376372955100031534236816681805396608147647003653628203258681097552049114308367967967184116839561

e1 = 20717541468269984768938524534679430706714860712589983300712432366828367981392533792814384884126053081363266457682162675931547901815985830455612301105504518353600255693451085179954519939635263372257973143178677586338992274607959326361412487748088349413448526455377296931144384663805056580662706419414607407821761761574754611275621927387380065975844282519447660467416826579669726178901884060454994606177784839804528666823956703141147239309978420776148158425922031573513062568162012505209805669623841355103885621402814626329355281853436655713194649170570579414480803671531927080535374958180810697826214794117466378050607

c = 17653913822265292046140436077352027388518012934178497059850703004839268622175666123728756590505344279395546682262531546841391088108347695091027910544112830270722179480786859703225421972669021406495452107007154426730798752912163553332446929049057464612267870012438268458914652129391150217932076946886301294155031704279222594842585123671871118879574946424138391703308869753154497665630799300138651304835205755177940116680821142858923842124294529640719629497853598914963074656319325664210104788201957945801990296604585721820046391439235286951088086966253038989586737352467905401107613763487302070546247282406664431777475

n = 22346087036331379968192118389403047568445805414881948978518580277027027486284293415097623011228506968071753709256352246733181304513713003096615266613365080909760605498017330085960699607777361429562376124376340215426398797920168016137830563564636922257215066266075494625782943973857490781916694118187094786034792437781964601089843549995939887939410763350338658901108020658475956489391300528691289604149598720803012371765770928211044755626045817053870803040863722458554924076011151695567147976903053993914859714631837755435592006986598006207692599019026644753575853382810261910332197447386727419606073948645238377595719

enc_flag = 12732299056226934743176360461051108799706450051853623472248552066649321279227693844417404789169416642586313895494292082308084823101092675162498154181999270703392144766031531668783213589136974486867571090321426005719333327425286160436925591205840653712046866950957876967715226097699016798471712274797888761218915345301238306497841970203137048433491914195023230951832644259526895087301990301002618450573323078919808182376666320244077837033894089805640452791930176084416087344594957596135877833163152566525019063919662459299054294655118065279192807949989681674190983739625056255497842063989284921411358232926435537518406L

There are two functions:

• little_trick()
• real_trick()

So we first recover p-1 and using that information we can get encrypted flag

The Approach

#1. Retrieving p

little_trick() encrypts p-1 taking it as messsage so first step is to get this decrypted and since we are give n1 (modulus) and e1 (public exponent) we can clearly see this is a direct use of Wiener’s attack

Wiener’s Theorem says that Let N = pq with q < p < 2q. Let equation [] . Then given (e, n), the attacker can efficiently recover d.

using a direct wieners attack on n1 and e1 we recover d1 as 36167461773898995192586226632578677184913220227461899855497899052924496298787

now we can easily get both the factors of n-

p = pow(c,d1,n1)+1
q = n//p

#2. Retrieving enc_flag

now comes the tricky part even though we have got the factors of n (modulus used to encrypt flag) we dont have any knowledge about the public exponent special which they used to encrypt the flag

but they have given us some useful info in an assert statement

assert (special > (ord("*")*100) and gcd(special,(p-1)*(q-1))!=1 )

From these checks we get that special has a lower bound of ord("*")*100 i.e 4200 and we can conclude from the second check that special and phi(p-1*q-1) have at least one common factor

now to find special I used the ecm.factor() in sage to get the factors of both p-1 and q-1 since special would be a factor of p-1*q-1 one of these two.

these are the factors of q-1

Surprisingly many of these factors repeated for p-1 and in the end gcd of phi got me ``

2³*5*89*1153*4919²*4933*28439*434167*5619323

since special and phi have common factors I decided to take the above factors one by and since special > 4200 I started with 4919 and that turned out to be correct.

All we have to do now is take the root in GF(q). This is easily done with this sage function

flags = GF(q)(enc_flag).nth_root(4919,all=True)

This gets us a list of possible roots and checking for the flag format in them gets us the flag

*CTF{S0_Y0u_ARE_REA11Y_GOOd_At_Pla1_This}Ifyoumissthetrainimonyouwillknowthatiamgoneyoucanheartheflagfluwwwwwwwwww