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 $p$ y $q$ de 1024 bits. Cifra la flag y muestra los parámetros públicos $n$ y $e = 65537$, y también el texto cifrado $c$.
Además, se nos da un leak, que es el valor de
$$ p^2 + q^2 - p - q \mod{n} $$
Debemos usar el valor de leak para encontrar los primos $p$ y $q$.
Solución
Observe que $n = p \cdot q$ es un número entero de 2048 bits, ya que es el producto de dos números enteros de 1024 bits. Como resultado, $p^2 + q^2 - p - q$ es también un número entero de 2048 bits. Por lo tanto,
$$ p^2 + q^2 - p - q = (p^2 + q^2 - p - q \mod{n}) + k \cdot n $$
Para un cierto $k$ pequeño. Suponiendo que conocemos el valor exacto de $p^2 + q^2 - p - q$ (llamémoslo $h$), Podemos resolver un sistema de ecuaciones en las variables $x$ e $y$:
$$ \begin{cases} x \cdot y = n \\ x^2 + y^2 - x - y = h \end{cases} $$
Por ejemplo, podemos despejar $y = n / x$ en la primera ecuación y encontrar el siguiente polinomio cuártico:
$$ x^4 - x^3 - h \cdot x^2 - n \cdot x + n^2 = 0 $$
Sabemos que $x = q$ es una solución entera a la ecuación polinómica anterior (y también $x = p$ debido a la simetría de las ecuaciones).
Entonces, podemos probar varios valores de $k$ (es decir. $k = 0, 1, 2, \dots$) e intentar resolver la ecuación polinómica. Una vez que encontremos una solución, sabremos $p$ y $q$ 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}'