[PicoCTF 2022] – Sequences

Description

Solution

diberikan sebuah file sequences.py seperti berikut:

Analisis Kode

Inti dari kode di atas adalah fungsi decrypt_flag akan menerima variabel sol, yang nantinya akan diverifikasi apakah nilai dari sol tersebut benar atau tidak dengan membandingkan hashnya dengan “VERIF_KEY”, yang apabila benar maka variabel tersebut akan digunakan untuk memproduksi key pemecah encryptionnya.

Nilai dari sol ini sendiri juga sebenarnya dapat kita peroleh secara otomatis dari fungsi m_funct. namun masalahnya adalah untuk memperoleh nilai ini harus dilakukan recursion berulang kali sebanyak 2e7 atau 20000000 kali, sehingga tentunya cara ini membutuhkan waktu terlalu lama. Kita butuh melakukan optimisasi agar fungsi berjalan lebih cepat.

Pemecahan

Kita coba lihat fungsi m_func, fungsi ini akan me-return

55692*m_func(i-4) – 9549*m_func(i-3) + 301*m_func(i-2) + 21*m_func(i-1)

setiap kali dipanggil, yang artinya rekursif. Terlihat familiar bukan? Ya, fungsi ini serupa dengan fungsi rekursif fibonacci sequence, namun dengan tambahan beberapa konstanta dan range yang lebih banyak.

kode fibonacci normal

Berpatokan dari hint yang diberikan, saya baru mengetahui bahwa fibonacci dapat dioptimisasi dengan konsep matrix diagonalization. Karena soal ini mirip seperti fibonacci, mungkin kita bisa memodifikasi sedikit konsep matrix tersebut. saya menggunakan referensi ini dan ini.

Step 1: cari A (core matrix)

Pertama, kita dapat mengubah fungsi rekursif m_funct menjadi notasi Fn seperti berikut dengan n adalah jumlah iterasi:

untuk membuat sistem persamaan linear, kita butuh 3 persamaan lagi. Supaya gampang, masing-masing persamaan bisa kita dapat hanya dengan mengalikan 0 pada setiap term n selain yang dicari.

F(n-1) = F(n-1) + (0)*F(n-2) + (0)*F(n-3) + (0)*F(n-4)
F(n-2) = (0)*F(n-1) + F(n-2) + (0)*F(n-3) + (0)*F(n-4)
F(n-3) = (0)*F(n-1) + (0)*F(n-2) + F(n-3) + (0)*F(n-4)

sehingga dapat dibentuk dalam notasi matriks seperti berikut:

model matriks ini kita simpan dan kita namai sebagai “A”

Step 2: cari eigenvectors dari A, gabungkan.

Selanjutnya, yang perlu kita cari adalah eigenvectors dari matriks A ini. Biar cepat, saya menggunakan tools online https://www.symbolab.com/solver/matrix-eigenvectors-calculator/ dan hasilnya:

diperoleh empat buah vector eigen, keempatnya kita gabungkan menjadi matriks sendiri dan kita namai sebagai “S”

Step 3: cari diagonal matrix (Λ)

Dan yang terakhir kita butuhkan adalah mencari matrix diagonal (Λ), dan bisa kita dapatkan dengan rumus:

matriks diagonal = (S invers)*(matriks A)*(matriks S)
(langsung ke hasilnya biar cepet)

Final step: hitung F(n)

Matriks A, Matriks diagonal Λ, dan matriks S sudah kita temukan, maka untuk mencari bilangan m_funct ke-n dapat menggunakan rumus berikut.

digunakan permisalan n = 0, maka:
F(0) = 1,
F(0+1) = 2,
F(0+2) = 3,
F(0+3) = 4
karena itu juga terdapat perkalian dengan matriks [4, 3, 2, 1]

Dari sini, kita tinggal memasukkan ITERS sebagai n pada matriks diagona. Setelah perkalian di sisi kiri dilakukan oleh komputer (yang seharusnya menjadi jauh lebih cepat dibanding metode rekursif), maka akan didapatkan sebuah matriks 4×1 sebagai matriks hasil.

Yang mau kita cari adalah F(n), sehingga kita hanya perlu mengambil nilai matriks baris ke-4 dari matriks hasil, lalu nilai tersebut tinggal di-passing ke function decrypt_flag(), dan flag pun didapatkan.

Seluruh konsep di atas dijadikan dalam bentuk script python dengan module sage, dan inilah hasil script yang saya buat:

output:

calculation time: <5s

Flag: picoCTF{b1g_numb3rs_cd8e813d}

referensi:

https://medium.com/@andrew.chamberlain/the-linear-algebra-view-of-the-fibonacci-sequence-4e81f78935a3

http://www.math.hawaii.edu/~pavel/fibonacci.pdf

Leave a Reply

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