Prosiding SNM 2014 Topik penelitian, hal. xx-xx.
Pemanfaatan Nonnegative Matrix Factorization pada Kriptografi untuk Mengamankan Data Gambar INDRA BAYU MUKTYAS1
1Program Studi Pendidikan Matematika, STKIP Surya, Tangerang, Banten,
[email protected]
Abstrak. Di dunia yang serba canggih sekarang ini, terutama di perkotaan, keamanan data sangatlah penting. Hal ini bisa dilakukan dengan kriptografi. Ada berbagai macam teknik dalam kriptografi, salah satunya adalah Hill cipher. Dalam makalah ini diajukan sebuah cara pengenkripsian data berupa gambar dengan memodifikasi Hill cipher. Ada dua cara pemilihan kunci, yaitu dengan kunci acak dan dengan autokey menggunakan Nonnegative Matrix Factorization (NMF). Pengenkripsian tersebut akan diimplementasikan pada data 100 foto mahasiswa STKIP Surya yang dipilih secara acak. Kata kunci : Kriptografi, Hill cipher, Autokey Nonnegative Matrix Factorization.
1.
Pendahuluan
Pengiriman data dari satu tempat ke tempat lain sudah tidak perlu lagi dengan biaya mahal dan waktu yang lama. Ini karena adanya internet. Akan tetapi keamanan data menjadi kebutuhan yang pokok di zaman yang serba canggih sekarang ini. Salah satu cara mengamankan data adalah dengan kriptografi. Data tersebut dienkripsi dengan sebuah kunci rahasia. Kemudian data enkripsi tersebut dikirimkan kepada pihak penerima (misalkan melalui email). Pihak penerima baru akan bisa membaca data tersebut jika sudah mendapatkan kunci dekripsi data dari pihak pengirim. Dalam makalah ini akan dikaji mengenai kriptografi klasik Hill cipher yang selanjutnya dikembangkan untuk data gambar. Ada dua cara pemilihan kunci yang digunakan. Pertama dengan kunci acak dan yang ke dua dengan kunci otomatis yang diperoleh dari Nonnegative Matrix Factorization (NMF).
1
2
Indra Bayu Muktyas
2.
Metode
A. Hill cipher Salah satu kriptografi simetris yang sudah tidak asing lagi adalah Hill cipher. Seorang asisten profesor matematika di Hunter College bernama Lester Hill menemukan cara untuk mengenkripsi plainteks berupa huruf. Ia membagi pesan plainteks menjadi blok-blok. Kemudian setiap blok tersebut dienkripsi dengan menggunakan sistem persamaan linier dengan variabel. Karena plainteksnya berupa huruf, maka disyaratkan perulangan modulo 26. Untuk dibentuk persamaan ( ) ( ) dengan ( ) [1]. Contoh: ( ) ( ) Plainteksnya DI BAWAH POT. Maka dipecah menjadi blok dua-dua, yaitu DI BA WA HP OT. Jika didefinisikan A=0 maka DI menjadi 3 8. Ilustrasi proses enkripsi dalam bentuk matriks adalah seperti ini. (
)(
)
(
)
Jika dikembalikan ke bentuk semula diperoleh cipherteks TBBBWWLAAT. B. Modifikasi Hill cipher Dalam makalah ini Hill cipher dimodifikasi untuk data gambar. Setiap piksel gambar mempunyai nilai warna RGB antara 0 sampai 255. Sehingga modulo yang dipakai bukan 26, akan tetapi 256. Diperlukan sebuah kunci berupa matriks persegi. Agar bisa didekripsi kembali, matriks kunci ini dipilih dengan syarat determinannya tidak nol dan relatif prima terhadap 256. Dipunyai matriks plainteks . Dipilih kunci dengan habis membagi . Diperoleh Matriks cipherteks . Untuk membalikkannya lagi cukup mudah, yaitu dengan mengalikan invers kuncinya dengan matriks cipherteks, dengan adalah invers modulo 256 dari .
Algoritma 1. Enkripsi data gambar dengan modifikasi Hill cipher. 1. 2.
Baca tiap gambar menjadi kolom dari matriks Plainteks Definisikan sebuah kunci dengan . ( ) ( ( ) ) syarat: dan .
3.
Ubah ukuran plainteks menjadi
.
.
. 4.
Cipherteks diperoleh dengan mengalikan matriks kunci dengan plainteks yang sudah diubah ukurannya. .
P em a n fa a t an NM F p ad a Kri p t ogra fi u n tu k M en ga m an ka n Da t a Ga m b a r
5.
Ubah ukuran Cipherteks menjadi seperti semula. .
6.
Simpan tiap kolom matriks
3
menjadi fotocipher.
Ilustrasinya seperti ini.
Gambar 2.1. Ilustrasi Proses Enkripsi gambar Sedangkan untuk proses dekripsinya, diperlukan matriks invers dari Kunci. Ini dapat diperoleh dengan menggunakan algoritma 4. Algoritma dekripsi secara lengkap sebagai berikut. Algoritma 2. Proses dekripsi data gambar dengan modifikasi Hill cipher. 1. 2. 3. 4. 5. 6.
Untuk i=1:maxfotocipher Ubah fotocipher(i) menjadi matriks kolom. Cipherteks(:,i)=fotocipher(i). Selesai. Baca matriks invers kunci sebagai Ubah ukuran Cipherteks menjadi
7. 8. 9.
Decipher = invKunci*Cipherteks_Ubah Plainteks = Reshape matriks Decipher menjadi Simpan tiap kolom dari matriks Plainteks plainteks.
. . menjadi
foto
4
Indra Bayu Muktyas
C. Nonnegative Matrix Factorization Salah satu pemfaktoran matriks yang sedang berkembang saat ini adalah Nonnegative Matrix Factorization (NMF). NMF sangat cocok digunakan pada gambar karena NMF memfaktorkan matriks taknegatif menjadi matriks-matriks taknegatif juga. Warna tiap piksel matriks juga taknegatif, berkisar dari 0 sampai 255. Matriks difaktorkan menjadi dengan . . Biasanya dipilih kurang dari dan . [2] Ada banyak algoritma dalam NMF, salah satunya adalah Multiplicative Update Rule. Berikut ini algoritma yang dimaksud. [2] Algoritma 3. Multiplicative Update Rule NMF 1. 2. 3. 4. 5. 6.
W = rand(m,r), dengan H = rand(r,n), dengan Untuk i = 1:MaksIter lakukan T T H = H .* (V V) ./ (W WH) T T W = W .* (VH ) ./ (WHH ) Selesai.
Matriks berisi basis dari matriks sedangkan H sebagai matriks bobotnya.[2] Karena adalah basis, maka setiap kolom saling bebas linier dengan kolom lainnya. Matriks ini yang akan diproses menjadi kunci enkripsi. Setiap kali algoritma tersebut dijalankan akan dihasilkan pemfaktoran matriks dan yang berbeda, tergantung nilai acak awal dari dan . Ini merupakan salah satu kekuatan rahasia dari kunci autokey NMF. D. Pemilihan Kunci Ada dua cara pemilihan kunci pada makalah ini, yaitu kunci acak dan autokey NMF. 1. Kunci Acak Pertama-tama dipilih sebuah kunci acak berupa matriks persegi yang ukurannya bisa membagi ukuran matriks plainteks. Pemilihan matriks acak ini tidak sembarang. Determinan matriks kunci ini selain tidak nol, juga harus relatif prima terhadap 256. Ini agar bisa diperoleh invers matriksnya. Teorema 2.1. Dipunyai yang elemen-elemennya di . modulo jika dan hanya jika ( ) mempunyai invers di invers modulo adalah ( dengan
adalah invers dari
( ) atas . [3]
) (
( )
mempunyai invers . Lebih jauh lagi,
)
P em a n fa a t an NM F p ad a Kri p t ogra fi u n tu k M en ga m an ka n Da t a Ga m b a r
Bukti: Ambil sembarang matriks Dipunyai
5
.
.
Jelas
(
)
Ini berarti ( ) Sehingga det(A) invertibel di Jelas
( )
(
)
.
( )
Diperoleh ( ) ( ) ( )
( ) ( ) ( )
( )
( )
Algoritma 4. Pemilihan kunci acak dan menentukan invers modulo 256 1. 2. 3. 4.
Lakukan Definisikan matriks acak ( ) Hitung ( ) Sampai . //Jika relatif prima terhadap 256, maka matriks mempunyai //invers,lanjutkan ke langkah berikutnya. Jika tidak, keluar //program, matriks tidak mempunyai invers. 5. Hitung invers dari modulo 256, tulis sebagai variabel . //bisa dengan brute force atau extended FPB. 6. Diperoleh .
Setelah diperoleh kunci acak dengan algoritma 1.
, selanjutnya dilakukan proses enkripsi
2. Autokey NMF Berbeda dari sub bab sebelumnya, pada sub bab ini akan dipilih sebuah kunci otomatis dari Plainteks gabungan dengan menggunakan NMF. NMF akan memfaktorkan matriks Plainteks tersebut menjadi dan dengan ( ). W adalah basis dari Plainteks. Karena W adalah basis, maka setiap
6
Indra Bayu Muktyas
kolomnya bebas linier. Definisikan kuncinya . Teorema 6.4.3. pada ( ) Anton Rorres menunjukkan bahwa K invertible, artinya .[6] Jika det(K) tidak relatif prima terhadap 256, maka dilakukan operasi baris elementer pada matriks K dengan mengalikan salah satu baris matriks K dengan invers dari FPB(det(K), 256). Tentunya perkalian ini dalam modulo 256. Berikut ini adalah algoritma autokey NMF. Algoritma 5. Autokey NMF 1. Faktorkan matriks Plainteks menjadi dengan algoritma 3. // pilih sedemikian hingga . 2. ( ( ) ) 3. Lakukan sampai 4. Ubah elemen diagonalnya dengan sembarang bilangan modulo 256 5. selesai 6. Diperoleh matriks K baru yang invertibel
=
W
H
= K
𝑊𝑇 𝑊
Gambar 2.2. Proses enkripsi Autokey NMF Setelah diperoleh kunci K, kemudian dilakukan proses enkripsi dengan algoritma 1.
P em a n fa a t an NM F p ad a Kri p t ogra fi u n tu k M en ga m an ka n Da t a Ga m b a r
7
3. Hasil – Hasil Utama 1. Dataset Dataset yang digunakan adalah kumpulan 100 foto closeup mahasiswa STKIP Surya. Setiap foto berukuran 110 x 140 piksel.
Gambar 3.1. Dataset 100 foto mahasiswa 2. Software Software yang digunakan adalah Scilab 5.4.1 dengan tambahan plugin Atoms: IPD_8.3.1-1.bin.windows.zip dan SIVP_0.5.3.12.bin.windows.zip. 3. Hardware Spesifikasi hardware yang digunakan pada percobaan ini adalah Laptop Asus A42F, Processor Intel(R) Pentium(R) Dual-core P6200 @ 2.13 GHz 2.13 GHz, RAM 2 GB, dan OS Windows 8 Pro. 4. Preprosesing Setiap foto mahasiswa STKIP Surya diubah menjadi matriks keabuabuan. Setiap elemen matriks tersebut bernilai antara 0 sampai 255, ini merepresentasikan tingkat warna tiap piksel. Kemudian matriksmatriks ini diubah menjadi matriks kolom. Matriks inilah yang menjadi plainteks. 5. Implementasi 5.1. Kunci Acak Enkripsi
Kunci
Plainteks
Cipherteks
8
Indra Bayu Muktyas
Dekripsi
Invers Kunci
Cipherteks
Plainteks
5.2. Autokey NMF Menentukan kunci
W=Basis
Plainteks
Kunci
Enkripsi
Plainteks
Kunci
Cipherteks
Dekripsi
Invers Kunci
Kunci
Cipherteks
dipilih dengan
Plainteks
. Ini berkaitan dengan keterbatasan
P em a n fa a t an NM F p ad a Kri p t ogra fi u n tu k M en ga m an ka n Da t a Ga m b a r
9
memori yang Scilab sediakan untuk dijalankan. Ketika dicoba dengan nilai yang agak besar, perhitungan terhenti oleh karena memori yang kurang. Untuk kunci acak, proses pemilihannya lebih mudah, sedangkan untuk autokey NMF, awalnya diperoleh kunci yang determinannya belum relatif prima dengan 256. Untuk itu pada elemen diagonalnya diganti dengan bilangan acak sehingga terpenuhi. Terlihat untuk autokey NMF, kunci dan invers kuncinya berupa matriks simetri. Cipherteks untuk kedua metode di atas secara kasat mata tidak bisa dibaca. Secara analisis pun cipherteks ini sangat powerful jika kuncinya tidak diketahui. Untuk autokey NMF pun bisa terjaga kerahasiaannya karena setiap kali program dijalankan, pemfaktoran matriks dengan NMF akan menghasilkan matriks yang berbeda, tergantung dari pemberian nilai awal W dan H pada algoritma multiplication update rule. Sedangkan nilai awal kedua matriks tersebut adalah acak. Sehingga kalaupun ada orang yang ingin mencoba memfaktorkan cipherteks tersebut akan sangat sulit untuk dipecahkan. 4. Kesimpulan Modifikasi Hill cipher dan autokey NMF menghasilkan gambar cipherteks yang powerful. Sangat sulit untuk mengembalikan ke gambar aslinya jika tidak mengetahui kuncinya. Terlebih lagi sulitnya menentukan nilai yang dipakai oleh penyandi. Seperti halnya kriptografi simetris lainnya, kelemahan dari metode ini adalah jika ada satu saja orang yang mengetahui kuncinya dan menyebarluaskannya maka cipherteks akan terpecahkan dengan sangat mudah. Pernyataan terima kasih. Penulis mengucapkan banyak terima kasih untuk Edy Haryono, Endriyani , Abdul Azis Abdillah, Puguh Wahyu Prasetyo, dan Annisa Dini H atas motivasi dan bimbingannya. Semoga bermanfaat dan dapat dikembangkan lebih lanjut.
Referensi [1] Burton, David M., 2009, Elementary Number Theory, Seventh Edition, McGraw-Hill Higher. Education, McGraw-Hill Company, New York. [2] Lee, D. D. dan Seung, H. S., 2001, Algorithms for nonnegatvie matrix factorization. In T. G. Dietterich and V. Tresp, editors, Advances in Neural Information Processing Systems, volume 13. The MIT Press. [3] Grunschlag, Zeph, 2014, Classical Cryptography, www1.cs.columbia.edu/~zeph/4261/lectures/classical-ciphers.pdf, diakses pada 19 Januari 2014.
10
Indra Bayu Muktyas
[4] Wikipedia, 2014, Euclidean Algorithm, http://en.wikipedia.org/wiki/Euclidean_algorithm, diakses pada 20 Januari 2014. [5] Scott, Emily, 2013, Extended Euclidean Algorithm and Inverse Modulo Tutorial, https://www.youtube.com/watch?v=fz1vxq5ts5I, diakses pada 20 Januari 2014. [6] Anton, H., Rorres, C., 2005, Elementary Linear Algebra with Applications, Ninth Edition, John Wiley & Sons, Inc., New York.
