Vigènere Cipher dengan Pembangkitan Kunci Menggunakan Bilangan Euler Budi Satrio - 13504006 Program Studi Teknik Info rmatika ITB, Bandung 40132, email:
[email protected] Abstract – Vigènere cipher adalah salah satu jenis kriptografi klasik yang melakukan substitusi cipher abjad majemuk , tetapi terdapat kelemahan dari cipher ini, salah satunya yaitu ia mudah diserang dengan metode Kasiski. Untuk lebih memperkuat cipher ini, penulis mengajukan algoritma vigènere cipher dengan pembangkitan kunci menggunakan bilangan euler. Pada dasarnya, metode ini adalah sebuah cara untuk mendapatkan suatu kunci internal berbentuk acak yang dibentuk dari perkalian matematis antara kunci yang dimasukkan dengan bilangan Euler. Diharapkan dengan metode ini, kunci yang dihasilkan untuk Vigènere cipher menjadi lebih panjang dan acak sehingga akan menyulitkan kriptanalisis untuk menyerang dengan metode Kasiski maupun dengan metode lainnya. Kata Kunci: Vigènere cipher, kunci internal, bilangan euler, perkalian matematis, metode kasiski. 1. PENDAHUL UAN Vigènere cipher merupakan salah satu jenis kriptografi klasik yang pada dasarnya adalah melakukan substitusi cipher abjad majemu k (polyalphabetic substitution) [1]. A lgorit ma ini ditemu kan oleh diplo mat sekaligus kriptologis dari Prancis, Blaise de Vigènere pada abad 16. Vigènere cipher dipublikasikan pada tahun 1856, tetapi algorit ma ini baru dikenal luas 200 tahun kemudian.
untuk vigènere cipher menjad i leb ih panjang dan acak sehingga akan menyulitkan kriptanalisis untuk menyerang baik dengan metode Kasiski maupun dengan metode lainnya. 2. VIGEN ER E CIPHER Vigènere Cipher adalah sebuah algorit ma enkripsi yang menggunakan konsep Caesar Cipher dengan kunci yang berbeda-beda. Vigènere cipher merupakan contoh sederhana dari algorit ma enkripsi subtitusi abjad majemu k. 2.1. Konsep Dasar Vigènere cipher menggunakan Bujursangkar vigènere untuk melakukan enkripsi (li hat gambar 1). Kolo m paling kiri menyatakan huruf-huruf kunci sedangkan baris paling atas menyatakan huruf-huruf plainteks. Setiap baris dalam bujursangkar menyatakan hurufhuruf cipherteks yang diperoleh dengan Caesar Cipher, yang mana jauh pergeseran huruf plainteks ditentukan oleh nilai desimal dari huruf kunci tersebut (a = 0, b = 1,…, z = 25). .
Algorit ma enkripsi ini terkenal karena mudah dimengerti dan diimp lementasikan, bahkan bagi kriptanalis pemu la akan tampak seperti tidak dapat dipecahkan. Reputasi ini lepas setelah Kasiski dengan tuntas memecahkan Vigènere Cipher pada abad ke 19 dengan cara mengetahui panjang huruf yang digunakan sebagai kunci [3], dan beberapa kriptanalis yang memiliki kemampuan tinggi berhasil memecahkan cipher tersebut pada abad ke 16. Untuk leb ih memperkuat cipher ini, banyak modifikasi dilakukan oleh para peneliti kriptografi. Salah satu cara yang penulis ajukan sebagai tugas makalah ini adalah dengan metode pembangkitan kunci internal dengan menggunakan bilangan euler. Pada dasarnya, metode in i adalah sebuah cara untuk mendapatkan suatu kunci berbentuk panjang dan acak yang didapatkan dari perkalian matematis antara kunci yang dimasukkan dengan bilangan Euler. Diharap kan dengan metode ini, kunci yang dihasilkan
Gambar 1: Bujursangkar Vigènere Bujursangkar vigènere digunakan untuk memperoleh cipherteks dengan menggunakan kunci yang sudah ditentukan. Jika panjang kunci lebih pendek daripada panjang plainteks, maka kunci diu lang penggunaannya (periodic system).
Sebagai contoh, jika plainteks adalah “TUGASMA KALA H” dan kunci adalah “KEY”, maka penggunaan kunci secara periodik dan hasil cipherteks adalah sebagai berikut: Plainteks :T U G A S M A K A L A H Kunci :K E Y K E Y K E Y K E Y Cipherteks:D Y E K W K K P Y V E F Dapat diamat i bahwa setiap huruf A dapat dienkripsi men jadi huruf yang berbeda. Hal ini merupakan karakteristik dari cipher abjad majemuk karena setiap huruf cipherteks dapat memiliki kemungkinan banyak huruf plainteks. Dekripsi pada Vigènere Cipher dilakukan dengan cara yang berkebalikan, yaitu menarik garis mendatar dari huruf kunci sampi ke huruf cipherteks yang dituju, lalu dari huruf cipherteks tarik garis vertical ke atas sampai huruf p lainteks. 2.2. Kelemahan Vigènere Ci pher Beberapa kelemahan dari Vigènere Cipher adalah mudahnya diserang dengan menggunakan metode analisis frekuensi dan metode kasiski untuk mengetahui frekuensi kemunculan huruf-huruf yang sama[2]. 2.3. Varian Vigènere Ci pher Vigènere Cipher mempunyai beberapa varian yang cukup terkenal. Varian in i muncul untuk memperbaiki dan menyempurnakan algorit ma vigènere cipher tersebut, diantaranya adalah sebagai berikut: 2.3.1 Auto-key Vigènere Ci pher Auto-key Vigènere Cipher adalah contoh varian vigènere cipher yang bersifat cipher aliran. Cipher aliran adalah metode untuk mengenkripsi huruf berdasarkan posisinya dalam teks. Idealnya, kunci yang digunakan tidak pernah berulang. 2.3.2 Running-key Vigènere Ci pher Running-key Vigènere Cipher adalah vigènere cipher yang kuncinya menggunakan teks yang memiliki arti atau cukup dikenal dalam masyarakat. Teks ini bisa berupa buku yang dimiliki oleh pengirim dan penerima pesan. 2.3.3 One Ti me Pad One Time Pad (OTP) adalah vigènere cipher yang menggunakan kunci berupa note sepanjang ukuran plainteks yang ingin dienkripsi secara acak. Setelah dipakai, kertas note tersebut dibuang untuk men jaga kerahasiaan dan juga randomisasi kunci selanjutnya. Aturan enkripsi yang digunakan sama persis dengan vigènere cipher biasa. Pengirim pesan mengenkripsi sebuah karakter plainteks dengan sebuah karakter dari kunci. Perhatikan bahwa panjang kunci sama dengan panjang plainteks sehingga tidak terjadi pengulangan/periodisasi kunci.
Kekuatan OTP terletak pada kunci yang acak sehingga menghasilkan cipherteks yang seluruhnya acak juga. Selain itu cipherteks yang sama mungkin menghasilkan teks berbeda yang sama-sama memiliki arti sehingga memb ingungkan kriptanalis. 3. ALGORITMA VIGEN ERE CIPHER DENGAN PEMBANGKITAN KUNCI MENGGUNAKAN BILANGAN EUL ER Algorit ma vigènere cipher dengan pembangkitan kunci menggunakan bilangan euler ini merupakan varian vigènere cipher yang diajukan oleh penulis mengingat keunikan dari bilangan euler yang panjangnya tidak terhingga[4]. 3.1. Konsep Umum Secara u mu m, int i dari algorit ma in i adalah bagaimana caranya untuk membuat kunci internal yang panjang dan acak sehingga algoritma akan berjalan seperti di OTP, namun kunci internal tersebut dapat dibentuk sesuai dengan masukan. Pembangkitan kunci internal yang penulis ajukan ini unik karena menggunakan perkalian secara matematis dengan bilangan euler, kemudian setiap angka hasil perkalian akan dikelo mpokkan sesuai dengan panjang digit dari kunci masukan lalu diubah kembali men jadi huruf-huruf yang akan digunakan sebagai kunci internal. Kunci internal in ilah yang akan digunakan untuk melaku kan enkripsi dan dekripsi. Sebagai contoh, jika kunci masukan adalah BUDI maka kunci tersebut bentuk angkanya adalah 1 20 3 8 Untuk contoh plainteks yang mempunyai panjang 20 karakter, maka ambil bilangan euler sepanjang 20 karakter 27182818284590452353 Berikutnya, kunci dalam bentuk angka tersebut dikalikan dengan bilangan euler 12038 x 27182818284590452353 sehingga menghasilkan angka 327226766509899865425414 Dari sini kita kelo mpokkan hasil perkalian sesuai dengan susunan struktur kunci masukan menjad i: 3 27 2 2 6 76 6 5 0 98 9 9 8 65 4 2 5 41 4 Kemudian kita ubah menjad i bentuk huruf lagi (mod 26) sehingga men jadi
D B C C G Y G F A U J J I N E C F P E sehingga didapatkan kunci internal DBCCGYGFA UJJINECFPE Kunci internal in i yang kemudian akan dipakai untuk melakukan proses enkripsi dan dekripsi. Algorit ma ini bekerja pada rangkaian huruf ASCII (256 karakter). Hal in i bertujuan agar variasi kunci yang memungkinkan men jadi semakin banyak sehingga mempersulit kriptanalis untuk memecahkan Namun dalam makalah ini, penulis hanya menggunakan 26 karakter (A-Z) dengan pertimbangan kemudahan untuk dimengerti. Perlu d iperhatikan bahwa harus terdapat kesepakatan untuk pengubahan setiap karakter A SCII menjad i angka. 3.2. Lingkung an Pengembangan Aplikasi Program ap likasi algorit ma vigènere cipher dengan pembangkitan kunci menggunakan bilangan euler ini dikembangkan pada lingkungan sebagai berikut : Intel Core Duo Processor @ 1.60 Gh z, 533 FSB, 2Mb L2 Cache. Memory 768M B DDR2. Intel Graphic Media Accelerator 950. Windows XP Service Pack 2. Kakas pemrograman M icrosoft Visual Studio .NET (C#). 3.3. Algoritma Umum Secara u mu m algorit ma vigènere cipher dengan pembangkitan kunci menggunakan bilangan euler ini terdiri dari tiga proses utama yaitu: 1. Proses pembangkitan kunci internal. 2. Proses enkripsi. 3. Proses dekripsi. 3.3.1 Proses pembangkitan kunci internal Pembangkitan kunci internal dalam algorit ma ini terdiri dari beberapa fase utama, yaitu: 1. Fase pengubahan dari karakter menjad i angka. 2. Fase generasi bilangan euler. 3. Fase perkalian antara bilangan euler dengan kunci dalam bentuk angka. 4. Fase pengelompokan angka. 5. Fase pengubahan dari angka men jadi karakter.
Kunci masukan
Plainteks
Bilangan euler
Angka
Perkalian
Pengelompokan
Kunci internal
Gambar 2: Skema pembangkitan kunci internal Pada fase pengubahan dari karakter menjadi angka, maupun dari angka menjadi karakter dilakukan dengan menggunakan algoritma dalam bentuk pseudocode adalah sebagai berikut: function charToNum(character){ //mengubah karakter menjadi angka integer n; switch(character){ case A : n = 0; break; case B : n = 1; break; case C : n = 2; break; . . Case Z : n = 25; break; } return n; } function numToChar(number){ //mengubah angka menjadi karakter integer n = number % 26; char c; switch(n){ case 0 : c = A; break; case 1 : c = B; break; case 2 : c = C; break; . . Case 25 : c = Z; break; } return c; }
Secara u mu m dapat digambarkan sebagai berikut: Perlu ditambahkan bahwa algorit ma d iatas adalah untuk 26 karakter. Jika yang digunakan adalah 255 karakter, maka pengubahan karakter menjadi angka maupun sebaliknya dibantu dengan menggunakan fungsi dasar pengubahan ASCII pada setiap bahasa pemrograman.
Pada fase generasi bilangan euler, dilakukan pengambilan b ilangan euler seju mlah panjang plainteks. Untuk menghitung panjang plainteks dapat menggunakan aplikasi web gratis di alamat in i : http://www.fwo intl.co m/FWOFormatter.ht ml Sedangkan untuk mengamb il bilangan euler sepanjang plainteks dapat digambarkan dalam pseudocode sebagai berikut: function getEuler(plaintextLength){ //mengambil bilangan euler sepanjang //plainteks bigint n = 0; for(i=1;i<=plaintextLength;i++){ n = n + readEuler(i); } return n; }
readEuler(i) adalah fungsi yang mengembalikan bilangan euler ke-i. Untuk bilangan euler sampai 100.000 angka, didapatkan dari web http://www.mu.o rg/~doug/exp/100000.ht ml. Pada fase perkalian antara angka dari kunci dengan bilangan euler sepanjang plainteks diperlukan algorit ma yang mampu mengelola d igit dalam ju mlah yang sangat besar. Terdapat sebuah aplikasi kalkulator gratis yang akan memproses perkalian sampai 5011 digit. Aplikasi in i dapat didownload di http://web.ukonline.co.uk/home52365/bcalc.htm. Untuk fase pengelompokan angka hasil perkalian, dapat digambarkan dalam pseudocode berikut: function grouping(number){ //mengelompokkan angka dari hasil //perkalian sesuai dengan pattern dari //kunci char[] hasil; bigint i,j,k = 0; while(number[i]!=EOF){ k=0; while(k
PATTERN_LENGTH adalah panjang dari susunan kunci dalam bentuk angka, sedangkan pattern[] adalah susunan kunci. Sebagai contoh, dari kunci “BUDI” kita dapatkan pattern kunci dalam bentuk angka “1 20 3 8” atau lebih lengkapnya: 1,” ”,20,” ”,3,” ”,8,”\n” Sedangkan panjang dari pattern tersebut adalah 8.
Secara u mu m, proses untuk membangkit kan kunci internal ini adalah dengan melakukan fase 1 sampai 5. 3.3.2 Proses Enkripsi Proses enkripsi pada algoritma vigènere cipher dengan pembangkitan kunci menggunakan bilangan euler sama dengan algoritma euler biasa, yaitu melakukan substitusi pada plainteks berdasarkan kunci internal yang telah dibangkitkan pada tahap sebelumnya sehingga didapatkan cipherteks. (1) Dimana Ci adalah Cipherteks ke-i, Pi adalah Plainteks ke-i, dan Ki adalah kunci internal ke-i. 3.3.3 Proses Dekripsi Proses dekripsi pada algoritma vigènere cipher dengan pembangkitan kunci menggunakan bilangan euler sama dengan algoritma euler biasa, yaitu melakukan substitusi pada cipherteks berdasarkan kunci internal yang telah dibangkitkan pada tahap sebelumnya sehingga didapatkan plainteks. (2) Dimana Ci adalah Cipherteks ke-i, Pi adalah Plainteks ke-i, dan Ki adalah kunci internal ke-i. 3.4. Kekuatan Algoritma Kekuatan dari metode ini adalah pengelompokan hasil perkalian antara kunci dengan bilangan euler yang sangat sulit untuk diterka serta bentuk acak dari kunci yang sangat panjang, sehingga akan menyulitkan kriptanalisis untuk menyerang dengan menggunakan metode Kasiski maupun analisis frekuensi. 3.5. Kelemahan Algoritma Kelemahan algorit ma in i terletak pada besarnya ju mlah dig it angka pada perkalian antara bilangan euler dengan angka hasil proses generasi kunci sehingga dapat memboroskan penggunaan memori. Selain itu, algorit ma ini memungkinkan terjadinya periodisasi kunci walaupun tidak berju mlah banyak. Maksimal terjadi periodisasi kunci in i adalah 2 kali, hal ini dapat terjadi karena pengelompokan angka untuk disesuaikan dengan susunan kunci membuat susunan huruf menjad i lebih sedikit dari angka hasil perkalian. 4. PENGUJ IAN TERHADAP ALGORITMA VIGEN ERE CIPHER DENGAN PEMBANGKITAN KUNCI MENGGUNAKAN BILANGAN EUL ER
4.1. Penguji an Terhadap Serangan-serangan Kri ptanalis Pengujian terhadap serangan kriptanalis dilakukan
untuk mengetahui kekuatan dan kelemahan algorit ma vigènere cipher dengan pembangkitan kunci menggunakan bilangan euler ini. Plainteks yang akan digunakan dalam pengujian ini penulis amb il dari koran The Jakarta Post, yaitu: ADAMAIRBLACKBOXRETRIEVEDBYSALVAGETEA MTHEFLIGHTDATARECORDERANDCOCKPITVOIC ERECORDERWEREFOUNDABOUT30TO50METERSF ROMEACHOTHERATDEPTHSOF2,000METERSAND 1,900METERSRESPECTIVELY. Kemudian kunci yang digunakan adalah “PESAWAT”. Dari proses pembangkitan kunci internal, d idapatkan kunci internal adalah sebagai berikut: PJKFDAHCJOABIYTESDOIZEBEGSHVCHWJVCMK FFICITKAIDRCIGAEHIGFAJFGAAXXHQCQDETA KHMIMVFVANDEEFZJDIJAFHGAITHHZHFBWNCM FRERE Kemudian dilakukan enkripsi plainteks dengan menggunakan kunci internal diatas, sehingga didapatkan cipherteks sebagai berikut: PMKRDIYDUOCLJMQVWWFQDZFHHQZVNCWPZVQK RYPGNESGPWUCBGRIJWXIEAFTDCLZRFKJYSBC OYQKAMIZRJHVIKNDQLJBTBZ30TW50FLADYXG NBOQFTLFXWNBFWDLRCVSPN2,000KXXWUGIMH 1,900NIZWYNTLOYZEFSAJTA. Asumsi untuk melakukan pengujian ini yaitu kara kter selain abjad (angka, tanda petik, tanda seru, dan sebagainya) tidak ikut d ienkripsi. 4.1.1. Ci phertext-onl y Attack Dari cipherteks contoh yang dihasilkan, didapatkan data frekuensi kemunculan setiap abjad sebagai berikut: A 5 N 8 B 6 O 4 C 6 P 5 D 7 Q 7 E 3 R 6 F 9 S 4 G 5 T 6 H 4 U 3 I 7 V 5 J 6 W 10 K 6 X 5 L 7 Y 7 M 4 Z 8 Dengan menggunakan metode terkaan, sangat tidak mungkin untuk dipecahkan, karena kemungkinan kata yang mudah untuk dipecahkan ternyata memiliki cipherteks yang berbeda. Sebagai contoh adalah kata yang berada dekat dengan angka 2,000 dan 1,900 yang kita asumsikan bahwa itu akan men jadi kata “METERS”, ternyata cipherteks sama sekali berbeda. Dengan menggunakan metode analisis frekuensi,
didapatkan hasil bahwa frekuensi huruf yang paling banyak muncul adalah W, dan ini sangat tidak sesuai dengan plainteks jika W diganti dengan E (huruf E paling banyak muncul dalam bahasa inggris). Untuk itu metode analisis frekuensi ini tidak dapat dilakukan pada algoritma vigènere cipher dengan pembangkitan kunci menggunakan bilangan euler. 4.1.2. Known-pl aintext Attack Pengujian untuk serangan ini dilakukan dengan cara membu ka sebagian plainteks untuk kemudian didapatkan kuncinya, namun serangan ini tidak dapat menembus kekuatan dari algorit ma ini karena kita tidak tahu kunci selanjutnya berbentuk acak. 4.1.3. Exhausti ve Attack Exhaustive Attack adalah salah satu jenis serangan dengan mencoba semua kemungkinan kunci yang ada. Tentunya pengujian ini cukup memakan waktu lama apabila kunci yang digunakan ju mlahnya panjang, oleh karena itu semakin panjang kunci, semakin lama waktu yang dibutuhkan untuk melaku kan exhaustive key search. Ju mlah kemungkinan kunci adalah 26n . 4.1.4. Kasiski Examination Pada dasarnya, metode Kasiski ini adalah melihat kemungkinan munculnya urutan-urutan huruf yang sama untuk kemudian dilakukan analisis terhadap kesamaan urutan huruf dengan struktur kata yang digunakan dalam bahasa sehari-hari[5]. Untuk melaku kan pengujian ini, digunakan alat bantu berupa program vigènere.jar yang didapatkan dari situs http://www.in formatika.org/rinald i untuk mengetahui urutan huruf yang berulang. Dari plainteks yang sengaja dipilih oleh penulis didapatkan hasil bahwa huruf yang berulang hanya kelompok huruf berju mlah satu dan dua, selain itu tidak d itemukan. Hal ini tentunya akan menyulit kan kriptanalisis dalam mengidentfikasi pasangan huruf yang berulang. 5. PEMB AHASAN Dari hasil percobaan-percobaan diatas, terdapat beberapa hal dari algorit ma ini yang perlu untuk dikaji, diantaranya mengenai keefektifan algorit ma dan kemampuannya dalam menghadapi serangan kriptanalisis. Untuk keefektifan algorit ma, semakin panjang kunci semakin lama pula pembangkitan kunci internalnya, hal ini disebabkan karena algoritma in i menggunakan perkalian matemat is antara bilangan-bilangan yang mempunyai dig it sangat besar. Hal in i tentunya akan men jadi salah satu kekurangan dari algorit ma ini. Untuk pengujian algoritma dengan menggunakan metode terkaan sangat tidak mungkin dilakukan, hal ini dapat terjadi karena algorit ma in i membuat kunci internal berupa susunan huruf yang acak dan panjang,
sehingga hubungan antara plainteks dengan cipherteks men jadi h ilang. Pengujian algorit ma dengan metode analisis frekuensi juga tidak dapat dilaku kan pada algorit ma in i. Hal ini dapat terjadi karena jejak frekuensi kemunculan huruf tidak ada hubungannya antara plainteks dan cipherteks dikarenakan penggunaan kunci internal yang panjang. Pada Known-plaintext Attack, wa laupun sebagian plainteks sudah diketahui dan sebagian kunci internal didapatkan, namun tetap saja tidak dapat melakukan proses untuk mengetahui kunci internal keseluruhan. Hal in i disebabkan karena kunci internal dari cipherteks sangat panjang sehingga akan menyulitkan untuk melakukan penerkaan kunci. Selain itu penebakan kunci masukan dari kunci internal juga sangat tidak mungkin dilakukan karena fase perkalian dan pengelompokan pada algoritma in i membuat operasi untuk mendapatkan kunci masukan dari kunci internal sangat sulit untuk dilaku kan. Untuk Exhaustive Attack, sudah jelas bahwa kemungkinan untuk mendapatkan kunci dari algorit ma ini adalah 26n . Selain itu, pada pembangkitan kunci internal akan memerlukan waktu yang cukup lama untuk kunci yang bentuknya panjang, sehingga apabila dilakukan percobaan satu-satu akan membutuhkan waktu yang sangat lama. Pada pengujian dengan menggunakan metode kasiski, terbukti bahwa huruf yang berulang akan muncul secara acak sehingga akanakan menyulitkan penyerangan melalui metode ini. Hal ini dikarenakan bentuk kunci internal yang panjang dan acak.
6. KES IMPULAN
Kesimpulan yang dapat diambil dari algorit ma Vigènere Cipher dengan pembangkitan kunci menggunakan bilangan euler adalah sebagai berikut: 1. Algorit ma vigènere cipher dengan pembangkitan kunci menggunakan bilangan euler lebih baik dari algorit ma v igènere cipher yang biasa dan variannya karena menggunakan kunci internal yang panjang dan acak untuk menghilangkan jejak periodisasi dan frekuensi serta hubungan antara plainteks dengan cipherteks. 2. Ko mpleksitas algorit ma in i adalah 26n karena menggunakan perkalian b iasa. 3. Kemungkinan terjadi periodisasi kunci tetap ada, namun ju mlahnya sangat sedikit. 4. Pembangkitan kunci dengan menggunakan bilangan euler ini membutuhkan waktu yang cukup lama mengingat terdapat perkalian dengan digit yang sangat besar serta proses pengelompokan angka. 5. Algorit ma in i kuat terhadap serangan cipherteksonly attack, known-palintext attack, exhaustive attack, dan metode kasiski.
DAFTAR REFER ENS I [1] Munir, Rinaldi, Diktat Kuliah IF5054 Kriptografi, Sekolah Teknik Elektro dan Informatika Institut Teknologi Bandung, 2007. [2] Bishop, David. Introduction to Cryptography with Java Applet, Jones and Bartlet Co mputer Science, 2003. [3] Gaines, Helen Fouche, Cryptanalysis, Dover New Yo rk, 1956 [4] Mart in, Crossley, Essential Topology: The Euler Number, Springer London, 2005 [5] A. Menezes, P. van Oorschot, dan S. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996.
