Algoritma kriptografi kunci publik yg keamanannya terleatak pada sulitnya memecahkan persoalan knapsack(karung/kantung). Karung mempunyai kapasitas muat terbatas.
Algoritma Knapsack Kunci Publik
1. Tentukan barisan superincreasing: suatu barisan dimana setiap nilai di dlm barisan lebih besar daripada jumlah semua nilai sebelumnya.
2. Kalikan setiap elemen di dalam barisan tersebut dengan n modulo m. Modulus m seharusnya angka yg lebih besar daripada jumlah semua elemen di dalam barisan. Sedangkan pengali n seharusnya tdk mempunyai faktor persekutuan dengan m.
3. Hasil perkalian akan menjadi kunci publik sedangkan barisan superincreasing semula menjadi kunci privat.
Contoh :
Proses Pembangkitan kunci:
Barisan superincreasing adalah (2,3,6,13,27,52)
M=105 dan n=31
Barisan non-superincreasing knapsack dihitung sbb :
2 x 31 mod 105 = 62
3 x 31 mod 105 = 93
6 x 31 mod 105 = 81
13 x 31 mod 105 = 88
27x 31 mod 105 = 102
52 x 31 mod 105 = 37
Jadi kunci publik adalah {62,93,81,88,102,37} dan kunci privat {2,3,6,13,27,52}
Proses Enkripsi
1. Plainteks dipecah menjadi blok bit yg panjangnya sama dengan kardinalitas(ukuran banyaknya anggota dalam suatu himpunan) barisan kunci publik.
2. Kalikan setiap bit di dalam blok dengan elemen yg berkoresponden di dalam kunci publik
Contoh :
Plainteks = 011000 110101 101110
Kunci publik yg digunakan {62,93,81,88,102,37}
Proses enkripsi :
Plainteks dibagi menjadi blok yg panjangnya 6
Blok plainteks_1 = 011000
Kunci publik = 62,93,81,88,102,37
Kriptogram = (1x93)+(1X81) =174
Blok plainteks_2 = 110101
Kunci publik = 62,93,81,88,102,37
Kriptogram = (1x62)+(1X93)+(1x88)+(1x37) =280
Blok plainteks_3 = 101110
Kunci publik = 62,93,81,88,102,37
Kriptogram = (1x62)+(1X81)+(1x88)+(1x102) =333
Jadi cipherteks yg dihasilkan (174,280,333)
Proses Dekripsi
1. Menggunakan kunci privat
2. Menghitung nilai n-1 yaitu inversi n modulo m sedemikian rupa sehingga n.n-1=1(mod m)
n-1 =(1+km)/n, k sembarang bilangan bulat.
Kunci privat {2,3,6,13,27,52}, n=31,m=105 maka
n-1 = (1+k.105)/31
dengan mencoba nilai k maka k=18 diperoleh n-1bilangan bulat yaitu 61.
Cipherteks 174,280,333
174 x 61 mod 105 = 9 = 3+6, berkoresponden dengan 011000
280 x 61 mod 105 = 70 = 2+3+13+52, berkoresponden dengan 110101
333 x 61 mod 105 = 48 = 2+6 +13+27, berkoresponden dengan 101110
0 Comments