1
IMPLEMENTASI JOINT KOMPRESI DAN ENKRIPSI DENGAN CHAOTICALLY MUTATED PADA HUFFMAN TREE Andrian Nova Ady1, Suadi Wahyu2 Teknik Informatika , Institut Teknologi Sepuluh Nopember, ITS Surabaya, Jawa Timur, Indonesia. Abstrak
Dengan semakin berkembangnya teknologi internet dan multimedia,kompresi dan enkripsi menjadi sangat penting. Tetapi,penggunaan enkripsi dan kompresi secara terpisah dinilai terlalu lambat untuk beberapa aplikasi multimedia. Dalam tugas akhir ini akan di implementasikan skema baru dalam joint enkripsi dan kompresi dengan menggunakan huffman codec. Terdapat 3 tahap utama yang dilakukan yaitu pembentukan basic huffman tree, memutasi huffman tree, dan melakukan enkrispi-deskripsi atau dekripsi-dekopresi . Untuk tahap pertama di lakukan pembentukan huffman tree dasar berdasarkan pesan atau plain text yang digunakan. Pada tahap kedua basic huffman tree yang didapat dari tahap pertama dimutasi dengan dasar keystream yang didapatkan dari chaotic map dan berdasarkan input message tanpa mengubah model satistiknya. Pada tahap terakhir dilakukan pengkodean dari plain text dengan menggunakan tree yang telah dimutasi pada tahap ke 2. Pada tahap uji coba akan ditunjukan bahwa algoritma CHT memiliki waktu eksekusi lebih besar dan memiliki kompresi rasio sama dengan huffman codec . . Kata Kunci:
1.
Joint compression and encription, huffman tree dan chaotic encryption.
Pendahuluan
Skema kriptografi kovensional seperti DES dan EAS telah dikembangkan terutama untuk melindungi alphanumeric data. Mengenkripsi seluruh aliran multimedia menggunakan skema kriptografi konvensional sering disebut sebagai pendekatan naif. Baru–baru ini, penelitian keamanan multimedia berfokus kearah integerasi enkripsi dengan system multimedia kompresi. Selective encryption memperlihatkan fakta bahwa dalam domain kompresi seperti, DTC atau wavelet data direpresentasikan sebagai sequence koefisien yang berkonstribusi tidak merata pada kualitas visual gambar atau video. Sehingga, seringkali kita cukup mengenkripsi beberapa bagian dari koefisien yang sebagian besar data terkonsentrasi daripada harus mengenkrispsi semua sequence dari koefisien. Untuk menggabungkan enkripsi dan kompresi diperlukan klasik codec seperti huffmana codec dan aritmatica codec. Jadi prinsip untuk joint enkripsi dan kompresi algoritma adalah menggunakan enkripsi
algoritma untuk mengubah entropy coder menjadi chipper. Banyak algoritma yang telah dibuat dalam domain ini [6]. Sebuah skema randomize pengkodean aritmatika yang menggunakan enkripsi dengan menyisipkan beberapa randomization dalam prosedur pengkodean aritmatika yang disebut dengan RAC[11]. Teknik ini diaplikasikan pada standart 2000 JPEG yang menggunakan pengkodean aritmatika sebagai codec. Enkripsi RAC berbasis pada interval random yang diasosiasikan dengan symbol. Urutan ini bersifat rahasia dan hanya synchronize decoder yang dapat membaca dengan benar. Skema lain adalah dengan pengkodean binary aritmatika dengan basis key interval (KSAC) untuk melakukan kompresi dan enkripsi dengan memisahkan interval sesuai dengan kunci rahasia. MHT memiliki pendekatan yang berbeda. Pada skema ini melakukan baik enkripsi dan kompresi dengan menggunakan beberapa model statistik pada entropy encoder. Setelah dilakukan cryptanalysed pada skema RAC,KSAC dan MHT oleh Jakimoski dan Subbalakshmi ditemukan bahwa MHT dan
2 KSAC vurnable terhadap serangan chosenpalintext dan pada RAC ditemukan kelemahan dibandingkan pendekatan kompresi enkripsi klasik[3]. Houcemeddine Hermassi, Rhouma Rhouma, dan Safya Belghith mengajukan suatu skema baru yang terinspirasi dari MHT dengan menggunakan huffman tree yang disebut dengan CHT. 2. Joint kompresi dan enkripsi CHT Prinsip utama dalam joint kompresi dan enkripsi adalah dengan membuat algoritma kompresi huffman sebagai stream cipher[1]. Sehingga kita mendapatkan algoritma enkripsi sekaligus kompresi dengan berbasis pada model statistik huffman tree dan dapat diimplementasiakan terhadap semua data yang belum di kompres. Kita akan menggunakan chaotic map ƒ untuk mendapatkan key stream yang akan digunakan untuk memperbaharui huffman tree.
2.1
(2.1) Diamana p €(0,1) sebagai parameter dan x0(0,1) adalah kondisi awal dari PWLCM. Peta ini dapat menggambarkan semua interval dari 0 sampai 1. Diagram bifurcation pada persamaan 2.1 dapat dilihat pada gambar 1.
Chaos dan Cryptography
Chaos banyak digunakan dalam domain cryptography. Selama dua puluh tahun belakangan ini banyak penelitian yang telah di lakukan dalam domain ini. Syarat dasar yang harus dipenuhi suatu chaos-based cryptosystems[5] sebagai berikut : Sensitif terhadap kondisi awal dari sinyal chaotic. Sehingga sedikit perbedaan pada plaint text dapat menyebabkan perubahan bessar pada cihertext. Deterministic dynamic dan pseudorandom adalah aspek dari sinyal chaotic. Ergodicty dari sinyal chaotic. Perfroma dari algoritma enkripsi mempunyai distrubusi yang sama untuk setiap plainttext. Dalam CHT digunakan chaotic map untuk mendapatkan pseudo random yang digabungkan dengan huffman codec untuk mendisainm algoritma enkripsi sekaligus deskripsi. Chaotic map yang digunakan adalah chaotic map PWLCM. 2.2
kontrol parameter karena memiliki Lyapunov exponen yang positif untuk semua nilai dengan satu parameter kontrol[4]. Persamaan chaotic untuk map PWLCM sebagai berikut:
Chaotic map PWlCM
Keluarga chaotic map PWLCM atau piecewise linear chaotic maps adalah map kelas diskrit dynamic systems dimana selalu chaotic untuk semua karakter dengan satu
Gambar 1 Diagram bifurcation dari PWLCM map Gambar 2.4 menunjukan untuk setiap parameter p yang dipakai, trajectory melintasi seluruh interval[0,1]. Dan nilai dari Lyapunov exponent diatas lebih besar dari nilai 0 untuk setiap nilai parameter kontrol. Lyapunov exponen menginformasikan tentang tingkat perbedaan dua orbit yang sangat dekat dengan kondisi awal. Jika nilai Lyaponuv adalah positif maka system adalah chaotic dan orbit yang didapat adalah orbit chaos. 2.3
Agoritma chaotic huffman tree(CHT)
CHT atau chaotic huffman tree adalah algoritma yang akan di implementasikan dalam tugas akhir ini[1]. Jika ada suatu message M dimana M = EDCBBAFAADEEFEDDADADCDFFCAE CACA DDACFAECCAAFFAFAE. M terdiri dari set symbol S={A,B,C,D,E,F},dan memiliki jumlah symbol N=6 dan kemungkanan muncul ditunjukan di tabel 1. Dengan manggunakan huffman coding
3 untuk membentuk huffman tree maka didapat sebuah huffman tree pada gambar 2. Tree pada gambar 2 adalah gambar dari basic tree. Tree tersebut memiliki N symbol dan memiliki N-1 “inner-nodes”. Berdasarkan representasi dari huffman tree jika dua branch pada satu inner-node di tukar maka akan terbentuk tree baru dengan statistik yang sama dengan basic tree. Jika kita tukar dua branch pada satu inner-node dengan label 2 pada gambar 3 maka kita akan mendapatkan tree baru pada gambar 3. Sehingga code dari symbol pun akan berubah seperti yang ditunjukan pada tabel 2. Dengan melakukan hal yang sama secara random kita dapat mengupdate basic tree setelah setiap proses pengkodean dari symbol sehingga proses enkripsi tidak akan berdasarkan static tree tetapi dengan tree dynamis yang akan di update berdasarkan dengan input symbol dan keystream yang terbentuk. Hal diatas merupakan prinsip dasar dari CHT. Jika M=m1,m2,..,mL maka V(mi) adalah representasi desimal ASCII code dari M. Berikut ini adalah algortima enkripsi-kompresi dan dekripsi-decompresi: 1. Algoritma enkripsi-kompresi. Diberikan set dari key(x0,p,V(m)), dan parameter (α,β). Dan map PWLCM dengan kondisi awal sesuai dengan subkey x0 dan memiliki parameter p. Maka proses enkripsikompresi sebagai berikut: 1. Membentuk basic huffman tree T dengan menggunakan huffman coding dari input.dan set i=1 2. Mendapatkan banyaknya iterasi dengan persamaan
(2.2) 3. Mendapatkan keystream ri dengan manggunakan persamaan (2.3) Dan mengupdate kondisi awal map f,x0=xn 4. Update huffman tree dengan menukar branch pada inner node yang ditunjukan dengan ri. 5. Mengkodekan message sesuai dengan tree yang telah di update ke ci dan C=C+ci.
6. Set i=i+1. Jika i>L maka chipertext dari M adalah C jika tidak kembali ke step 2 7. Menuliskan code C ditambah dengan basic tree ke decoder. 2. Algoritma dekripsi-dekompresi Diberikan set dari key(x0,p,V(m)), dan parameter (α,β). Dan map PWLCM dengan kondisi awal sesuai dengan subkey x0, chiphertext C yang didapat dari enkripsi dengan menggunakan CHT dan memiliki parameter p. Maka proses enkripsi-kompresi sebagai berikut: 1. Membentuk basic huffman tree T dengan menggunakan huffman coding dari input.dan set i=1 2. Mendapatkan banyaknya iterasi dengan persamaan 2.2 3. Mendapatkan keystream ri dengan manggunakan persamaan 2.3. Dan mengupdate kondisi awal map f,x0=xn 4. Update huffman tree dengan menukar branch pada inner node yang ditunjukan dengan ri. 5. Mengkodekan message C sesuai dengan tree yang telah di update untuk mendapatkan plaintext. 6. Set i=i+1. Jika i>L maka chipertext dari M adalah C jika tidak kembali ke step 2
Tabel 1 Tabel Probability
4 Pada tahap mutasi huffman tree ini dibagi menjadi 2 yaitu proses menurunkan chaotical map dan proses memperbaharui huffman tree. Setelah mendapatkan huffman tree yang telah termutasi maka dilanjutkan dengan tahap terakhir yaitu tahap enkripsi-kompresi atau dekripsi-dekompresi. Pada tahap ini dibagi lagi menjadi 2 proses yaitu proses enkripsikompresi atau dekripsi-dekompresi dan proses penulisan file. Gambar 2 Basic Huffman Tree
3.1.
Gambar 3 Tree Telah Di Perbaharui Tabel 2 Tabel Codeword Telah Diperbaharui
Implementasi pembentukan list
Tahap ini merupakan tahap awal dari algoritma CHT. Pada tahap ini data masukan yang bertipe file dibaca dan dibuat informasinya. File masukan di baca tiap byte dan dirubah dalam bentuk simbol dan dimasukan dalam sebuah data struktur yang merupakan sebuah queue. Setelah semua file berhasil dibaca dan informasinya dimasukan ke dalam queue maka dilanjutkan dengan mengurutkan tiap elemen dalam queue secara descending atau dari urutan besar ke kecil berdasarkan informasi jumlah simbol dalam tiap elemen queue. Setelah dilakukan pengurutan maka elemt queue disalin ke struktur data yang diberi nama datainput head yang nantinya akan digunakan ketika menulis informasi dasar dari huffman tree 3.2. Implementasi pembentukan huffman tree
3. Implementasi algoritma CHT Secara umum terdapat tiga tahap utama dalam algoritma CHT. Tahapan tersebut adalah pembentukan basic huffman tree, memutasi huffman tree, dan melakukan enkrispi-deskripsi atau dekripsi-dekopresi. Dan tiap tahap tersebut dibagi lagi menjadi beberapa proses. Pada tahap pembentukan huffman tree ini dibagi menjadi tiga proses yaitu prose pembentukan list dan queue, pembuatan tree,indexing inner node pada tree. Setelah huffman tree terbentuk maka dilanjutkan dengan proses memutasi huffman tree.
Setelah dilakukan proses membaca data masukan dari file dan memasukan dalam queue selanjutnya dilakukan proses pembentukan huffman tree. Dari proses ini akan dihasilkan sebuah huffman tree dasar berdasarkan data masukan yang nantinya pohon ini digunakan untuk proses selanjutnya. Langkah-langkah dalam pembentukan huffman tree sebagai berikut : 1. Mengambil 2 elemen prioritas (simbol yang memiliki jumlah paling kecil) dari queue yang bersisi informasi mengenai simbol dan jumlah simbol. 2. Buat inner node dimana kedua elemen yang diambil dari queue diatas sebagai
5
3. 4.
5. 6.
child dan jumlah dari kedua simbol merupakan kemungkinan inner node. Masukan inner node tersebut kedalam queue sebagai elemen baru. Jika terdapat lebih dari 1 elemen dalam queue maka ulangi langka kedua sampai tersisa satu elemen dalam node. Jika tidak maka lanjutkan ke langkah lima. Elemen yang tersisa dari queue merupakan root dari huffman tree. Masukan huffman tree yang telah terbentuk kedalam data huffman tree.
3.3. Implementasi pembentukan index Setelah huffman tree dasar telah terbentuk dilanjutkan dengan pemeberian index pada huffman tree. Pemberian index yang dimaksud disini adalah pemberian no pada inner node pada huffman tree sehingga mempermudah dalam proses memperbaharui huffman tree. Proses ini berlangsung secara rekursif dimulai dengan root dari huffman tree sampai tiap leaf dari huffman tree di temukan.
sehingga akan didapatkan bentuk huffman tree yang baru. 3.6. Implementasi enkripsi-kompresi Setelah mendapatkan huffman tree yang baru maka dilanjutkan dengan proses enkripsikompresi. Proses ini di mulai dengan mendapatkan simbol yang akan di enkripsikompresi. Proses ini berlangsung secara rekursif. Pada prinsipnya proses ini mencari simbol yang dimaksud diatas dalam huffman tree yang telah termutasi sehingga didapatkan kodenya. Langkah-langkah kompresienkripsi sebagai berikut: 1. Membaca file untuk mendapatkan simbol yang akan di enkripsi. 2. Mendapatkan root dari huffman tree yang telah dimutasi. 3. Mencari simbol mulai dari root dilanjutkan ke semua child hingga simbol ditemukan. Jika menuju left node maka masukan nilai 0 atau 1 jika melalui rigth node didalam S. S adalah string sementara. 4. Jika simbol ada dalam node maka kembalikan S sebagai codeword. 3.7. Implementasi dekripsi-dekompresi
3.4. Implementasi menurunkan chaotical map Penurunan chaotical map dilakukan dengan melakukan iterasi dari persamaan dalam chaotical map. Dengan melakukan iterasi pada persaman sebanyak n kali dari kondisi awal xo maka akan didapatkan hasil xn. n didapat dari persamaan 2.4. Hasil xn inilah yang akan digunakan dalam perhitungan untuk memperbaharui huffman tree. Setelah mendapatkan xn maka nilai x0 akan di perbaharui sehingga nilai xo sama dengan xn. 3.5. Implementasi memperbaharui atau updare huffman tree Setelah mendapatkan nilai xn yang di turunkan dari chaotical map maka dilanjutkan dengan memperbaharui huffman tree. Hal pertama yang dilakukan adalah mendapatkan nilai ri. ri merupakan representasi dari inner node dan didapat dengan menggunakan persamaan 2.5. Setalah index inner node ri didapatkan maka child dari inner node tersebut akan di tukarkan
Proses ini adalah proses untuk mendapatkan plain text dari text yang telah enkripsikompresi menggunakan algoritma CHT. Pada prinsipnya proses ini hampir sama dengan proses enkripsi-kompresi yaitu mencari simbol yang ada dalam huffman tree. Perbedaanya adalah dalam proses ini masukannya adalah codeword dan keluaranya adalah simbol yang ada pada plaintext. Langkah-langkah deskripsi-kompresi sebagai berikut: 1. Membaca file tiap byte dan simpan dalam S yang merupakan String sementara. 2. Mengambil root dari huffman tree. 3. Ambil karakter pertama dari S. Jika karakter 0 maka menuju ke left node jika 1 menuju ke rigth node. 4. Jika node adalah leaf maka kembalikan simbol dalam node jika tidak kembali ke step 3. 4. Uji Coba dan Evaluasi
6 Pada bagian ini akan ditunjukan hasil ujicoba yang dilakukan beserta evaluasinya. 4.1. Uji Coba Uji coba dilakukan untuk mengetahui hasil perbandingan antara hasil dari enkripsikompresi dengan plaint text. Variable yang akan digunakan dalam uji coba adalah rasio kompresi dan waktu yang akan digunakan. Dalam uji coba ini akan di lakukan enkripsikompresi yang akan dilakukan terhadap beberapa file uji coba yang telah ditentukan. Dalam uji coba ini akan dilakukan perbandingan rasio enkripsi-kompresi dari algoritma CHT dengan plaintext dengan menggunakan persamaan:
Rasio = Ukuran ciphertext * 100% Ukuran plaintext (5.1) Selain itu akan dibandingkan rasio enkripsikompresi dengan CHT dengan kompresi dengan kompresi huffman. Terakhir akan dibandingkan waktu yang digunakan dalam enkripsi-kompresi CHT dengan waktu kompresi dengan menggunakan huffman code. 4.2. Uji Coba I Uji coba ini dilakukan untuk mendapatkan rasio kompresi dari algoritma CHT. Rasio kompresi didapat dari membandingkan ukuran plaintext dengan ciphertext sesuai dengan persamaan 5.1. hasil uji coba dapat dilihat pada tabel 3.
Uji coba ini dilakukan untuk mendapatkan perbandingan rasio antara algoritma CHT dengan kompresi huffman codec. Hasil uji coba dapat dilihat pada tabel 4. Tabel 4 Hasil uji coba III
4.4. Uji Coba III Uji coba ini dilakukan untuk mendapatkan rasio kompresi dari algoritma CHT. Rasio kompresi didapat dari membandingkan ukuran plaintext dengan ciphertext sesuai dengan persamaan 5.1. hasil uji coba dapat dilihat pada tabel 5 Tabel 5 Hasil uji III
Tabel 3 Hasil uji coba I
2.4 4.3. Uji Coba II
Evaluasi
7 Aplikasi ini memiliki kelemahan dalam hal waktu eksekusi yang ditunjukan pada uji coba ketiga. Pada uji coba ketiga menunjukan perbedaan waktu yang cukup besar. Hal ini disebabkan bukan hanya karena iterasi pada chaotical map tepapi juga pada pembentukan huffman tree dasar terutama pada proses sorting list. Algoritma sorting yang digunakan menggunakan algoritma bubble sort yang kurang efisien sehingga memberi waktu lebih dalam waktu eksekusi. 5. Kesimpulan dan Saran Pada bagian ini akan diberikan kesimpulan berdasarkan ujicoba yang telah dilakukan serta saran untuk penggunaanya lebih lanjut . 5.1. Kesimpulan
(4) Model yang digunakan dalam algoritma CHT sama dengan kompresi dengan menggunakan huffman codec. Karena itu algoritma CHT memiliki best case dan worst case yang sama dengan huffman codec dalam rasio kompresi.hal ini ditunjukan dalam uji coba kedua yang membandingkan hasil kompresi CHT dengan kompresi yang dilakukan dengan huffman codec. (5) Worst case algoritma CHT dalam hal kompresi adalah ketika probability dari simbol lebih besar dari 2−1. (6) Kompresi algoritma CHT optimal dalam hal kompresi adalah ketika setiap simbol memiliki probability pangkat 2 dari bilangan negatif. 5.2. Saran
Berdasarkan uji coba yang telah dilakukan, terdapat kesimpulan yang dapat diambil, yaitu: (1) Rasio kompresi yang dihasilkan pada aplikasi ini hampir sama dengan rasio aplikasi yang ditunjukan pada paper yang berjudul Joint commpression and encryption using chaotically mutated huffman trees yang digunakan sebagai acuan dari pembuatan aplikasi. Hal ini ditunjukan pada data uji coba pertama. (2) Setelah melakukan uji coba kedua dapat disimpulkan bahwa algoritma enkripsi-kompresi menggunakan CHT memiliki kompresi rasio yang sama dengan menggunkan huffman codec. Hal ini disebabakan karena model statistik yang digunakan pada algoritma CHT adalah huffman dan mutasi yang dilakukan pada algoritma CHT tidak merubah model statistik. (3) Setelah melakukan uji coba ketiga dapat disimpulkan waktu eksekusi yang dibutuhkan lima sampai sepuluh kali lebih besar daripada waktu eksekusi kompresi biasa yang dilakukan dengan huffman codec. Hal ini disebabkan dalam algoritma CHT diperlukan stream cipher yang diperoleh dengan melakukan iterasi chaotical map.
Adapun saran yang berkaitan dengan Tugas Akhir ini adalah sebagai berikut: (1) Nilai parameter alpha dan beta pada algoritma CHT harus bernilai lebih kecil dari 50. Apabila lebih besar dari 50 maka entropy yang dihasilkan akan menurun. (2) Untuk pengembangan aplikasi lebih lanjut perlu adanya algoritma sorting yang lebih baik pada proses pengurutan dalam list yang berisi informasi tiap simbol sehingga waktu eksekusi dapat dikurangi. 6. Referensi [1] Houcemeddine Hermassi, Rhouma Rhouma *, Safya Belghith, “Joint compression and encryption using chaotically mutated Huffman trees”, Communications in Nonlinear Science and Numerical Simulation, Volume 15, Issue 10, October 2010, Pages 29872999. [2] Wu CP, Kuo CCJ. “Design of integrated multimedia compression and encryption systems”. IEEE Trans Multimedia 2005;7(5):828–39. October.. [3] Jakimoski Goce, Subbalakshmi KP. “Cryptanalysis of some multimedia encryption schemes”. IEEE Trans Multimedia 2008;10(3):330–8..
8 [4] Li S, Chen G, Mou X. “On the dynamical degradation of digital piecewise linear chaotic maps”. Int J Bifurc Chaos 2005;15(10):3119–51. [5] Alvarez G, Li S. Some basic crytographic requirement for chaos-base cryptosystems. [6] Furth B, Socek D, Eskicioglu AM Fundamental of multimedia encryption techniques. A chapter in multimedia security hand book , CRS Press; 2005. [7] “Data Compression.” Wikipedia. 2011. Wikipedia Foundation, Inc.. 9 januari 2011
[8] “Encryption” Wikipedia. 2011. Wikipedia Fondation,Inc.. 9januari 2011 [9] “Huffman coding” Wikipedia. 2011. Wikipedia Fondation,Inc.. 10 januari 2011 [10] “List of Chaotic map” Wikipedia. 2011. Wikipedia Fondation,Inc.. 10 januari 2011 [11] Grangetto marco, Magli Enrico, Olmo Gabriella. Multimedia selective encryption by means of randomized arithmetic coding. IEEE Trans Multimedia 2006;8(5):905-17. oktober [12] ftp://ftp.cpsc.ucalgary.ca/pub/project s/text.compression.corpus/
