baby quick maffs

2 minutos de lectura

Se nos proporciona este código en Python para cifrar la flag, y nos dan el archivo output.txt:

#!/usr/bin/env python3
from secret import flag, p, q
from Crypto.Util.number import bytes_to_long
from random import randint


def partition_message(m, N):
    m1 = randint(1, N)
    parts = []
    remainder = 0
    while sum(parts) < m:
        if sum(parts) + m1 < m:
            parts.append(m1)
        else:
            remainder = m - sum(parts)
            parts.append(m1 + remainder)
    return (parts, remainder)


def encode(message, N):
    m = bytes_to_long(message)
    parts, remainder = partition_message(m, N)  
    ciphers = [pow(c, 2, N) for c in parts]
    return (ciphers, remainder)


N = p * q
ciphers, remainder = encode(flag, N)

with open("output.txt", "w") as f:
    out = f'{N}\n{remainder}\n{ciphers}'
    f.write(out)

6083782486455360611313889289556658208725888944237734041722591252756006664878102248734673207367745303402874595854966731263105387801996693270011840173939423
1081087287982224274239399953615475281184099226198643053396569433856757255106426461817760194704250226883807897800355728788149068771546876055268915238961343
[5408283916250636369066846815501131861319520431106165986129813106223074286810632222888292034380612581416458756909119954039579666773680866532576166358987272, 5408283916250636369066846815501131861319520431106165986129813106223074286810632222888292034380612581416458756909119954039579666773680866532576166358987272, 5598555010250184271123226314796180406367795504188162611960100902143581636125416986623404842897202277277978566659455918773104687212096435095590205751904580]

Analizando el cifrado

Vamos a ver qué tenemos. El cifrado consiste en coger un número aleatorio $m_1$ de manera que $1 \leqslant m_1 \leqslant N$, donde $N = p q$. Luego, coge la flag como $m$ (formato decimal) y la particiona como $m = m_1 + m_1 + r$ (hay tres elementos en la lista del resultado), donde $r$ es remainder en el código. Cada una de las particiones se cifra como:

$$ a = m_1^2 \mod{N} $$

$$ b = m_1^2 \mod{N} $$

$$ c = (m_1 + r)^2 \mod{N} $$

Donde $a, b, c$ son los tres valores de la lista de output.txt. Nótese que $a = b$, evidentemente.

Encontrando la debilidad

Conocemos estos valores: $N$, $r$ y $[a, b, c]$.

Nótese que

$$ c = (m_1 + r)^2 = m_1^2 + 2 m_1 r + r^2 = a + 2 m_1 r + r^2 \mod{N} $$

Entonces,

$$ 2 m_1 r = c - a - r^2 \mod{N} $$

Y por tanto,

$$ m_1 = (2 r)^{-1} \cdot (c - a - r^2) \mod{N} $$

Y ahora que tenemos $m_1$, podemos encontrar $m = m_1 + m_1 + r$.

Implementación en Python

Este es un script en Python para resolver el reto:

#!/usr/bin/env python3

def main():
    with open('output.txt') as f:
        N = int(f.readline())
        remainder = int(f.readline())
        a, b, c = eval(f.readline())

    m1 = pow(2 * remainder, -1, N) * (c - a - remainder ** 2) % N  
    m = m1 + m1 + remainder

    print(bytes.fromhex(hex(m)[2:]).decode())


if __name__ == '__main__':
    main()

Flag

$ python3 solve.py
HTB{d0nt_ev4_r3l4ted_m3ss4ge_att4cks_th3y_ar3_@_d3a1_b7eak3r!!!}

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