Cryptography Vigenere Cipher

8 min readAug 18, 2020

Halo, setelah sebelumnya saya membahas mengenai cryptography Caesar Cipher. Pada kesempatan kali ini saya akan membahas algoritma lainnya yaitu Vignere Cipher. Algoritma ini prinsip dasarnya sama dengan Caesar Cipher, yaitu melakukan subtitusi dan pergeseran pada plaintext, namun kemungkinan key yang digunakan bisa lebih banyak. Mari kita langsung ke pembahasan.

Vigenere Cipher

Vigenere Cipher merupakan jenis algoritma cryptography dengan melakukan perubahan informasi melalui subtitusi (pergeseran) dengan menggunakan key berupa deretan kata.

Algoritma ini pertama kali dikenalkan oleh Giovan Battista Bellaso pada abad ke 16 dengan sebutan Autokey Cipher. Algoritma ini sangatlah tangguh terhadap pembobolan sampai abad ke 19. Sampai dengan Friedrich Kasiski memperkenalkan metode miliknya untuk melakukan dechipering Vigenere Cipher yang disebut Kasiski Algorithm. Pada abad ke 19 juga seorang ilmuan bernama Blaise de Vigenère memperbaharui algoritma Autokey Cipher, dan telah terjadi kesalah pahaman tentang “first inventor” dari algoritma ini, sehingga namanya-lah yang digunakan sebagai nama dari algoritma Vigenere Cipher hingga sampai saat ini.

Pada dasarnya algoritma ini hampir sama dengan algoritma Caesar Cipher hanya saja key yang digunakan tidak menggunakan satu nilai, melainkan deretan kata yang telah dimetakan kedalam angka numerik. Formula yang digunakan untuk melakukan encryption dan decryptionnya pun serupa yaitu:

E(x) adalah hasil encryption, dimana x adalah dari huruf original atau plaintext.
D(x) adalah hasil decryption, dimana x adalah dari huruf yang telah terdecrypt atau ciphertext.
k adalah nilai atau key yang digunakan untuk menggeser huruf. Pada Vigenere Cipher i menunjukan huruf ke- yang dilakukan encryption
Mod 26 masih digunakan dikarenakan untuk membuat kata kita masih menggunakan huruf alfabet, sehingga ketika nilai operasinya lebih atau kurang dari 26 maka kita akan tetap dapat melakukan pemetaannya.
Kita ingin memastikan bahwa hasil dari encryption masih berada dalam rentang dari [0, ukuran_alfabet-1], sehingga kita gunakanlah mod26.

Contoh Kasus:

Kita akan melakukan encryption pada kalimat “HALO BUDYMAN” dimana key yang kita gunakan adalah kata “RAHASIA”. Maka untuk menghasilkan ciphertext hal yang kita lakukan adalah

Sedangkan untuk melakukan decrpytion kita hanya akan melakukan hal yang sebaliknya

Mudah sekali bukan !!! Proses yang dilakukan sama persis dengan yang dilakukan Caesar Cipher hanya saja key yang digunakan akan lebih beragam tergantung kata yang kita gunakan sebagai keynya. Karena hal inilah algoritma Vigenere Cipher cukup lama dapat dibobol hingga metode kasiski ditemukan.

Untuk lebih jelasnya saya sudah membuat contoh penggunaan Vigenere Cipher dengan menggunakan pemograman Python pada jupyter notebook yang bisa diakses di Example Vigenere Cipher. Pada contoh di jupyter notebook, list alphabet ditambahkan “spasi” yang berada pada index 0, sehingga totalnya list alphabet berubah menjadi 27.

Aplikasi Vigenere Cipher pada Python Notebook

Cracking Vigenere Cipher

Melakukan pembobolan pada Vigenere Cipher jauh lebih sulit dibandingkan dengan melakukannya pada Caesar Cipher. Dikarenakan jumlah kemungkinan key nya sangatlah besar yaitu 26^(panjang key). Terdapat dua cara untuk melakukan pembobolan pada algoritma ini yaitu:

Dictionary Attack, kita bisa menggunakan kumpulan dari kata pada suatu database dan melakukan Brute Force Attack.
Menggunakan Kasiski Algorithm.

Kasiski Algorithm

Algoritma ini dibuat oleh Friedrich Kasiski pada tahun 1863 dan dikembangkan juga oleh Charles Babbage. Pada dasarnya jika kita mengetahui panjang dari key yang digunakan, kita bisa melakukan analisa frekuensi untuk melakukan decryption pada ciphertext yang kita miliki. Informasi leaking sangat diperlukan untuk dapat melakukan pembobolan dengan menggunakan algoritma ini. Tahap-tahapannya adalah sebagai berikut

Kita harus menemukan kata yang berulang (repeated substrings) pada ciphertext (minimal 3 huruf berurutan berulang).
Mencari jarak antara repeated subtrings dan menemukan faktor untuk valuenya.
Kita gunakan analisa frekuensi untuk menemukan kata yang digunakan untuk key.
Melakukan Brute Force dengan menggunakan sub keys yang memungkinkan.

Contoh kasus:

Misalnya terdapat suatu ciphertext

PPQCAXQVEKGYBNKMAZUYBNGBALJONITSZMJYIMVRAGVOHTVRAUCTKSGDDWUOXITLAZUVAVVRAZCVKBQPIWPOU

1. Mencari Kata Berulang (Repeated Substrings)

dari ciphertext tersebut kita dapatkan tiga jenis kata berulang yaitu: VRA, AZU, dan YBN

PPQCAXQVEKGYBNKMAZUYBNGBALJONITSZMJYIMVRAGVOHTVRAUCTKSGDDWUOXITLAZUVAVVRAZCVKBQPIWPOUPPQCAXQVEKGYBNKMAZUYBNGBALJONITSZMJYIMVRAGVOHTVRAUCTKSGDDWUOXITLAZUVAVVRAZCVKBQPIWPOUPPQCAXQVEKGYBNKMAZUYBNGBALJONITSZMJYIMVRAGVOHTVRAUCTKSGDDWUOXITLAZUVAVVRAZCVKBQPIWPOU

Setelah menemukan kata yang berulang, kita hitung jarak diantaranya:

Antara kata pertama dan kedua pada VRA terdapat 8 huruf.
Antara kata kedua dan ketiga pada VRA terdapat 24 huruf.
Antara kata pertama dan ketiga pada VRA terdapat 32 huruf.
Antara kata pertama dan kedua pada AZU terdapat 48 huruf.
Antara kata pertama dan kedua pada YBN terdapat 8 huruf.

2. Mencari Faktor dari Kata Berulang

Jarak antara kata berulang pada kalimat di atas adalah 8, 8, 24, 32, dan 48. Faktor-faktornya adalah

8 : 2, 4, dan 8.24 : 2, 4, 6, 8, 12, dan 24.32 : 2, 4, 8, 16, dan 32.48 : 2, 4, 6, 8, 12, 24, dan 48.

Jika kita hitung jumlah dari setiap faktornya:

2 sebanyak 4 buah.4 sebanyak 4 buah.6 sebanyak 2 buah.8 sebanyak 4 buah.12 sebanyak 2 buah.16 sebanyak 1 buah.24 sebanyak 2 buah.32 sebanyak 1 buah.48 sebanyak 1 buah.

Faktor yang memiliki nilai terbanyak kemungkinan besar adalah panjang dari key Vigenere Cipher. Dari contoh diatas faktor dengan jumlah terbanyak adalah 2, 4, dan 8.

3. Melakukan Analisa Frekuensi

Jika kita mengasumsikan panjang keynya adalah 4. Kita akan memetakan kata dengan jarak 4 kata

Setiap 4 kata yang dimulai dari huruf pertama: PPQCAXQVEKGYBNKMAZUYBNGBALJONITSZMJYIMVRAGVOHTVRAUCTKSGDDWUOXITLAZUVAVVRAZCVKBQPIWPOUSetiap 4 kata yang dimulai dari huruf kedua: PPQCAXQVEKGYBNKMAZUYBNGBALJONITSZMJYIMVRAGVOHTVRAUCTKSGDDWUOXITLAZUVAVVRAZCVKBQPIWPOUSetiap 4 kata yang dimulai dari huruf ketiga: PPQCAXQVEKGYBNKMAZUYBNGBALJONITSZMJYIMVRAGVOHTVRAUCTKSGDDWUOXITLAZUVAVVRAZCVKBQPIWPOUSetiap 4 kata yang dimulai dari huruf keempat: PPQCAXQVEKGYBNKMAZUYBNGBALJONITSZMJYIMVRAGVOHTVRAUCTKSGDDWUOXITLAZUVAVVRAZCVKBQPIWPOU

Ketika digambungkan maka kata-katanya menjadi:

PAEBABANZIAHAKDXAAAKIU (gabungan dari 4 kata huruf pertama)
PXKNZNLIMMGTUSWIZVZBW (gabungan dari 4 kata huruf kedua)
QQGKUGJTJVVVCGUTUVCQP (gabungan dari 4 kata huruf ketiga)
CVYMYBOSYRORTDOLVRVPO (gabungan dari 4 kata huruf keempat)

Pada dasarnya Vigenere Cipher sama dengan Caesar Cipher, hanya saja Vigenere Cipher menggunakan multiple sub keys. Sehingga untuk melakukan pembobolannya kita bisa melakukan decryption pada gabungan-gabungan kata di atas dengan key dari A hingga Z.

Kita ambil contoh untuk melakukan decryption pada gabungan kata PAEBABANZIAHAKDXAAAKIU. Kita akan melakukan decryption dengan menggunakan sub keys A — Z. Dan melakukan analisa frekuensi berdasarkan English Frequency Match Score.

English Frequency Match Score yang digunakan yaitu dengan melihat berapa score huruf paling sering muncul dari hasil decryption pada setiap key dengan merujuk berapa banyak 6 huruf yang paling sering muncul dalam bahasa inggris (ETAOIN) dan 6 huruf yang paling tidak sering muncul dalam bahasa inggris (VKJXQZ).

Misalnya jika kita melakukan decryption pada PAEBABANZIAHAKDXAAAKIU dengan menggunakan sub key sama dengan A maka hasilnya adalah PAEBABANZIAHAKDXAAAKIU. Dalam gabungan kata tersebut huruf yang paling sering muncul yaitu:

A sebanyak 8 kali
K sebanyak 2 kali
B sebanyak 2 kali
I sebanyak 2 kali
Z sebanyak 1 kali
X sebanyak 1 kali

Dan angka yang paling sering tidak muncul adalah CLRSOT sebanyak 0 kali (mungkin jika hasil tidak muncul atau 0 lebih dari 6 huruf, akan terdapat perbedaan hasil tergantung dari algoritma perhitungan dan sorting, hasil tersebut tidak masalah selama semua proses dilakukan dengan menggunakan algoritma yang sama).

Jika diurutkan, huruf yang paling sering muncul pada hasil decryption adalah AKBIZX PUDHNEQJVYGFWM CLRSOT. Dari hasil tersebut kita bandingkan 6 huruf pertama dan 6 huruf terakhirnya, apakah ada yang termasuk dalam ETAOIN (untuk huruf pertama) atau VKJXQZ (untuk huruf terakhir) untuk kita dapatkan English Frequency Match Score. Dari hasil tersebut kita mendapatkan huruf A dan I masuk kepada ETAOIN (6 huruf yang paling sering muncul) sehingga dari hasil decryption ciphertext dengan menggunakan sub keys A kita mendapatkan English Frequency Match Score sebesar 2.

Jika kita melakukannya pada semua sub keys, maka kita akan mendapatkan

Sub keys yang hasil decyrptionnya paling mendekati dengan English Frequency Match Score memiliki kemungkinan hubungan yang tinggi dengan real key. Hasil English Frequency Match Score yang paling banyak dari gabungan 4 kata huruf pertama adalah ‘A’, ‘I’, ’N’, ‘W’, dan ‘X’ (Hasil English Frequency Match Score yang kecil = 2, terjadi karena ciphertext yang digunakan hanya sedikit, dengan panjangnya ciphertext yang digunakan tingkat keberhasilan melakukan analisa frekuensi semakin tinggi).

Selanjutnya kita perlu melakukan kembali decryption dengan 26 sub keys pada gabungan 4 kata huruf kedua, ketiga, dan keempat. Maka hasil English Frequency Match Score yang didapatkan adalah

Gabungan 4 kata huruf pertama : A, I, N, W, X
Gabungan 4 kata huruf kedua : I dan Z
Gabungan 4 kata huruf ketiga : C
Gabungan 4 kata huruf keempat : K, N, R, V, Y

4. Brute Force pada Subkeys yang Memungkinkan

Setelah kita mendapatkan huruf-huruf yang mungkin akan membentuk real key dengan panjang key sama dengan 4. Maka kita akan melakukan kombinasi dari huruf-huruf tersebut. Hal ini lebih baik dibandingkan dengan melakukan kombinasi terhadap 26 huruf untuk setiap sub keys, sehingga menghasilkan kemungkinan sebesar 26 x 26 x 26 x 26 = 456, 976. Dengan melakukan analisa frekuensi terlebih dahulu, kita hanya memiliki kemungkinan sebesar 5 x 2 x 1 x 5 = 50 kemungkinan real key yaitu:

Setelah melakukan Brute Force pada 50 kemungkinan key tersebut, kita mendapatkan bahwa ciphertext

PPQCAXQVEKGYBNKMAZUYBNGBALJONITSZMJYIMVRAGVOHTVRAUCTKSGDDWUOXITLAZUVAVVRAZCVKBQPIWPOU

dengan menggunakan key “WICK” hasil decryptionnya adalah

THOSEPOLICEOFFICERSOFFEREDHERARIDEHOMETHEYTELLTHEMAJOKETHOSEBARBERSLENTHERALOTOFMONEY

Keren sekali bukaan !!! kita telah melakukan pembobolan pada Vigenere Cipher. Prosesnya jauh lebih sulit dibandingkan melakukan pembobolan pada Caesar Cipher. Namun dikarenakan telah terdapat algoritma untuk melakukan pembobolan pada Vigenere Cipher, algoritma cryptography jenis ini tidak banyak digunakan lagi.

Salah satu algoritma yang menggunakan prinsip dasar yang sama seperti Caesar ataupun Vigenere Cipher (melakukan shifting plaintext) lainnya adalah One Time Pad, dimana key yang digunakan adalah hasil dari suatu nilai random (Pseudo Random ataupun True Random). Namun masih terdapat celah-celah juga untuk melakukan pembobolan. Sehingga munculah algoritma yang lebih tangguh lagi yaitu DES (Data Encryption Standard) dan juga AES (Advanced Encryption Standard).

Penutup

Sekian dulu penjelasan mengenai algoritma Vigenere Cipher, selanjutnya saya akan membahas contoh-contoh dari cryptography symmetric lainnya yang sekarang masih umum digunakan yaitu DES dan juga AES. Pada algoritma ini untuk melakukan pembobolan seperti sebelumnya sangatlah sulit, dibutuhkan komputer dengan kemampuan komputasi yang sangat cepat (Sejauh ini hanya DES yang bisa dibobol). Namun terdapat teknik lainnya untuk melakukan pembobolan dengan menggunakan SCA (Side Channel Attack) yang akan saya bahas dipostingan-postingan selanjutnya.

Referensi:

https://inventwithpython.com/hacking/chapter21.html

Materi terkait lainnya:

-Terimakasih-