May 20

Solusi CTF IDSECCONF 2013 – Medium Programming

Berhubung kemarin ada waktu buat iseng ikut CTF di IDSECCONF 2013, ada yang ingin dibagi disini. Ada satu soal yang cukup menarik di CTF tahun ini, yaitu mengenai bilangan prima. Panitia menyediakan sebuah file PDF berukuran 7.2 MB yang berisi sejumlah besar bilangan. Kita diminta untuk mencari manakah bilangan yang bukan bilangan prima.

Masalah pertama yang dihadapi adalah bagaimana mengambil data teks yang ada di dalam PDF tersebut. Sebetulnya kita bisa menggunakan beberapa script yang ada untuk mengambil data, tetapi berhubung waktu tersisa tinggal beberapa menit, akhirnya nekat saja menggunakan Ctrl+A, Ctrl+C, Ctrl+V ke text editor. Meskipun cukup berat, untung saja berhasil. Langkah berikutnya adalah menghilangkan tanda ‘[‘ di awal data.

Cara memeriksa apakah suatu bilangan adalah bilangan prima sebetulnya dapat dilakukan dengan cara membagi squareroot dari bilangan tersebut dengan seluruh bilangan ganjil yang lebih kecil. Tetapi cara tersebut akan butuh waktu lama, karena di sini ada ratusan ribu atau bahkan jutaan bilangan yang harus diperiksa. Untuk itu ada satu algoritma yang sangat efisien untuk memeriksa bilangan prima, yaitu MILLER RABIN ALGORITHM

Dengan bekal dari mbah google dan sedikit modifikasi, script python untuk memecahkan soal CTF ini dapat diunduh di sini. Yang dilakukan script ini pertama kali adalah parsing tiap baris dan mengambil bilangan-bilangan yang ada, kemudian memeriksa bilangan tersebut dengan algoritma Miller Rabin. Jika bukan bilangan prima, maka akan ditampilkan nilainya. Algoritma ini cukup cepat, kira-kira 5 menit dia sudah berhasil memeriksa semua bilangan yang ada, dan muncullah 3 buah bilangan yang bukan prima, yang jika digabungkan, nilainya adalah 1084956205735190077777.

Be Sociable, Share!

0
comments

Reply

[+] kaskus emoticons nartzco