[ARACTF Qual 2022] – Numbers

Chall.py

from Crypto.Util.number import bytes_to_long
from flag import FLAG

f1, f2, f3, f4 = [bytes_to_long(FLAG[i:i+8]) for i in range(0, len(FLAG), 8)]

print(f'{f1**3 – f2**3 + f3 – f4 = }’)
print(f'{-f1**3 * f2**3 + f1**3 * f3 – f2**3 * f3 – f1**3 * f4 + f2**3 * f4 – f3 * f4 = }’)
print(f'{-f1**3 * f2**3 * f3 + f1**3 * f2**3 * f4 – f1**3 * f3 * f4 + f2**3 * f3 * f4 = }’)
print(f'{f1**3 * f2**3 * f3 * f4 = }’)

output.txt

f1**3 – f2**3 + f3 – f4 = -154349410602236914368877960074454245584617536741274771201
-f1**3 * f2**3 + f1**3 * f3 – f2**3 * f3 – f1**3 * f4 + f2**3 * f4 – f3 * f4 = -173300260595425513368006654853724366639234098975846023255973730400067103563681384340773876217479712872605985785121
-f1**3 * f2**3 * f3 + f1**3 * f2**3 * f4 – f1**3 * f3 * f4 + f2**3 * f3 * f4 = -649560207765725124119095639623286131226265601775204230243569659459611663387954438352044423083359356546898517306231466777967489926719
f1**3 * f2**3 * f3 * f4 = 20313138117747746241186774106446632463641261791426299190459482804563306036297162159526171331177242643844748405380302184559404183866619475228749207040

Analisis Code

Untuk code soal ini cukup straightforward, yaitu flag dipisah per 8 karakter dan ditampung dalam variabel f1, f2, f3, f4, lalu variabel-variabel tersebut dimasukkan ke dalam operasi seperti yang ditampilkan di code soal. Tugas kita adalah mencari tahu berapa nilai f1, f2, f3, dan f4 untuk disusun kembali menjadi flag semula.

Solusi

Untuk memecahkan soal ini, kita dapat menggunakan fitur dari sagemath yaitu solve() yang mampu memecahkan persamaan-persamaan aljabar seperti ini. Penjelasan detailnya dapat di link ini: https://doc.sagemath.org/html/en/tutorial/tour_algebra.html

Maka dari itu, kami menyusun script sage seperti ini:

from Crypto.Util.number import *
f1, f2, f3, f4 = var(‘f1 f2 f3 f4’)

eq1 = (f1^3 – f2^3 + f3 – f4 == -154349410602236914368877960074454245584617536741274771201)

eq2 = (-f1^3 * f2^3 + f1^3 * f3 – f2^3 * f3 – f1^3 * f4 + f2^3 * f4 – f3 * f4 == -173300260595425513368006654853724366639234098975846023255973730400067103563681384340773876217479712872605985785121)

eq3 = (-f1^3 * f2^3 * f3 + f1^3 * f2^3 * f4 – f1^3 * f3 * f4 + f2^3 * f3 * f4 == -649560207765725124119095639623286131226265601775204230243569659459611663387954438352044423083359356546898517306231466777967489926719)

eq4 = (f1^3 * f2^3 * f3 * f4 == 20313138117747746241186774106446632463641261791426299190459482804563306036297162159526171331177242643844748405380302184559404183866619475228749207040)

solns = solve([eq1,eq2,eq3,eq4],f1, f2, f3, f4, solution_dict=True)
for i in solns:
    print(i)

Output:

Seperti yang bisa dilihat pada gambar, sagemath secara otomatis melakukan komputasi terhadap kemungkinan-kemungkinan nilai variabel f1, f2, f3, dan f4 yang memenuhi persamaan. Namun karena bytes_to_long() terhadap flag tidak mungkin menghasilkan nilai negatif (dengan kata lain, nilai variabelnya juga tidak boleh negatif), maka secara manual (baca: males scripting) kami mencari nilai f1, f2, f3, dan f4 yang seluruhnya positif. Kami menemukannya di sini:

Karena nilai-nilainya sudah kita ketahui, tinggal memasukkannya ke dalam array, lalu looping sembari ubah ke byted dengan long_to_bytes() dan decode, lalu diprint secara menyatu.

From Crypto.Util.number import *
flag = [ 7021781637208879739,  7939974096361578344,  3779193398384159865,  31015492973259901]
for i in flag:
    print(long_to_bytes(i).decode(), end=””)

Output:

 

Flag = ara2022{n0t_so_h4rd_p0lyn0m14l}

Leave a Reply

Your email address will not be published. Required fields are marked *