Algorima Knapsack dan Penerapan di Kode Java

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 public class Knapsack { public static void main(String[] args) { int[] weights = {2, 3, 4, 3}; int[] values = {2, 3, 4, 5}; int capacity = 1; int[][] solution = getSolutionMatrix(values, weights, capacity); int[] optimalSubset = getOptimalSubset(solution, weights); printMatrix(solution, "Solution Matrix"); printArray(optimalSubset, "Optimal Subset"); } /** * * Returns the solution matrix for the Knapsack problem associated with the * given values, weights and knapsack capacity. * * @param values The values of the items. * @param weights The weights of the items. * @param capacity The capacity of the knapsack. * */ private static int[][] getSolutionMatrix(int[] values, int[] weights, int capacity) { int[][] matrix = new int[values.length + 1][capacity + 1]; for(int i = 1; i <= values.length; i++) { for (int j = 0; j <= capacity; j++) { if (j - weights[i-1] >= 0) { matrix[i][j] = Math.max(matrix[i-1][j], values[i-1] + matrix[i-1][j-weights[i-1]]); } else { matrix[i][j] = matrix[i-1][j]; } } } return matrix; } /** * * Returns the optimal subset of items that should be included in the knapsack * given a completed solution matrix. * * @param solutionMatrix An N by W matrix, where N is the number of items and W * is the capacity of the knapsack. * @param weights An array of size N containing the weights of each of the items. * */ private static int[] getOptimalSubset(int[][] solutionMatrix, int[] weights) { int[] subset = new int[weights.length]; int numItems = 0; int i = solutionMatrix.length - 1; for (int j = solutionMatrix[0].length - 1; j >= 0 && i > 0;i--) { // If the item is in the optimal subset, add it and subtract its weight // from the column we are checking. if (solutionMatrix[i][j] != solutionMatrix[i-1][j]) { subset[numItems] = i; j -= weights[i-1]; numItems++; } } return Arrays.copyOfRange(subset, 0, numItems); } /** * Prints an array to the console, applying the given title. */ private static void printArray(int[] array, String title) { StringBuilder builder = new StringBuilder(); builder.append("\n").append(title).append(":\n{"); if (array.length != 0) builder.append(array[0]); for (int i = 1; i < array.length; i++) { builder.append(", ").append(array[i]); } builder.append("}"); System.out.println(builder.toString()); } /** * Prints a matrix (2-dimensional array) to the console, applying the given title. */ private static void printMatrix(int[][] matrix, String title) { StringBuilder builder = new StringBuilder(); builder.append(title).append(":\n"); for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[0].length; j++) { builder.append(matrix[i][j]).append("\t"); } builder.append("\n"); } System.out.print(builder.toString()); } }