Challenge Summary
- Name: quick maffs
- Category: Crypto
- Difficulty: Hard
- Goal: Recover the plaintext triplet and reconstruct the flag.
Root Cause
The service encrypts three related plaintext chunks under the same RSA modulus/exponent pair:
c1 = m1^e mod Nc2 = m2^e mod Nc3 = m3^e mod N- and leaks
m1 + m2 + m3 = hint
Because e is a prime < 1024, we can iterate candidate exponents and solve the algebraic system directly.
Exploit Strategy
For each prime e < 1024, define:
P0 = x1 + x2 + x3 - hint
P1 = x1^e - c1
P2 = x2^e - c2
P3 = x3^e - c3
Then compute a Gröbner basis of Ideal(P0, P1, P2, P3) in Z_N[x1,x2,x3].
For the correct exponent, the basis gives linear forms that recover m1,m2,m3.
Concatenate the three recovered message chunks in hex and decode bytes.
Recovered exponent in this solve: e = 41.
Solve Script (Full PoC)
#!/usr/bin/env python3
from sage.all import Ideal, PolynomialRing, Primes, Zmod
N = 5981664384988507891478572449251897296717727847212579781448791472718547112403550208352320926002397616312181279859738938646168022481824206589739320298482728968548378237391009138243024910596491172979923991673446034011260330224409794208875199561844435663744993504673450898288161482849187018770655419007178851937895764901674192425054643548670616348302447202491340266057221307744866082461604674766259695903766772980842036324667567850124019171425634526227426965833985082234968255176231124754301435374519312001547854794352023852342682220352109083558778402466358598254431167382653831478713628185748237886560605604945010671417
c1 = 4064195644006411160585797813860027634920635349984344191047587061586620848352019080467087592184982883284356841385019453458842500930190512793665886381102812026066865666098391973664302897278510995945377153937248437062600080527317980210967973971371047319247120004523147629534186514628527555180736833194525516718549330721987873868571634294877416190209288629499265010822332662061001208360467692613959936438519512705706688327846470352610192922218603268096313278741647626899523312431823527174576009143724850631439559205050395629961996905961682800070679793831568617438035643749072976096500278297683944583609092132808342160168
c2 = 3972397619896893471633226994966440180689669532336298201562465946694941720775869427764056001983618377003841446300122954561092878433908258359050016399257266833626893700179430172867058140215023211349613449750819959868861260714924524414967854467488908710563470522800186889553825417008118394349306170727982570843758792622898850338954039322560740348595654863475541846505121081201633770673996898756298398831948133434844321091554344145679504115839940880338238034227536355386474785852916335583794757849746186832609785626770517073108801492522816245458992502698143396049695921044554959802743742110180934416272358039695942552488
c3 = 956566266150449406104687131427865505474798294715598448065695308619216559681163085440476088324404921175885831054464222377255942505087330963629877648302727892001779224319839877897857215091085980519442914974498275528112936281916338633178398286676523416008365096599844169979821513770606168325175652094633129536643417367820830724397070621662683223203491074814734747601002376621653739871373924630026694962642922871008486127796621355314581093953946913681152270251669050414866366693593651789709229310574005739535880988490183275291507128529820194381392682870291338920077175831052974790596134745552552808640002791037755434586
hint = 2674558878275613295915981392537201653631411909654166620884912623530781
R = PolynomialRing(Zmod(N), names=("x1", "x2", "x3"))
x1, x2, x3 = R.gens()
P0 = x1 + x2 + x3 - hint
for e in Primes(proof=False):
if e >= 1024:
break
basis = Ideal(
P0,
x1**e - c1,
x2**e - c2,
x3**e - c3,
).groebner_basis()
if len(basis) <= 1:
continue
m1 = int((-basis[0].coefficients()[1]) % N)
m2 = int((-basis[1].coefficients()[1]) % N)
m3 = int((-basis[2].coefficients()[1]) % N)
blob = f"{m1:x}{m2:x}{m3:x}"
if len(blob) % 2:
blob = "0" + blob
print(bytes.fromhex(blob).decode())
break
Run
micromamba run -p /opt/micromamba/envs/sage python solve.py
Flag
HTB{5h0u1d_1t_b3_und3r_RSA_c4t3g0ry_0r_und3r_m4ths_c4t3g0ry?,1dk!but_gb_is_c00l}