CAUCHY – ISSN: 2086-0382 55 APLIKASI QUASIGROUP DALAM PEMBENTUKAN KUNCI RAHASIA PADA ALGORITMA HIBRIDA (RSA-QUASIGROUP CIPHER) Muhammad Khudzaifah Jurusan Matematika, F.MIPA, Universitas Brawijaya, Malang, Indonesia Email : m_khudzaifah@yahoo.com ABSTRAK Pada artikel ini dibahas penerapan quasigrup di bidang kriptografi. Didefinisikan Suatu operasi quasigroup order 𝑝 − 1 sehingga bisa membentuk suatu algoritma kriptografi yang disebut sebagai quasigrup cipher, quasigrup cipher merupakan algoritma kriptografi simetris. Algoritma kriptografi simetris memiliki sistem keamanan lemah karena kunci yang digunakan untuk proses enciphering sama dengan kunci yang digunakan untuk proses deciphering. Sehingga pada artikel ini algoritma quasigroup cipher dimodifikasi dengan menggabungkannya dengan algoritma RSA menjadi suatu algoritma hibrida yang memiki dua tingkatan kunci. Kata kunci : quasigrup, kriptografi, algoritma hibrida. ABSTRACT In this article discusses application of quasigroup in the field of cryptography, a quasigroup order 𝑝 − 1 operation is defined so that it can form a cryptographic algorithm called a cipher quasigrup, quasigrup cipher is a symmetric cryptographic algorithms, symmetric cryptographic algorithms have weak security systems which are used as the key for enciphering process same as the key used for deciphering process. So at this article quasigroup cipher algorithm is modified by combining the RSA algorithm into a hybrid algorithm that is thinking about the two key levels. Keywords: quasigrup, cryptography, hybrid algorithm PENDAHULUAN Kriptografi memegang peranan penting seiring dengan perkembangan teknologi informasi dan komunikasi. Masalah keamanan merupakan salah satu aspek penting dari sebuah sistem informasi. Salah satu hal yang penting dalam komunikasi menggunakan komputer dan dalam jaringan komputer untuk menjamin keamanan pesan, data, ataupun informasi adalah enkripsi. Disini enkripsi dapat diartikan sebagai kode atau cipher. Di sisi lain, beberapa teori dalam aljabar abstrak khususnya teori mengenai quasigroup telah dikembangkan secara luas mulai dari bentuk integrasinya dengan disiplin ilmu lain hingga aplikasinya dalam berbagai bidang. Banyak teori quasigroup yang telah diterapkan dalam steganografi, teori pengkodean, dan kriptografi. Penggunaan quasigroup pada kriptografi adalah quasigroup cipher, yang merupakan kriptografi kunci simetri yang keamanannya kurang baik. Hal ini dikarenakan proses dekripsinya dan enkripsinya menggunakan kunci yang sama. Oleh karena itu akan dikombinasikan dengan algoritma kunci asimetris, yang proses enkripsi dan dekripsinya menggunakan kunci yang berbeda. Pada tahun 2004 Gligoroski mengembangkan quasigroup cipher dengan mendefinisikan quasigroup order p − 1, dan dikombinasikan dengan algoritma Elgamal. Dalam tesis ini dibahas penggunaan quasigroup pada kriptografi yang dikombinasikan dengan algoritma RSA. Alasan pemilihan algoritma RSA ini adalah karena proses enkripsi dan dekripsi RSA lebih cepat daripada Algoritma Elgamal. TEORI DASAR 1. Mengkontruksi Kunci Rahasia dalam Bentuk Quasigroup Cipher Pada sub-bab ini akan diperkenalkan definisi dan teori quasigroup yang dikutip dari (Markovski, et al., 1997) Teorema 1.1 Misalkan (𝐴,∗) adalah quasigroup yang menetapkan sebuah operasi biner \ pada A sedemikian sehingga untuk semua 𝑥, 𝑦 ∈ 𝐴 berlaku, 𝑥\𝑦 = 𝑧 ↔ 𝑥 ∗ 𝑧 = 𝑦, Maka groupoid (𝐴,\) adalah quasigroup. mailto:m_khudzaifah@yahoo.com Muhammad Khudzaifah 56 Volume 3 No. 2 Mei 2014 Definisi 1.2 Operasi ∖ adalah dual dari ∗ sehingga quasigroup (𝐴,∖) adalah dual dari quasigroup (𝐴,∗).(𝐴,∗,∖) adalah quasigroup yang diperoleh dari hasil perluasan quasigroup (𝐴,∗). Teorema 2.3 Quasigroup (𝐴,∗,∖) memenuhi persamaan identitas : 𝑥 ∖ (𝑥 ∗ 𝑦) = 𝑦, 𝑥 ∗ (𝑥 ∖ 𝑦) = 𝑦 , Untuk semua 𝑥, 𝑦 ∈ 𝐴. Definisi 2.4 Misalkan 𝑢𝑖 ∈ 𝐴 +, 𝑘 ∈ ℕ, 𝑘 ≥ 1, dan 𝑎1 ∈ 𝐴 maka, 𝑓∗(𝑢1𝑢2 … 𝑢𝑘 ) = 𝑣1𝑣2 … 𝑣𝑘 ⇔ 𝑣1 = 𝑎1 ∗ 𝑢1, 𝑣2 = 𝑣2 ∗ 𝑢2, 𝑣3 = 𝑣3 ∗ 𝑢3, ⋮ 𝑣𝑖+1 = 𝑣𝑖 ∗ 𝑢𝑖+1, 𝑖 = 1,2, … , 𝑘 − 1, 𝑓∖(𝑢1𝑢2 … 𝑢𝑘 ) = 𝑣1𝑣2 … 𝑣𝑘 ⇔ 𝑣1 = 𝑎1 ∖ 𝑢1, 𝑣2 = 𝑣1 ∖ 𝑢2, 𝑣3 = 𝑣2 ∖ 𝑢2, ⋮ 𝑣𝑖+1 = 𝑣𝑖 ∖ 𝑢𝑖+1, 𝑖 = 1,2, … , 𝑘 − 1. Sixtuple (𝐴,∗,∖, 𝑎1, 𝑓∗, 𝑓∖) disebut quasigroup cipher atas alfabet 𝐴. 2. Mengkontruksi Kunci Rahasia dalam Bentuk Quasigroup Cipher menggunakan quasigroup atas order p-1 Misalkan himpunan huruf alfabet adalah himpunan berhingga 𝑄 dan dinotasikan 𝑄+ adalah himpunan semua kata tak kosong atau string berhingga yang terdiri atas anggota dari Q. Anggota dari 𝑄+ akan dinotasikan sebagai 𝑎1𝑎2, … 𝑎𝑛 . 𝑎𝑖 ∈ 𝑄. Misalkan ∗ adalah operasi pada quasigroup pada himpunan 𝑄 dan (𝑄,∗) adalah quasigroup, untuk 𝑎 ∈ 𝑄 didefinisikan dua fungsi 𝑒𝑎 , 𝑑𝑎 : 𝑄 + ⟶ 𝑄+ sebagai berikut Misal 𝑎𝑖 ∈ 𝑄, 𝛼 = 𝑎1𝑎2 … 𝑎𝑛 . Maka 𝑒𝑎 (𝛼) = 𝑏1𝑏2 … 𝑏𝑛 ⟺ 𝑏1 = 𝑎 ∗ 𝑎1, 𝑏2 = 𝑏1 ∗ 𝑎2, … , 𝑏𝑛 = 𝑏𝑛−1 ∗ 𝑎𝑛 . Sehingga 𝑏𝑖+1 = 𝑏𝑖 ∗ 𝑎𝑖+1 untuk setiap 𝑖 = 0,1, … , 𝑛 − 1, dimana 𝑏0 = 𝑎, dan 𝑑𝑎 (𝛼) = 𝑐1𝑐2 … 𝑐𝑛 ⟺ 𝑐1 = 𝑎 ∗ 𝑎1, 𝑐2 = 𝑎1 ∗ 𝑎2, … , 𝑐𝑛 = 𝑎𝑛−1 ∗ 𝑎𝑛 . Sehingga 𝑐𝑖+1 = 𝑎𝑖 ∗ 𝑎𝑖+1 untuk setiap 𝑖 = 0,1, … , 𝑛 − 1, dimana 𝑎0 = 𝑎. Definisi dan teori quasigroup pada sub bab ini dikutip dari [1] Definisi 2.1 Fungsi 𝑒𝑎 dan 𝑑𝑎 disebut sebagai 𝑒- transformasi string dan 𝑑-transformasi string dari 𝑄+ berdasarkan operasi ∗ dengan leader 𝑎. Definisi 2.2 Jika dipilih sebanyak 𝑘 leaders 𝑎1, 𝑎2, … , 𝑎𝑘 ∈ 𝑄 maka didefinisikan pemetaan fungsi komposisi 𝐸𝑘 = 𝐸𝑎1…𝑎𝑘 = 𝑒𝑎1 ∘ 𝑒𝑎2 ∘ ∙∙∙ ∘ 𝑒𝑎𝑘 dan 𝐷𝑘 = 𝐷𝑎1…𝑎𝑘 = 𝑑𝑎1 ∘ 𝑑𝑎2 ∘ ∙∙∙ ∘ 𝑑𝑎𝑘 disebut sebagai 𝐸- dan 𝐷- quasigroup transformasi string pada 𝑄+. Lemma 2.3 Fungsi 𝐸𝑘 dan 𝐷𝑘 adalah permutasi pada 𝑄 +. Lemma 2.4 Pada quasigroup (𝑄,∗) dengan diberikan himpunan dari 𝑘 𝑙𝑒𝑎𝑑𝑒𝑟𝑠 {𝑎1, 𝑎2, … , 𝑎𝑘 } maka invers dari 𝐸𝑘 = 𝐸𝑎1…𝑎𝑘 = 𝑒𝑎1 ∘ 𝑒𝑎2 ∘ ∙∙∙ ∘ 𝑒𝑎𝑘 adalah 𝐸𝑘 −1 = 𝐷𝑘 = 𝐷𝑎𝑘…𝑎1 = 𝑑𝑎𝑘 ∘ ∙∙∙ ∘ 𝑑𝑎1 . Definisi 2.5 Quasigroup (𝑄,∗) dan k-tuple (𝑎1, 𝑎2, … , 𝑎𝑘 ) dari leader 𝑎𝑖 ∈ 𝑄, sistem ((𝑄,∗), (𝑎1, 𝑎2, … , 𝑎𝑘 ), 𝐸𝑎1…𝑎𝑘 , 𝐷𝑎𝑘…𝑎1 ) terdefinisi sebagai quasigroup stream cipher atas string di 𝑄+. Lemma 2.6 Untuk suatu 𝑝 bilangan prima dan bilangan 𝐾 yang memenuhi 1 ≤ 𝐾 ≤ 𝑝 − 2, fungsi 𝑓𝐾 (𝑗) = 1 1+(𝐾+𝑗)𝑚𝑜𝑑(𝑝−1) 𝑚𝑜𝑑 𝑝 adalah permutasi dari element di ℤ𝑝 ∗ Lemma 2.7 Operasi biner ∗ pada himpunan 𝑄 = {1,2, … , 𝑝 − 1} didefinisikan sebagai 𝑖 ∗ 𝑗 = 𝑖 × 𝑓𝐾 (𝑗)𝑚𝑜𝑑 𝑝 membentuk quasigroup (𝑄,∗). Akibat 2.8 Jika didefinisikan fungsi 𝑔(𝑖, 𝑗, 𝐾) = ((𝑖 × 𝑗−1𝑚𝑜𝑑 𝑝) − 1 − 𝐾) 𝑚𝑜𝑑 (𝑝 − 1) yang mengambil parameter 𝑖, 𝑗, 𝐾 dari himpunan 𝑄 = {1,2, … , 𝑝 − 1}, yang memetakan himpunan 𝐴 = {1,2, … , 𝑝 − 1}3 ke himpunan 𝐵 = {1,2, … , 𝑝 − 2} maka pembagi kiri (𝑄,\) dari quasigroup (𝑄,∗) Aplikasi Quasigroup dalam Pembentukan Kunci Rahasia pada Algoritma Hibrida CAUCHY – ISSN: 2086-0382 57 yang didefinisikan pada Lemma 3.2.7 didefinisikan sebagai 𝑖 \ 𝑗 = { 𝑔(𝑖, 𝑗, 𝐾), jika 𝑔(𝑖, 𝑗, 𝐾) ≠ 0 𝑝 − 1, jika 𝑔(𝑖, 𝑗, 𝐾) = 0 PEMBAHASAN 1. Mengkontruksi Algoritma Hibrida (RSA- Quasigroup cipher) Ilustrasi proses encipher dan decipher 1) A membangkitkan kunci publik dan kunci privat dengan algoritma RSA yang mana kunci publik akan dikirimkan ke B. 2) B mengenkripsi pesan dengan algoritma Quasigroup cipher, dan mengenkripsi session key dari Quasigroup cipher dengan kunci publik yang diberikan oleh A dengan menggunakan Algoritma RSA. Pesan dan key yang telah terenkripsi dikirim ke A. 3) A mendekripsi session key dari B dengan menggunakan kunci privat algoritma RSA, lalu mendekripsi pesan dari B dengan menggunakan session key yang sudah terdekripsi dengan algoritma Quasigroup cipher. 2. Algoritma Hibrida (RSA-Quasigroup cipher) Algoritma Enkripsi 1) Pilih sebarang bilangan bulat 𝐾, 1 ≤ 𝐾 ≤ 𝑝 − 1 yang mana quasigroup (𝑄,∗) terdefinisi untuk elemen {1,2, … , 𝑝 − 1} dengan persamaan pada Lemma 2.7, dengan p adalah sebarang bilangan prima yang dipilih 2) Enkripsi 𝐾 dengan Algoritma RSA 3) Pilih 𝑘 ≥ 3 bilangan bulat acak 𝑎𝑖, 𝑖 = 1,2, … , 𝑘, 1 ≤ 𝑎𝑖 ≤ 𝑝 − 2 untuk menjadi leader untuk quasigroup cipher dan enkripsikan dengan Algoritma RSA 4) Ubah setiap karakter pada pesan 𝑚𝜇 menjadi bilangan bulat pada range {1,2, … , 𝑝 − 1}, dengan 𝜇 adalah indeks setiap karakter dari pesan 5) Secara berulang hitung 𝑚𝜇 𝑖 = 𝑎𝑖 ∗ 𝑚𝜇 𝑖−1, dimana 𝑚𝜇 0 = 𝑚𝜇, 𝑖 = 1, … , 𝑘 dan ∗ adalah operasi quasigroup yang terdefinisi pada Lemma 2.7 6) 𝑐𝜇 = 𝑚𝜇 𝑘 dan update nilai leader dengan 𝑎𝑖 = 𝑚𝜇 𝑖 , 𝑖 = 1, … , 𝑘 − 1 dan 𝑎𝑘 = 1 + (∑ 𝑚𝜇 𝑖𝑘 𝑖=1 𝑚𝑜𝑑 (𝑝 − 1)). 7) Didapatkan Session key terenkripsi dan pesan yang terenkripsi 𝑐𝜇 (ciphertext) Algoritma Dekripsi 1) Dekripsi Session key dengan Algoritma RSA, maka didapatkan 𝐾 untuk membuat (𝑄,\) dan didapatkan sejumlah 𝑘 leader. 2) Secara berulang hitung 𝑐𝜇 𝑘 = 𝑎𝑘 \𝑐𝜇, 𝑐𝜇 𝑖 = 𝑎𝑖 \𝑐𝜇 𝑖+1, 𝑖 = 𝑘 − 1, … , 1 dan \ adalah operasi 𝑞𝑢𝑎𝑠𝑖𝑔𝑟𝑜𝑢𝑝 yang terdefinisi pada Akibat 2.8 3) 𝑚𝜇 = 𝑐𝜇 1 dan update nilai leader dengan 𝑎𝑖 = 𝑐𝜇 𝑖+1, 𝑖 = 1, … , 𝑘 − 1 dan 𝑎𝑘 = 1 + (𝑐𝜇 + ∑ 𝑐𝜇 𝑖𝑘 𝑖=2 𝑚𝑜𝑑 (𝑝 − 1)). 4) Didapatkan plaintext 𝑚𝜇 KESIMPULAN Algoritma kriptografi yang didasarkan dari quasigroup yaitu quasigroup cipher memiliki keamanan cukup baik, hal ini dibuktikan pada contoh ketika kriptanalis salah mendekripsi satu huruf saja maka pesan tidak bisa terbaca. Kelemahan algoritma quasigroup adalah karena kuncinya adalah kunci simetris, sehingga bila kuncinya bocor kepada orang lain, maka pesan bisa dibaca orang lain. Sehingga diperkuat dengan algoritma RSA yang memiliki kunci asimetris menjadi algoritma hibrida yang tingkat keamanannya lebih tinggi karena memiliki 2 tingkatan kunci. BIBLIOGRAPHY [1] D. Gligoroski, "Stream Cipher Based on Quasigroup String Transformation in Zp*.," Faculty of Natural Sciences institute of Informatics, Skopje, 2004. [2] D. Ariyus, Pengantar Ilmu Kriptografi, Yogyakarta: Andi Press, 2008. [3] M. A. Al-Turky, "On the number and Equivalent Latin Squares," Journal of Al-Anbar University for pure Science, pp. 71-75, 2007. [4] P. B. Bhattacharya, S. K. Jain and S. R. Nagpaul, Basic Abstrack Algebra, New York: Cambridge University Press, 1990. [5] J. Bell, "An Introduction to SDR’s and Latin Squares," More-head Electonic Journal of Applicable Mathematics, pp. 1-8, 2005. [6] Koscielny, "Generating Quasigroups for Cryptograpic Applications," International Muhammad Khudzaifah 58 Volume 3 No. 2 Mei 2014 Journal of Applied Mathematic and Computer Science, pp. 559-569, 2002. [7] E. Ochodkova. and V. Snasel, "Using Quasigroups for Secure Encoding of File Sistem," in Proceedings of The Confrence for Security and Protection of Information, 2001. [8] S. Markovski, D. Glikoroski and S. Andonova., "Using Quasigroups for One-one Secure Encoding," in Proceeding of VII-th Confrence for Logic and Computing-LIRA’97, 1997. Pendahuluan Teori Dasar 1. Mengkontruksi Kunci Rahasia dalam Bentuk Quasigroup Cipher 2. Mengkontruksi Kunci Rahasia dalam Bentuk Quasigroup Cipher menggunakan quasigroup atas order p-1 Pembahasan 1. Mengkontruksi Algoritma Hibrida (RSA-Quasigroup cipher) 2. Algoritma Hibrida (RSA-Quasigroup cipher) Algoritma Enkripsi Algoritma Dekripsi Kesimpulan Bibliography