Basic LLL - L3AK2025

Autor del reto: S1mple

Dificultad: Fácil

Enunciado

“Simple crypto is the best crypto.”

Archivos

En este reto, tenemos el siguiente archivo.

• basic-lll.sage: Contiene un script de encriptado.

Archivos utilizados aquí.

Analizando el reto

Si abrimos el código podemos observar lo siguiente.

def generate():
    p = random_prime(2^1024, lbound=2^1023)
    x=randint(1,2^16)
    y=randint(1,2^256)
    a=randint(2^1023,2^1024)
    q=random_prime(2^1024)
    n=p*q
    return x,a,y,n,p

x,a,y,n,p = generate()
k = x * y + a * p
e=65537
print(f"x = {x}")
print(f"a = {a}")
print(f"n = {n}")
print(f"k = {k}")

m = b'L3AK{<Redacted>}'
flag = int.from_bytes(m, byteorder='big')
c= pow(flag, e, n)
print(f"c = {c}")

'''
x = 54203
a = 139534605978199350449870348663594126359773246906906418074945064315708552206952695156472923968554408862426942537522569163756593332601739006413404986641247624386522169136633429464195370373009454673819688653512479919153332504769835621608305089536245284458011218876474599059184828911301976396971466368457267831713
n = 12909957208634846878337953184362917609451224905637563117148705894888627434882610771803126452504238664471840340722310690445704139825753660053450331966698205860077330083433391290469454571152366284661640391190008258576947840075212180965738595761925516686689797153224716140447515370184846067654512660266993573880775530634588475842083212670090415716860925772115834314563453955681012820960922892736520042799257599331942717963921797157341454739255402633419216921702659541513141028779948257696746810146033667942181244847983610429227387863821351416689099862418820999250005071861968501333899759899513283613946626413863922604073
k = 24474689179117620559916890529357882261493825442019850679598519081287156822984032786458479363048845076078220151760752906879055457682971398809768604333650029141164831566127754715775782823279839766009120238777348170982471623193652714921064243946655726118484337862412275391615166714375745390409664610412156281691721978732319253694004232933156865189917761521085635692596755802274763409871937618659197646864593743015558828475450200247766980008744319676783526158213931581034209356092026748307730083927225249093712227456855972520574747646873074625455900058136458828591335711677741591552501530047335481073272381631524755666119
c = 11185314040721202177044508537272244264288033276739579716599246665772965854249656943282002695659011960313245796587834222078633141747802754149848079632693280265262199729548775879612614113828267471629389698999657686858047585254549801752634049341009476489652456620836030696102393122618822021082792763848220677651608135328630551380537642144416978955966827336280510774254681264136102268730343853559751471313539810499170669215479225898738527316798768622089152851154959800113070358637984124299357803777453137311143202502153552192970732744885328421213081964363890280109214401691255867427694709196120824176729643585687319321473
'''

A grandes rasgos, este código genera un par de números primos para calcular n, cifra la flag y calcula k y c mediante \(K = x*y + a*p\) que utiliza para esconder parcialmente el primo p usando un valor a

Solución

Como se menciona en el enunciado, este código es vulnerable a un ataque basado en reducción por la manera en que se contruye la variable k.

\[k = a \cdot p + x \cdot y\]

Donde sabemos:

• p es un primo secreto grande (~1024 bits).
• a es un entero grande conocido (~1024 bits).
• x es un número pequeño (~16 bits).
• y también es relativamente pequeño (~256 bits).
• Por tanto, el error $x \cdot y$ es mucho más pequeño que $a \cdot p$.

En este caso, podemos recuperar el primo p a partir de \(k = a \cdot p + \text{error}\)

Dado que a y k son conocidos, y el término de error es pequeño, esto se reduce a un problema clásico de “residuos con error pequeño” el cual mediante LLL, encontramos vectores cortos en retículos.

Por lo que tenemos que construir una retícula (lattice) en la que el vector corto nos proporcione la corrección de error o directamente el primo p,

La idea es transformar la ecuación:

\[k = a \cdot p + e\]

En un problema de reducción de retícula:

• El vector $[a, -k]$ vive en una retícula generada por $[a, 0]$ y $[1, M]$, donde M es un valor grande (por ejemplo, $2^{1024}$).
• Al aplicar LLL, se pueden recuperar los valores pequeños como e = x*y.

Además la siguiente información nos comprueba que efectivamente es vulnerable a este tipo de ataque.

• x tiene solo 16 bits.
• y tiene solo 256 bits.
• Entonces $e = x \cdot y \leq 2^{272}$, que es mucho menor que $a \cdot p \sim 2^{2048}$.
• Eso hace que el error sea muy pequeño en comparación con el término principal, y por lo tanto detectable y corregible con LLL.

El código final es el siguiente.

from sage.all import *
import binascii

x_known = 54203
a = 139534605978199350449870348663594126359773246906906418074945064315708552206952695156472923968554408862426942537522569163756593332601739006413404986641247624386522169136633429464195370373009454673819688653512479919153332504769835621608305089536245284458011218876474599059184828911301976396971466368457267831713
n = 12909957208634846878337953184362917609451224905637563117148705894888627434882610771803126452504238664471840340722310690445704139825753660053450331966698205860077330083433391290469454571152366284661640391190008258576947840075212180965738595761925516686689797153224716140447515370184846067654512660266993573880775530634588475842083212670090415716860925772115834314563453955681012820960922892736520042799257599331942717963921797157341454739255402633419216921702659541513141028779948257696746810146033667942181244847983610429227387863821351416689099862418820999250005071861968501333899759899513283613946626413863922604073
k = 24474689179117620559916890529357882261493825442019850679598519081287156822984032786458479363048845076078220151760752906879055457682971398809768604333650029141164831566127754715775782823279839766009120238777348170982471623193652714921064243946655726118484337862412275391615166714375745390409664610412156281691721978732319253694004232933156865189917761521085635692596755802274763409871937618659197646864593743015558828475450200247766980008744319676783526158213931581034209356092026748307730083927225249093712227456855972520574747646873074625455900058136458828591335711677741591552501530047335481073272381631524755666119
c = 11185314040721202177044508537272244264288033276739579716599246665772965854249656943282002695659011960313245796587834222078633141747802754149848079632693280265262199729548775879612614113828267471629389698999657686858047585254549801752634049341009476489652456620836030696102393122618822021082792763848220677651608135328630551380537642144416978955966827336280510774254681264136102268730343853559751471313539810499170669215479225898738527316798768622089152851154959800113070358637984124299357803777453137311143202502153552192970732744885328421213081964363890280109214401691255867427694709196120824176729643585687319321473
e = 65537

def solve_lll():
    print("Resolviendo con reducción de LLL...\n")

    # Lattice basado en la relación: k = x * y + a * p
    M = Matrix(ZZ, [
        [a, 1, 0],
        [x_known, 0, 1],
        [k, 0, 0]
    ])

    L = M.LLL()

    print("Vectores reducidos por LLL:")
    for i, vec in enumerate(L):
        print(f"  Vector {i}: {vec}")

        if vec[0] == 0 and vec[1] != 0:
            potential_p = abs(vec[1])
            potential_y = abs(vec[2])
            print(f"    Candidato posible: p = {potential_p}, y = {potential_y}")

            if 2^1023 < potential_p < 2^1024 and is_prime(potential_p):
                if x_known * potential_y + a * potential_p == k:
                    print("    ¡Verificación exitosa!")
                    return potential_p, potential_y

    # Método alternativo con GCD
    print("\nIntentando con propiedades modulares...")
    for vec in L:
        if vec[1] != 0:
            potential_p = abs(vec[1])
            if n % potential_p == 0 and is_prime(potential_p):
                y_calc = (k - a * potential_p) // x_known
                if x_known * y_calc + a * potential_p == k:
                    print("    ¡Verificación con módulo exitosa!")
                    return potential_p, y_calc

    print("No se encontró un p válido.")
    return None, None

def decrypt_flag(p):
    if p is None:
        print("No se puede descifrar: p es None")
        return

    q = n // p
    if p * q != n:
        print("Error: p * q no coincide con n")
        return

    phi_n = (p - 1) * (q - 1)
    d = pow(e, -1, phi_n)
    flag_int = pow(c, d, n)

    flag_bytes = flag_int.to_bytes((flag_int.bit_length() + 7) // 8, byteorder='big')
    print(f"\nFlag descifrado (bytes): {flag_bytes}")

def main():
    p, y = solve_lll()

    if p:
        print("\n== Parámetros encontrados ==")
        print(f"p = {p}")
        print(f"y = {y}")
        print(f"Verificación: x*y + a*p = {x_known * y + a * p}")
        print(f"k = {k}")
        print(f"¿Coinciden? {x_known * y + a * p == k}")

        decrypt_flag(p)
    else:
        print("\nNo se pudo resolver el problema con los métodos implementados.")

if __name__ == "__main__":
    main()

Flag

L3AK{u_4ctu4lly_pwn3d_LLL_w1th_sh0rt_v3ct0rs_n1c3}