DISAIN KRIPTOSISTEM KUNCI PUBLIK BERDASARKAN TEORI KODING LINEAR1 Oleh Budi Murtiyasa FKIP Universitas Muhammadiyah Surakarta Abstract The paper addresses an application of the theory of linear code over Z2 = {0, 1} in the field of computer science, especially public- key cryptosystem. The development idea of this design is based on the error-correcting code by technique of generalized inverses of matrices. Based on that design, discusses the method of the encryption and decryption, and the key generation of the cryptosystem. Kata kunci : kode linear, matriks, enkripsi, dekripsi.
A. Pendahuluan Banyak cabang matematika yang telah digunakan untuk mengembangkan konsep kriptosistem kunci publik. Beberapa cabang matematika yang telah digunakan untuk mengembangkan konsep kunci publik dapat disebutkan di antaranya adalah teori bilangan, aljabar, dan teori koding. Beberapa kriptosistem kunci publik yang telah ada di antaranya adalah RSA, ElGamal, Elliptic Curve, Chor-Riverst, Merkle-Hellman Knapsack, dan sebagainya [Stinson, 1995; Patterson, 1987; Simmons, 1993]. Sistem kunci publik RSA, yang ditemukan oleh River, Shamir, dan Adleman, dikembangkan berdasarkan teori bilangan. Keamanan sistem RSA terletak pada kesulitan pemfaktoran bilanganbilangan besar. Tetapi hal ini juga menyiratkan adanya kelemahan bahwa seiring dengan kemajuan teknologi komputasi, problem pemfaktoran bilangan besar juga akan mudah diatasi. Kelemahan lain dari sistem RSA adalah terlalu lambat pada proses enkripsi data [Tanenbaum, 1997 : 191]. Sementara itu Shao (1998) telah mengembangkan konsep kriptosistem kunci publik berdasarkan faktorisasi dan logaritma diskrit. Dalam penelitiannya tersebut, Shao menyimpulkan bahwa kunci publik yang dibangun berdasarkan faktorisasi dan logaritma diskrit tidak bisa diterobos (unbreakable) jika problem faktorisasi dan logaritma diskrit secara simultan tidak bisa diselesaikan. Tetapi Lee (1999:119) dalam penelitiannya menunjukkan bahwa pada kriptosistem kunci publik yang didisain oleh Shao tersebut tersirat adanya kelemahan, yaitu jika problem faktorisasi bisa diselesaikan, maka kunci publik akan dapat diterobos. Kriptosistem kunci publik yang dikembangkan oleh Merkle dan Hellman, yang lebih dikenal dengan sebutan The Merkle-Hellman Knapsack System dibangun berdasar pada teori subset sum [Stinson, 1995:190-193]. Tetapi semua versi algoritma dari kriptosistem kunci publik ini ternyata terbukti tidak aman dan jarang digunakan lagi [Tanenbaum, 1997 : 191; Stalling, 1995 : 108]. Memperhatikan uraian tersebut, sangat dimungkinkan mengembangkan disain kriptosistem kunci publik bedasarkan cabang-cabang matematika yang lain, dalam hal ini, teori koding linear dan teori matriks. B. Kunci Publik McEliece Kriptosistem kunci publik adalah metode penyandian data yang menggunakan dua buah kunci yang berbeda antara pengirim dan penerima pesan. Skema dari public-key cryptosystem bisa dijelaskan sebagai berikut : data (pesan) asli dari user A, yang biasa disebut dengan plaintext, dienkripsikan (disandikan) dengan kunci milik user B (public key). Setelah chipertext (data yang sudah disandikan) diterima user B, chipertext ini kemudian didekripsikan dengan menggunakan kunci kedua milik user B (privat key); sehingga user B dapat membaca plaintext yang dikirim user A.
1
Disampaikan pada Seminar dan Konferensi Nasional Himpunan Matematika Indonesia di UM Malang pada tanggal 22-25 Juli 2002. 1
public key B plaintext
privat key B
chipertext Enkripsi
plaintext Dekripsi
User A
User B Gambar 1: Skema enkripsi-dekripsi kunci publik
Teori koding linear dengan bantuan teori matriks telah menjadi alat bantu yang potensial untuk melakukan penyandian data. Untuk itulah sangat dimungkinkan mengembangkan kriptosistem kunci publik berdasarkan teori koding linear. Teknik untuk mendapatkan katakode c dari suatu pesan m yang ditransmisikan adalah menggunakan formula : c = mG + e (1) di mana G adalah matriks generator dan e adalah vektor kesalahan (error vector) sebagai bentuk koreksi kesalahan terhadap kode mG. [Vanstone dan Oorschot, 1989; Macwilliams dan Sloane, 1993]. Terdapat beberapa jenis kriptosistem kunci publik berdasarkan teori koding linear. Salah satu kriptosistem kunci publik tersebut adalah McEliece public key cryptosystem. Disain enkripsi dan dekripsi dari kriptosistem ini sebagaimana ditunjukkan Tabel 1 di bawah ini. Tabel 1. Sistem Enkripsi-Dekripsi Kunci Publik McEliece Publik G’, t Rahasia G, P, S Enkripsi c = mG’ ⊕ e Dekripsi (1) c1 = c P-1 (2) m1 = c1 ⊕ e1 (3) dapatkan m0 dari m0 G = m1 (4) m = m0 S-1 [Stinson, 1995 : 196] Dalam Tabel 1 tersebut, m adalah pesan yang dikirimkan dan c adalah chipertext dari pesan m. Sedangkan G adalah matriks generator dari kode Goppa C-(n,k), S adalah matriks yang invertibel, dan P adalah matriks permutasi, serta G’ = SGP. Sementara itu e, dengan bobot (weight) t, adalah sembarang vektor biner yang juga berfungsi sebagai bentuk koreksi kesalahan kode mG’. Sementara itu Canteaut dan Sendrier (1998:187) telah menunjukkan bahwa dengan menggunakan kode goppa, kriptosistem McEliece belum bisa memberikan layanan keamanan yang memadai. Penggunaan kode goppa pada kriptosistem McEliece ternyata juga menunjukkan beberapa kelemahan dari kriptosistem tersebut [Loidreu dan Sendrier, 1998:382]. Lebih lanjut Wu-Dawson (1998) menyatakan bahwa keunggulan dari kriptosistem McEliece terletak pada proses enkripsi dan dekripsi yang cepat. Sedangkan kelemahan dari kriptosistem McEliece adalah memerlukan ruang kunci yang besar dan adanya ekspansi pesan yang dikirimkannya [Wu and Dawson, 1998 : 321]. Karena tujuan utama kriptosistem adalah memberikan layanan keamanan data, maka perlu dibuat disain kriptosistem kunci publik yang mampu memberikan layanan keamanan data yang memadai. Untuk itu, tulisan ini mengajukan disain baru kriptosistem kunci publik berdasarkan teori koding linear, yang dikembangkan dari kunci publik McEliece. Ide dasar pengembangan adalah melakukan rekonstruksi terhadap matriks G dan vektor random e dari persamaan (1) untuk mendapatkan katakode atau chipertext c. Rekontruksi vektor random e digunakan teknik matriks invers tergeneralisasi. C. Kode Linear Suatu k blok data atau pesan m = m1m2m3…mk akan dikodekan ke dalam katakode (codeword) x = x1x2x3…xn, di mana n ≥ k. Katakode – katakode tersebut membentuk kode (code). Melalui prosedur tersebut, bagian pertama dari katakode memuat data itu sendiri, yaitu : 2
x1 = m1, x2 = m2, x3 = m3, …, xk = mk; sedangkan bagian berikutnya memuat n-k simbol kontrol (check symbols), yaitu xk+1, xk+2, …, xn. Baik data maupun katakode berada dalam sistem biner, karenanya operasi hitung yang berhubungan dengan katakode mengikuti operasi hitung dalam modulo 2.. Definisi 1: Diketahui k , n bilangan bulat positip dengan k ≤ n dan himpunan terhingga Z2. Kode linear C yang mempunyai dimensi k, dinyatakan dengan C-(n,k), adalah ruang bagian (subspace) dari ruang vektor Vn(Z2). Pada kode linear C-(n,k) yang mempunyai dimensi k, berarti C dapat dibangun oleh k buah vektor yang bebas linear. Dengan demikian, jika satu basis dari C dipilih, maka ada korespondensi satu-satu antara ruang pesan (data) berdimensi-k dengan kode C. Suatu kode linear juga bisa dibangun oleh suatu matriks tertentu. Matriks yang digunakan untuk membangun kode linear ini dinamakan matriks generator. Definisi 2. Matriks generator G untuk kode linear C-(n,k) adalah suatu matriks berdimensi kxn yang mempunyai baris-baris berupa vektor basis dari C. Berdasarkan Definisi 2 tersebut, untuk pesan m dan matriks generator G, maka c = mG adalah katakode. Karena basis suatu ruang vektor yang berdimensi k adalah tidak tunggal, maka matriks generator G untuk kode linear C pun tidak tunggal. Tetapi satu matriks generator tertentu mungkin lebih berguna (menguntungkan) daripada matriks generator yang lain. Dalam hal matriks generator G mempunyai bentuk : G = [Ik A] (2) dengan Ik adalah matriks identitas berdimensi kxk dan A adalah matriks berdimensi kx(n-k), matriks G tersebut dikatakan dalam bentuk standard (standard form). Suatu matriks generator yang belum dalam bentuk standard dapat dibawa ke dalam bentuk standard dengan jalan melakukan sederetan operasi baris elementer. Definisi 3: Diketahui kode linear C-(n,k) pada Z2. Komplemen ortogonal (orthogonal complement) dari C, dinotasikan dengan C⊥, adalah C⊥ = {x ∈Vn(Z2) | x.y = 0 untuk semua y ∈ C}. Jika G = [Ik A] adalah matriks generator untuk C, maka H = [-AT In-k] adalah matriks generator untuk C⊥. Dalam operasi modulo 2 untuk matriks pada Z2 karena -A = A, maka matriks : (3) H = [-AT In-k] = [AT In-k] Dapat ditunjukkan bahwa GHT = 0 atau juga HGT = 0. Ini berarti bahwa baris-baris dari G dan H saling ortogonal. [Vansone dan Oorschot, 1989:56 ]. Dari uraian tersebut menunjukkan bahwa untuk vektor x ∈ Vn(Z2) adalah katakode dari kode linear C-(n,k) jika dan hanya jika HxT = 0, dengan H adalah matriks generator untuk C⊥. Definisi 4: Diketahui kode linear C-(n,k) pada Z2. Jika H adalah matriks generator untuk C⊥, maka H dikatakan matriks paritas (parity-check matrix) untuk C. Definisi 4 tersebut memberikan arti juga bahwa jika G dan H berturut-turut adalah matriks generator untuk C dan C⊥, maka H dan G berturut-turut adalah matriks paritas untuk C dan C⊥. Secara khusus, jika G = [Ik A] adalah matriks generator untuk C, maka H = [AT In-k] adalah matriks paritas untuk C dan matriks generator untuk C⊥. Dengan demikian suatu kode linear C bisa dispesifikasikan berdasarkan matriks generator G atau matriks paritas H. Andaikan kode c = mG, dengan c ∈ C-(n,k) dikirimkan melalui saluran transmisi. Karena saluran transmisi bersifat tidak aman, maka kode c tersebut diterima sebagai r. Oleh karena itu, supaya penerima pesan dapat menerima kode c sesuai kode yang dikirimkan, maka penerima pesan
3
perlu melakukan koreksi terhadap kode. Metode untuk melakukan koreksi terhadap kode c tersebut dengan jalan menambahkan vektor kesalahan (error vector) e. r=c+e (4) atau c = r – e. [Mcwilliams dan Sloane, 1993; Vanstone dan Oorschot, 1989]. D. Matriks Invers Tergenaralisasi Pembahasan matriks invers tergeneralisasi (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 : AA+A = A (5) [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 A- A A- = A(6) [Wu dan Dawson, 1998:321]. Matriks A berdimensi mxn yang mempunyai rank r dapat dibawa ke bentuk :
⎡I r ⎣O
O⎤ ⎡I r , atau A = P-1 ⎢ ⎥ O⎦ ⎣O
PAQ = ⎢
O ⎤ -1 Q O ⎥⎦
(7)
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 (7) adalah :
⎡I r ⎣V
A+ = Q ⎢
U⎤ P W ⎥⎦
(8)
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). [Murtiyasa, 2001: 3] 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 ⎢
(9)
dengan X dan Y memenuhi hubungan : (10) X2 = X dan YX = Y Dapat ditunjukkan bahwa matriks Y(n-m,m) sedemikian hingga kolom ke-i semuanya nol jika elemen diagonal ke-i dari matriks X(m,m) adalah 0, pasangan matriks X dan Y ini memenuhi persamaan (10) tersebut [Wu dan Dawson, 1998 : 322]. E. Disain Kriptosistem 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. Andaikan S adalah matriks invertibel berdimensi kxk, serta G’ = SG. Diketahui juga plaintext m adalah vektor biner dengan panjang k. Selanjutnya dipilih bentuk kesalahan (sebagai proses koreksi kesalahan katakode) : E = e(H-)T (11) di mana e adalah vektor biner random dengan panjang n-k; maka chipertext dari kode C-(n,k) tersebut adalah: c = mG’ ⊕ e(H-)T (12)
4
Proses dekripsi untuk memperoleh kembali plaintext m dari chipertext c, dapat dilakukan sebagai berikut : (i)hitung c(H- H)T = mSGHT(H-)T ⊕ e(H-)T (H)T (H-)T = e(H-)T = E (ii) hitung mG’ = c ⊕ E = y (iii) hitung m0 sedemikian hingga m0G = y (iv) m = m0 S-1 Berdasarkan uraian tersebut dapat disimpulkan bahwa proses enkripsi intinya terletak pada proses koreksi kesalahan kode mG’ yang akan ditransmisikan dengan menambahkan bentuk kesalahan E = e(H-)T yang berupa produk dari sembarang vektor biner e dengan transpose MRIT dari matriks paritas H. Karena m berupa pesan yang akan dikirimkan dan e adalah vektor biner random, maka proses enkripsi untuk mendapatkan chipertext c = mG’ ⊕ e(H-)T ini sangat tergantung pada matriks G’ dan MRIT dari H, yaitu H-. Jadi dalam hal ini matriks G’ dan H- bersifat publik. Sedangkan proses dekripsinya dimulai dengan menghitung produk dari chipertext c yang diterima dengan tranpose dari produk matriks paritas H dan MRIT-nya, yaitu H-H, untuk memperoleh bentuk kesalahan E. Jadi c(H-H)T = E. Jika E diperoleh, maka didapatkan katakode : mG’ = c ⊕ E mG’ = c ⊕ c(H-H)T mG’ = c (In ⊕ (H-H)T) = y mSG = y cari m0 dari m0G = y m = m0 S-1 Jadi dalam hal ini R=H-H, G, dan S bersifat rahasia (private), yang berfungsi menemukan bentuk kesalahan E dan pesan m kembali. Uraian di atas dapat dirangkum sebagaimana ditunjukkan dalam Tabel 2 di bawah. Tabel 2. Sistem Enkripsi-Dekripsi Publik G’, HRahasia R, G, S Enkripsi c = mG’ ⊕ e(H-)T Dekripsi (1) y = c(In⊕ RT) (2) dapatkan m0 dari m0G = y (3) m = m0 S-1 Prosedur Pembentukan Kunci Untuk kode C-(n,k), prosedur untuk membangun matriks kunci G, S, G’, H, dan H- dapat dijelaskan sebagai berikut : (1) Pilih matriks generator G = [Ik A]; dengan sembarang A(k, n-k). (2) Pilih sembarang matriks invertibel S(k,k). (3) G’ = SG (4) H = [AT In-k]. (5) Bawa H ke bentuk H = [In-k 0]Q, dengan 0(n-k, k) matriks nol dan Q(n, n) matriks nonsingular. (6) Pilih matriks X(n-k, n-k) dan Y(k, n-k) yang memenuhi persamaan (10)
⎡X ⎤ ⎥. ⎣Y ⎦
(7) MRIT dari H adalah H- = Q-1 ⎢
(8) R = H- H Selanjutnya G’ dan H- dipublikasikan sebagai kunci publik untuk enkripsi data oleh pengirim pesan, dan R, G, dan S disimpan sebagai privat key untuk mendekripsikan pesan yang diterima.
5
F. Penutup Dari simulasi dapat ditunjukkan bahwa disain tersebut telah dapat bekerja dengan benar. Ini menunjukkan bahwa teori matriks dan koding linear dapat dijadikan dasar untuk mengembangkan konsep kriptosistem kunci publik. Untuk itu, kajian lanjutan tentang penggunaan teori koding dan teori matriks di bidang kriptografi masih terbuka lebar. Penelitian lanjutan yang dapat disarankan dari tulisan ini adalah tentang analisis keamanan (security analysis) dari disain kriptosistem tersebut, sebab salah satu tujuan utama dari kriptosistem adalah keamanan data yang akan ditransmisikan. Dari hasil analisis keamanan akan dapat diketahui apakah disain tersebut layak untuk melakukan enkripsi data atau tidak. Penelitian lain yang juga dapat dikembangkan adalah model persetujuan kunci (key-agreement) antara pengirim dan penerima pesan atau data. G. Daftar Pustaka Canteaut, A., and Sendrier, N., 1998, ‘’Cryptanalysis of the original McEliece cryptosystem’’, dalam Advances in Cryptology-ASIACRYPT’98, Springer-Verlag, Pp : 187-199. Lee, N.Y., 1999, “Security of Shao’s Signature Schemes Based on Factoring and Discrete Logarithms” dalam IEE Proceedings Computer Digit. Tech. Vol. 146 No. 2, March 1999, Pp : 119 – 124. Loidreau, P., and Sendrier, N., 1998, “Some Weak keys in McEliece public-key cryptosystem”, dalam IEE International Symposium on Information Theory, ISIT’98, p. 382. MacWilliams, F.J., and Sloane, N.J.A., 1993, The Theory of Error Correcting Codes, Eight Impression, Amsterdam : North-Holland Mathematical Library. Murtiyasa, B., 2001, ‘Aplikasi Matriks Invers Tergeneralisasi pada Kriptografi’, Makalah pada Seminar Nasional dan Konferda Matematika VII Wil Jateng & DIY di FMIPA UII Yogyakarta tanggal 3 Februari 2001. Patterson, W., 1987, Mathematical Cryptology for Computer Scientists and Mathematicians, Totowa New Jersey : Rowman & Littlefield. Shao, Z., 1998, “Signature Schemes Based on Factoring and Descrete Logarithms” dalam IEE Proceedings Computer Digit. Tech. Vol. 145 No. 1, January 1998, Pp : 33 – 36. Simmons, G.J.(ed.), 1993, Contemporary Cryptology : The Science of Information Integrity, New York : IEEE Press. Stalling, W., 1995, Network and Internetwork Security Principles and Practice, New Jersey : Prentice Hall. Stinson, D.R., 1995, Cryptography Theory and Practice, Florida : CRC Press LLC. Tanembaun, A.S., 1997, Jaringan Komputer. Edisi Bahasa Indonesia. Jilid 2, Jakarta : Prenhallindo. Vanstone, S.A., and Oorscot, V.P.C., 1989, An Introduction to Error Correcting Code with Applications, Kluwer Academic Publisher. Wu, C.K., and Dawson, E., 1998, “Generalised Inverses in Public Key Cryptosystem Design” dalam IEE Proceedings Computer Digit. Tech. Vol. 145 No. 5, September 1998, Pp : 321-326.
6
