quick maffs

4 minutes to read

We are given the source code to encrypt the flag in SageMath:

from Crypto.Util.number import *
from secret import pts,p,q

e = random_prime(2^10) # this will also be a secret , don't complain

N = p*q
pts = [bytes_to_long(i) for i in pts]
cts = [pow(i,e,N) for i in pts]
hint = sum(pts) # bcuz i don't want make chall unsolvable
print(f"{N},{cts},{hint}")

It uses RSA to encrypt the flag divided in three parts:

5981664384988507891478572449251897296717727847212579781448791472718547112403550208352320926002397616312181279859738938646168022481824206589739320298482728968548378237391009138243024910596491172979923991673446034011260330224409794208875199561844435663744993504673450898288161482849187018770655419007178851937895764901674192425054643548670616348302447202491340266057221307744866082461604674766259695903766772980842036324667567850124019171425634526227426965833985082234968255176231124754301435374519312001547854794352023852342682220352109083558778402466358598254431167382653831478713628185748237886560605604945010671417,[4064195644006411160585797813860027634920635349984344191047587061586620848352019080467087592184982883284356841385019453458842500930190512793665886381102812026066865666098391973664302897278510995945377153937248437062600080527317980210967973971371047319247120004523147629534186514628527555180736833194525516718549330721987873868571634294877416190209288629499265010822332662061001208360467692613959936438519512705706688327846470352610192922218603268096313278741647626899523312431823527174576009143724850631439559205050395629961996905961682800070679793831568617438035643749072976096500278297683944583609092132808342160168, 3972397619896893471633226994966440180689669532336298201562465946694941720775869427764056001983618377003841446300122954561092878433908258359050016399257266833626893700179430172867058140215023211349613449750819959868861260714924524414967854467488908710563470522800186889553825417008118394349306170727982570843758792622898850338954039322560740348595654863475541846505121081201633770673996898756298398831948133434844321091554344145679504115839940880338238034227536355386474785852916335583794757849746186832609785626770517073108801492522816245458992502698143396049695921044554959802743742110180934416272358039695942552488, 956566266150449406104687131427865505474798294715598448065695308619216559681163085440476088324404921175885831054464222377255942505087330963629877648302727892001779224319839877897857215091085980519442914974498275528112936281916338633178398286676523416008365096599844169979821513770606168325175652094633129536643417367820830724397070621662683223203491074814734747601002376621653739871373924630026694962642922871008486127796621355314581093953946913681152270251669050414866366693593651789709229310574005739535880988490183275291507128529820194381392682870291338920077175831052974790596134745552552808640002791037755434586],2674558878275613295915981392537201653631411909654166620884912623530781

Source code analysis

We are given , , , , and :

We don’t know any of and the exponent .

Solution

After a lot of research, we find an old paper that shows an attack on RSA when the exponent is low and we have some imformation about the plaintexts (for example, the sum of the plaintexts): Low-Exponent with Related Messages.

In section 4, we can see a generalization for messages related by a polynomial when we know the ciphertexts and the coefficients of the polynomial .

The paper says to build a system of congruences like this:

After that

The above result can also be obtained using resultants on each pair of polynomials (this will remove common variables). More information in the paper.

In subsection 4.2, we see a particular case when

with a known constant . In fact, we can set to be the sum of plaintexts in order to satisfy the first of the equations.

Let’s particularize for . We have that

Now we only need to compute to obtain linear polynomials that contain the messages as constant terms.

Implementation

We can use Python / SageMath for this:

x1, x2, x3 = PolynomialRing(Zmod(N), names='x1, x2, x3').gens()
P0 = x1 + x2 + x3 - w


def low_exponent_with_related_messages_attack(e):
    P1 = x1 ** e - c1
    P2 = x2 ** e - c2
    P3 = x3 ** e - c3
    return Ideal(P0, P1, P2, P3).groebner_basis()

However, we don’t know . But we can assume that it will be short, so we can do a brute force attack using prime numbers until we find the flag. Actually, will return just if there’s no solution, so we can use this to determine if the tested is correct or not:

for e in Primes(proof=False):
    if len(b := low_exponent_with_related_messages_attack(e)) > 1:
        break

m1 = N - b[0].coefficients()[1]
m2 = N - b[1].coefficients()[1]
m3 = N - b[2].coefficients()[1]

print(bytes.fromhex(hex(m1)[2:] + hex(m2)[2:] + hex(m3)[2:]).decode())

Flag

And with this, we get the flag:

$ python3 solve.py
HTB{5h0u1d_1t_b3_und3r_RSA_c4t3g0ry_0r_und3r_m4ths_c4t3g0ry?,1dk!but_gb_is_c00l}

The full script can be found in here: solve.py.