Teknik secret sharing yang efektif pada berkas yang terkompresi dengan menggunakan Algoritma Huffman 1)
Ibnul Qoyyim 1) Jurusan Teknik Informatika ITB, Bandung, email:
[email protected]
Abstract – Makalah ini membahas tentang secret sharing yang efektif pada berkas yang dikompresi dengan algoritma huffman.
kurang dari k memberi informasi signifikan terhadap rahasia [5], namun pada masalah Huffman asalkan header Huffman aman, body berkas Huffman dapat menggunakan naive secret sharing karena informasi body tanpa header Huffman tidak memiliki makna yang berarti.
Kata Kunci: secret sharing, Huffman hoding. 3. HASIL DAN PEMBAHASAN 1. PENDAHULUAN Secret sharing adalah metode untuk mendistribusikan rahasia kepada sebuah grup partisipan yang berjumlah n, setiap partisipan diberikan share dari rahasia, rahasia hanya dapat disusun jika k share digabungkan dengan k <= n, setiap share atau gabungan share yang berjumlah kurang dari k tidak berguna untuk mengetahui rahasia. [2]. Rahasia yang dibagi adalah berkas yang dimampatkan menggunakan Huffman. Huffman adalah cara memampatkan data dengan mengkodekan setiap karakter dalam data dengan kode yang lebih pendek. Untuk meminimumkan jumlah bit yang dibutuhkan, panjang kode untuk setiap karakter sedapat mungkin diperpendek, terutama untuk karakter yang kekerapannya (frequency) kemunculannya besar[1]. 2. DASAR TEORI Secret sharing pada berkas yang dikompresi menggunakan Huffman dapat dibuat lebih efektif dibanding berkas umum karena untuk menirmampatkan berkas diperlukan pohon Huffman atau tabel Huffman sehingga pohon atau tabel Huffman dapat dianalogikan sebagai kunci untuk membuka berkas Huffman. Shamir secret sharing cukup baik digunakan untuk menshare data umum, namun kurang efektif secara ukuran karena ukuran share sama dengan atau lebih besar dari ukuran rahasia sehingga keseluruhan share yang diperlukan memiliki ukuran sekitar k kali ukuran sumber, selain itu shamir secret sharing tidak bisa memanfaatkan sifat dari data khusus seperti graf, pohon dsb. Oleh karena itu penulis berusaha mencari skema secret sharing yang efektif digunakan pada header berkas Huffman agar ukuran share dapat seminimal mungkin. Naive secret sharing secara ukuran cukup baik namun kurang aman untuk digunakan untuk menshare data umum karena share yang terkumpul meskipun
Representasi header Huffman bisa berupa Huffman table atau Huffman tree oleh karena itu metode secret sharing yang dapat digunakan pada header Huffman dapat bermacam macam. misal mengencode dengan cara biasa kemudian byte-byte header disecret sharing menggunakan Shamir secret sharing, atau merepresentasikan Huffman tree (graf) sebagai matriks kemudian melakukan secret sharing khusus matriks atau menggunakan variasi dari prinsip visual kriptografi dimana pixel-pixel digantikan oleh bit-bit. Variasi dari prinsip visual kriptografi pada matriks Huffman sebuah elemen matriks dengan value [0,1] dibagi menjadi beberapa sub elemen dengan masing masing sub elemen memiliki value [0,1] untuk mengetahui apakah value sebenarnya dari element tersebut didapatkan dengan mengoperasikan sub elemen setiap matriks dengan operasi OR, Hamming Weight dari elemen matriks tsb adalah ∑ hasil operasi OR sub elemen yang bernilai 1 kemudian membandingkannnya dengan tabel berikut : Value 0 1
H(V) H(V) ≥ d H(V) < d - αm
Dengan : H(V) : Hamming Weight = ∑ subelemen hasil operasi OR subelemen dari tiap share d : ambang batas (1 ≤ d ≤ m) α : kontras m : jumlah subelemen modifikasi pada visual kriptografi adalah perubahan sub pixel menjadi bit bit pada matriks. Untuk enkripsi mula-mula buat Huffman tree kemudian representasikan graf tersebut menjadi matriks. untuk pembagiannya sama dengan visual kriptografi biasa yaitu membuat dua buah koleksi matriks boolean berukuran n x m, C0 dan C1. Untuk membagi elemen 0 pada matriks, dipilih salah satu dari matriks pada C0, sedangkan untuk membagi
elemen 1, dipilih salah satu matriks dari C1. Matriks yang terpilih merupakan representasi dari m subpixel pada masing-masing n lembar transparan. Solusi dianggap valid jika seluruh kondisi berikut terpenuhi: 1. Untuk sembarang matriks M pada C0, hasil operasi OR dengan V dengan sembarang baris k dari n memenuhi H(V) < d - am. 2. Untuk sembarang matriks M pada C1, hasil operasi OR dengan V dengan sembarang baris k dari n memenuhi H(V) = d. 3. Untuk sembarang j < k baris yang dipilih, submatriksnya muncul dengan frekuensi yang sama pada C0 dan C1. Sementara untuk dekripsinya mula-mula untuk setiap sub elemen pada suatu share OR-kan dengan sub elemen pada share yang lain, matriks hasil dari operasi OR tersebut ditentukan H(V) setiap elemennya yaitu ∑ subelemen dalam satu elemen. Kemudian ditentukan apakah elemen tersebut bernilai 1 atau 0 dari tabel H(V) diatas matriks hasilnya ditransformasi menjadi huffman tree yang akan digunakan untuk men decode body. seperti yang dijelaskan diawal secret sharing pada body dapat menggunakan naive secret sharing namun harus dicari cara agar skema k to n dapat terlaksana yaitu untuk mendapatkan keseluruhan rahasia cukup dengan mengumpulkan k share dari n share yang dibuat, oleh karena itu naive secret sharing yang dipakai memiliki redundansi, Untuk mendapatkan skema pembagian naive secret sharing per sharenya dapat diperoleh beberapa cara: 1. Brute Force Pendekatan secara brute force diperoleh dengan cara mengkombinasikan m bagian body kepada n share dan mengecek apakah semua kemungkinan k share dapat membentuk keseluruhan rahasia.
} } } while test = false
Dari algoritma diatas dapat dilihat bahwa bottle neck terdapat pada bagian test sehingga kompleksitas algoritma dalam notasi O adalah O ( nk ). 2.
Pencarian skema yang lebih baik 2.1. Skema yang pasti Skema dibawah ini pasti dan karenanya dipakai basis jika terdapat algoritma yang rekursif k = 1 maka seluruh share memiliki elemen yang sama, misal :
Untuk k = 1, n = 3 masing masing share adalah : a a a k = n maka tidak ada rendundansi seluruh share memiliki elemen yang berbeda-beda, misal: Untuk k = 2, n = 2 masing masing share adalah : a b
2.2. Skema lainnya Untuk skema naïve lainnya digunakan percobaan sebagai berikut untuk mendapatkan algoritma: Dari hasil hipotesis : Untuk k = 2, n = 3 masing masing share adalah :
Algoritma secara garis besar:
ab
do {
bc for i = 1 to n { share[ i ] = kombinasi_m_bagian(); }
ac Sementara untuk k = 3, n = 4 masing masing share adalah : abd bce
for a = 1 to n { for b = 1 to n {
acf def
… hingga kedalaman k… test is_complete(share[ a share[ k ])
= ],
test share[ b
and ] …
Dari hasil diatas dapat disimpulkan bahwa untuk setiap skema k to n yang terdefinisi dapat dibuat skema k+1 to n+1 turunannya dengan cara : Buat skema untuk k+1 to n elemen Untuk setiap share asal ditambah share baru yang
berbeda satu dengan lain Buat suatu share yang merupakan gabungan share share yang ditambahkan pada share asal Dari hasil hipotesis : Untuk k = 2, n = 3 masing masing share adalah :
abd bcd acd abc
ab
Dari hasil diatas dapat disimpulkan bahwa untuk setiap skema k to n yang terdefinisi dapat dibuat skema k to n+1 turunannya dengan cara : Buat suatu share baru yang merupakan union seluruh share yang lain. Buat skema k-1 to n bagikan ke share selain yang baru saja dibuat
bc ac Sementara untuk k = 1, n = 2 masing masing share adalah : b
Dari hasil hipotesis :
b
Untuk k = 3, n = 4 masing masing share adalah : Dari hasil diatas dapat disimpulkan bahwa untuk setiap skema k to n yang terdefinisi dapat dibuat skema k-1 to n-1 turunannya dengan cara : Pilih salah satu share yang akan dieliminasi Untuk setiap share lainnya kurangkan elemen yang terdapat pada share yang akan dieliminasi Eliminasi share yang terpilih
Dari hasil hipotesis : Untuk k = 2, n = 3 masing masing share adalah : ab
abd bce acf def Sementara untuk k = 2, n = 4 masing masing share adalah : abd bcd acd
bc
abc
ac Sementara untuk k = 2, n = 2 masing masing share adalah : a c Dari hasil diatas dapat disimpulkan bahwa untuk setiap skema k to n yang terdefinisi dapat dibuat skema k to n-1 dengan (k ≤ (n-1)) turunannya dengan cara : Pilih salah satu share yang akan dieliminasi Untuk setiap sahare selain yang terpilih gunakan operasi AND dengan share yang terpilih Eliminasi share yang terpilih Dari hasil hipotesis : Untuk k = 2, n = 3 masing masing share adalah : ab bc ac Sementara untuk k = 2, n = 4 masing masing share adalah :
Dari hasil diatas dapat disimpulkan bahwa untuk setiap skema k to n yang terdefinisi dapat dibuat skema k-1 to n dengan ((k-1) > 1) turunannya dengan cara : Pilih salah satu share yang akan diganti Untuk setiap share lainnya kurangkan elemen yang terdapat pada share yang akan diganti Ganti share yang terpilih dengan union seluruh share yang lain. Buat skema k-2 to n bagikan ke share selain yang baru saja diganti Dari hasil hipotesis : Untuk k = 2, n = 4 masing masing share adalah : abd bcd acd abc Sementara untuk k = 3, n = 4 masing masing share adalah : abd
bce acf def Dari hasil diatas dapat disimpulkan bahwa untuk setiap skema k to n yang terdefinisi dapat dibuat skema k+1 to n dengan ((k+1) < n) turunannya dengan cara : Pilih salah satu share yang akan diganti Untuk setiap share lainnya kurangkan elemen yang yang beririsan di semua share selain yang terpilih Buat skema k+1 to n-1 bagikan ke share selain yang baru saja diganti Ganti share yang terpilih dengan gabungan share share yang ditambahkan pada share asal Dari hasil hipotesis diatas dapat dirumuskan algoritma transformasi sebagai berikut : increment k and n (array of share_scheme) Æ array of share_scheme { new_share_scheme = create_scheme (k+1,n) for i = 1 to count(share_scheme) { new_share_scheme[ i ] = share_scheme[ i ] + new_share_scheme[ i ] union = union + share_scheme[ i ] } new_share_scheme[ i + 1 ] = union Ænew_share_scheme } decrement k and n (array of share_scheme) Æ array of share_scheme { chosen_share_scheme = share_scheme[count(share_scheme)] for i = 1 to count(share_scheme) - 1 { new_share_scheme[ i ] = share_scheme[ i ] - chosen_share_scheme } Ænew_share_scheme } increment n (array of share_scheme) Æ array of share_scheme { new_share_scheme = create_scheme (k+1,n) for i = 1 to count(share_scheme) { new_share_scheme[ i ] = share_scheme[ i ] + new_share_scheme[ i ] union = union + share_scheme[ i ] }
new_share_scheme[ i + 1 ] = union Ænew_share_scheme } decrement n (array of share_scheme) Æ array of share_scheme { chosen_share_scheme = share_scheme[count(share_scheme)] for i = 1 to count(share_scheme) - 1 { new_share_scheme[ i ] = share_scheme[ i ] - chosen_share_scheme } Ænew_share_scheme } increment k (array of share_scheme) Æ array of share_scheme { chosen_share_scheme = share_scheme[count(share_scheme)] new_share_scheme = create_scheme (k+1,n1) intersect = share_scheme[ 1 ] for i = 1 to count(share_scheme) - 1 { union = union + new_share_scheme[ i ] intersect = intersect AND share_scheme[ i ] } for i = 1 to count(share_scheme) - 1 { new_share_scheme[ i ] = (share_scheme[ i ] - intersect) + new_share_scheme[ i ] } new_share_scheme[ i + 1 ] = union Ænew_share_scheme } decrement k (array of share_scheme) array of share_scheme { chosen_share_scheme share_scheme[count(share_scheme)]
Æ
=
new_share_scheme = create_scheme (k-2,n) for i = 1 to count(share_scheme) - 1 { union = union + share_scheme[ i ] new_share_scheme[ i ] = (share_scheme[
i ] chosen_share_scheme) new_share_scheme[ i ]
+
●○
2
} new_share_scheme[ i + 1 ] = union Ænew_share_scheme
○A
○B
○
●
A
B
●
3 4
}
○
○
○
○
○
AC
BC
C
C
C
C
●
A
B
●
A
B
●
A
B
●
A
B
●
A
5 Dari algoritma diatas dapat dilihat beberapa merupakan fungsi rekursif. Fungsi tersebut dijalankan hingga mencapai basisnya yaitu k = 1 atau k = n. namun untuk mencapai keadaan itu bisa melalui berbagai macam cara melihat cukup banyak algoritma yang dapat digunakan, karena itu agar pencarian skema berjalan dengan efektif maka perlu dibuat cara mencari pilihan terpendek (dilihat dari kedalaman rekursif fungsi), cara yang saya usulkan adalah membuat peta k/n seperti berikut :
k\n
1
2
3
4
5
6
7
8
9
1
●○
○
○
○
○
○
○
○
○
2
●
3
6 7 8 9
○ = basis k = 1 A = daerah dimana k+1 to n merupakan basis B = daerah dimana k+1 to n-1 merupakan basis C = daerah dimana k-2 to n merupakan basis Dari keempat algoritma tersebut perlu dipilih algoritma mana yang paling efektif dilihat dari berapa banyak skema yang perlu diekspansi hingga menemukan skema hasil, disini penulis mencari skema 4 to 7 angka tersebut digunakan karena letak pada peta k\n sama sama memiliki jarak 3 petak dari basis k = 1 maupun k = n. Bila kita hanya menggunakan increment k and n
●
5
●
6
●
7
●
8
●
9
●
3
1
2
3
4
5
6
7
8
9
1
●○
○
○
○
○
○
○
○
○
●
x
x
x
●
x
x
x
●
x
x
3
Dari peta k/n diatas dapat dibuat rute perpendek dari basis menggunakan algoritma yang telah ditemukan, namun tidak seluruh algoritma dipakai sebaiknya algoritma yang tidak menggunakan fungsi create_scheme agar lebih efektif. Dari daftar diatas algoritma yang tidak memakai fungsi create_scheme adalah decrement k and n dan decrement n. decrement k and n membuat posisi pada peta k/n bergerak ke kiri atas sementara decrement n membuat posisi pada peta k/n menjadi kekanan, dilihat dari posisi basis dan perubahan posisi maka kedua algoritma ini tidak cukup untuk mendapatkan seluruh skema k to n yang ada karena itu diperlukan algoritma lain. Dari 4 algoritma yang kurang efektif karena menggunakan fungsi create_scheme dua diantaranya menggunakan k+1 to n sementara yang lainnya adalah k+1 to n-1 dan k-2 to n dari peta k/n : 2
k\n 2
● = basis k = n ○ = basis k = 1
1
●
● = basis k = n
●
4
k\n
1
4
5
6
7
8
9
4 5
+
●
6
●
7
●
8
●
9 Maka skema yang perlu diekspansi = 9.
●
Bila kita hanya menggunakan increment n k\n
1
2
3
4
5
6
7
8
9
1
●○
○
○
○
○
○
○
○
○
●
x?
x
+
●
x?
2 3 4 5
● ●
6
x
●
7
●
8
Dari algoritma diketahui bahwa algoritma increment k and n dapat digunakan sebagai komplemen increment n, jika pencarian skema menggunakan algoritma decrement k and n ruang pencarian akan menjadi :
●
9 ● Maka skema yang perlu diekspansi = 4 jika skema 4 to 5 dan 5 to 6 diketahui.
k\n
1
2
3
4
5
6
7
8
9
Bila kita hanya menggunakan increment k
1
●○
○
○
○
○
○
○
○
○
●
x x
x
+
●
x
k\n
1
2
3
4
5
6
7
8
9
2
1
●○
○
○
○
○
○
○
○
○
3
●
x
x
x
x
x
4
●
x
x
x
x
5
●
x
x
+
6
2 3 4 5 7
●
8
●
9 Maka skema yang perlu diekspansi = 12.
●
k\n
1
2
3
4
5
6
7
8
9
1
●○
○
○
○
○
○
○
○
○
● ●
4 6
x ●
7
x ●
8 9
+ ●
● ● Seperti yang dapat dilihat diatas tidak mungkin mendapatkan skema dengan hanya menggunakan fungsi decrement k Dari percobaan diatas dapat dilihat bahwa cara yang hanya menggunakan fungsi increment n mengekspansi paling minimal, namun fungsi tersebut masih memerlukan bantuan agar bisa terdefinisi : Dari algoritma increment n dapat dilihat bahwa untuk mendapatkan skema k to n maka kita perlu mengetahui skema k to n-1 dan k-1 to n, digambarkan dalam peta k/n sebagai berikut : x
+
● ●
9 Keterangan : + : skema yang dicari
●
x : skema yang didapat menggunakan increment x : skema yang didapat menggunakan increment k and n hasil : skema yang perlu diekspansi = 4 dengan cara diatas dapat dibuat algoritma create_scheme yang menggunakan increment_n dan decrement_k_and_n sebagai berikut :
x? ●
5
●
k
Bila kita hanya menggunakan decrement k
3
●
8
●
2
x
7
●
6
●
create_scheme(int k, int n) Æ array of share_scheme { //basis if (k=1) { new_element = new_elements() for i = 1 to n { new_share_scheme[ i ] = new_element } } else if (k=n) { for i = 1 to n { new_share_scheme[ new_elements() }
i
]
=
} //rekurens (algoritma increment n) else if (n-k > 1) { share_scheme = create_scheme (k,n-1) new_share_scheme = create_scheme (k+1,n-1) for i = 1 to count(share_scheme) { new_share_scheme[ i ] = share_scheme[ i ] + new_share_scheme[ i ] union = union + share_scheme[ i ] } new_share_scheme[ i + 1 ] = union Ænew_share_scheme } //rekurens (algoritma increment k and n) else //n-k == 1 { share_scheme = create_scheme (k-1,n-1) new_share_scheme = create_scheme (k,n1) for i = 1 to count(share_scheme) { new_share_scheme[ i ] = share_scheme[ i ] + new_share_scheme[ i ] union = union + share_scheme[ i ] } new_share_scheme[ i + 1 ] = union } Ænew_share_scheme } Perbandingan ukuran setiap share (dalam % ukuran awal): k\n
1
2
3
4
5
6
1
100
100
100
100
100
100
50
66
75
80
83
33
50
60
66
25
40
50
20
33
2 3 4 5 6
16
Perbandingan ukuran keseluruhan share (dalam % ukuran awal): k\n
1
2
3
4
5
6
1
100
200
300
400
500
600
2 3 4
100
133
150
160
166
100
150
180
200
100
160
200
100
166
5 6
100
Dari hasil diatas dapat dilihat bahwa ukuran setiap share berbanding lurus dengan n dan berbanding terbalik dengan k, sementara pada ukuran keseluruhan share walaupun ukuran terbesar digunakan oleh k = 1 dan ukuran terkecil oleh k=n ukuran keseluruhan tidak berbanding lurus namun memiliki puncak di k = 0,5 n dan menurun di k < 0,5 n maupun k > 0,5 n. 4. KESIMPULAN Dari pembahasan diatas dapat disimpulkan bahwa secret sharing pada berkas yang dimampatkan menggunakan Huffman coding dimungkinkan dengan cara memisahkan header dari body kemudian membagi dengan algoritma secret sharing yang berbeda, secret sharing yang secure seperti yang dicontohkan diatas adalah modifikasi dari visual kriptografi untuk header dan naïve secret sharing untuk body. Metode yang sama diharapkan dapat digunakan untuk berkas kompresi yang lain yang memiliki header dan body. Dengan menggunakan prinsip yang sama yaitu menggunakan secret sharing yang secure untuk header dan naïve secret sharing untuk body. Beberapa saran utuk pengembangan dimasa depan adalah : 1. Implementasi pada format kompresi yang lebih rumit seperti zip, rar, 7z dll. 2. Algoritma transformasi yang lebih efektif. 3. Implementasi algoritma secret sharing lain untuk header.
DAFTAR REFERENSI [1] Munir, Rinaldi., Diktat Kuliah IF5054 Kriptografi, 2004 [2] Munir, Rinaldi., Slide Kuliah IF5054 Kriptografi : Skema Pembagian Data Rahasia, 2007 [3] Munir, Rinaldi., Slide Kuliah IF5054 Kriptografi : Kriptografi Visual, 2007 [4] Makalah IF5054 : Pemanfaatan Steganografi dalam Kriptografi Visual [5] http://en.wikipedia.org diunduh 11 Desember 2007
