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 remainder
en el código. Cada una de las particiones se cifra como:
Donde output.txt
. Nótese que
Encontrando la debilidad
Conocemos estos valores:
Nótese que
Entonces,
Y por tanto,
Y ahora que tenemos
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
.