quick maffs

3 minutos de lectura

Se nos proporciona el código fuente para cifrar la flag en 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}")

Se utiliza RSA para cifrar la flag dividida en tres partes:

5981664384988507891478572449251897296717727847212579781448791472718547112403550208352320926002397616312181279859738938646168022481824206589739320298482728968548378237391009138243024910596491172979923991673446034011260330224409794208875199561844435663744993504673450898288161482849187018770655419007178851937895764901674192425054643548670616348302447202491340266057221307744866082461604674766259695903766772980842036324667567850124019171425634526227426965833985082234968255176231124754301435374519312001547854794352023852342682220352109083558778402466358598254431167382653831478713628185748237886560605604945010671417,[4064195644006411160585797813860027634920635349984344191047587061586620848352019080467087592184982883284356841385019453458842500930190512793665886381102812026066865666098391973664302897278510995945377153937248437062600080527317980210967973971371047319247120004523147629534186514628527555180736833194525516718549330721987873868571634294877416190209288629499265010822332662061001208360467692613959936438519512705706688327846470352610192922218603268096313278741647626899523312431823527174576009143724850631439559205050395629961996905961682800070679793831568617438035643749072976096500278297683944583609092132808342160168, 3972397619896893471633226994966440180689669532336298201562465946694941720775869427764056001983618377003841446300122954561092878433908258359050016399257266833626893700179430172867058140215023211349613449750819959868861260714924524414967854467488908710563470522800186889553825417008118394349306170727982570843758792622898850338954039322560740348595654863475541846505121081201633770673996898756298398831948133434844321091554344145679504115839940880338238034227536355386474785852916335583794757849746186832609785626770517073108801492522816245458992502698143396049695921044554959802743742110180934416272358039695942552488, 956566266150449406104687131427865505474798294715598448065695308619216559681163085440476088324404921175885831054464222377255942505087330963629877648302727892001779224319839877897857215091085980519442914974498275528112936281916338633178398286676523416008365096599844169979821513770606168325175652094633129536643417367820830724397070621662683223203491074814734747601002376621653739871373924630026694962642922871008486127796621355314581093953946913681152270251669050414866366693593651789709229310574005739535880988490183275291507128529820194381392682870291338920077175831052974790596134745552552808640002791037755434586],2674558878275613295915981392537201653631411909654166620884912623530781

Análisis del código fuente

Tenemos , , , , y :

No sabemos ninguno de los ni el exponente .

Solución

Después de bastante investigación, encontrarmos un paper antiguo que muestra un ataque a RSA cuando el exponente es pequeño y tenemos información sobre los mensajes (por ejemplo, su suma): Low-Exponent with Related Messages.

En la sección 4, podemos ver una generalización para mensajes relacionados por un polinomio cuando sabemos los textos cifrados y los coeficientes del polinomio .

El paper dice que construyamos un sistema de congruencias como este:

Luego se calcula

Este resultado también se puede obtener usando resultantes en cada par de polinomios (esto elimina las variables comunes). Más información en el paper.

En la subsección 4.2, vemos un caso particular cuando

con una constante conocida. De hecho, podemos hacer que sea la suma de los mensajes para que se cumpla la primera de las ecuaciones.

Vamos a particularizar para . Tenemos

Ahora solo necesitamos calcular para obtener polinomios lineales que contienen los mensajes como términos constantes.

Implementación

Podemos usar Python / SageMath para esto:

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()

No obstante, no sabemos . Pero podemos asumir que será pequeño, por lo que podemos hacer un ataque de fuerza bruta usando números primos hasta que encontremos la flag. De hecho, devolverá cuando no encuentre solución, por lo que podemos usar esto para determinar si el exponente es correcto o no:

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

Y con esto, conseguimos la flag:

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

El script completo se puede encontrar aquí: solve.py.