Heyyo Hackers/CTFers! Hope you all doing well. This Challenge over here is from the HackTM ctf. This is a Cryptography challenge and took me way over 5 hours to figure out. Hope you’ll like this writeup for it.

After having first glance at the challenge files, I was certain this had something to do with the RSA encryption. They way I solved this challenge I guess was not intended but none the less I got the flag.

I’ll First get on the basics of RSA for beginner who don’t exactly know what that is (you can skip this paragraph if you know how RSA encryption works). RSA encryption is a asymmetric encryption type which means while encrypting message we use a different key (public key) and while decrypting that same message we use a different key(private key). How are these keys acquired? To get these keys we basically do alot of maths (Don’t worry, just hang on with me). In RSA encryption while encrypting message we do message^e (mod n) where e is an exponent (usually 65537 but not in this challenge which makes it interesting) and n is the modulus value here and how is this n value derived? n variable here is achieved by multiplying two prime numbers (p and q and these prime numbers are not small, for security reasons they can even go upto 200 digits long) . e and n are the public key set in RSA and the private key is d. To get the value of d what we do is first get phi (totient not to confuse with golden ratio). phi = (p-1)(q-1). Now what we basically do is d = e^-1(mod phi). These are the basic RSA variables we’ll be going through in this writeup…..

Values.txt file
n = 24476383567792760737445809443492789639532562013922247811020136923589010741644222420227206374197451638950771413340924096340837752043249937740661704552394497914758536695641625358888570907798672682231978378863166006326676708689766394246962358644899609302315269836924417613853084331305979037961661767481870702409724154783024602585993523452019004639755830872907936352210725695418551084182173371461071253191795891364697373409661909944972555863676405650352874457152520233049140800885827642997470620526948414532553390007363221770832301261733085022095468538192372251696747049088035108525038449982810535032819511871880097702167
enc_d = 23851971033205169724442925873736356542293022048328010529601922038597156073052741135967263406916098353904000351147783737673489182435902916159670398843992581022424040234578709904403027939686144718982884200573860698818686908312301218022582288691503272265090891919878763225922888973146019154932207221041956907361037238034826284737842344007626825211682868274941550017877866773242511532247005459314727939294024278155232050689062951137001487973659259356715242237299506824804517181218221923331473121877871094364766799442907255801213557820110837044140390668415470724167526835848871056818034641517677763554906855446709546993374
enc_phi = 3988439673093122433640268099760031932750589560901017694612294237734994528445711289776522094320029720250901589476622749396945875113134575148954745649956408698129211447217738399970996146231987508863215840103938468351716403487636203224224211948248426979344488189039912815110421219060901595845157989550626732212856972549465190609710288441075239289727079931558808667820980978069512061297536414547224423337930529183537834934423347408747058506318052591007082711258005394876388007279867425728777595263973387697391413008399180495885227570437439156801767814674612719688588210328293559385199717899996385433488332567823928840559
enc_flag = 24033688910716813631334059349597835978066437874275978149197947048266360284414281504254842680128144566593025304122689062491362078754654845221441355173479792783568043865858117683452266200159044180325485093879621270026569149364489793568633147270150444227384468763682612472279672856584861388549164193349969030657929104643396225271183660397476206979899360949458826408961911095994102002214251057409490674577323972717947269749817048145947578717519514253771112820567828846282185208033831611286468127988373756949337813132960947907670681901742312384117809682232325292812758263309998505244566881893895088185810009313758025764867

from Crypto.Util.number import bytes_to_long, getStrongPrime

from secret import flag

assert len(flag) == 255
e = 3
p = getStrongPrime(1024, e=e)
q = getStrongPrime(1024, e=e)
n = p * q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
enc_d = pow(d, e, n)
enc_phi = pow(phi, e, n)
enc_flag = pow(bytes_to_long(flag), e, n)
print(f“{n = }“)
print(f”{enc_d = }“)
print(f”{enc_phi = }“)
print(f”{enc_flag = }“)

I first tried to understand the encryption process since this challenge was a bit different than usual RSA encryption. e = 3 caught my interest since whenever e = 3 (or smaller) it is usually a RSA cube root attack. RSA cube root attack is basically that c^e < n (c is the cipher text in this case the enc_flag). That’s an easy flag, right? NO! since c^e < n is false in this case (I should’ve realized it earlier since c > n). After a long, hefty time of thinking one formula popped up in my mind which I think turned the tables! I refer this as the Golden formula!!!

e*d-1 = 0 (mod phi)

And then I researched a bit more on this formula (Since my brain got rusty about this formula). And I ended up finding this formula which also was a game-changer.

e * d-1 = k * phi

I made a python script by using e=3 and generated alot of test results and everytime the output was k=2.

from Crypto.Util.number import bytes_to_long, getStrongPrime

e = 3
p = getStrongPrime(1024, e=e)
q = getStrongPrime(1024, e=e)
n = p * q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

k = (e*d-1)//phi
print(k)

According to the python code:

d^e - enc_d = 0 (mod n)
phi^e - enc_phi = 0 (mod n)

At this point of time I was just out of my mind and was brute forcing alot of different RSA attacks until I found this great writeup. https://connor-mccartney.github.io/cryptography/rsa/one-step-closer-HTB-cyber-apocalypse-CTF-2022 (credits: Connor Mccartney). This writeup Explained the Franklin-Reiter attack. I copied the gcd and Franklin-Reiter function from that writeup and then I made up this sage code using the above achieved values and formulas.

PR. = PolynomialRing(Zmod(n))
f1 = x^3 - enc_d
f2 = ((x*3 - 1)/2)^3 - enc_phi
d = FranklinReiter(f1, f2)

x over here is just random value for d, everything (mod n). then according to the “d^e — enc_d = 0 (mod n)” we get the f1 variable and then according to the “e * d-1 = k * phi” formula we achieve that (x*3–1)/2 is the value of phi and then we raise that to 3 and the -enc_phi all according to the formula and then run the franklin Reiter function on the values obtained. the final script was:

n = 24476383567792760737445809443492789639532562013922247811020136923589010741644222420227206374197451638950771413340924096340837752043249937740661704552394497914758536695641625358888570907798672682231978378863166006326676708689766394246962358644899609302315269836924417613853084331305979037961661767481870702409724154783024602585993523452019004639755830872907936352210725695418551084182173371461071253191795891364697373409661909944972555863676405650352874457152520233049140800885827642997470620526948414532553390007363221770832301261733085022095468538192372251696747049088035108525038449982810535032819511871880097702167
enc_d = 23851971033205169724442925873736356542293022048328010529601922038597156073052741135967263406916098353904000351147783737673489182435902916159670398843992581022424040234578709904403027939686144718982884200573860698818686908312301218022582288691503272265090891919878763225922888973146019154932207221041956907361037238034826284737842344007626825211682868274941550017877866773242511532247005459314727939294024278155232050689062951137001487973659259356715242237299506824804517181218221923331473121877871094364766799442907255801213557820110837044140390668415470724167526835848871056818034641517677763554906855446709546993374
enc_phi = 3988439673093122433640268099760031932750589560901017694612294237734994528445711289776522094320029720250901589476622749396945875113134575148954745649956408698129211447217738399970996146231987508863215840103938468351716403487636203224224211948248426979344488189039912815110421219060901595845157989550626732212856972549465190609710288441075239289727079931558808667820980978069512061297536414547224423337930529183537834934423347408747058506318052591007082711258005394876388007279867425728777595263973387697391413008399180495885227570437439156801767814674612719688588210328293559385199717899996385433488332567823928840559
enc_flag = 24033688910716813631334059349597835978066437874275978149197947048266360284414281504254842680128144566593025304122689062491362078754654845221441355173479792783568043865858117683452266200159044180325485093879621270026569149364489793568633147270150444227384468763682612472279672856584861388549164193349969030657929104643396225271183660397476206979899360949458826408961911095994102002214251057409490674577323972717947269749817048145947578717519514253771112820567828846282185208033831611286468127988373756949337813132960947907670681901742312384117809682232325292812758263309998505244566881893895088185810009313758025764867
def gcd(a, b):
while b:
a, b = b, a % b
return a.monic()

def FranklinReiter(f1, f2):
return int(-gcd(f1, f2).coefficients()[0])
PR. = PolynomialRing(Zmod(n))
f1 = x^3 - enc_d
f2 = ((x*3 - 1)/2)^3 - enc_phi
d = FranklinReiter(f1, f2)
integerflag = pow(enc_flag, d, n)

This is sage code. The flag we get is in integer form. I couldn’t find a way to do the long_to_bytes thing in sage code and since I was under pressure I just used pycrytography long_to_bytes and Voila! we have the flag. The flag also makes sense

HackTM{Have you warmed up? If not, I suggest you consider the case where e=65537, although I don’t know if it’s solvable. Why did I say that? Because I have to make this flag much longer to avoid solving it just by calculating the cubic root of enc_flag.}

None the less this was a crazy experience of solving a cryptography challenge!