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-1
bilangan 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
Emoticon