Quadratic Leak

3 minutos de lectura

Se nos proporciona el código fuente de Python para cifrar la flag:

from Crypto.PublicKey import RSA
from Crypto.Util.number import long_to_bytes, bytes_to_long

flag = b'ptm{REDACTED}'
flag = bytes_to_long(flag)

key = RSA.generate(2048)
n = key.n
e = key.e
p, q = key.p, key.q

leak = (p**2 + q**2 - p - q)%key.n

ciph = pow(flag, key.e, key.n)
ciph = long_to_bytes(ciph)

print(f'{n = }')
print(f'{e = }')
print(f'{ciph = }')
print(f'{leak = }')

Y tenemos la salida del script en output.txt:

n = 18981841105895636526675685852772632158842968216380018810386298633786155635996081803989776444322885832862508871280454015266715098097212762303823817669399277859053310692838636039765017523835850272300243126797277954387477501506925762258179024160726332434715115654485883242651742714579029928789693932848304595300833348009779987606253681750351002940239431890559231554840489325837351081804589516122959648786979395257143753954514874848903523580352634665455711644772319481340052722305319056316013353993453687301538982087215697860640865435677605005049256026879380517059221652220476972139202570771113865372482940490650024591211
e = 65537
ciph = b'/>\xf0a\xe4\x95a\xb8!h\x11[\xa01\xa2\x08\xd2\xa0\xd7G\xb0CU`\x97\xc7\xa2\xe9\x94\x10=\xf7\xd6y{\x01u\xcbl\xe1\x7f\x8d\xa0\xd8_\xba\x8a\xd9\x85\xc1\xcc\rK\xc7\xb6\xfb.(\x99%\x1f\x0b\xeci\nR\x8b\xcc>\x86\x18\xe1ie\x19\x9dI\xda\x9bNh8N\xe5\xf2\xf3kP\xeb\x02d\xdei\xadd\xa0\x17WKs~3ohp\xeb\x83\x17>[\x87K\xd1\x0e>\xf6\xeeR\x08\xc4y\x9c\xc7\xbf\xdaq\x9a\xff\x99EQSg\x04"H\xc0=\xfc\x1b\xdcA\x95\xb9\x15m\xe6\x04N\x81%\xda\xa5\xb2P\x02\xbb\xb9\x83\xbf\xcfR\xffe\x0fT\xd9=f\xc1\xab\xd3:\xfb\xf8k\xc0\xd1]V\xc6pK\x86T\xfe\xd5\xadb\x7f\x1b\xb1\x9d9\xe51\xb8\'BY\xcb\x934\x1e\xfb\xc8\x96V4\x0f\xb3\xe4\xd9\x92e;v\x88\x8e\x16\x14?\xe9ew\x95\x8c\xa2\xfc\xc3\xf7,\xd50\xc3@\x11|\x8a\xe0\xee\xf3u\xa0\x8a_?A2[\xad\x8e\x81\x99\xf0\r'
leak = 110277838449088002585424592968018361142419851286027284241723700708406129526007148628583636124051067276081936889565484783806534793568491888186904160969266846545579940493300734427497600123059580090561311191997050900418560468769108541786093143743441372956591688646550593311523980201035231511541259853198512190703006995530566933548862787123808685889850952840156903871573965022335639190635103252052979042642912530238710466180279568731038056810280199578414064760950459385877300845399348928704648108281000674478903445454838155321984920936780746021819652974978142789457099370813760033995294668404782700700352547809925049256

Análisis del código fuente

El código es directo. Implementa un RSA de libro con números primos y de 1024 bits. Cifra la flag y muestra los parámetros públicos y , y también el texto cifrado .

Además, se nos da un leak, que es el valor de

Debemos usar el valor de leak para encontrar los primos y .

Solución

Observe que es un número entero de 2048 bits, ya que es el producto de dos números enteros de 1024 bits. Como resultado, es también un número entero de 2048 bits. Por lo tanto,

Para un cierto pequeño. Suponiendo que conocemos el valor exacto de (llamémoslo ), Podemos resolver un sistema de ecuaciones en las variables e :

Por ejemplo, podemos despejar en la primera ecuación y encontrar el siguiente polinomio cuártico:

Sabemos que es una solución entera a la ecuación polinómica anterior (y también debido a la simetría de las ecuaciones).

Entonces, podemos probar varios valores de (es decir. ) e intentar resolver la ecuación polinómica. Una vez que encontremos una solución, sabremos y y podremos descifrar RSA para obtener la flag.

Implementación

Podemos usar el REPL de SageMath directamente:

$ sage -q
sage: with open('output.txt') as f:
....:     exec(f.read())
....: 
sage: P.<x> = PolynomialRing(ZZ)
sage: k = 0
sage: 
sage: while True:
....:     h = leak + k * n
....:     if (roots := (x ** 4 - x ** 3 - h * x ** 2 - n * x + n ** 2).roots()):
....:         (p, _), (q, _) = roots
....:         break
....:     k += 1
....: 
sage: k
2
sage: n == p * q and 1 < p < n and 1 < q < n
True

Flag

En este punto, podemos descifrar RSA de la forma habitual de obtener la flag:

sage: phi_n = (p - 1) * (q - 1)
sage: d = pow(e, -1, phi_n)
sage: c = int(ciph.hex(), 16)
sage: m = pow(c, d, n)
sage: bytes.fromhex(hex(m)[2:])
b'ptm{Nonlinear_Algebra_Preserved_Over_Large_Integers}'