Foreword#
I participated in HackTM CTF 2023 with NUS Greyhats. We managed to get 15th place. Overall I am quite happy with my performance this CTF, I managed to solve 1 challenge solo and collaborated with mechfrog88 to solve another Crypto challenge.
The Crypto challenges of this CTF are quite tough, and it is an interesting read of the solution given by the creator. I think the given writeups by the author are good enough, and should provide a better view of the educational values after solving the challenges. My solution to the easiest challenge d-phi-enc is the use of Franklin Reiter attack, and the fact that $ed = k * phi + 1$, where $k = 2$.
The other challenge, kaitenzushi, was mostly solved by mechfrog88. I contributed very little in solving the challenge.
View the writeups at this link from the author.
Challenges#
d-phi-enc#
Again, as stated, the writeup from the author should provide a good view of how to solve the challenge. First, after a bit of testing (10 tries), I realize that $ed = k * phi + 1$, for $e = 3$ always have $k = 2$.
Knowing this, the challenge is just a very straightforward application of the Franklin-Reiter attack.
Sage Implementation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
from Crypto.Util.number import long_to_bytes
n = 24476383567792760737445809443492789639532562013922247811020136923589010741644222420227206374197451638950771413340924096340837752043249937740661704552394497914758536695641625358888570907798672682231978378863166006326676708689766394246962358644899609302315269836924417613853084331305979037961661767481870702409724154783024602585993523452019004639755830872907936352210725695418551084182173371461071253191795891364697373409661909944972555863676405650352874457152520233049140800885827642997470620526948414532553390007363221770832301261733085022095468538192372251696747049088035108525038449982810535032819511871880097702167
enc_d = 23851971033205169724442925873736356542293022048328010529601922038597156073052741135967263406916098353904000351147783737673489182435902916159670398843992581022424040234578709904403027939686144718982884200573860698818686908312301218022582288691503272265090891919878763225922888973146019154932207221041956907361037238034826284737842344007626825211682868274941550017877866773242511532247005459314727939294024278155232050689062951137001487973659259356715242237299506824804517181218221923331473121877871094364766799442907255801213557820110837044140390668415470724167526835848871056818034641517677763554906855446709546993374
enc_phi = 3988439673093122433640268099760031932750589560901017694612294237734994528445711289776522094320029720250901589476622749396945875113134575148954745649956408698129211447217738399970996146231987508863215840103938468351716403487636203224224211948248426979344488189039912815110421219060901595845157989550626732212856972549465190609710288441075239289727079931558808667820980978069512061297536414547224423337930529183537834934423347408747058506318052591007082711258005394876388007279867425728777595263973387697391413008399180495885227570437439156801767814674612719688588210328293559385199717899996385433488332567823928840559
enc_flag = 24033688910716813631334059349597835978066437874275978149197947048266360284414281504254842680128144566593025304122689062491362078754654845221441355173479792783568043865858117683452266200159044180325485093879621270026569149364489793568633147270150444227384468763682612472279672856584861388549164193349969030657929104643396225271183660397476206979899360949458826408961911095994102002214251057409490674577323972717947269749817048145947578717519514253771112820567828846282185208033831611286468127988373756949337813132960947907670681901742312384117809682232325292812758263309998505244566881893895088185810009313758025764867
def gcd(a,b):
# custom GCD implementation because Sage's one apparently doesn't work here
while b:
a, b = b, a % b
return a.monic()
F.<x> = PolynomialRing(Zmod(n), implementation='NTL')
# Set the unknown as phi
f = x ^ 3 - enc_phi
# We are given d ^ 3, then we can calculate (ed) ^ 3 = (k phi + 1) ^ 3
t = (27 * enc_d) % n
# k = 2, from fuzzing
g = (2 * x + 1) ^ 3 - t
phi = int(-gcd(f, g).coefficients()[0])
e = 3
d = pow(e, -1, phi)
print(long_to_bytes(pow(enc_flag, d, n)))
|