Laporkan Masalah

Desain Kriptosistem kunci publik dengan invers kiri/kanan

MURTIYASA, Budi, Promotor Prof.Drs. Subanar, Ph.D

2005 | Disertasi | S3 MIPA

Teori matriks telah menjadi alat bantu yang potensial dalam riset di bidang kriptografi. Terakhir diketahui Wu dan Dawson telah membuat desain kriptosistem kunci publik dengan teknik matriks invers tergeneralisasi. Penelitian dalam disertasi ini mengkaji pengembangan desain kriptosistem kunci publik dengan teknik matriks invers kiri/kanan pada lapangan Z2. Ide dasar pengembangan adalah serupa dengan kriptosistem kunci publik yang telah ada sebelumnya, yaitu kriptosistem McEliece dan kriptosistem Wu-Dawson, dalam hal ini adalah menggunakan teori koding. Suatu matriks A berdimensi mxn, jika m ≥ n dan A mempunyai rank n, maka A mempunyai invers kiri. Jika AL menyatakan invers kiri, AL A = In. Sebaliknya, untuk matriks A berdimensi mxn, jika m ≤ n dan A mempunyai rank m, maka A mempunyai invers kanan. Jika AR menyatakan invers kanan, A AR= Im. Dapat ditunjukkan bahwa matriks A mempunyai invers kanan jika dan hanya jika AT (transpose dari A) mempunyai invers kiri. Demikian pula sebaliknya, matriks A mempunyai invers kiri jika dan hanya jika AT mempunyai invers kanan. Karenanya, jika A mempunyai invers kanan, (AR)T adalah invers kiri dari AT. Sedangkan jika A mempunyai invers kiri, (AL)T adalah invers kanan dari AT. Ini berarti (AR)T = (AT)L dan (AL)T = (AT)R. Sembarang kode linear C(n,k) dapat dipandang sebagai ruang vektor bagian berdimensi k dari ruang vektor Vn(Z2). Matriks generator untuk kode C adalah matriks G berdimensi kxn yang mempunyai rank k. Untuk pesan m, c = mG adalah katakode. Dengan melakukan rekonstruksi terhadap matriks generator G, yaitu G = (PRS-1)T, ciphertext dari plaintext m dengan panjang k adalah c = mG. S adalah matrik permutasi berdimensi kxk, dan P adalah matriks berdimensi kxn dengan rank k. PR dan S-1berturut-turut adalah invers kanan dari P dan invers dari S. Karenanya, matriks G merupakan kunci publik untuk melakukan enkripsi terhadap pesan m. Proses dekripsi untuk mendapatkan kembali pesan m dapat dilakukan sebagai berikut. Hitung c(SP)T = mG(SP)T = m (PRS-1)T (SP)T = m(S-1)T (PR)T PTST = m. Jadi, R = SP merupakan kunci pribadi untuk mendekripsi ciphertext c. Kriptosistem ini cukup efisien dalam penggunaan ruang kunci, yaitu 2kn bit. Kompleksitas enkripsi dan dekripsi juga rendah, yaitu 4kn – k – n yang merupakan famili dari O(kn). Dari perbandingkan karakteristik kriptosistem, diketahui bahwa kriptosistem dengan invers kiri/kanan ini lebih efisien jika dibandingkan dengan kriptosistem McEliece dan kriptosistem Wu-Dawson. Dibandingkan dengan kriptosistem RSA, kriptosistem dengan invers kiri/kanan ini kurang efisien dalam penggunaan ruang kunci, tetapi lebih cepat dalam proses enkripsi dan dekripsi. Kelemahan dari Kriptosistem ini adalah mempunyai ekspansi pesan, dalam hal ini rasio ekspansi pesan adalah n/k. Analisis resiko dari kriptosistem didasarkan pada keamanan dari ciphertext c dari kemungkinan serangan para penyusup. Jika penyusup mengetahui kunci pribadi R, ciphertext c dapat dipatahkan. Dengan melakukan komputasi cRT = m, penyusup akan mendapatkan pesan m. Penyusup kemungkinan mencari kunci pribadi R dengan jalan : (1) mencari matriks-matriks yang membangun R, yaitu S dan P, (2) mencari invers kanan dari G, dan (3) mencoba sembarang matriks R. Dari analisis, dapat disimpulkan bahwa jika k dan n besar, dalam hal ini untuk nilai k dan n sedemikian hingga n – k ≥ 250 serta n » 2k, ciphertext c akan tetap aman dari gangguan penyusup. Di samping aplikasinya pada pengamanan data melalui enkripsi dan dekripsi, kriptosistem dengan invers kiri/kanan ini juga dapat diaplikasikan untuk tanda tangan digital. Dengan demikian kriptosistem ini dapat memberikan layanan kerahasiaan, autentikasi, dan nonrepudiasi. Hal ini berarti bahwa desain kriptosistem dengan invers kiri/kanan ini lebih baik jika dibandingkan dengan desain kriptosistem McEliece dan kriptosistem Wu-Dawson, sebab kedua kriptosistem tersebut tidak dapat diaplikasikan untuk tanda tangan digital. Jika dibandingkan dengan kriptosistem RSA yang juga dapat diaplikasikan untuk tanda tangan digital, desain kriptosistem dengan invers kiri/kanan ini lebih cepat dalam proses enkripsi/dekripsi untuk verifikasi pesan, tetapi kurang efisien untuk penggunaan ruang pesan, sebab memiliki ekspansi pesan.

The theory of matrices becomes a potential tool in cryptographic research during recent years. Wu and Dawson have recently proposed a public key cryptosystem design based on generalized inverses of` matrices. The research addresses to develop a public key cryptosystem based on left / right inverse of matrices in the field Z2 . The idea is similar to the previous public key cryptosystem, that is McElice’s public key and Wu-Dawson’s public key, in term of the usage of a coding theory. A mxn matrix A, if m ≥ n and A has rank n, A has a left inverse. If AL denotes a left inverse, AL A = Im. Conversely, a mxn matrix A, if m ≤ n and A has rank m, A has a right inverse. If AR denotes a right inverse, A AR = Im. It can be shown that A has a right inverse if and only if AT (transpose of A) has a left inverse. Conversely, a matrix A has a left inverse if and only if AT has a right inverse. Therefore, if A has a right inverse, (AR)T is left inverse of AT. Meanwhile, if A has a left inverse, (AL)T is a right inverse of AT. This means (AR)T = (AT)L and (AL)T = (AT)R. An arbitrary linear code C(n,k) can be treated as a k-dimensional vector subspace of Vn(Z2). A generator matrix for C is a kxn matrix G that has rank k. For message m, c = mG is codeword. By reconstruction of generator matrix G, that is G = (PR S-1)T, the ciphertext of plaintext m with length k is c = mG. S is a kxk permutation matrix, and P is a kxn matrix with rank k. PR and S-1 are right inverse of P and inverse of S respectively. Matrix G is public to encrypt message m. The decryption to obtain message m can be performed as follows. Compute c(SP)T = mG(SP)T = m (PR S-1)T (SP)T = m (S-1)T (PR)T PT ST = m. So, R = SP is private key to decrypt ciphertext c. The cryptosystem is efficient enough in key space, i.e. 2kn bits. A complexity of encryp tion and decryption is very low, i.e. 4kn – k – n which constitutes the order of O(kn). From the analysis, the cryptosystem is more efficient than McEliece’s cryptosystem and Wu-Dawson’s cryptosystem. Compared with RSA cryptosystem, the cryptosystem is faster in encryption and decryption process than RSA cryptosystem, but the cryptosystem is less efficient in using key space than RSA cryptosystem. The disadvantage is that the cryptosystem has a message expansion, in this case ratio of message expansion is n/k. The risk analysis of the cryptosystem is based on security of ciphertext c, which is possibly attacked by the intruder. If the intruder has known a private key xxiii R, the ciphertext c can be broken. By computation m = cRT, the intruder will obtain message m. The intruder will perhaps find out the private key R by : (1) find a matrix that generates R, i.e. S and P, (2) find a right inverse of G, and (3) try an arbitrary matrix R. From the analysis, it can be concluded that if k and n are large, its suggested n – k ≥ 250 and n ≈ 2k, the ciphertext c is still secure from the intruder. The cryptosystem is also applicable in digital signature scheme. So, the cryptosystem is better than McEliece’s cryptosystem and Wu-Dawson’s cryptosystem, because those cryptosystem are not applicable for digital signature scheme. This means that the cryptosystem by left/right inverse provides confidentiality, authenticity, and non repudiation services. Compared with digital signature scheme by RSA cryptosystem, the digital signature scheme of the cryptosystem by left/right inverse is faster in encryption/decryption process and message verification than the digital signature scheme of RSA cryptosystem. Conversely, the digital signature of RSA cryptosystem is more efficient in us ing of message space than the digital signature scheme by cryptosystem based left/right inverse.

Kata Kunci : Ilmu Matematika,Kriptosistem,Invers Kiri/Kanan, left inverse, right inverse, public key cryptosystem


    Tidak tersedia file untuk ditampilkan ke publik.