grammar nazi

Se nos proporciona el siguiente código fuente en Python, con la salida como una string multilínea:

from Crypto.Util.number import *

FLAG = 'maltactf{???????????????????????????????}'
assert len(FLAG) == 41

p = getPrime(128)
q = getPrime(128)
N = p * q
e = 65537

m = f'The flag is {FLAG}'
c = pow(bytes_to_long(m.encode()), e, N)

# ERROR: Sentences should end with a period.
m += '.'
c += pow(bytes_to_long(m.encode()), e, N)

# All good now!
print(f'{N = }')
print(f'{c = }')

'''
N = 83839453754784827797201083929300181050320503279359875805303608931874182224243
c = 32104483815246305654072935180480116143927362174667948848821645940823281560338
'''

Análisis del código fuente

El código fuente es corto y directo:

• Sabemos el formato de la flag y su longitud
• El programa genera dos números primos de 128 bits y (clave privada RSA)
• y usa eso para crear una clave pública RSA y
• Después, el programa cifra un mensaje que contiene la flag:
• Luego, actualiza de una manera extraña para “agregar un punto”

Se nos da como N y el valor actualizado de $ccomoc`. Con esta información, necesitamos encontrar la flag.

Solución

Sea el mensaje original y el mensaje actualizado con el punto. Por lo tanto, , donde 46 es el valor ASCII decimal de un punto.

Como resultado, el valor dado de c es :

En resumen, podemos definir un polinomio , tal que es una raíz de en . Sin embargo, encontrar raíces bajo un módulo compuesto con factorización desconocida es difícil.

En una implementación segura de RSA, como RSA-2048 o RSA-4096, esto sería imposible de resolver en un tiempo razonable. Sin embargo, esta vez el servidor usa RSA-256, ya que los primos y son números de 128 bits. Podríamos usar herramientas como cado-nfs para factorizar , pero esta vez, el número ya fue subido a factordb:

$ sage -q
sage: N = 83839453754784827797201083929300181050320503279359875805303608931874182224243
sage: c = 32104483815246305654072935180480116143927362174667948848821645940823281560338
sage: 
sage: e = 65537
sage: 
sage: p = 276784813000398431755706235529589161781
sage: q = 302904819256337380397575865141537456903
sage: N == p * q
True

Entonces, dado que conocemos y tales que , podemos encontrar dentro de las raíces de en . Para esto, podemos considerar por separado en y , encontrar posibles raíces y luego aplicar el Teorema Chino del Resto (CRT).

En otras palabras, podemos encontrar fácilmente tal que y tal que , lo que significa

Implementación

En SageMath, podríamos sentirnos tentados a usar el siguiente código:

sage: Pp.<xp> = PolynomialRing(GF(p))
sage: Pq.<xq> = PolynomialRing(GF(q))
sage: 
sage: fp = xp ** e + (256 * xp + 46) ** e - c
sage: fq = xq ** e + (256 * xq + 46) ** e - c
sage: 
sage: fp.roots()
sage: fq.roots()

Sin embargo, esto tardará mucho en finalizar. Una forma rápida de obtener una raíz es usar any_root:

sage: fp.any_root()
38745752538982310497402322032299730998

Podemos hacer lo mismo con definido en y calcular el CRT. Obviamente, puede haber muchas raíces, por lo que necesitamos ejecutar any_root varias veces hasta obtener la deseada. Sin embargo, incluso si encontramos las raíces deseadas, no podremos obtener el mensaje esperado. Observa que la flag tiene 41 bytes de longitud, por lo que el mensaje tiene 53 bytes de longitud debido a "The flag is ". Recuerda que es un entero de 256 bits, es decir, de 32 bytes. Por lo tanto, en lugar de encontrar el mensaje esperado , obtendremos , y no será trivial encontrar .

La forma de abordar este problema es considerar los bytes conocidos, de modo que , donde es el valor entero de "The flag is maltactf{\0\0...\0}", y es el valor entero desconocido de la flag interna, reemplazando los bytes nulos. Con esto, la nueva incógnita tiene solo 31 bytes de longitud (41 menos la longitud de "maltactf{}"), lo cual es menor que ; y por lo tanto encontraremos el valor exacto. Así que, este es el polinomio después del cambio de variable:

sage: M = int.from_bytes(b'The flag is maltactf{???????????????????????????????}'.replace(b'?', b'\0'))
sage: 
sage: fp = (M + 256 * yp) ** e + (256 * (M + 256 * yp) + 46) ** e - c
sage: fq = (M + 256 * yq) ** e + (256 * (M + 256 * yq) + 46) ** e - c

Ahora, usando any_root varias veces tanto en fp como en fq y probando con el CRT, eventualmente encontraremos la flag.

Truco para hallar raíces

Sin embargo, hay otra forma de calcular raíces de un polinomio bajo un cuerpo finito, que es un truco de implementación en SageMath.

Consideremos en , donde es un número primo. Sabemos que para cualquier porque (pequeño teorema de Fermat), y . En otras palabras, todos los elementos de son una raíz de , lo que significa que puede reescribirse como:

Regresemos al reto. Teóricamente, tiene al menos una raíz (sabemos que existe ya que la flag satisface la ecuación). Sin pérdida de generalidad, consideremos como bajo y . Recuerda que para cualquier elemento de . Por lo tanto, las raíces de también son raíces de . Como resultado, podemos usar el máximo común divisor (GCD) de polinomios para considerar solo las raíces comunes (precisamente, las que queremos de ), así que

Sin embargo, no podemos simplemente definir en SageMath como yp ** p - yp, porque se quejará de que el exponente es enorme. En cambio, recordemos esta propiedad del GCD: . Podemos usar esta propiedad de forma astuta para definir como pow(yp, p, fp) - yp.

Así, podemos obtener todas las posibles raíces de en y en :

sage: roots_p = fp.gcd(pow(yp, p, fp) - yp).roots(multiplicities=False)
sage: roots_q = fq.gcd(pow(yq, q, fq) - yq).roots(multiplicities=False)

Flag

En este punto, solo necesitamos considerar cada par posible, calcular el CRT y ver si el resultado es la flag esperada:

sage: from itertools import product
sage: 
sage: for rp, rq in product(roots_p, roots_q):
....:     if (data := long_to_bytes(crt([int(rp), int(rq)], [p, q]))).isascii():
....:         print((b'maltactf{' + data + b'}').decode())
....: 
maltactf{Ferm4ts_littl3_polyn0mial_tr1ck}