Pendahuluan
Dalam bidang kriptografi, telah banyak cabang matematika yang digunakan yaitu teori aljabar, teori bilangan, dan teori koding. Shao (1998) telah mengembangkan konsep kunci publik berdasarkan faktorisasi dan logaritma diskrit. Jenis kunci publik yang lain adalah RSA yang menggunakan teori bilangan, ElGamal menggunakan logaritma diskrit, Elliptic Curve System yang dikembangkan berdasarkan teori grup, The Merkle-Ellman Knapsack System yang berdasar pada subset sum, dan McEliece public key system yang menggunakan teori koding (Stinson, 1995; Patterson, 1987).
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; Rao dan Mitra, 1971). MIT juga dibatasi pada lapangan terhingga (finite field) Z2. Wu dan Dawson menawarkan desain kunci publik yang menggunakan MIT. Ide dasar pengembangan kunci publik tersebut menggunakan koreksi kesalahan kode dengan teknik MIT. Dari desain telah dapat ditunjukkan bahwa MIT dapat digunakan untuk melakukan enkripsi dan dekripsi data, serta mampu menjamin kerahasiaan data.
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 matriks A yang berdimensi kxn, jika berlaku ABA = A. Jika A+ menyatakan MIT dari A, maka:
AA+A = A [1]
(Israel dan Greville, 1974; Rao dan Mitra, 1971).
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- [2]
( Wu dan Dawson, 1998 ).
Matriks A berdimensi mxn yang mempunyai rank r dapat dibawa ke bentuk:
PAQ = [■(Ip&0@0&0)], atau
A = P-1 [■(Ip&0@0&0)]Q-1 [3]
Dengan P adalah matriks nonsingular hasil penggandaaan 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:
A+ = Q [■(Ip&U@V&W)] P [4]
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 adalah 2r(n-r)+n(m-r).
Menurut Wu dan Dawson (1998) untuk matriks A berdimensi mxn dan A = [Im 0] dengan rank (A) = m, MRIT dari A adalah:
A- = [█(X@Y)] [5]
Untuk suatu matriks X(m,m) dan Y(n-m, m) tertentu. Dalam hal ini X dan Y adalah suatu matriks sedemikian hingga:
X2 = X dan YX = Y [6]
Dapat ditunjukkan bahwa untuk suatu matriks X adalah matriks diagonal yang sekurang-kurangnya ada satu entri diagonal yang tidak nol sedangkan matriks Y adalah matriks yang entri pada kolom ke-i semuanya nol jika entri diagonal ke-i dari X adalah nol, pasangan X dan Y tersebut memenuhi [6].
Secara umum untuk matriks A(m,n) yang mempunyai rank m, bahwa 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:
A- = Q-1 [█(X@Y)] [7]
Dengan X dan Y memenuhi [6].
Dalam bidang kriptografi, telah banyak cabang matematika yang digunakan yaitu teori aljabar, teori bilangan, dan teori koding. Shao (1998) telah mengembangkan konsep kunci publik berdasarkan faktorisasi dan logaritma diskrit. Jenis kunci publik yang lain adalah RSA yang menggunakan teori bilangan, ElGamal menggunakan logaritma diskrit, Elliptic Curve System yang dikembangkan berdasarkan teori grup, The Merkle-Ellman Knapsack System yang berdasar pada subset sum, dan McEliece public key system yang menggunakan teori koding (Stinson, 1995; Patterson, 1987).
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; Rao dan Mitra, 1971). MIT juga dibatasi pada lapangan terhingga (finite field) Z2. Wu dan Dawson menawarkan desain kunci publik yang menggunakan MIT. Ide dasar pengembangan kunci publik tersebut menggunakan koreksi kesalahan kode dengan teknik MIT. Dari desain telah dapat ditunjukkan bahwa MIT dapat digunakan untuk melakukan enkripsi dan dekripsi data, serta mampu menjamin kerahasiaan data.
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 matriks A yang berdimensi kxn, jika berlaku ABA = A. Jika A+ menyatakan MIT dari A, maka:
AA+A = A [1]
(Israel dan Greville, 1974; Rao dan Mitra, 1971).
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- [2]
( Wu dan Dawson, 1998 ).
Matriks A berdimensi mxn yang mempunyai rank r dapat dibawa ke bentuk:
PAQ = [■(Ip&0@0&0)], atau
A = P-1 [■(Ip&0@0&0)]Q-1 [3]
Dengan P adalah matriks nonsingular hasil penggandaaan 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:
A+ = Q [■(Ip&U@V&W)] P [4]
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 adalah 2r(n-r)+n(m-r).
Menurut Wu dan Dawson (1998) untuk matriks A berdimensi mxn dan A = [Im 0] dengan rank (A) = m, MRIT dari A adalah:
A- = [█(X@Y)] [5]
Untuk suatu matriks X(m,m) dan Y(n-m, m) tertentu. Dalam hal ini X dan Y adalah suatu matriks sedemikian hingga:
X2 = X dan YX = Y [6]
Dapat ditunjukkan bahwa untuk suatu matriks X adalah matriks diagonal yang sekurang-kurangnya ada satu entri diagonal yang tidak nol sedangkan matriks Y adalah matriks yang entri pada kolom ke-i semuanya nol jika entri diagonal ke-i dari X adalah nol, pasangan X dan Y tersebut memenuhi [6].
Secara umum untuk matriks A(m,n) yang mempunyai rank m, bahwa 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:
A- = Q-1 [█(X@Y)] [7]
Dengan X dan Y memenuhi [6].
0 komentar:
Posting Komentar