KNAPSACK

KNAPSACK

Algoritma Knapsack adalah algoritma kriptografi kunci-publik yang keamanannya terletak pada sulitnya memecahkan persoalan knapsack(Knapsack Problem). Knapsack di sini artinya adalah kantung. Di algorima ini dikenal permasalahan yang disebut Knapsack Problem.

Knapsack Problem
Jika m merupakan bobt knapsack dan n adalah banyaknya objek yang masing-masing mempunyai bobot w1,w2,…,wn. Tentukan nilai bi sedemikian sehingga
M=b1w1+b2w2+…+bnwn
Yang dalam hal ini bi hanya bernilai 0 dan 1. Jika b=1, maka objek I dimasukkan ke dalam Knapsack, sebaliknya jika b=0, maka tidak dimasukkan ke dalam knapsack.

Algoritma Knapsack Sederhana
Ide dasar Knapsack adalah mengkodekan pesan sebagai rangkaian solusi dari persoalan knapsack. Setiap bobot w1 di dalam persoalan knapsack merupakan kunci privat, sedangkan bit-bit plainteks menyatakan b1
Contoh :
Misalkan n=6 dan w1=1, w2=5, w3=6, w4=11, w5=14 dan w6=20.
Plainteks = 111001010110000000011000
Jawab:
Plainteks dibagi menjadi blok yang panjangnya n, kemudian setiap bit di dalam blok dikalikan dengan w1 yang berkoresponden sesuai persamaan di atas:
Blok plainteks ke-1 : 111001
Blok plainteks ke-2 : 010110
Blok plainteks ke-3 : 000000
Blok plainteks ke-4 : 011000
Knapsack : 1,5,6,11,14,20
Kriptogram ke-1 : (1×1) + (1×5) + (1×6) + (1×20) =32
Kriptogram ke-2 : (1×5) + (1×11) + (1×14) = 30
Kriptogram ke-3 : 0
Kriptogram ke-4 : (1×5) + (1×6) = 11
Jadi, cipherteks yang dihasilkan : 32, 30, 0, 11
Untuk algoritma di atas hanya bias digunakan untuk enkripsi saja. Misalkan kita diberikan kriptogram 32, maka kita harus mencari nilai b1,b2,…,b6 untuk persamaan 32 = b1+5b2+6b3+11b4+14b5+20b6

Solusi dari persamaan di atas tidak dapat dipecahkan dalam orde waktu polynomial dengan orde waktu polynomial dengan semakin besar n dan barisan bobot tidak dalam urutan naik.

Super increasing knapsack
Superincreasing knapsack adalah persoalan knapsack yang dapat dipecahkan dalam orde 0(n) yang bersifat polynomial. Ini adalah perrsoalan knapsack yang mudah. Kita dapat membentuk barisan superincreasing kannpsack. Barisan superincreasing adalah suatu barisan di mana setiap nilai di dalam barisan lebih besar daripada jumlah semua nilai sebelumnya, misalnya(1,3,6,13,27,52).
Solusi dari superincreasing knapsack mudah dicari dengan cara berikut:
1.Jumlahkan semua bobot dalam barisan.
2.Bandingkan bobot total dengan bobot terbesar di dalam barisan. Jika bobot terbesar lebih kecil atau sama dengan bobot total, maka ia dimasukkan ke dalam knapsack, jika tidak, maka tidak dimasukkan.
3.Kurangi bobot total dengan bobot yang telah dimasukkan, kemudian bandingkan bobot total sekarang dengan bobot terbesar selanjutnya. Demikian seterusnya sampai seluruh bobot di dalam barisan selesai dibandingkan.
4.Jika bobot total menjadi nol, maka terdapat solusi superincreasing knapsack, tetapi jika tidak nol, maka tidak ada solusinya.
Contoh :
Misalkan bobot-bobot yang membentuk barisan superincreasing adalah (2,3,6,13,27,52) dan diketahui bobot knapsack (m) = 70. untuk mencari nilai bi, caranya adalah sebagai berikut:

1.Bandingkan 70 dengan nilai terbesar yaitu 52. Karena 52< 52="18," 13="5">5, maka 6 tidak termasuk.
2. Bandingkan bobot 3 dengan bobot total. Karena 3<5, 3="2." 2="0." 70 =" (1×2)" m="105," n="31." 105 =" 62" 105 =" 93" 105 =" 81" 105 =" 88" 105 =" 102" 105 =" 37" 1=" 1" 1=" 1"> n. n-1= 1 + km => n. n-1= (1+km)/n, k sembarang bilangan bulat..Kalikan setiap kriptogram dengan n-1 mod m, lalu nyatakan hasil kalinya sebagai penjumlahan elemen-elemen kunci privat untuk memperoleh plainteks dengan menggunakan algoritma pencarian solusi superincreasing knapsack.Contoh:Dari contoh sebelumnya, dengan menggunakan kunci privat (62,93,81,88,102,37). Di sini, n=31 dan m=105. Nilai n-1 diperoleh dari: n-1 = (1+105k)/31, dengan mencoba k=0,1,2,…, maka kita akan memperoleh nilai n-1 jika k=18.n-1 = (1+105.18)/31 = 61Plain teks yang berkoresponden diperoleh kembali dengan cara membuka di awal yang telah kita bahas. Hasilnya akan diperoleh174.61 mod 105 = 9 , bobotnya 3+6, berkoresponden dengan 011000280.61 mod 105 = 70 , bobotnya 2+3+13+52, berkoresponden dengan110101333.61 mod 105 = 48 , bobotnya 2+6+13+27, berkoresponden dengan 101110
Jadi plainteksnya adalah: 011000 110101 101110