Algoritma KnapSack

Algorima Knapsack

Salah satu algoritma public key adalah algoritma knapsack. Apa sih algoritma Knapsack itu?

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.

Superincreasing 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.
6.
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 dengan 110101333.61 mod 105 = 48 , bobotnya 2+6+13+27, berkoresponden dengan 101110

Jadi plainteksnya adalah: 011000 110101 101110

Sourcenya

#include

#include

#include

#define TRUE 1

#define FALSE 0

int recursiveKnapsack(int target, int candidate, int weights[],int taken[], int N);

void initTaken(int taken[], int N);

int main(void)

{

const int N = 5;

int weights[] = {3, 1, 2, 3, 8};

int taken[N];

initTaken(taken, N);

assert(recursiveKnapsack(7, 0, weights, taken, N));

assert( taken[0] == TRUE &&

taken[1] == TRUE &&

taken[2] == FALSE &&

taken[3] == TRUE &&

taken[4] == FALSE);

initTaken(taken, N);

assert(recursiveKnapsack(10, 0, weights, taken, N));

assert(t aken[0] == FALSE &&

taken[1] == FALSE &&

taken[2] == TRUE &&

taken[3] == FALSE &&

taken[4] == TRUE);

initTaken(taken, N);

assert(!recursiveKnapsack(30, 0, weights, taken, N));

initTaken(taken, N);

assert(recursiveKnapsack(17, 0, weights, taken, N));

assert( taken[0] == TRUE &&

taken[1] == TRUE &&

taken[2] == TRUE &&

taken[3] == TRUE &&

taken[4] == TRUE);

return EXIT_SUCCESS;

}



int recursiveKnapsack(int target, int candidate, int weights[],int taken[], int N)

{

if (target == 0)

return TRUE;

if (target <> N-1)

return FALSE;

if (recursiveKnapsack(target – weights[candidate], candidate + 1,weights,taken, N))

{

taken[candidate] = TRUE;

return TRUE;

}

return recursiveKnapsack(target, candidate + 1, weights, taken,N);

}



void initTaken(int taken[], int N)

{

int i;

for (i = 0; i <>