Rangkuman Kuis Kode: Basic Cryptanalisys

Cryptanalisys merupakan proses mempelajari sistem kriptografi untuk mencari kelemahan atau bocornya informasi. Sebuah kuis *Basic Cryptanalisys dapat ditemukan di HackerRank menarik untuk dipecahkan. *Penulis berkesempatan untuk menyelesaikan kuis tersebut. Tulisan kali ini akan berisi proses dalam penyelesaian kuis tersebut sebagai pembelajaran bersama. Sebagai informasi, penulis menggunakan bahasa Golang untuk mengimplementasikan proses algoritmanya.

Image Source: live.staticflickr.com

Pada soal diberikan beberapa bahan. Bahan yang pertama adalah sekumpulan ciphertext atau tulisan yang telah dikodekan. Ciphertext inilah yang menjadi tugas untuk diterjemahkan kembali menjadi plaintext sehingga dapat dibaca isinya. Bahan yang kedua adalah sekumpulan kata-kata dalam kamus yang menjadi sumber dari isi plaintext. Pada kamus ini diberikan keterangan bahwa istilah yang ada di dalamnya merupakan istilah khusus, sehingga statistik bahasa umum akan percuma untuk digunakan dalam pemecahan kuis ini. Informasi lain yang diberikan adalah jenis teknis kriptografi yang digunakan. Teknik kriptografi yang digunakan adalah Mono Alphabetic Substitution Cipher (MASC). Sebuah teknik menukar sebuah huruf dengan huruf lainnya. Tabel pemetaan dari sebuah haruf ke huruf lainnya tidak berikan sebagai petunjuk.

Pada awal menganalisa kuis ini, terdapat dua cara yang terpikirkan. Yang pertama adalah melakukan bruteforce dari himpunan semesta kunci (keyspace). Cara yang kedua adalah mencari jarak antar huruf yang berdampingan sebagai sebuah atribut dan memetakan atribut tersebut dari ciphertext ke dictionary yang memiliki kesamaan nilai atribut.

Cara yang pertama relatif mudah untuk disusun baris kodenya. Namun cara pertama ini memiliki kompleksitas waktu yang besar yaitu 26!. Angka 26 muncul dari banyaknya variasi permutasi alfabet dari 26 huruf alfabet. Bisa jadi solusinya ditemukan, namun ada kemungkinan terkena batas waktu eksekusi algoritma terlebih dahulu. Secara aturan kuis, ada batasan waktu dalam menjalankan algoritma yang dibuat.

Twitter.com

Cara kedua setelah direnungkan ternyata tidak cocok diimplementasikan untuk menjadi solusi. Karena teknik kriptografi yang digunakan bukanlah Caesar Cipher. Caesar Cipher sudah pasti merupakan MASC. Namun dalam kuis ini pemetaannya setelah diperhatikan tidak memiliki jarak huruf yang sama selayaknya yang terjadi di Caesar Cipher. Oleh karenanya cara kedua ini gugur.

Akhirnya penulis fokus lagi ke cara yang pertama. Terdapat kemungkinan terburuk kompleksitas waktu dapat melewati batas waktu yang diberikan. Oleh karena itu perlu dicari cara untuk mengoptimasi bruteforce yang dilakukan keyspace. Bila diperhatikan keyspace berisi pemetaan dari huruf plaintext kepada huruf ciphertext. Hal ini konsisten dengan kebalikan atau proses dekripsinya. Artinya bila huruf “a” dipetakan ke huruf “j” pada proses enkripsi, maka huruf “j” akan dipetakan ke huruf “a” pada proses dekripsi. Di sinilah tercetus ide bruteforce yang dilakukan tidak benar-benar acak. Bruteforce yang dilakukan bertujuan untuk menemukan pasangan dari ciphertext dengan dictionary atau kamus diberikan sebagai bahan. Sambil menjalankan proses bruteforce, dicatat pula variasi-variasi key yang terbuat. Bila key yang ditemukan konsisten hingga akhir, maka key itulah yang merupakan pemetaan dari MASC pada kuis ini.

[embed]

Dari implementasi kode di atas, berhasil dilakukan proses cracking dari MASC pada kuis ini. Kompleksitas waktu menurut penulis tetap O(n!) pada kondisi terburuk. Namun hal ini dapat dipangkas secara signifikan bilamana deretan ciphertext di awal-awal proses sangat variatif. Proses pencarian key dianggap lengkap bila telah lengkap 26 alfabet dipetakan. Misalkan rata-rata sebuah kata terdapat 4 jenis huruf yang unik. Maka dibutuhkan 7 kata yang ortogonal atau tidak berbagi huruf yang sama. Sehingga dalam contoh ini ada kemungkinan 26! dibagi 19! kemungkinan keyspace.

Hasil Running

Penutup

Saya ucapkan terima kasih bagi pembaca yang sabar membaca setiap kalimat hingga bagian ini. Tetap semangat untuk belajar hal baru. Silahkan bila ada pandangan lain dari rekan pembaca dapat disampaikan di kolom komentar untuk dapat bersama-sama kita diskusikan.