BEBERAPA KARAKTERISTIK KRIPTOSISTEM KUNCI PUBLIK BERDASARKAN MATRIKS INVERS TERGENERALISASI
Oleh Budi Murtiyasa FKIP Universitas Muhammadiyah Surakarta
Makalah disampaikan pada Seminar Nasional Matematika di Universitas Brawijaya Malang tanggal 6 Agustus 2001
FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN UNIVERSITAS MUHAMMADIYAH SURAKARTA 2001
BEBERAPA KARAKTERISTIK KRIPTOSISTEM KUNCI PUBLIK BERDASARKAN MATRIKS INVERS TERGENERALISASI1 Oleh Budi Murtiyasa2 Abstrak Teori matriks invers tergeneralisasi atas Z2 dapat digunakan untuk melakukan kriptografi kunci publik. Tulisan ini menyajikan disain kriptosistem kunci publik berdasarkan matriks invers tergeneralisasi. Dikaji juga beberapa sifat yang dimiliki oleh sistem kunci publik berdasarkan matriks invers tergeneralisasi serta analisis resiko terhadap sistem tersebut. Kata kunci : matriks, enkripsi, dekripsi A. Pendahuluan Teori matriks invers tergeneralisasi (generalized invers of matrices) telah berkembang sejak awal tahun 1970-an. Tetapi pembahasan matriks invers tergeneralisasi (MIT) ini umumnya terbatas pada lapangan (field) bilangan real (Israel dan Greville, 1974). Tulisan ini mengkaji MIT pada lapangan terhingga Z2. Dapat ditunjukkan bahwa MIT pada Z2 memberikan alternatif baru bidang kriptografi pada sistem kunci publik. Sistem kunci publik, yang menggunakan pendekatan matematis dalam pengembangannya, telah menjadi alternatif baru dalam bidang enkripsi dan dekripsi data. Salah satu kriptosistem kunci publik yang dibangun dengan pendekatan matematis adalah kunci publik berdasarkan MIT (Murtiyasa, 2001; Wu and Dawson, 1998). Tulisan ini akan mengkaji beberapa karakteristik yang dimiliki oleh sistem kunci publik yang dibangun berdasarkan teori matriks invers tergeneralisasi. B. Matriks Invers Tergeneralisasi Pembahasan MIT berada dalam himpunan terhingga Z2 = {0,1}. Diketahui matriks umum A yang berdimensi kxn. Suatu matriks B yang berdimensi nxk adalah MIT dari matiks A yang berdimensi kxn, jika berlaku ABA = A. Jika A+ menyatakan MIT dari A, maka : [1] AA+A = A (Israel dan Greville, 1974). Sebaliknya, untuk matriks A tersebut di atas, matriks re-invers tergeneralisasi (generalized re-inverses) dari matriks A adalah suatu matriks X berdimensi nxk sedemikian hingga A adalah generalized inverses dari X, jadi berlaku XAX = X. Jika A- menyatakan matriks re-invers tergeneralisasi (MRIT) dari A, maka [2] A- A A- = A(Wu dan Dawson, 1998). Matriks A berdimensi mxn yang mempunyai rank r dapat dibawa ke bentuk :
⎡I r ⎣O
PAQ = ⎢
O⎤ ⎡I r , atau A = P-1 ⎢ ⎥ O⎦ ⎣O
O ⎤ -1 Q O ⎥⎦
[3]
dengan P adalah matriks nonsingular hasil penggandaan matriks baris elementer dan Q adalah matriks nonsingular hasil penggandaan matriks kolom elementer; P-1 dan Q-1 berturut-turut adalah matriks invers dari P dan Q. MIT dari A dalam bentuk [3] adalah :
⎡I r ⎣V
A+ = Q ⎢
U⎤ P W ⎥⎦
[4]
1
Makalah disampaikan pada Seminar Nasional Matematika di Universitas Brawijaya Malang, pada tanggal 6 Agustus 2001. 2 Staff Pengajar FKIP Universitas Muhammadiyah Surakarta. 1
dengan sembarang matriks-matriks U berdimensi rx(m-r), V berdimensi (n-r)xr dan W berdimensi (n-r)x(m-r). Pada Z2 = {0,1), banyaknya MIT tergantung dari banyaknya cara untuk memilih U, V, dan W yang berbeda; dalam hal ini banyaknya adalah 2r(n-r)+n(m-r). Secara umum untuk matriks A(m,n) yang mempunyai rank m, bawa matriks A sedemikian hingga A = [Im 0] Q, dengan 0 matriks nol berdimensi mx(n-m) dan Q matriks nonsingular berdimensi nxn. MRIT dari A adalah :
⎡X ⎤ ⎥ ⎣Y ⎦
A- = Q-1 ⎢
dengan X dan Y memenuhi hubungan : X2 = X dan YX = Y
[5]
[6]
C. Disain Sistem Diketahui kode linear C–(n,k), matriks generator G = [Ik A] berdimensi kxn; dan matriks paritas H berdimensi (n-k)xn dari kode linear C tersebut. Matriks H- berdimensi nx(n-k) adalah MRIT dari matriks H. Diketahui juga plaintext m adalah vektor biner dengan panjang k; maka mG adalah katakode (code word). Dengan menambahkan bentuk kesalahan (sebagai proses koreksi kesalahan katakode mG): E = e(H-)T [7] di mana e adalah vektor biner random dengan panjang n-k; diperoleh chipertext : [8] c = mG ⊕ e(H-)T Jadi dalam hal ini G dan H- bersifat publik (public key) untuk proses enkripsi pesan m yang menghasilkan chipertext c. Selanjutnya proses dekripsi untuk memperoleh kembali plaintext m dari chipertext c, dapat dilakukan sebagai berikut : (i) hitung mG = c ⊕ E (ii) dapatkan m dari mG dengan menyelesaikan sistem persamaan linear menurut sembarang k vektor kolom G yang bebas linear. Sedangkan bentuk kesalahan E dapat dicari dengan cara sebagai berikut : c(H- H)T = mGHT(H-)T ⊕ e(H-)T (H)T (H-)T = e(H-)T = E Jadi di sini H- H bersifat rahasia (privat key) untuk proses dekripsi dari chipertext c. D. Sifat-sifat Sistem Selain harus menjamin keamanan data, sifat lain yang penting dari sistem kunci publik adalah harus efisien, khususnya dalam hal ruang kunci, kompleksitas enkripsi dan dekripsi, toleransi kesalahan media transmisi, dan ekspansi pesan (Simmons ,1993:232). Berikut ini dibahas sifat-sifat khusus dari sistem kunci publik ini. 1. Ruang kunci. Telah diketahui bahwa sistem ini menggunakan dua buah kunci, yaitu kunci publik dan kunci rahasia. Karena kunci publik adalah matriks generator G dan matriks re-invers tergeneralisasi H-, ruang kunci tergantung pada dimensi dari G dan H-. Untuk kode linear C-(n,k), berarti matriks generator G berdimensi kxn, sedangkan matriks H- berdimensi nx(n-k). Ini berarti bahwa G memerlukan kn bit, sedangkan H- memerlukan n(n-k) = n2 – kn bit. Jadi total ruang kunci publik yang diperlukan adalah kn + n2 – kn = n2 bit. Sedangkan untuk kunci rahasia dari sistem adalah R = H-H. Ruang kunci juga tergantung dari dimensi matriks R = H-H. Dimensi matriks H- dan H berturut-turut adalah nx(n-k) dan (n-k)xn. Sehingga dimensi dari H-H adalah nxn. Jadi ruang kunci rahasia adalah n2 bit. 2. Kompleksitas enkripsi dan dekripsi. Kompleksitas enkripsi dan dekripsi ini didasarkan pada banyaknya operasi hitung (baik penjumlahan maupun perkalian) yang terjadi pada proses enkripsi dan 2
dekripsi. Pada proses enkripsi untuk mendapatkan chipertext c = mG ⊕ e(H-)T, ada tiga tahap komputasi, yaitu (i) komputasi mG, (ii) komputasi e(H-)T, dan (iii) menjumlahkan hasil tahap (i) dan (ii), yaitu mG ⊕ e(H-)T. Pada tahap pertama, komputasi mG, banyaknya operasi yang diperlukan pada tahap pertama ini adalah (2k – 1)n operasi. Komputasi mG menghasilkan array berdimensi 1xn. Pada tahap kedua, komputasi e(H-)T memerlukan (2(n-k)-1)n operasi. Pada tahap ketiga, yaitu operasi mG ⊕ e(H-)T, baik mG maupun e(H-)T berdimensi 1xn, banyaknya operasi penjumlahan adalah n buah. Jadi total banyaknya operasi yang diperlukan untuk enkripsi adalah (2k – 1)n + (2(n-k)-1)n + n = (2n2–n) operasi. Jadi kompleksitas enkripsi adalah (2n2–n) operasi, termasuk anggota O(n2). Pada proses dekripsi diketahui ada dua langkah , yaitu : (1) mG = c(In ⊕ RT) (2) Dapatkan m dari mG Pada langkah ke dua, yaitu dapatkan m dari mG, karena G = [Ik A] dalam bentuk standard, maka sudah dapat dipastikan bahwa k kolom yang bebas linear dari mG adalah k kolom yang pertama. Ini berarti bahwa m sama dengan k kolom pertama dari mG. Berdasarkan cara memperoleh m ini, maka banyaknya operasi adalah k kali. Jadi dalam hubungannya untuk pencarian kompleksitas dekripsi akan tergantung dari banyaknya operasi pada langkah yang pertama. Pada langkah pertama, ada dua tahap komputasi, yaitu pada tahap (i) In ⊕ RT , dan pada tahap (ii) c (In ⊕ RT). Pada tahap pertama, karena masing-masing berdimensi nxn, maka banyaknya operasi penjumlahan yang diperlukan adalah n2 operasi. Sedangkan pada tahap kedua, c berdimensi 1xn dan In ⊕ RT berdimensi nxn, sehingga banyaknya operasi adalah (2n-1)n = 2n2–n operasi. Total operasi pada langkah pertama ini adalah 2n2–n + n2 = 3n2–n operasi. Jadi kompleksitas dekripsi adalah 3n2 – n + k operasi, yang termasuk anggota O(n2). Berdasarkan hasil kompleksitas enkripsi dan kompleksitas dekripsi tersebut, total kompleksitas untuk enkripsi dan dekripsi adalah 5n2 – 2n + k, yang termasuk anggota O(n2). 3. Toleransi kesalahan media transmisi. Jika diketahui terdapat kesalahan r pada saluran selama transmisi data, maka chipertext c = mG ⊕ e(H-)T akan diterima menjadi c’ = c ⊕ r, dengan r adalah vektor biner dengan panjang n. Sesuai prosedur dekripsi, setelah menerima chipertext c’, penerima pesan akan melakukan komputasi : x = c’(In ⊕ RT) x = (c ⊕ r) (In ⊕ ( H- H)T) x = c (In ⊕ ( H- H)T) ⊕ r (In ⊕ H- H)T) x = mG ⊕ r (In ⊕ H- H)T) Hal ini menunjukkan bahwa jika r (In ⊕ H- H)T) = 0, maka kesalahan yang ditimbulkan oleh media transmisi dapat ditolerir (diabaikan). 4. Ekspansi pesan. Suatu sistem kunci publik dikatakan mempunyai ekspansi pesan jika panjang dari blok chipertext lebih panjang dari blok plaintext. Semakin besar ekspansi pesan, sistem tersebut menjadi semakin tidak efisien. Dalam sistem kunci publik ini, panjang blok plaintext (pesan) adalah k, sedangkan panjang blok chipertext adalah n. Jadi rasio ekspansi pesan adalah p = n/k. E. Analisis Resiko Analisis resiko terhadap sistem ini didasarkan pada kemungkinan serangan (attack) terhadap sistem kunci publik ini. Kemungkinan serangan terhadap sistem ini terutama berhubungan dengan pencarian matriks paritas H. Jika matriks paritas H diperoleh, maka penyusup akan memperoleh kunci rahasia R = H-H. Selanjutnya, kunci rahasia tersebut dapat digunakan oleh penyusup untuk mendapatkan plaintext dari pesan yang dikirimkan. 3
1.Mencari semua matriks H yang mungkin. Berdasarkan definisi, H- adalah matriks re-invers tergenaralisasi (MRIT) dari H. Hal ini berarti bahwa H adalah matriks invers tergeneralisasi (MIT) dari H- . Jika matriks H diperoleh, maka kunci rahasia R = H- H dapat ditemukan. Penyusup (intruder) mungkin mencoba mencari setiap MIT dari H- (yang dipublikasikan) untuk memperoleh H, dengan harapan mendapatkan kunci rahasia R. Jika rank dari H- adalah r dan H- berdimensi nx(n-k), maka banyaknya MIT dari H- adalah 2r(n-k-r)+(n-k)(n-r) = 2r(n-r)+n(n-k-r). Suatu jumlah yang sangat besar untuk mendapatkan sebuah matriks kunci. 2. Mencoba sembarang matriks (H-)+ sebagai MIT dari H-. Matriks (H-)+ ini sebenarnya adalah matriks paritas H, sehingga diharapkan dapat digunakan sebagai kunci untuk menemukan bentuk kesalahan E = e(H-)T. Jika memperoleh E, maka mG = c ⊕ E. Selanjutnya pesan m dapat ditemukan dengan mengambil k kolom pertama dari mG. Dari disain sistem telah diketahui bahwa bentuk kesalahan E ini dapat diperoleh dengan melakukan komputasi : E = c (H- H)T = c (H- (H-)+)T = (mG ⊕ e(H-)T) ((H-)+)T (H-)T) E = mG (((H-)+)T (H-)T) ⊕ e(H-)T Dapat diamati bahwa kesalahan E = e(H-)T akan diperoleh jika dan hanya jika mG (((H-)+)T (H-)T) = 0. Suatu kondisi yang hampir tidak mudah dipenuhi, sebab jika dipilih (H-)+ ≠ 0, maka hampir dapat dipastikan bentuk mG (((H-)+)T (H-)T) ≠ 0, sebab (H-)+ hanyalah salah satu dari 2r(n-r)+n(n-k-r) matriks H yang mungkin. Sebaliknya jika dipilih (H-)+ = 0, maka akan selalu didapatkan E = c (H- (H-)+)T= 0. Bentuk kesalahan E = 0 adalah satu bentuk kesalahan yang mustahil dipilih oleh para pengirim pesan. Kesimpulannya, dengan langkah tersebut di atas, para penyusup tetap sangat kesulitan menemukan plaintext yang dikirimkan. 3. Mencari matriks paritas H dari matriks generator G. Bentuk mG (((H-)+)T (H-)T) = 0 ini dapat dipenuhi jika dan hanya jika G ((H-)+)T = 0. Berdasarkan teori kode linear, jika G adalah matriks generator dan H adalah matriks paritas, maka GHT = 0. Ini berarti penyusup dapat mengalihkan strategi menemukan bentuk E diubah menjadi strategi untuk menemukan (H-)+ dengan mencari ((H-)+)T dari sistem persamaan : G ((H-)+)T = 0 yang dapat dipandang sebagai sistem persamaan dengan k buah persamaan yang yang masing-masing memuat n buah variabel. Kolom-kolom dari ((H-)+)T masingmasing dapat dipandang memuat n buah variabel yang berbeda yang harus diselesaikan. Tetapi karena rank dari G adalah k < n, maka sistem persamaan akan mempunyai banyak penyelesaian. Menurut teori sistem persamaan linear, jika rank G adalah k dan banyaknya variabel adalah n, maka banyaknya variabel bebas adalah n-k. Pada himpunan Z2, tiap variabel mempunyai dua kemungkinan nilai, yaitu 0 atau 1, sehingga banyaknya pilihan untuk menentukan nilai-nilai dari variabel bebas adalah 2n-k. Sedangkan nilai dari k variabel sisanya ditentukan oleh nilai-nilai (n-k) variabel bebas yang dipilih. Jadi dalam hal ini banyaknya penyelesaian yang mungkin untuk mendapatkan salah satu kolom dari ((H-)+)T adalah 2n-k. Jika matriks ((H-)+)T berdimensi nx(n-k), maka ((H-)+)T mempunyai n-k kolom, banyaknya pilihan untuk mendapatkan ((H-)+)T adalah 2(n-k)(n-k). Suatu cara yang tidak praktis untuk menemukan (H-)+ atau H dari matriks generator G. 4. Mencari matriks paritas H berdasarkan matriks paritas bentuk standard. Dalam bentuk standard matriks generator G = [Ik A], berarti ada matriks paritas H1 = [AT In-k]. Matriks paritas H dapat diperoleh dengan jalan melakukan sederetan operasi baris elementer terhadap H1. Dalam hal ini operasi baris elementer yang digunakan adalah tipe 1 (menukar satu baris dengan baris lain) dan/atau tipe 3 (mengganti satu baris dengan jalan menambahnya dengan baris lain). Jadi : H = Es Es-1 … E1 H1 atau H = S H1
4
di mana matriks nonsingular S ∈ M(n-k,n-k) adalah hasil penggandaan matriks baris elementer yang membawa H1 ke H. Pada himpunan Z2 ={0,1}, banyaknya matriks nonsingular S tersebut adalah : (2n-k – 20) (2n-k – 21) (2n-k – 22) . . . (2n-k – 2n-k-1). (Macwilliams and Sloane, 1993:231). 5. Mencari vektor biner e untuk menemukan bentuk kesalahan E. Telah diketahui bahwa bentuk kesalahan E dalam sistem ini adalah E = e(H-)T. Jika vektor biner e ditemukan, maka E diperoleh. Selanjutnya jika E diperoleh, maka mG dapat diperoleh dengan jalan menghitung mG = c ⊕ E. Vektor biner e mempunyai panjang n-k. Jadi banyaknya pilihan yang berbeda untuk menemukan vektor biner e ini adalah 2n-k. Jika n cukup besar dan k cukup kecil, maka 2n-k juga sangat besar. Metode ini juga menjadi tidak praktis untuk dilakukan. Tetapi dibandingkan dengan metode untuk menemukan H, metode mencari vektor biner e mempunyai peluang keberhasilan yang lebih besar. F. Penutup Memperhatikan kemungkinan serangan para penyusup, dengan jalan mencari berbagai kemungkinan matriks paritas H dan mencoba sembarang vektor biner e, kemungkinan keberhasilan terbesar dengan mencari vektor biner e. Sebaiknya untuk menjaga keamanan dari sistem kunci publik, nilai k dan n ini dibuat atau dipilih cukup besar. Tetapi yang harus diingat walaupun n dan k cukup besar, jika n dan k terlalu dekat, yang berarti n-k menjadi kecil, maka sistem menjadi kurang aman. Sebaliknya nilai n jangan sampai terlalu besar jika dibandingkan nilai k, sebab jika hal ini terjadi akan muncul ekspansi pesan yang sangat besar. Hal ini berakibat sistem menjadi kurang efisien. Sebaiknya nilai n ini sekitar dua kali nilai k supaya sistem tetap efisien dan aman (Wu and Dawson, 1998 : 325). Penelitian ini telah menunjukkan bahwa teori matriks, salah satunya matriks invers tergeneralisasi dapat digunakan pada bidang kriptografi. Operasi penjumlahan dan perkalian matriks, yang merupakan operasi utama pada kriptografi yang berdasarkan pada matriks, mempunyai kompleksitas yang rendah. Hal ini menunjukkan bahwa dengan menggunakan matriks, proses pengkodean dan pe-dekodean suatu pesan juga akan berlangsung dengan cepat. Penelitian lanjutan tentang aplikasi matriks pada bidang kriptografi, sehingga menghasilkan alternatif baru pada kriptografi berdasarkan teori matriks, masih terbuka lebar. Di samping itu, sistem kunci publik yang dibangun berdasarkan matriks invers tergeneralisasi ini juga masih memerlukan penelitian lebih lanjut, misalnya dalam hal autentikasi (authentication). Penelitian lanjutan lainnya yang bisa disarankan adalah penggunaan sistem kunci publik jika pesan yang akan dikirimkan tidak berupa teks tetapi berupa gambar atau peta. G. Daftar Pustaka Israel, A.B., dan Greville, T.N.E., 1974, Generalized Inverses : Theory and Applications, John Wiley & Sons, New York. MacWilliams, F.J., dan Sloane, N.J.A., 1993, The Theory of Error Correcting Codes, Eight Impression, North-Holland Mathematical Library, Amsterdam. Murtiyasa,. B., 2001, ‘Aplikasi Matriks Invers Tergeneralisasi pada Kriptografi’, Makalah pada Seminar Nasional dan Konferda Matematika VII di FMIPA UII Yogyakarta tanggal 3 Februari 2001. Simmons, G.J.(ed.), 1993, Contemporary Cryptology : The Science of Information Integrity, New York : IEEE Press. Wu, C.K., dan Dawson, E., 1998, “Generalised Inverses in Public Key Cryptosystem Design” dalam IEE Proceedings Computer Digit. Tech. Vol. 145 No. 5, September 1998
5
