KNAPSACK PROBLEM DAN ALGORITMA LLL

8/7/2019 KNAPSACK PROBLEM DAN ALGORITMA LLL

http://slidepdf.com/reader/full/knapsack-problem-dan-algoritma-lll 1/11

KNAPSACK PROBLEM DAN ALGORITMA LLL

Ada beberapa variasi knapsack problem yang relevan dengan teorikompleksitas, matematika, dan kriptografi. Di sini, kita hanya akan

membahas knapsack problem yang relevan dengan kriptografi. Alasan

kenapa knapsack relevan ialah karena proses enkripsinya sangat cepat,

bahkan lebih cepat dari RSA.

Knapsack problem bisa digambarkan sebagai berikut. Ada seorang

pencuri yang masuk ke took perhiasan yang menjual beberapa perhiasan.

Masing-masing perhiasan memiliki berat yang berbeda-beda. Jika ia ingin

mengisi knapsacknya, perhiasan mana yang harus dia ambil agar

mendapatkan nilai maksimal?

Berikut ini adalah simulasi applet sederhana dari knapsack problem

dimana c = kapasitas, p = harga, w = berat, dan x = 0 atau 1 (masuk atau

keluar).

Kasus special yang terjadi dengan problem ini ialah ketika nilai dari

masing-masing perhiasan sama dan menemukan subset perhiasan yang

sesuai dengan kapasitasnya. Ini biasa disebut “subset sum problem” atau

“knapsack problem” di dalam kriptografi. Ini memungkinkan nantinya tidak

ada subset atau jumlah perhiasannya terlalu banyak sehingga scenario

terburuk sekalipun tidak dapat diselesaikan, sehingga masalahnya pun

menjadi NP-complete. Masalah ini menjelaskan masalah NP-complete yang

lain, yaitu Traveling Salesman Problem (TSP).

Skema Kriptografi Knapsack

Salah satu kriptosistem kunci public paling awal ialah kriptosistem

knapsack, yang awalanya dijelaskan oleh Ralph Merkle dan Martin Hellman



pada tahun 1978 dan mendasari skema subset sum problem. Seperti yang

telah disebutkan sebelumnya, subset sum problem biasanya tidak dapat

diselesaikan, tetapi masih ada beberapa bagian dari problem tersebut yang

dapat diselesaikan. Ide dasar dari skema Merkle-Hellman ini ialah dalam

transforming hard atau subset sum problem yang tidak terselesaikan

menjadi subset sum problem yang mudah untuk diselesaikan.

Enciphering dan Deciphering

Bob ingin mengirimkan pesan ke Alice, dan kunci public alice ialah a =

(a1, a2, ..., an). Untuk meng-encipherkan pesan x = (x1, x2, ..., xn) dari n bits, Bob

membuat sum-nya :

(1)

S kemudian dikirim ke Alice. Jika pesan tersebut panjang, pesan

tersebut bisa dibagi-bagi ke dalam beberapa blok n-bits, jika perlu mengisi

blok terakhir dengan 0. Karena kunci enciphering ialah public dan S dapat

secara potensial dirahasiakan, kemudian pengekstrasian x dari S dan a

seharusnya secara sengaja menjadi keras. Jika a dipilih untuk menjadi

integer sequence, maka Alice biasanya tidak dapat mendapatkan x dalam

jumlah CPU yang sesuai atau tugas tersebut menjadi NP-hard. Ini

dikarenakan satu-satunya jalan untuk menemukan x ialah dengan mencoba

semua nilai 2n yang memungkinkan dari x jika persamaan (1) terpenuhi,

yang mana tidak dapat diselesaikan jika n lebih besar dari 100. ini membuat

proses eavesdropping menjadi suatu yang tidak penting dan nantinya akan

membuat ini menjadi lebih sulit untuk menemukan x.

Jika a dipilih secara acak oleh Alice, juga akan menyulitkannyauntuk

melakukan decipher S dan menemukan plaintext x. Disinilah Merkle-Hellman

trapdoor berperan. Ini memungkinkan Alice untuk mendapatkan nilai x yang



diberikan oleh S dan memberikan dia beberapa informasi rahasia. Informasi

rahasia tersebut disebut kunci deciphering. Informasi trapdoor dimasukkan

ke dalam konsiderasi ketika Alice membuat kunci publiknya. Inilah kegunaan

teknik trapdoor yang membuat skema tersebut tidak aman.

S merupakan fungsi satu-satu karena jika ada dua plaintext x dan y

berbeda memberikan ciphertext yang sama, penerima tidak dapat

memperoleh plaintext. Sehingga harus ditemukan bagaimana menghitung

satu-satu kunci enciphering, yang umumnya merupakan NP-complete

problem. Namun, trapdoor memiliki solusinya.

Merkle-Hellman Trapdoor

Ketika Alice membuat kunnci enchipering public a, pertama-tama ia

menghitung super increasing sequence dari angka-angka natural .

Vektor dikatakan menjadi super increasing jika masing-

masing i dengan ,

Super increasing sequence ialah ketika tiap-tiap term lebih besar dari

jumlah term sebelumnya. Contohnya, (1, 2, 4, 8, ..., 2n-1) merupakan super

increasing sequence yang mudah dan (1, 2, 3, 4, 5,...,9) bukan merupakan super

increasing sequence. Untuk mengetahui apakan suatu sequence merupakan

super increasing, maka computer hanya akan membuat 1 pass over untuksemua sequence dalam waktu O(h). Jadi, untuk menentukan apakah suatu

subset sum T merupakan bagian dari super increasing atau bukan, komputer

harus menentukan apakah angka terbesar dalam himpunan tersebut kurang

dari atau sama dengan T dan mensubstraksinya untuk memperoleh T’.



Proses ini terus berulang. Jika T’ = 0, maka subset sum terdiri dari semua

angka yang disubstraksi dari T.

Menyembunyikan “easy” super increasing sequence dari eavesdroppers

melibatkan beberapa transformasi modulo. Transformasi tersebut ialah

(2)

(3)

and , (4)

or and ,

Ketika k transformasi digunakan, kunci public = .

Persamaan (2) disebut Merkle-Hellman dominance dan persamaan (4) ialah

Merkle-Hellman trncformation. Ketika menggunakan trnsformasi pada bagian

aj+1 ke aj , disebut reverse Merkle-Hellman transformation. Jika 1 trnsformasi

digunakan, maka ini disebut sebagai basic atau basic iterated scheme (kita

juga menurunkan indeks j, j+i, k, dan k+i) dan jika 2 transformasi digunakan,

maka disebut double iterated scheme.

Untuk men-dechuoher pesan yang dienkripsikan, Alice harus

menghitung dan kunci dechipering, dimana

dan (5)

Sehingga h = n, jika , maka xh = 1 atau 0. Kemudian alice

melanjutkan secara iterative, mensubstraksi xhah dari S 1 dengan h

decrementing dari n ke 1 selama proses iterasi.



Menyerang Skema Trapdoor Knapsack

Notasi Dasar dan Terminologi

• Posets

Posets atau partially ordered set ialah himpunan yang diambil bersamaan

secara partial order di dalamnya. Untuk mengilustrasikannya, anggap A

dan B merupakan dua buah himpunan, A ialah subset dari B, sehingga

himpunan-himpunan tersebut secara parsial diurutkan (partially ordered)

oleh masing-masing himpunan. Jika A bukan subset dari B dan B bukan

merupakan subset A, maka mereka tidak partially ordered.

• Latice

Latice didefinisikan oleh pada himpunan memenuhi beberapa syarat

untuk lattice, yaitu :

• Least Upper Bound dan Greatest Lower Bound

Definisi dari Least Upper (lub) Greatest Lower (glb) Bounds ialah :



Algoritma LLL

Algoritma LLL pertama kali ditemukan pada tahun 1980 oleh Lenstra,

Lenstra, dan Lovasz. Sebenarnya tujuan dari algoritma LLL bukan untuk

membobol kripto sistem manapun, tetapi untuk mencari factor polynomial

dengan keofisien rasional. Hal ini juga berkembang untuk algoritma

pengurangan Latice yang digunakan untuk menyelesaikan pemrograman

integer linier.

Sebelum memulai penjelasan mengenai algoritam LLL, mari definisikan

lattice yang lebih bermanfaat. (v1,...vn) adalah himpunan linier bebas untuk

vector nyata dalam vector n-dimensional nyata ruang Euclidean. Himpunan

dari semua poin u1v1+...+unv

n dengan integral u1,...un disebut lattice baris (v1,...vn).

Teorema

(v1

,...vn

) adalah baris dari lattice L dan v'i

adalah poin untuk

dan dimana zij adalah integer, himpunan (v'1,...,v'n) adalah

baris untuk lattice L, jika dan hanya jika det(zij) = +/- 1. Kita dapat menyebut

matriks integer Z dengan det(zij) = +/- 1 sebagai matriks yang unimodular.

Akibatnya, |det(v1,...,vn)| bergantung pada basis tertentu untuk suatu

lattice.

Ini sesuai untuk basis-basis lattice jika sewaktu-waktu memilikikoefisien-koefisien yang besar berdasarkan pada teori geometric angka-

angka yang tidak terdapat dalam suatu himpunan n-vektor sepertihalnya

himpunan orthogonal. Algoritma LLL menemukan bahwa dalam waktu

polinomial, suatu baris untuk suatu lattice L, yang mana mendekati

orthogonal sehubungan dengan ukuran tertentu yang tidak orthogonality.



Suatu baris disebut reduced jika baris tersebut terdiri dari vector-vektor yang

relative pendek dan seperti yang dijelaskan teorema diatas, menemukan

vector pendek. Tidak ada jaminan untuk menjadi vector terpendek, tetapi

panjangnya itu sendiri tidak akan melebihi panjang dari vector terpendek

oleh lebih dari 1 multiplicative constant.

v1,...,vn milik n-dimensi ruang vector nyata. Untuk menginisialisasikan

algoritmanya, suatu baris nyata orthogonal v'i dihitung bersamaan dengan

, seperti yang

(6)

(7)

dimana * menandakan hasil linier scalar. Pada algoritma yang lain v1,v2...,vn

akan diubah beberapa kali, tetapi akan selalu menyisakan basis L. Setelah

semua perubahan, v'i dan mij diperbaharui dengan menggunakan persamaan

(6) dan (7). Subscript k saat itu digunakan selama algoritma LLL dimulai

dengan k = 2. Jika k = n +1, maka algoritma tersebut akan dijalankan.

Misalnya saat ini k <= n, maka pertama-tama kita ingin mk k-1| <= ½ jika k > 1 .

Jika hal ini tidak terjadi, r adalah integer terdekat ke mk k-1 dan menggantikan vk

dengan vk - rvk-1 (jangan lupa update). Selanjutnya kita membedakan dua

kasus. Misalnya k >= 2 dan |v'k + mk k-1v'k-1| < (3/4) |v'k-1|

2 ,maka ganti vk-1 dan vk

(jangan lupa update), kemudian ganti k dengan k-1 dan restart. Dalam kasus

ini kita ingin :

untuk (8)

Jika kondisi pada persamaan (8) tidak terjadi, kemudian L akan menjadi

indeks terbesar <k dengan mlk > ½ , r menjadi yang terdekat ke ml

k dan

mengganti bk dengan bk - rbl (jangan lupa update), ulangi sampai kondisi pada



persamaan (8) terpenuhi, kemudian gantikan k dengan k+1 dan restart.

Catatan, jika kasus k = 1 terjadi, gantikan dengan k = 2.

Matematika dapat mengimplimentasikan algoritma LLL dengan

memanggil fungsi lattice LatticeReduce[matrix] . Catatan, jika masukan

terdiri dari angka-angka rasional.

Contoh aplikasi

Misalnya kita memiliki super increasing knapsack :

•

S = [2, 5, 9, 21, 45, 103, 215, 450, 946] adalah kunci public kita• p = 2003;

• m = 1289; dimana m-1 = 317.

Knapsack public :

• ti = 1289 *si mod 2003

• Jadi T = [575, 436, 1586, 1030, 1921, 569, 721, 1183, 1570] ialah kunci public kita

Kita akan mengenkripsikan 101100111 sebagai 575 + 1586 + 1030 + 721 +

1183 + 1570 = 6665. Penerima komputer 6665 * 317 mod 2003 = 1643 danmenggunakan S untuk menemukan plaintext ini dapat dilakukan oleh

pengkonstruksi string binary dari kanan ke kiri; 1643 - 946(1) = 697; 697 - 450(1) =

247; 247 - 215(1) = 32; 32 - 45(0) = 32; 32 - 21(1) = 11; 11 - 9(1) = 2; 2 - 5(0) = 2; 2 - 2(1) = 0.

Sehingga kita mendapatkan plaintextnya 101100111.

Seorang penyerang mengetahui :

•

kunci publik T = [575, 436, 1586, 1030, 1921, 569, 721, 1183, 1570]• dan ciphertext 6665

Si penyerang ingin mengetahui xi dalam {0,1}. Sehingga 575x0 + 436x1 +

1586x2 + 1030x3 + 1921x4 + 569x5 + 721x6 + 1183x7 + 1570x8 = 6665. Mari tulis ulang

masalahnya sebagai M*V=W dimana:



Solusinya ialah vector pendek dalam kolom lattice matriks M, dan

disinilah kita menggunanakan algoritma LLL untuk mendapatkan solusinya.

Matriks M’ merupakan hasil dari menerapkan LLL ke dalam M.

____________________________________@_________________



Kolom yang ditandai dengan “@” mirip seperti solusi 101100111

dimana itu adalah jawaban yang benar.

Kesimpulan

Setelah menyadari algoritma LLL, kemudian modifikasi pun diterapkan

pada skema knapsack, mencoba untuk meningkatkan kualitas

keamanannya. Tetapi karena skema knapsack semakin berkembang, sama

halnya dengan algoritma LLL, khususnya yang diusulkan oleh Schnorr.

Shamir adalah yang pertama benar-benar menerapkan algoritma LLL untuk

mematahkan sistem kriptografi Merkle-Hellman menggunakan algoritma

pemrograman linier Lenstra dan kemudian Adleman melanjutkan

pekerjaannya dengan memperlakukan masalah kriptografi sebagai suatu

masalah lattice dari pada suatu masalah pemrograman linier. Bahkan lebih

lanjut lagi, pengembangan-pengembangan dibuat hingga semua skema

kunci public knapsack problem yang diketahui terpecahkan seluruhnya, yang

terakhir ialah skema Chor-Rivest dan skema knapsack umum.

Kegunaan lain dari knapsack dalam kriptografi termasuk penggunaan

knapsack (subset sum sebagai suatu fungsi one-way sebagi pengganti S-box

di dalam DES, diusulkan oleh Desmedt, Vandewalle dan Govaerts. Shamir

juga telah mengusulkan “provably” protocol keamanan untuk melindungi

paspor.

Nampaknya terdapat sedikit keamanan dalam menggunakan

kriptosistem berdasarkan knapsack trapdoor manapun untuk melindungi

signatures dan authenticity. Mungkin nantinya juga dapat digunakan untuk

aplikasi-aplikasi science lainnya, contohnya protocol-protokol yang

merupakan alat standar komunikasi antar mesin dalam jaringan. Tentu saja



penelitian menuju ide ini akan melibatkan pendekatanpendekatan yang

berbeda.

Nama : Adriani Yulida Kusuma

NPM : 50407039

Sumber :

http://www.math.ucsd.edu/~crypto/Projects/JenniferBakker/Math187/index.html

KNAPSACK PROBLEM DAN ALGORITMA LLL

Documents