ALGORITME LLL DAN APLIKASINYA DALAM PEMBONGKARAN SISTEMKRIPTO KNAPSACK MERKLE-HELLMAN
ARI AGUSTIANSA
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2012
ABSTRAK ARI AGUSTIANSA. Algoritme LLL dan Aplikasinya dalam Pembongkaran Sistemkripto Knapsack Merkle-Hellman. Dibimbing oleh SUGI GURITMAN dan BIB PARUHUM SILALAHI. Algoritme LLL adalah algoritme yang dapat digunakan untuk menentukan hampiran dari vektor terpendek pada suatu latis. Algoritme reduksi ukuran merupakan langkah penting pada algoritme LLL. Algoritme LLL dapat diterapkan dalam berbagai bidang. Pada karya ilmiah ini dibahas bagaimana algoritme LLL dapat digunakan dalam pembongkaran salah satu sistemkripto yang terkenal, yaitu sistemkripto knapsack Merkle-Hellman. Sistemkripto knapsack Merkle-Hellman adalah sistemkripto asimetrik yang menggunakan masalah jumlah subhimpunan sebagai tumpuan keamanan. Masalah jumlah subhimpunan dapat diubah menjadi masalah menentukan vektor terpendek pada suatu latis, sehingga algoritme LLL dapat juga digunakan untuk menyelesaikan masalah jumlah subhimpunan. Karena masalah jumlah subhimpunan dapat diselesaikan dengan mudah dengan menerapkan algoritme LLL, maka sistemkripto knapsack Merkle-Hellman juga dapat dengan mudah dihancurkan. Kata kunci: latis, algoritme LLL, sistemkripto knapsack.
ABSTRACT ARI AGUSTIANSA. LLL Algorithm and Its Application in Breaking Merkle-Hellman Knapsack Cryptosystem. Supervised by SUGI GURITMAN and BIB PARUHUM SILALAHI. LLL algorithm is an algorithm that can be used to determine an approximation of the shortest vector in a lattice. Size reduction algorithm is an important step of LLL algorithm. The LLL algorithm can be applied in many …elds. This paper shows how LLL algorithm can be used in breaking one of the famous cryptosystem, namely the Merkle-Hellman knapsack cryptosystem. Merkle-Hellman knapsack cryptosystem is an asymmetric cryptosystem using the subset sum problem as the support of security. Subset sum problem can be transformed into the problem of determining shortest vector in a lattice, so that LLL algorithm can also be used to solve the subset sum problem. Since the subset sum problem can be easily solved by applying LLL algorithm, then the Merkle-Hellman knapsack cryptosystem can also be easily be destructed. Keywords: lattice, LLL algorithm, knapsack cryptosystem.
ALGORITME LLL DAN APLIKASINYA DALAM PEMBONGKARAN SISTEMKRIPTO KNAPSACK MERKLE-HELLMAN
ARI AGUSTIANSA
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2012
Judul Skripsi
: Algoritme LLL dan Aplikasinya dalam Pembongkaran Sistemkripto Knapsack Merkle-Hellman
Nama
: Ari Agustiansa
NIM
: G54080040
Menyetujui Pembimbing I
Pembimbing II
Dr. Sugi Guritman NIP. 19620927 199203 1 004
Dr. Ir. Bib Paruhum Silalahi, M.Kom. NIP. 19670101 199203 1 004
Mengetahui Ketua Departemen Matematika
Dr. Berlian Setiawaty, MS. NIP. 19650505 198903 2 004
Tanggal Lulus : .........................................
PRAKATA Puji syukur penulis panjatkan ke hadirat Allah SWT atas segala limpahan rahmat dan karunia-Nya sehingga penulis dapat menyelesaikan karya ilmiah ini. Penyusunan karya ilmiah ini juga tidak terlepas dari dukungan doa, moril dan materiil dari berbagai pihak. Pada kesempatan ini, penulis menyampaikan terima kasih kepada : 1. Dr. Sugi Guritman dan Dr. Ir. Bib Paruhum Silalahi, M.Kom. selaku pembimbing pertama dan kedua yang telah dengan sabar membimbing penulis dalam menyusun karya ilmiah ini, 2. Dr. Paian Sianturi selaku dosen pembimbing akademik, Muhamad Ilyas, M.Si. selaku dosen penguji, dan seluruh dosen Departemen Matematika FMIPA IPB, 3. Bapak dan almarhumah Ibu tercinta atas doa, dukungan, kasih sayang, nasihat, dan kepercayaannya, 4. Retno Wulandari, yang senantiasa menemani, mendukung, membantu, dan memberi semangat kepada penulis, 5. teman-teman Matematika 45 atas segala dukungan, bantuan, dan ketulusan hati yang telah diberikan, 6. seluruh staf Departemen Matematika : Bapak Yono, Mas Heri, Ibu Ade, Bapak Acep, Ibu Susi, Mas Bono (Alm), Mas Deni yang telah membantu penulis dalam administrasi dan sebagainya. Penulis menyadari bahwa dalam tulisan ini masih terdapat kekurangan, oleh kerena itu penulis mengharapkan saran dan kritik dari semua pihak. Semoga tulisan ini bermanfaat bagi semua pihak yang memerlukan.
Bogor, Oktober 2012
Ari
RIWAYAT HIDUP Penulis dilahirkan di Jakarta, pada tanggal 22 Agustus 1990 dari pasangan Hazarin dan Zubaidah. Penulis merupakan putra kedua dari tiga bersaudara. Pada tahun 2002, penulis lulus dari SD Negeri Sunter Agung 13 Jakarta. Pada tahun 2005, penulis lulus dari SMP Negeri 116 Jakarta. Pada tahun 2008, penulis lulus dari SMA Negeri 80 Jakarta dan pada tahun yang sama penulis diterima di Departemen Matematika IPB melalui jalur USMI (Undangan Seleksi Masuk IPB) Disamping kegiatan akademis, penulis pernah menjadi asisten beberapa mata kuliah, diantaranya: Pengantar Metode Komputasi pada tahun ajaran 2010-2011, Persamaan Diferensial Biasa pada tahun ajaran 2010-2011, Pemodelan Matematika pada tahun ajaran 2011-2012, Analisis Numerik pada tahun ajaran 2012-2013. Penulis juga aktif dalam kegiatan kemahasiswaan yaitu menjadi anggota Himpunan Keprofesian Departemen Matematika IPB (Gumatika) sebagai staf divisi keilmuan.
DAFTAR ISI
Halaman DAFTAR GAMBAR .................................................................................................... viii DAFTAR LAMPIRAN ................................................................................................. viii I
PENDAHULUAN ................................................................................................. 1.1 Latar Belakang ............................................................................................. 1.2 Tujuan ..........................................................................................................
1 1 1
II
LANDASAN TEORI ............................................................................................
1
III
PEMBAHASAN ................................................................................................... 3.1 Latis dan Basis ............................................................................................. 3.2 Gram-Schmidt dan Determinan .................................................................... 3.2.1 Kompleksitas Gram-Schmidt ................................................................ 3.3 Permasalahan dalam Latis ............................................................................ 3.4 Algoritme LLL .............................................................................................. 3.4.1 Pengertian Basis Terreduksi .................................................................. 3.4.2 Reduksi Ukuran ..................................................................................... 3.4.3 Algoritme LLL dan Analisisnya ............................................................ 3.5 Sistemkripto Knapsack Merkle-Hellman ....................................................... 3.6 Pembongkaran Sistemkripto Knapsack Merkle-Hellman ...............................
3 3 6 8 9 10 10 11 18 22 24
IV
SIMPULAN DAN SARAN ................................................................................... 4.1 Simpulan ....................................................................................................... 4.2 Saran .............................................................................................................
24 24 24
DAFTAR PUSTAKA .................................................................................................... 25 LAMPIRAN .................................................................................................................. 26
vii
DAFTAR GAMBAR
Halaman Gambar 3.1: Latis dengan basis B = f(0; 1); (1; 0)g ......................................................
3
Gambar 3.2: Latis dengan basis B = f(2; 1); (3; 1)g ......................................................
3
Gambar 3.3: Latis dengan basis B = f(1; 2); (2; 1)g ......................................................
4
Gambar 3.4: Latis dengan basis B = f(1; 1)g ................................................................
4
Gambar 3.5: Parallelepiped dasar dengan B = f(2; 1); (1; 2)g..........................................
6
DAFTAR LAMPIRAN Halaman Lampiran 1: Sintaks Mathematica Algoritme LLL ....................................................... 27 Lampiran 2: Sintaks Mathematica Pembangkitkan kunci ............................................. 28 Lampiran 3: Sintaks Mathematica Enkripsi .................................................................. 28 Lampiran 4: Sintaks Mathematica menentukan solusi masalah jumlah subhimpunan ... 28 Lampiran 5: Sintaks Mathematica Dekripsi .................................................................. 29
viii
I PENDAHULUAN 1.1 Latar Belakang Latis (lattice) merupakan obyek geometrik dalam ruang dimensi-n yang diilustasikan sebagai himpunan titik-titik dengan susunan yang teratur dan periodik (Guritman 2012). Dalam latis, terdapat suatu permasalahan yang sangat mendasar, yaitu masalah menentukan vektor terpendek (shortest vector problem) yang disingkat SVP. SVP adalah suatu masalah yang sangat sulit diselesaikan dalam komputasi. Hingga pada tahun 1982, A. K. Lenstra, H. W. Lenstra, Jr, dan L. Lovasz berhasil menemukan sebuah algoritme untuk menentukan hampiran dari masalah SVP yang bernama algoritme LLL. Walaupun algoritme LLL tidak dapat menyelesaikan masalah SVP secara eksak, algoritme ini cukup ampuh dalam menjawab SVP. Sehingga algoritme ini lebih disukai karena memiliki waktu running polinomial. Setelah ditemukannya algoritme LLL, bahasan tentang latis menjadi lebih berwarna. Kini latis dapat diterapkan
pada banyak bidang ilmu komputer, seperti aljabar komputer (computer algebra), teori koding (coding theory), dan kriptologi (kriptogra… dan kriptanalisis). Salah satu yang akan dibahas dalam karya ilmiah ini adalah penerapan latis dalam membongkar sistemkripto knapsack Merkle-Hellman. Terbukti bahwa masalah latis dapat diterapkan pada pembongkaran sistemkripto knapsack Merkle-Hellman. Hal ini membuat sistemkripto knapsack Merkle-Hellman mengalami kejatuhan. 1.2 Tujuan Tujuan dari penulisan karya ilmiah ini antara lain adalah : 1. merekonstruksi ulang dan melakukan analisa pada algoritme LLL. 2. mengaplikasikan algoritme LLL dalam pembongkaran sistemkripto knapsack Merkle-Hellman. 3. mengimplementasikan proses pembongkaran sistemkripto knapsack Merkle-Hellman dalam software Mathematica 8.0.
II LANDASAN TEORI De…nisi 2.1 Jika m adalah bilangan bulat positif, maka sebuah m-tuple terurut adalah barisan m bilangan real (a1 ,a2 ,. . . ,am ). Himpunan dari semua m-tuple disebut m-ruang Euclidean dan dinotasikan sebagai Rm . (Anton 2000) De…nisi 2.2 Jika u = (u1 ; u2 ; : : : ; um ) dan v = (v1 ; v2 ; : : : ; vm ) adalah vektor-vektor yang berada dalam Rm , maka hasil kali dalam Euclidean u v dide…nisikan sebagai u v = u1 v1 + u2 v2 + ::: + um vm : (Anton 2000) De…nisi 2.3 Panjang Euclidean (atau norm Euclidean) dari sebuah vektor u = (u1 ; u2 ; : : : ; um ) dalam Rm dide…nisikan sebagai q kuk = u21 + u22 + ::: + u2m : (Anton 2000)
De…nisi 2.4 Dua vektor u dan v disebut ortogonal jika u v = 0: (Anton 2000) De…nisi 2.5 Sebuah vektor w disebut kombinasi linear dari vektor-vektor v1 ; v2 ; :::vr jika dapat diekspresikan dalam bentuk w = k1 v1 + k2 v2 + ::: + kr vr dengan k1 ; k2 ; :::kr adalah skalar. (Anton 2000) De…nisi 2.6 Jika S = fv1 ; v2 ; : : : ; vr g adalah himpunan tak kosong yang berisi vektor-vektor, maka persamaan k1 v1 + k2 v2 + ::: + kr vr = 0 memiliki minimal satu solusi, yaitu: k1 = 0,
k2 = 0,...,
kr = 0:
Jika hanya didapatkan satu solusi, maka S disebut himpunan vektor bebas linear. Jika terdapat solusi lain maka S disebut himpunan vektor bergantung linear. (Anton 2000)
2
De…nisi 2.7 Jika a dan b adalah bilangan bulat, dengan a 6= 0, dan jika terdapat sebuah bilangan bulat c sedemikian sehingga b = ac, maka kita katakan bahwa a membagi b, dan ditulis ajb. Jika a tidak membagi b, maka ditulis a - b: (Stark 1970)
De…nisi 2.11 Misalkan a dan b adalah bilangan bulat dan n sebuah bilangan bulat positif. Jika nj(a b), maka kita katakan bahwa a kongruen ke b modulo n dan kita tulis a
b mod n: (Stark 1970)
De…nisi 2.8 Sebuah bilangan bulat yang nilainya lebih besar dari nol dan hanya memunyai satu pembagi positif yaitu bilangan itu sendiri, maka bilangan tersebut disebut bilangan prima. Sebuah bilangan yang lebih besar dari satu yang bukan merupakan bilangan prima disebut bilangan komposit. (Stark 1970)
De…nisi 2.12 Misalkan S adalah subhimpunan dari R. u 2 R disebut sebagai batas atas dari S jika s u untuk semua s 2 S. Serupa dengan sebelumnya, w 2 R disebut sebagai batas bawah dari S jika w s untuk semua s 2 S.
De…nisi 2.9 Misalkan a dan b adalah bilangan positif tak nol. Dan misalkan d adalah bilangan terbesar yang berada dalam himpunan pembagi bersama dari a dan b. Maka kita sebut d adalah pembagi bersama terbesar (greatest common divisor ) dari a dan b. Dan ditulis sebagai d = gcd(a; b): (Stark 1970)
De…nisi 2.13 Misalkan S adalah subhimpunan dari R yang terbatas di atas. Sebuah batas atas dari S disebut sebagai supremum (batas atas terkecil) dari S jika nilainya lebih kecil dari batas atas yang lain dari S. Serupa dengan sebelumnya, sebuah batas bawah dari S disebut sebagai in…mum (batas bawah terbesar) dari S jika nilainya lebih besar dari batas bawah yang lain dari S.
De…nisi 2.10 Misalkan a dan b adalah bilangan bulat tak nol. Jika gcd(a; b) = 1, maka kita katakan bahwa a dan b relatif prima. (Stark 1970)
(Bartle 1964)
(Bartle 1964)
III PEMBAHASAN 3.1 Latis dan Basis Seperti yang telah dijelaskan dalam pendahuluan bahwa latis merupakan obyek geometrik dalam ruang dimensi-n yang diilustasikan sebagai himpunan titik-titik dengan susunan yang teratur dan periodik. Secara formal, de…nisi latis diberikan sebagai berikut. De…nisi 3.1 Misalkan B = fb1 ; b2 ; : : : ; bn g adalah himpunan n vektor bebas linear dalam ruang vektor Rm . Latis L(B) adalah subgrup aditif diskrit dari Rm , yang beranggotakan semua kombinasi linear intejer dari B: 8 9 n <X = L(B) = xj bj xj 2 Z : ; j=1
dengan n m. Dalam hal ini B disebut basis untuk L(B).
Dalam karya ilmiah ini, notasi " " dibaca sebagai "dengan". Seperti dalam ruang vektor, basis B untuk latis L(B) dapat diperagakan sebagai matriks B berukuran m n yang kolom-kolomnya merupakan vektor bj : B=
b1
b2
bn
.
Sehingga L(B) dapat dituliskan sebagai perkalian matriks
Dalam hal ini, matriks dari B.
B merupakan bentuk
De…nisi 3.2 Dimensi atau rank pada latis L(B) dide…nisikan sebagai banyaknya anggota pada basis B. Untuk kasus m = n, maka latis L(B) dikatakan berdimensi penuh (full dimensional ) atau disebut juga memiliki rank penuh (full rank ). Terdapat kemiripan antara pengertian latis yang dibangkitkan oleh B dengan pengertian subruang vektor dalam Rm yang direntang oleh B: 8 9 n <X = hBi = xj bj xj 2 R . : ; j=1
Perbedaannya hanya terdapat pada bilangan yang dipakai pada kombinasi linear. Pada latis L(B), kombinasi linear menggunakan koe…sien dalam rentang intejer (Z R). Sedangkan pada hBi, koe…sien pada kombinasi linear yang digunakan adalah rentang bilangan real (R). Sehingga dapat disimpulkan jika B adalah basis untuk L(B), maka B pasti juga merupakan basis untuk hBi. Namun hal ini tidak berlaku sebaliknya, jika B adalah basis untuk hBi, belum tentu B juga basis untuk L(B). Berikut merupakan contoh latis dalam R2 .
L(B) = fBx x 2 Zn g .
Gambar 3.1: Latis dengan basis B = f(0; 1); (1; 0)g
Gambar 3.2: Latis dengan basis B = f(2; 1); (3; 1)g
4
Gambar 3.3: Latis dengan basis B = f(1; 2); (2; 1)g
Gambar 3.1 dan gambar 3.2 merupakan latis Z2 yang dibangkitkan oleh basis baku B1 = f(1; 0); (0; 1)g dan basis B2 = f(2; 1); (3; 1)g. Hal ini memperlihatkan bahwa sama seperti ruang vektor, basis untuk suatu latis tidak tunggal. Pada gambar 3.3 merupakan contoh bahwa basis B3 = f(2; 1); (1; 2)g bukan merupakan basis untuk Z2 walaupun B3 memunyai rank penuh di dalam R2 . Selanjutnya gambar 3.4 merupakan sebuah contoh bahwa basis B4 = f(1; 1)g masih dapat membentuk latis L(B4 ) walaupun B4 tidak memiliki rank penuh di dalam R2 . Cara bagaimana menentukan basis lain dalam suatu latis akan dijelaskan setelah de…nisi berikut. De…nisi 3.3 Dua basis A dan B dikatakan ekuivalen, dinotasikan dengan A B, jhj A dan B membangkitkan latis yang sama, yaitu
Bukti: Misalkan U = (uij ) adalah matriks unimodular berukuran n n, dari asumsi diperoleh uij 2 Z dan det(U) = 1. Berdasarkan rumus matriks invers, maka U
De…nisi 3.4 Matriks U berukuran n n disebut unimodular jika U 2 Zn n dan det(U) = 1. matriks matriks
1
=
1 ( det(U)
T ij )
dimana ij adalah kofaktor dari uij . Karena uij 2 Z, dari de…nisi kofaktor, jelas bahwa ij 2 Z sehingga (
T ij )
2 Zn
n
.
(i)
Disamping itu, U 1U = I ) det(U 1 U) = det(I) , det(U 1 ) det(U) = 1 1 , det(U 1 ) = . det(U) Karena det(U) = det(U
L(A) = L(B).
Proposisi 3.1 Invers dari unimodular juga merupakan unimodular.
Gambar 3.4: Latis dengan basis B = f(1; 1)g
1
)=
1, maka 1 dan
1 2 Z. det(U)
(ii)
Dari (i) dan (ii), dapat disimpulkan bahwa U 1 merupakan matriks unimodular. Proposisi 3.2 Misalkan A = fa1 ; a2 ; : : : ; an g adalah basis untuk L(A) dan B = fb1 ; b2 ; : : : ; bn g adalah basis untuk L(B). Maka A B jhj ada matriks unimodular U 2 Zn n sehingga B = AU, dimana A dan B adalah bentuk matriks dari A dan B.
5
Bukti: ())Misalkan L(A) = L(B). Dari asumsi ini diperoleh bahwa untuk setiap j = 1; 2; : : : ; n, bj 2 L(A), dan dari de…nisi L(A) maka ada uj = (u1j ; u2j ; : : : ; unj ) 2 Zn sehingga bj =
n X
uij ai .
(i)
i=1
Dengan demikian, dapat dide…nisikan matriks U 2 Zn n yang kolom-kolomnya adalah vektor uj sebagai berikut. U=
u1
u2
Dan dari persamaan persamaan matriks
un (i)
diperoleh
B = AU
(ii)
dimana B =
b1
b2
bn
A =
a1
a2
an
U =
u1
u2
un
Dengan langkah-langkah yang sama, dapat diperoleh matriks V 2 Zn n sehingga A = BV
(iii)
Dari persamaan (ii) dan (iii), didapatkan A = BV ) det(A) = det(AUV) , det(U) det(V) = 1. Disamping itu, karena U dan V adalah matriks intejer, maka determinannya juga intejer. Dengan demikian, dapat disimpulkan bahwa det(U) = 1 (()Misalkan B = AU dengan U unimodular. Dari asumsi ini diperoleh bahwa untuk setiap j = 1; 2; : : : ; n, bj 2 L(A), karena bj merupakan kombinasi linear intejer dari A. Selanjutnya, karena untuk setiap x 2 L(B) merupakan kombinasi linear intejer dari B, maka dapat disimpulkan bahwa x juga merupakan kombinasi linear intejer dari A (artinya, x 2 L(A)). Dengan demikian diperoleh L(B) L(A). Kemudian perhatikan bahwa dari asumsi juga diperoleh A = BU 1 dengan U 1 juga unimodular (proposisi 3.1). Sehingga dengan langkah-langkah yang serupa dengan sebelumnya, diperoleh L(A) L(B).
Cara yang lebih mudah dalam menentukan dua basis yang ekuivalen adalah dengan menerapkan operasi kolom intejer (integer column operations) De…nisi 3.5 Operasi kolom intejer (OKI) pada matriks B memiliki 3 jenis berikut: 1. Kjk (B): menukar kolom ke-j dan kolom ke-k pada matriks B 2. Kj(-1) (B): mengalikan kolom ke-j dengan skalar -1 pada matriks B 3. Kjk( ) (B): menambahkan kolom ke-j dengan skalar 2 Z kali kolom ke-k pada matriks B OKI hampir sama dengan operasi kolom dasar (OKD) yang biasanya diterapkan pada ruang vektor. Hal yang membedakan hanya terdapat pada jenis kedua. Pada OKD, pengali yang digunakan adalah sembarang bilangan real taknol, sedangkan pada OKI pengali yang digunakan adalah -1. Kemudian misalkan I adalah matriks identitas dan K adalah serangkaian OKI yang diterapkan pada suatu matriks B dan menghasilkan matriks C, maka berlaku K(B) = C , B K(I) = C. Serangkaian OKI yang diterapkan pada I pasti akan menghasilkan matriks intejer, sehingga K(I) merupakan matriks intejer. Disamping itu, karena det(I) = 1, OKI jenis pertama dan kedua bersifat mengubah tanda determinan, dan OKI jenis ketiga bersifat tidak mengubah nilai determinan, sehingga didapatkan det(K(I)) = 1. Dengan demikian dapat disimpulkan bahwa K(I) merupakan matriks unimodular. Sehingga didapatkan proposisi berikut. Proposisi 3.3 Dua basis dikatakan ekuivalen jhj yang satu merupakan hasil serangkaian OKI dari yang lain. 3.2 Gram-Schmidt dan Determinan Salah satu bahasan dalam aljabar linear yang merupakan kunci penting dalam latis adalah proses ortogonalisasi Gram-Schmidt. Proses ini yang akan menjadi ide utama dalam pembentukan algoritme LLL. Berikut merupakan de…nisi proses ortogonalisasi Gram-Schmidt.
6
De…nisi 3.6 (Ortogonalisasi GramSchmidt (OGS)) Misalkan B = fb1 ; b2 ; : : : ; bn g adalah himpunan n vektor bebas linear dalam ruang vektor Rm . Maka dapat dikonstruksi barisan n vektor yang saling ortogonal B = fb1 ; b2 ; : : : ; bn g dimana b1 bj
= b1 , = bj
j 1 X
hB i. Sehingga dapat dide…nisikan fungsi proyeksi sebagai berikut. De…nisi 3.7 Untuk j = 1; 2; : : : ; n, fungsi proyeksi j dari ruang vektor V = hB i = hBi ke subruang vektor fbj ; bj+1 ; : : : ; bn g dide…nisikan sebagai j (v)
=
n X i=j
ji bi ,
v bi bi bi
bi .
i=1
dengan j = 2; 3; : : : ; n, dan ji
=
bj bi bi bi
Jika himpunan B = fb1 ; b2 ; : : : ; bn g adalah bebas linear, maka B merupakan basis untuk hBi, dan jika B = fb1 ; b2 ; : : : ; bn g adalah hasil OGS dari B, maka B juga merupakan basis untuk hBi. Namun hal ini secara umum tidak berlaku dalam latis, jika B adalah basis untuk L(B) tidak harus B merupakan basis untuk L(B). Bahkan belum tentu B L(B). DalamP ruang vektor, vektor j 1 pj = b merupakan vektor i=1 ji i proyeksi dari bj pada subruang vektor fb1 ; b2 ; : : : ; bj 1 g dari hB i. Sedangkan bj merupakan vektor proyeksi dari bj pada subruang vektor fbj ; bj+1 ; : : : ; bn g dari
Jika diambil nilai v = 1; 2; : : : ; n, maka diperoleh 8 < 0 b j (bk ) = : k Pk 1 bk + i=j ki bi
bk , k
=
jika k < j jika k = j jika k > j
Selanjutnya perhatikan de…nisi berikut.
De…nisi 3.8 Misalkan = L(B) adalah latis yang dibangkitkan oleh basis B = fb1 ; b2 ; : : : ; bn g, maka dapat dide…nisikan himpunan 8 9 n <X = P(B) = xj bj xj 2 R; 0 xj < 1 . : ; j=1
Dimana P(B) merupakan bangun geometrik yang disebut parallelepiped dasar atau daerah fundamental (fundamental region). Berikut ilustrasi dari P(B).
Gambar 3.5: Parallelepiped dasar dengan B = f(2; 1); (1; 2)g
7
Dari gambar 3.5 terlihat bahwa pada latis dalam R2 , P(B) digambarkan sebagai daerah arsir bidang jajaran genjang. Hasil dari luas jajaran genjang pada gambar 3.5 disebut vol(P(B)). Pada sembarang latis , dapat dide…nisikan nilai determinan dari latis , dinotasikan dengan det( ), yang merupakan nilai dari vol(P(B)). Dari ilustrasi gambar 3.5, maka de…nisi det( ) dapat dinyatakan sebagai berikut. De…nisi 3.9 Misalkan = L(B) adalah latis yang dibangkitkan oleh basis B = fb1 ; b2 ; : : : ; bn g dan B = fb1 ; b2 ; : : : ; bn g adalah hasil OGS dari B. Determinan dari dide…nisikan sebagai det( ) =
n Y
i=1
b2
dimana B adalah bentuk matriks dari B.
b1
b1
b2
,
maka ada matriks U dengan unsur diagonal adalah 1 sehingga
b1
B=
b2
bn
B = B U. Dengan demikian diperoleh T
BT B = (B U) (B U) , BT B = UT (B )T B U T
Bukti: Perhatikan bahwa rumus OGS dapat diubah menjadi
bn
= b1 = b2 + 21 b1 = b3 + ( 31 b1 + .. . n X1 = bn + ni bi
32 b2 )
Hal ini menunjukkan bahwa transformasi balik OGS dari B ke B merupakan serangkaian OKD yang dilakukan pada matriks B, yaitu B = K(B ) , B = B K(I). demikian
dapat
dide…nisikan
U
T
, det(B B) = det (B ) B !2 n Y T , det(B B) = kbi k i=1
,
i=1
Dengan
,
) det(BT B) = det UT (B )T B
B=B U
b1 b2 b3
bn
menurut lemma 2.1 terdapat sebuah matriks U yang unsur diagonalnya adalah 1 sehingga
bn
bn
b2
adalah matriks hasil OGS dari matriks
adalah matriks hasil OGS dari matriks B=
C C C A
Proposisi 3.4 Jika = L(B) adalah latis yang dibangkitkan oleh basis B = fb1 ; b2 ; : : : ; bn g, maka q det( ) = det(BT B)
B =
Lemma 3.1 Jika matriks b1
1
Bukti: Misalkan
kbi k .
Cara menentukan determinan suatu latis tanpa melakukan OGS akan dijelaskan oleh proposisi setelah lemma berikut ini.
B =
sebuah matriks U =K(I), dimana 0 1 21 n1 B 0 1 n2 B K(I) = B . .. .. . . . @ . . . . 0 0 0 1
n Y
i=1
kbi k =
, det( ) =
q
det(BT B)
q
det(BT B)
Berikut merupakan proposisi yang menjelaskan bahwa determinan suatu latis tidak bergantung pada pemilihan suatu basis. Proposisi 3.5 Jika A det(L(A)) = det(L(B)).
B,
maka
Bukti: Misalkan A B, dengan A dan B adalah bentuk matriks dari A dan B.
8
Berdasarkan proposisi 3.2 terdapat sebuah matriks unimodular U sehingga A = BU. Dengan demikian, q det(AT A) det(L(A)) = q T = det((BU) (BU)) q = det(UT (BT B)U) q = det(BT B) =
det(L(B))
3.2.1 Kompleksitas Gram-Schmidt Dalam OGS terlihat bahwa banyaknya operasi aritmetik yang dilibatkan dalam OGS adalah O(n3 ). Namun belum dapat disimpulkan bahwa waktu running pada OGS adalah polinomial. Harus dipastikan terlebih dahulu bahwa bilangan-bilangan yang diproses pada OGS tidak tumbuh terlalu besar. Diasumsikan bahwa matriks B yang digunakan adalah matriks intejer. Perhatikan bahwa langkah ke-j dari OGS dapat dirumuskan ulang sebagai bj = bj +
j 1 X i=1
vji bi untuk suatu vji 2 R
(3.1) Karena bj ortogonal ke bt untuk setiap t < j, maka diperoleh ! j 1 X bt bj = (bt bj ) + bt vji bi i=1
, 0 = (bt bj ) + j 1 X
, bt
vji bi =
bt
vji bi
i=1
!
(bt bj )
(3.2)
i=1
Untuk t = 1; 2; : : : ; j tersebut bisa ditulis dalam Pj 1 0 1 b1 i=1 vji bi P j 1 B b2 C i=1 vji bi C B B C= .. A @ . Pj 1 bj 1 i=1 vji bi Jika dide…nisikan matriks Bj
j 1 X
1
=
b1
b2
1, Persamaan bentuk matriks 0 1 b1 bj B b2 bj C B C B C .. @ A . bj
bj
1
1
bj
dan matriks
0
B B uj = B @
1
vj1 vj2 .. . vj;j
1
C C C A
maka persamaan (3.2) dapat ditulis sebagai 0 1 0 1 b1 bj b1 (Bj 1 uj ) B b2 bj C B b2 (Bj 1 uj ) C B C B C C B C= B .. .. @ A @ A . . bj
1
(Bj
1 uj )
, BTj 1 (Bj
, (BTj 1 Bj
bj
1
bj
1 uj )
=
BTj 1 bj
1 )uj
=
BTj 1 bj(3.3)
Persamaan 3.3 merupakan SPL dengan matriks koe…sien BTj 1 Bj 1 dan vektor BTj 1 bj adalah intejer. Dengan demikian, untuk s = 1; 2; : : : ; j 1, berdasarkan aturan Cramer diperoleh vjs 2
Z det(BTj 1 Bj
1)
=
Z det(L(B j
2 1 ))
Hasil ini akan digunakan untuk memberi batas pada koe…sien Misalkan ji . Dj 1 = det(BTj 1 Bj 1 ) dan dikalikan nilainya kedua ruas dari persamaan 3.1 maka diperoleh j 1 X Dj 1 bj = Dj 1 bj + (Dj
1 vji )bi
i=1
merupakan persamaan yang semua koe…sien vektornya adalah intejer. Ini berarti semua penyebut dari bilangan dalam vektor bj adalah faktor dari Dj 1 . Kemudian bj bi ji = bi bi Di 1 (bj bi ) = Di 1 (bi bi ) bj (Di 1 bi ) Z ! = 2 iY 1 Di 2 2 kbs k kbi k s=1
Hasil ini menunjukkan bahwa penyebut dari ji harus membagi Di . Uraian di atas membuktikan bahwa bilangan-bilangan yang ada di dalam vektor bi dan ji memunyai penyebut paling banyak max Dk k
n Y
i=k
2
kbk k
9
Akhirnya, besarnya bilangan juga kbj k. polinomial karena bj Dengan demikian secara keseluruhan OGS memunyai kompleksitas waktu running polinomial. Hasil ini bermanfaat untuk menganalisis algoritme LLL yang merupakan algoritme yang berbasiskan OGS. 3.3 Permasalahan dalam Latis Berikut merupakan pengertian jarak minimum dan panjang vektor minimum dari suatu latis.
Bukti: Ambil sembarang v 2 L(B) dengan v 6= 0, maka ada vektor x 2 Zn dengan x 6= 0 sehingga v = Bx dengan B adalah bentuk matriks dari B. Misalkan x = fx1 ; x2 ; : : : ; xn g dan k adalah indeks terbesar dari komponen x sehingga xk 6= 0; Karena untuk setiap j < k, bk ortogonal ke bj dan juga ortogonal ke bj , maka =
(Bx) bk 0 1 k X = @ xj bj A bk
v bk
De…nisi 3.10 Jarak minimum antara sembarang dua titik di dalam latis , dinotasikan dengan ( ), dide…nisikan sebagai ( ) = inffkx
yk
x; y 2
; x 6= yg
x2
= xk (bk bk ) dan
De…nisi 3.11 Panjang vektor minimum di antara titik-titik di dalam latis , dinotasikan dengan ( ), dide…nisikan sebagai ( ) = inffkxk
j=1
; x 6= 0g
0
k X1
= @bk
bk bk
kj bj
j=1
= bk bk .
1
A bk
Dengan demikian diperoleh v bk
= xk (bk bk ) 2
Dua pengertian di atas memiliki arti yang ekuivalen. Hal tersebut dinyatakan dalam proposisi berikut. Proposisi 3.6 Untuk sembarang latis berlaku
,
( ) = ( ). Bukti: Karena ( )
adalah grup, maka berlaku
= inffkx yk x; y 2 ; x 6= yg = inffkzk z = x y 2 ; x 6= yg = inffkzk z 2 ; z 6= 0g = ( )
Berikut merupakan batas bawah dari . Teorema 3.1 Jika = L(B) adalah latis yang dibangkitkan oleh basis B = fb1 ; b2 ; : : : ; bn g dan B = fb1 ; b2 ; : : : ; bn g adalah hasil ortogonalisasi dari B, maka min bj
j2In
( ), In = f1; 2; : : : ; ng
= xk kbk k
) jv bk j = jxk j kbk k
2
Berdasarkan ketaksamaan Cauchy-Schwartz, maka diperoleh , ,
jv bk j
jxk j kbk k jxk j kbk k
Karena jxk j diperoleh
2
kvk kbk k
kvk kbk k kvk
1, untuk In = f1; 2; : : : ; ng
min bj
j2In
kbk k kvk
Selanjutnya, karena v adalah sembarang vektor dalam L(B), maka dapat disimpulkan min bj
j2In
( )
Selanjutnya akan dide…nisikan masalah yang paling mendasar di dalam latis, yaitu SVP. Berikut merupakan varian dari SVP.
10
Soal 3.1 (Pelacakan SVP) Diberikan sebuah latis dengan basis B, carilah x 2L(B) sehingga kxk = (L(B)) Soal 3.2 (Optimisasi SVP) Diberikan sebuah latis dengan basis B, carilah (L(B)). Soal 3.3 (Pelacakan SVP) Diberikan sebuah latis dengan basis B dan bilangan rasional q 2 Q, tentukan apakah (L(B))
q atau (L(B)) > q
Soal 3.4 (Pelacakan SVP) Diberikan sebuah latis dengan basis B dan 1, carilah x 2L(B) dengan x 6= 0 sehingga kxk
(L(B))
2
bj
bj+1 +
2 j+1;j )
, (
(L(B))
d
3.4 Algoritme LLL 3.4.1 Pengertian Basis Terreduksi Berikut merupakan de…nisi dari basis terreduksi . De…nisi 3.12 Suatu basis B = [b1 ; b2 ; : : : ; bn ] dalam Rm disebut terreduksi (atau terreduksi LLL dengan parameter ) jika memenuhi 1 1. ji 2 , untuk setiap intejer i; j, dengan 1 i < j n, 2 2 2. k j (bj )k k j (bj+1 )k , untuk j = 1; 2; : : : ; n 1, dimana merupakan parameter reduksi yang bernilai real dengan 14 < < 1. Syarat pertama dalam de…nisi di atas disebut dengan reduksi ukuran. Syarat pertama mengatakan bahwa basis terreduksi harus "hampir ortogonal" dan dalam komputasinya syarat ini mudah dicapai OGS. Pembahasan mengenai syarat pertama akan dibahas pada subbab 3.4.2. Sedangkan pada syarat kedua dari de…nisi di atas disebut syarat pertukaran, atau disebut juga kondisi Lovasz, yang
j+1;j bj
2
bj
2 2
bj+1 (3.5) .
Ketaksamaan 3.5 menyatakan bahwa vektor-vektor Gram-Schmidt dari basis terreduksi LLL harus terurut turun dengan 2 faktor penurunan sebesar j+1;j . Jika terdapat pasangan vektor (bj ; bj+1 ) yang tidak memenuhi kondisi Lovasz, maka dapat dilakukan pertukaran antara vektor tersebut kemudian OGS kembali dilakukan. Selanjutnya dengan menerapkan syarat-syarat yang terdapat pada de…nisi 3.12, maka didapatkan batas atas untuk kb1 k dari basis terreduksi . Teorema 3.2 Jika B = [b1 ; b2 ; : : : ; bn ] dalam Rm adalah basis terreduksi , maka berlaku n
kb1 k
Soal 3.5 (Pelacakan SVP) Diberikan sebuah latis dengan basis B dan 1, carilah d sehingga d
dapat ditulis ulang sebagai
dengan
1
=
1 4
1
( )
2
.
Bukti: Misalkan B = [b1 ; b2 ; : : : ; bn ] adalah basis terreduksi , dari de…nisi didapatkan bj+1
2
2 j+1;j )
(
1 4 1
, bj
2
2
2
bj 2
bj
bj+1
bj
2
(i)
Maka dengan menerapkan ketaksamaan (i) secara berulang, diperoleh 2
2
kb1 k
kb2 k
2
.. .
kb3 k
n 1
2
2
kbn k .
Atau dengan kata lain, secara umum untuk setiap j 2 In = f1; 2; : : : ng, berlaku 2
kb1 k )
kb1 k
,
kb1 k
j 1 j
1 2
j
1 2
bj
2
bj bj
Karena berlaku untuk setiap j 2 In , maka kb1 k
n
1 2
min bj
j2In
(ii)
11
Misalkan B = [b1 ; b2 ; : : : ; bn ] adalah basis terreduksi LLL untuk latis = L(B), menurut teorema 3.1 diperoleh ( )
min bj
j2In
sehingga ketaksamaan (ii) menjadi kb1 k
n
1 2
bwj e 2 Z sehingga wj = bwj e + tj , dengan
w
n X
=
j=1 n X
=
j=1
3.4.2 Reduksi Ukuran Sebagaimana telah dinyatakan sebelumnya bahwa syarat reduksi ukuran 1 (yaitu ji 2 ) mudah dicapai dengan menggunakan OGS. Selanjutnya akan dibahas syarat reduksi ukuran melalui interpretasi geometrik. Untuk akan dibahas terlebih dahulu de…nisi berikut. De…nisi 3.13 Misalkan = L(B) adalah latis yang dibangkitkan oleh basis B = [b1 ; b2 ; : : : ; bn ] dalam ruang vektor Rm . Daerah fundamental terpusat (centered fundamental region) dari , dinotasikan dengan C(B), dide…nisikan sebagai: 8 9 n <X 1= 1 C(B) = xj bj xj 2 R; xj . : 2 2;
tj
1 . 2
Selanjutnya,
( )
Teorema 3.2 menyatakan bahwa vektor pertama pada basis terreduksi merupakan jawaban dari soal 3.4 dengan nilai = n 1 2 .
1 2
(bwj e + tj ) bj bwj e bj +
= v+t
n X tj bj j=1
Lemma 3.2 Misalkan B = [b1 ; b2 ; : : : ; bn ] adalah hasil proses ortogonalisasi Gram-Schmidt dari himpunan bebas linear B = [b1 ; b2 ; : : : ; bn ], danPdiberikan n sembarang w 2 hBi. Jika w = j=1 wj bj , maka w bn wn = bn bn Bukti: Perhatikan bahwa 0 w bn
1 n X = @ wj bj A bn j=1
n X = wj (bj bn ) j=1
= wn (bn bn )
j=1
C(B) juga disebut parallelepiped dasar terpusat (centered fundamental parallelepiped ).
Proposisi 3.7 Jika = L(B) adalah latis yang dibangkitkan oleh basis B = [b1 ; b2 ; : : : ; bn ] dalam ruang vektor Rm , maka untuk setiap vektor w 2 hBi, ada tepat satu vektor t 2 C(B) sehingga dapat dituliskan w = v + t
, wn =
Selanjutnya akan ditunjukkan bahwa bn bn = bn bn , ! n X1 bn bn = bn + bn ni bi i=1
= bn bn +
w=
n X wj bj . j=1
Kemudian, karena wj 2 R, maka ada
n X1
ni
(bi bn )
i=1
= bn bn Bukti: Karena B merupakan basis untuk , maka B juga merupakan basis untuk ruang vektor hBi. Dan karena w 2 hBi, maka ada tepat satu (w1 ; w2 ; : : : ; wn ) 2 Rn sehingga
w bn bn bn
Sifat dari daerah fundamental terpusat dinyatakan dalam proposisi berikut. Proposisi 3.9 Jika B = [b1 ; b2 ; : : : ; bn ] adalah hasil OGS dari basis latis B = [b1 ; b2 ; : : : ; bn ], maka setiap w 2 hBi, ada tepat satu vektor latis v 2 L(B) dan ada tepat satu vektor t 2 C(B ) sehingga dapat
12
dituliskan
dituliskan w = v + t. Bukti: Demi kepentingan bagaimana menentukan v dan t secara algoritmik, proposisi akan dibuktikan secara instruktif. Kemudian, tanpa mengurangi keumuman, akan diambil untuk kasus n = 3 sebagai berikut. 1. De…nisikan w3 = w. Karena w3 2 hfb1 ; b2 ; b3 gi, berarti ada tepat satu (x31 ; x32 ; x33 ) 2 R3 sehingga w3 =
w2 b2 b2 b2 b2 w2 b2 = x21 b1 + + b2 b2 t2 )b2 = x21 b1 +
w2
1 2
dengan
2 X x3j bj +
=
j=1
w2 b2 b2 + b2 b2 t2 (b2 + 21 b1 )
dapat w2 b2 b2 + t2 b2 = b2 b2 x21 b1 + t2 21 b1 = (x21 + t2 21 )b1 (ii)
, w2
w3 b3 + b3 b3
3. De…nisikan w1 = w2
t3 b3 ) dengan =
w3
1 2
t3
1 2.
Selanjutnya,
2 X x3j bj +
w3 b3 b3 + b3 b3
j=1
t3 b3 )
=
2 X w3 b3 b3 + x3j bj + b3 b3 j=1 ! 2 X t3 b3 + 3i bi i=1
,
w3
w3 b3 b3 + (t3 b3 ) = b3 b3
2 2 X X x3j bj + t3 j=1
1 dengan 21 t1 Dari ketiga 2. langkah di atas, didapatkan bahwa
w1
(i)
3i bi
w2
i=1
= w3
w3 b3 b3 + b3 b3
t3 b3 ). Dari persamaan (i) dan karena hfb1 ; b2 gi = hfb1 ; b2 gi, maka w2 2 hfb1 ; b2 gi. Dengan ada tepat satu (x21 ; x22 ) 2 R2 sehingga w2 = x21 b1 + x22 b2 dan berdasarkan lemma 3.2,
dapat
w2 b2 b2 + t2 b2 . b2 b2
Dari persamaan (ii), maka w1 2 hfb1 gi dan ada x11 2 R sehingga w1 = x11 b1 . Berdasarkan lemma 3.2, dapat dituliskan w1 b1 w1 = b1 b1 b1 w1 b1 = + t1 b1 b1 b1 w1 b1 b1 + t1 b1 = b1 b1
2. De…nisikan w2
w2 b2 b2 + b2 b2
= x21 b1 +
2 X w3 b3 b3 x3j bj + b3 b3 j=1
=
Selanjutnya,
t2 b2
j=1
w3
1 2.
= x21 b1 +
w2
3 X x3j bj
dan berdasarkan lemma 3.2, dituliskan
t2
w3
w1 b1 b1 + t1 b1 b1 b1 w2 b2 = w1 + b2 + t2 b2 b2 b2 w3 b3 = w2 + b3 + t3 b3 b3 b3 =
Karena w = w3 , maka dapat dituliskan w =v+t dimana w1 b1 w2 b2 b1 + b2 + b1 b1 b2 b2 w3 b3 b3 b3 b3 t = t1 b1 + t2 b2 + t3 b3
v
=
13
dan dapat dilihat bahwa v 2 L(B) dan t 2 C(B )
ortogonalisasi Gram-Scmidt dari B 0 . Dalam hal ini,
Bukti dari proposisi sekaligus merupakan bukti kebenaran dari algoritme berikut. Algoritme 3.1 Input: B = [b1 ; b2 ; : : : ; bn ] basis untuk L(B) dan w 2 hBi. Output: Vektor latis v 2 L(B) dan vektor t 2 C(B ). 1. Dengan OGS, hitung [b1 ; b2 ; : : : ; bn ] dengan input B. 2. v := 0 3. t := 0 4. Untuk i = n; n 1; : : : ; 1, lakukan: wb a. xi := b bi i i b. vi := bxi e c. v := v + vi bi d. ti := xi vi e. t := t + ti bi f. w := w (vi bi + ti bi ) 5. return(v dan t) Algoritme di atas dapat disederhanakan hanya untuk menentukan vektor v sebagai berikut. Algoritme 3.2 (Menentukan vektor terdekat) Input: B = [b1 ; b2 ; : : : ; bn ] basis untuk L(B) dan w 2 hBi. Output: Vektor latis v 2 L(B) 1. Dengan OGS, hitung [b1 ; b2 ; : : : ; bn ] dengan input B. 2. v := 0 3. Untuk i = n; n 1; : : : ; 1, lakukan: wb a. xi := b bi i i b. vi := bxi e c. v := v + vi bi d. ti := xi vi e. w := w (vi bi + ti bi ) 4. return(v) Akibat dari proposisi 3.7 diberikan dalam teorema berikut. Teorema 3.3 Jika B = [b1 ; b2 ; : : : ; bn ] adalah hasil proses ortogonalisasi Gram-Scmidt dari basis latis B = [b1 ; b2 ; : : : ; bn ], maka B dapat ditransformasikan menjadi B0 = 0 0 0 [b1 ; b2 ; : : : ; bn ] yang juga merupakan basis untuk L(B) dan B juga merupakan hasil
b1
= b01
bj
= b0j
j 1 X
0 ji bi
i=1
untuk j = 2; 3; : : : ; n, dengan 0 ji
=
b0j bi dan bi bi
0 ji
1 : 2
Bukti: Transformasi dari B ke B 0 akan dilakukan secara instruktif sebagai berikut. 1. De…nisikan b01 = b1 Dalam hal ini, diperoleh subruang vektor berdimensi-1, yaitu S1
= hfb1 gi = hfb01 gi = hfb1 gi
2. Dari proses ortogonalisasi b2 ke b2 berlaku hubungan b2 = b2
p1 b b
dengan p1 = 21 b1 = b2 b1 b1 adalah 1 1 vektor proyeksi dari b2 pada S1 berarti p1 2 S1 . Dengan demikian, berdasarkan proposisi 3.6, ada vektor latis v1 2 L(fb1 g) dan vektor t1 2 C(fb1 g) sehingga p1 = v1 + t1 dan diperoleh b2
= b2 (v1 + t1 ) = (b2 v1 ) t1 .
Kemudian dari persamaan di atas dapat dide…nisikan b02 = b2
v1
sehingga jelas (karena latis adalah grup) bahwa b02 2 L(B) dan diperoleh persamaan b2 = b02
t1 .
Hasil ini menunjukkan bahwa ortogonalisasi fb01 ; b02 g juga menghasilkan fb1 ; b2 g dengan vektor proyeksi dari b02
14
dalam hal ini, untuk i = 1; 2, berlaku
pada S1 adalah =
t1
=
0 21 b1 b02 b1
b1 b1
0 3i 0 3i j
=
21
b
21 e
1 sehingga j 021 j 2 . Selanjutnya, untuk 0 menghitung b2 berarti ukup menghitung v1 menggunakan algoritme 3.2 dan
b02 = b2
v1
Sebelum ke langkah berikutnya, dinotasikan terlebih dahulu subruang vektor berdimensi-2, yaitu S2
= hfb1 ; b2 gi = hfb01 ; b02 gi = hfb1 ; b2 gi
3. Dari proses ortogonalisasi b3 ke b3 berlaku hubungan b3 = b3
p2
dengan p2 =
31 b1
+
32 b2
p2 dimana adalah vektor proyeksi dari b3 pada S2 berarti p2 2 S2 . Dengan demikian,berdasarkan proposisi 3.6, ada vektor latis v2 2 L(fb1 ; b2 g) dan vektor t2 2 C(fb1 ; b2 g) sehingga p2 = v2 + t2 dan diperoleh b3
= b3 (v2 + t2 ) = (b3 v2 ) t2 .
Kemudian dari persamaan di atas dapat dide…nisikan b03 = b3
v2
sehingga jelas bahwa b03 2 L(B) dan diperoleh persamaan b3 = b03
t3 .
Hasil ini menunjukkan bahwa ortogonalisasi b03 juga menghasilkan b3 dengan vektor proyeksi dari b03 pada S2 adalah t1
= =
0 31 b1 + b03 b1
b1 b1
0 32 b2 b03
b1 +
b2
3i
b
1 2. b03
3i e
sehingga j Selanjutnya, untuk menghitung berarti cukup menghitung v2 menggunakan algoritme 3.2 dan
b1
dalam hal ini 0 21
=
b2 b b2 2
b03 = b3
v2
Demikian seterusnya, dari 3 langkah di atas secara rekursuf dapat dilanjutkan sampai langkah ke-n untuk memperoleh basis latis B 0 hasil transformasi dari basis latis B. Makna geometrik dari transformasi B ke B 0 dalam teorema 3.3 beserta buktinya adalah memperkecil panjang vektor basis, yaitu untuk j = 1; 2; : : : ; n berlaku kbj k b0j . Hal ini terlihat dari vektor proyeksi pi 1 hasil proyeksi dari bi ke subruang Si 1 untuk i = 2; 3; : : : ; n, ditransformasikan ke vektor proyeksi ti 1 , hasil proyeksi dari b0i ke subruang Si 1 . Jika pi 1 2 C([b1 ; b2 ; : : : ; bi 1 ]), maka bi b0i , tetapi jika pi 1 2 = C([b1 ; b2 ; : : : ; bi 1 ]), maka bi ditransformasikan b0i dengan vektor proyeksi pada Si 1 adalah t 2 C([b1 ; b2 ; : : : ; bi 1 ]) sehingga kbi k kb0i k. Dengan demikian, teorema 3.3 beserta buktinya merupakan landasan teori yang digunakan untuk menyusun algoritme reduksi ukuran dari algoritme LLL berikut ini. Algoritme 3.3 (Reduksi Ukuran LLL) Input: B = [b1 ; b2 ; : : : ; bn ] basis untuk L(B) Output: B = [b1 ; b2 ; : : : ; bn ] adalah hasil proses ortogonalisasi Gram-Schmidt dari B dan B 0 = [b01 ; b02 ; : : : ; b0n ] adalah hasil reduksi ukuran dari B 1. b1 := b1 2. b01 := b1 . 3. Untuk j = 2; 3; : : : ; n, lakukan: a. p := 0 b. Untuk i = 1; 2; : : : ; j 1, lakukan: b b i. ji := bj bi i i ii. p := p + ji bi c. Gunakan algoritme 3.2 untuk menghitung vektor v dengan input B = [b1 ; b2 ; : : : ; bn ] dan B = [b1 ; b2 ; : : : ; bn ] serta p d. b0j := bj v 4. return([b1 ; b2 ; : : : ; bn ]
15 dan [b01 ; b02 ; : : : ; b0n ])
penyusunan algoritme reduksi ukuran LLL yang sifatnya rekursif tanpa memanggil algoritme 3.2
Berikut ini langkah-langkah ilustratif
1. Untuk j = 1, de…nisikan langsung b1 := b1 dan b01 := b1 2. Untuk j = 2, perhatikan bahwa p1 =
21 b1 ,
berdasarkan algoritme 3.2, maka
p b1 b1 b1 b1 = b 21 e b1 =
v1
Jadi, untuk menghitung b2 dan b02 , cukup menghitung dahulu = b2 = b2
b2
21 ,
kemudian
p1 21 b1
dan b2
= b2 = b2
3. Untuk j = 3, perhatikan bahwa p2 = nyatakan v2 = v22 + v21 sehingga v22
v21
v1 b 21 e b1 31 b1
+
32 b2 ,
berdasarkan algoritme 3.2,
(p2 b2 b1 b2 b2 = b 32 e b2 0 p2 b 32 e b2 32 b2 ) b1 b1 = b1 b1 = b 31 b 32 e 21 e b1 =
Jadi, untuk menghitung b3 dan b03 , dapat dilakukan secara rekursif sebagai berikut. (a) untuk i = 2, hitung 32 , kemudian b3 = b3
32 b2
dan b03 (b) untuk i = 1, hitung
31 ,
= b3 = b3
v22 b 32 e b2
kemudian b3 = b3
31 b1
dan b03
= b03 = b03
4. Untuk j = 4, perhatikan bahwa p3 =
v21 b 31 41 b1
+
b
32 e ( 21 )e b1
42 b2
+
43 b3 ,
berdasarkan algoritme
16
3.2, nyatakan v3 = v33 + v32 + v31 sehingga v33
= = =
v32
= =
v31
= =
p3 b3 b3 b3 b3 ( 43 b3 ) b3 b3 b3 b3 b 43 e b3 (p ( b 43 e b3 + 043 b3 )) b2 b2 b2 b2 b 42 b 43 e ( 32 )e b2 (p ( b 43 e b3 + 043 b3 ) (b 42 e b2 + b1 b1 b 41 b 43 e 31 b 42 e 21 e b1
0 42 b2 )
b1
b1
Jadi, untuk menghitung b4 dan b04 , dapat dilakukan secara rekursif sebagai berikut (a) untuk i = 3, hitung 43 , kemudian b4 = b4
43 b3
dan b04 = b4 (b) untuk i = 2, hitung
42 ,
b
43 e b3
kemudian b4 = b4
42 b2
dan b04 = b04 (c) untuk i = 1, hitung
41 ,
b
b
42
43 e
32 e b3
kemudian b4 = b4
41 b1
dan b04 = b04
b
41
Berdasarkan pola dari 4 langkah di atas, berikut ini diberikan algoritme reduksi ukuran yang sifatnya rekursif. Algoritme 3.4 (Reduksi Ukuran LLL) Input: B = [b1 ; b2 ; : : : ; bn ] basis untuk L(B) Output: B = [b1 ; b2 ; : : : ; bn ] adalah hasil proses ortogonalisasi Gram-Schmidt dari B dan B 0 = [b01 ; b02 ; : : : ; b0n ] adalah hasil reduksi ukuran dari B. 1. b1 := b1 2. b01 := b1 b b 3. 21 := b2 b1 1 1 4. b2 := b2 21 b1 5. b02 := b2 b 21 e b1 6. Untuk j = 3; 4; : : : ; n, lakukan: (a) bj := bj (b) bj := bj
b
43 e
31
(c)
b
42 e
j;j 1
:=
21 e b3
bj bj 1 bj 1 bj 1
(d) bj := bj j;j 1 bj 1 (e) b0j := b0j j;j 1 bj 1 (f) Untuk i = j 2; j 3; : : : ; 1, lakukan: b b i. ji := bj bi i i ii. bj := bj ji bi iii. c := ji iv. Untuk k = i; i + 1; : : : ; j 2, lakukan: A. c := c j;k+1 k+1;i v. b0j := b0j bce bi 7. return([b1 ; b2 ; : : : ; bn ] dan [b01 ; b02 ; : : : ; b0n ]) Berikut ini merupakan langkah-langkah ilustratif penyusunan algoritme reduksi ukuran LLL dengan menggunakan rumus rekursif yang lebih sederhana
17
1. Untuk j = 1, de…nisikan langsung b1 = b1 dan b01 = b1 2. Untuk j = 2, perhatikan bahwa p1 = v1
21 b1 ,
berdasarkan algoritme 3.2, maka
p1 b1 b1 b1 b1 = b 21 e b1 =
Jadi, untuk menghitung b2 dan b02 cukup menghitung dahulu b2
= b2 = b2
21 ,
kemudian
p1 21 b1
dan b02
= b2 = b2
v1 b 21 e b1
3. Untuk j = 3, dari uraian sebelumnya, b03
= =
(b3 (b3
= x x
y
b
32 e b2 )
b
32 e b2 )
b
31
(b3
b 32 e 21 e b1 b 32 e b2 ) b1 b1 b1 b1
y
= b3 b 32 e (b02 + b 21 e b1 ) = b3 b 32 e b02 b 32 e b 21 e b1 (b3 b 32 e (b02 b 21 e b1 )) b1 = b1 b1 b1 (b3 b 32 e b02 b 32 e b 21 e b1 ) b1 b1 = b1 b1 (b3 b 32 e b02 ) b1 = b 32 e b 21 e b1 b1 b1 (b3 b 32 e b02 ) b1 b1 b 32 e b 21 e b1 = b1 b1
Dengan demikian, diperoleh b03 = (b3
b
0 32 e b2 )
(b3
b 32 e b02 ) b1 b1 b1 b1
Jadi,untuk menghitung b3 dan b03 , dapat dilakukan secara rekursif sebagai berikut (a) untuk i = 2, hitung 32 , kemudian b3 = b3
32 b2
dan b03 = b3 (b) untuk i = 1, hitung
31 ,
b
0 32 e b2
kemudian b3 = b3
31 b1
dan b03 = b03
b03 b1 b1 b1 b1
18
Berdasarkan pola dari 3 langkah di atas, berikut ini diberikan algoritme reduksi ukuran yang sifatnya rekursif Algoritme 3.5 (Reduksi Ukuran LLL) Input: B = [b1 ; b2 ; : : : ; bn ] basis untuk L(B) Output: B = [b1 ; b2 ; : : : ; bn ] adalah hasil proses ortogonalisasi Gram-Schmidt dari B dan B 0 = [b01 ; b02 ; : : : ; b0n ] adalah hasil reduksi ukuran dari B. 1. b1 := b1 2. b01 := b1 3. Untuk j = 2; 3; : : : ; n, lakukan: (a) Untuk i = j 1; j 2; : : : ; 1, lakukan: b b i. ji := bj bi i i ii. bj := bj ji bi iii.
b0j bi 0 ji := bi bi b0j := b0j
0 iv. ji bi 4. return([b1 ; b2 ; : : : ; bn ] dan [b01 ; b02 ; : : : ; b0n ])
1. (Langkah Reduksi Ukuran) Terapkan algoritme reduksi ukuran pada B. 2. (Langkah Penukaran) Jika ada j 2 f2; 3; : : : ; ng yang memenuhi (
j;j 1 )
bj
2
1
> bj
Algoritme 3.6 (Algoritme LLL) Input: B = [b1 ; b2 ; : : : ; bn ] basis untuk L(B) dan 41 < < 1. Output: B = [b1 ; b2 ; : : : ; bn ] adalah basis terreduksi LLL untuk L(B) dan B = [b1 ; b2 ; : : : ; bn ] adalah hasil proses ortogonalisasi Gram-Schmidt dari B. 1. Inisialisasi b1 := b1 . 2. j := 2. 3. Reduksi Ukuran. Sementara j n, hitung: (a) bj := bj . (b) Untuk i = j 1 s.d. i = 1, hitung: b b i. ji := bj bi i i ii. bj := bj ji bi . iii. bj := bj ji bi . (c) Penukaran. 2 > Jika ( j;j 1 )2 bj 1 2
3.4.3 Algoritme LLL dan Analisisnya Dari pembahasan sebelumnya, dapat disimpulkan bahwa algoritme LLL adalah algoritme yang mentransformasikan basis B menjadi basis B 0 dengan menerapkan algoritme reduksi ukuran. Kemudian, ketika kondisi Lovasz tidak memenuhi, algoritme LLL akan melakukan penukaran pada vektor pasangan vektor (bj ; bj+1 ) dan reduksi ukuran kembali dilakukan. Jika ada beberapa pasang vektor (bj ; bj+1 ) yang tidak memenuhi kondisi Lovasz, tidak ada masalah pasangan vektor yang harus ditukar terlebih dahulu. Bahkan pasangan vektor tersebut dapat ditukar secara bersamaan, yang mengarah pada varian algoritme LLL paralel. Algoritme yang asli akan melakukan penukaran pada pasangan vektor dengan nilai j terkecil. Berikut merupakan garis besar deskripsi algoritme LLL.
2
Sedangkan bentuk praktis algoritme LLL diberikan sebagai berikut.
2
maka tukar bj 1 dan bj , kemudian kembali ke langkah 1: 3. Jika tidak, algoritme selesai.
bj , maka i. jika j = 2, A. tukar b1 dan b2 B. b1 := b2 ii. jika j > 2, A. tukar bj 1 dan bj B. j := j 1 Selainnya, j := j + 1 4. return([b1 ; b2 ; : : : ; bn ] dan [b1 ; b2 ; : : : ; bn ]) Algoritme LLL merupakan algoritme yang mampu menghitung menghitung vektor terpendek dalam suatu latis L(B). Namun ketika n cukup besar dan basis B cukup jauh dari ortogonal, maka algoritme LLL sulit untuk menghasilkan vektor terpendek. Hal ini disebabkan karena prinsip algoritme LLL yang mentransformasikan B ke suatu basis yang "hampir ortogonal". Sehingga jika basis B jauh dari ortogonal, maka kerja algoritme LLL semakin berat. Karena basis B memengaruhi kinerja dari algoritme LLL, maka suatu basis dapat diklasi…kasikan berdasarkan jauh dekatnya basis tersebut dari ortogonal. De…nisi 3.14 Basis latis B dikatakan bagus jika B mendekati ortogonal. Sedangkan basis latis B dikatakan buruk jika basis tersebut jauh dari ortogonal.
19
Suatu nilai yang dapat menjadi indikator sebuah basis baik atau buruk dide…nisikan sebagai berikut. De…nisi 3.15 Rasio Hadamard dari suatu basis latis B = fb1 ; b2 ; : : : ; bn g, dinotasikan dengan H(B), dide…nisikan sebagai 1 n1 0 C B B det( ) C C B H(B) = B n C A @Y kbj k j=1
Karena nilai 0 < H(B) 1 dan memenuhi sifat "semakin dekat nilai H(B) ke 1, semakin dekat B ke ortogonal". Maka basis B dikatakan bagus jika nilai H(B) dekat ke 1 dan basis B dikatakan buruk jika nilai H(B) dekat ke 0. Selanjutnya akan dilakukan analisis terhadap algoritme LLL dengan cara membatasi banyaknya iterasi dan dan membatasi besarnya bilangan yang dilibatkan. Membatasi banyaknya iterasi Diasumsikan bahwa basis latis yang digunakan dalah intejer, artinya B Zn . Terlihat bahwa algoritme LLL cepat selesai ketika langkah penukaran (swap) yang dilakukan tidak terlalu banyak. Oleh karena itu, hal pertama yang perlu diperhatikan dalam menganalisis algoritme LLL adalah seberapa besar jumlah maksimum terjadinya penukaran. Dengan demikian, akan dide…nisikan suatu intejer positif yang terkait dengan basis B berikut ini. Ingat kembali de…nisi determinan suatu latis berikut. det(L([b1 ; b2 ; : : : ; bj ])) =
j Y
i=1
,
kbi k
dimana matriks
b1
b2
D=
bj
Dari asumsi Bj adalah matriks intejer, jelas bahwa 2
(det(L(Bj ))) 2 Z Dengan demikian, dapat dide…nisikan intejer positif D yang terkait dengan
n Y
det(L(Bj ))2
j=1
dan kemudian berlaku sifat dalam proposisi berikut ini. Proposisi 3.8 Langkah reduksi ukuran tidak mengubah nilai D, tetapi setiap terjadi penukaran mengakibatkan nilai D menurun dengan faktor . Bukti: Berdasarkan teorema 3.3, perhatikan bahwa langkah reduksi ukuran tidak akan mengubah nilai D. Dengan demikian, selanjutnya tinggal ditunjukkan bahwa setiap terjadi penukaran, nilai D menurun dengan faktor . Misalkan terjadi penukaran bj dan bj+1 , misalkan pula intejer positif D terkait dengan B sebelum terjadinya penukaran, dan D0 terkait dengan B0 setelah bj dan bj+1 ditukar. Sekarang perhatikan bahwa, jika i < j, maka basis [b1 ; b2 ; : : : ; bi ] tidak berubah oleh terjadinya penukaran sehingga jelas bahwa 2
det(L(Bi ))2 = (det(L(B0i ))
Ketika i > j, maka pada basis [b1 ; b2 ; : : : ; bi ] vektor bj dan bj+1 ditukar (menukar sepasang vektor kolom pada Bi ) sehingga L(Bi ) = L(B0i )
2
2
) (det(L(Bi )) = (det(L(B0i ))
Di lain pihak, untuk i = j, maka basis Bj = [b1 ; b2 ; : : : ; bj 1 ; bj ] berubah menjadi B0j = [b1 ; b2 ; : : : ; bj 1 ; bj+1 ] sehingga 2
q det(L(Bj )) = det(BTj Bj ) Bj =
matriks, yaitu
(det(L(Bj ))
=
j Y
i=1
=
2
kbi k
jY1 i=1
2
kbi k
!
bj
2
Karena syarat pertukaran ( ( j+1;j )2 ) bj > bj+1 , maka berlaku
20
2
(det(L(Bj ))
jY1
>
i=1
2
kbi k 1
( >
( 1
(
( jY1 i=1
1
>
,
!
2 j+1;j ) )
2
kbi k
)2 )
!
bj+1
(det(L(Bj )))
2
0
<
D D
det(L(B0j )
n Y
2
2
(det(L(Bj )))
j=1 2
det(L(B0j ))
=
2
(det(L(Bj )))
<
,
D0 < D 1 D> D
,
D
,
1
D0
bj = bj +
j 1 X i=1
Berdasarkan proposisi di atas, sekarang akan dimisalkan k banyaknya iterasi dalam algoritme LLL dan D(j) menyatakan nilai D pada iterasi ke-j, maka 1
D .. .
D(1) 2 (2) D k
D(k)
Karena untuk setiap j nilai D intejer positif, maka D(k) ) D ,
D
, k
j=1
k k
log 1 (D)
1
2A
kbi k
vji bi untuk suatu vji 2 R
(3.6) Karena bj ortogonal ke bt untuk setiap t < j, maka diperoleh (bt bj ) = (bt bj ) + bt
j 1 X
vji bi
i=1
, 0 = (bt bj ) + bt (j)
adalah
, bt
j 1 X
vji bi =
j 1 X
vji bi
i=1
(bt bj )
(3.7)
i=1
Untuk i = 1; 2; : : : ; j
1 1
@
n Y
Membatasi besarnya bilangan yang terlibat Sebelumnya telah ditunjukkan bahwa banyaknya iterasi dalam algoritme LLL terbatas secara polinomial dalam ukuran input. Namun demikian, hal ini belum cukup untuk menyimpulkan bahwa algoritme LLL memunyai waktu running polinomial. Perlu dipastikan bahwa ukuran bilangan yang dilibatkan dalam keseluruhan komputasi juga terbatas secara polinomial. Algoritme LLL menggunakan aritmetik bilangan rasional, sehingga perlu dibatasi presisinya maupun besarannya. Perhatikan bahwa langkah ke-j dari proses Gram-Schmidt dapat dirumuskan ulang sebagai
j=1
=
j=1
j=1
0
membutuhkan waktu polinomial, maka dapat disimpulkan bahwa banayknya iterasi dalam algoritme LLL juga terbatas secara polinomial.
Akhirnya, n Y
j Y
2
2
det(L(B0j )) 2
2
j=1
j+1;j
det(L(B0j ))
bj+1
Hasil ini menunjukkan bahwa banyaknya iterasi terbatas ke atas pada fungsi yang nilainya bergantung pada nilai awal D, karena menghitung 0 1 j n Y Y 2 @ D = kbi k A
1, Persamaan
21
tersebut bisa ditulis dalam bentuk matriks 1 0 Xj 1 0 1 b1 vji bi b1 bj C B Xi=1 j 1 C B B b2 bj C B b2 vji bi C C C= B B i=1 B C .. C B .. @ A . C B . @ A Xj 1 bj 1 bj bj 1 vji bi
Dj 1 bj 2 Zn . Ini berarti semua penyebut dari bilangan dalam vektor bj adalah faktor dari Dj 1 . Sekarang dihitung
=
i=1
Jika dide…nisikan matriks Bj
1
b1
=
dan matriks
=
b2 0
B B uj = B @
bj
1
s=1
1
vj1 vj2 .. . vj;j
Hasil ini menunjukkan bahwa penyebut dari ji adalah Di . Oleh karena itu, bilangan rasional yang ada di dalam vektor
C C C A
1
maka persamaan (3.7) dapat ditulis sebagai 0 1 0 1 b1 (Bj 1 uj ) b1 bj B b2 (Bj 1 uj ) C B b2 bj C B C B C B C= B C .. .. @ A @ A . . bj 1 (Bj 1 uj ) bj 1 bj BTj 1 (Bj
1 uj )
=
BTj 1 bj
, (BTj 1 Bj
1 )uj
=
BTj 1 bj
,
Persamaan terakhir tersebut merupakan SPL dengan matriks koe…sien BTj 1 Bj 1 dan vektor BTj 1 bj adalah intejer. Dengan demikian, untuk s = 1; 2; : : : ; j 1, berdasarkan aturan Cramer diperoleh vjs
Z
Z 2 = T det(L(B j det(Bj 1 Bj 1 )
1
))2
Hasil ini akan digunakan untuk memberi batas pada koe…sien ji . Perhatikan lagi de…nisi D sebagai D
=
=
,D
=
n Y
j=1 n Y j=1 n Y j=1
2
(det(L(Bj ))) det(BTj 1 Bj
1)
Dj dengan Dj = det(BTj 1 Bj
Kemudian, hitung Dj = det(BTj 1 Bj 1 ) dan dikalikan nilainya kedua ruas dari persamaan (3.6), maka diperoleh Dj
1 bj = Dj
dan karena Dj
1 bj +
1 vji
bj bi bi bi Di 1 (bj bi ) Di 1 (bi bi ) bj (Di 1 bi ) Z ! 2 iY 1 Di 2 2 kbs k kbi k
=
ji
j 1 X (Dj
1 vji )bi
i=1
2 Z, maka diperoleh
j 1 X
bj = bj
ji bi
i=1
dan ji dapat dituliskan dengan penyebut D (D merupakan kelipatan setiap Di ). 1 Karena ji 2 , maka ukuran bit yang digunakan terbatas pada lg D. Kemudian dari Dj = diperoleh bj
2
=
j Y
2
kbs k
s=1
Dj Dj 1
Dj
D
Akhirnya, kbj k
2
=
bj
2
+
j 1 X i=1
D + (j
1)
2 ji
2
kbi k
n D 4
nD Dengan demikian, semua pembilang dan penyebut dari bilangan rasional yang terjadi di dalam eksekusi algoritme LLL memunyai ukuran bit yang terbatas secara polinomial dalam lg D. 3.5 Sistemkripto Knapsack Merkle1 ) Hellman
Sistemkripto Knapsack Merkle-Hellman merupakan sistemkripto yang berlandaskan kerumitan komputasi NP-complete. Sistemkripto ini diperkenalkan oleh Merkle dan Hellman pada akhir 1970-an. Tumpuan keamanan utamanya adalah problem klasik matematika yang terkenal dengan nama problem jumlah subhimpunan (subset-sum problem). Namun belakangan
22
keamanan sistem ini menjadi melemah secara signi…kan ketika tumpuan keamanan tersebut bisa dibawa ke masalah latis.
sifat rj >
k X1
ri , j = 2; 3; : : : ; n
i=1
De…nisi 3.16 (Masalah jumlah subhimpunan) Diberikan list yang terdiri dari n bilangan intejer positif a = fa1 ; a2 ; : : : an g dan suatu intejer positif lain s yang ditetapkan. Masalah jumlah subhimpunan adalah mencari subhimpunan dari a yang jumlahnya sama dengan s (diasumsikan ada sedikitnya satu sub-himpunan). Deskripsi yang lain dari de…nisi di atas bisa dinyatakan adalah sebagai berikut. Diketahui vektor intejer a 2 Zn adalah bentuk vektor dari list intejer positif a = fa1 ; a2 ; : : : an g dan intejer s 2 Z+ . Tentukan vektor biner x = (x1 ; x2 ; : : : ; xn ) dengan xi 2 Z2 sehingga a x=s n X , ai xi = s i=1
Pelacakan brute force untuk menyelesaikan problem ini adalah 2n . Untuk n yang cukup besar, sulit menentukan x pada masalah jumlah subhimpunan (a;s). Namun sebagaimana layaknya paradigma kriptosistem, masalah ini dapat digunakan sebagai tumpuan keamanan kalau dapat dide…nisika informasi ekstra (trapdoor ) pada a. Sehingga dengan informasi ekstra tersebut masalah jumlah subhimpunan (a;s) dapat diselesaikan dengan mudah. Untuk itu, akan dide…nisikan suatu barisan dengan sifat khusus sebagai berikut. De…nisi 3.17 Suatu barisan supernaik (superincreasing sequence) adalah suatu barisan r = fr1 ; r2 ; : : : ; r2 g dengan sifat ri+1
2ri , i = 1; 2; : : : ; n
1
Bukti: Bukti akan dilakukan secara induktif. Sebagai basis induksi, untuk k = 2, berdasrkan de…nisi jelas benar bahwa r2 2r1 > r1 . Kemudian diasumsikan Pj 1benar untuk k = j, yaitu rj > i=1 dan selanjutnya akan dibuktikan juga benar untuk k = j + 1. Berdasarkan de…nisi berlaku rj+1
2rj = rj + rj >
rj +
j 1 X
ri
i=1
j X
=
ri
i=1
Proposisi 3.10 Misalkan (a; s) adalah masalah jumlah subhimpunan dengan a = fa1 ; a2 ; : : : ; an g adalah barisan supernaik. Jika diasumsikan masalah tersebut memiliki suatu solusi, yaitu x = fx1 ; x2 ; : : : ; xn g. Maka nilai x dapat ditentukan dengan xn = 1 , s xi = 1 , s dimana i = n
1; n
an n X
xj aj
ai
j=i+1
2; : : : ; 1.
Bukti: Misalkan a = fa1 ; a2 ; : : : ; an g adalah barisan supernaik. Dari de…nisi jumlah subhimpunan diperoleh s=
n X
xi a i
i=1
Lalu misalkan s
an , maka didapatkan
Lemma berikut ini akan digunakan untuk membuktikan suatu proposisi yang berkaitan dengan barisan supernaik.
s an n X , xi ai
Lemma 3.3 Misalkan r = fr1 ; r2 ; : : : ; r2 g adalah barisan supernaik, maka berlaku
, xn an +
an
i=1
n X1 i=1
xi ai
an
23
Jika nilai xn = 0, maka n X1
xi ai
Jika s < a3 , maka x3 = 0 sehingga s1
an
i=1
Hal ini kontradiksi dengan de…nisi barisan supernaik an
>
n X1
ai xi ai
i=1
Sehingga haruslah xn = 1.Kemudian misalkan dide…nisikan sebuah masalah subhimpunan yang baru, yaitu (bi ; si ) dimana bi si
= fa1 ; a2 ; : : : ; ai g n X = s xj aj j=i+1
dengan i = n 1; n 2; : : : ; 1. Dengan cara yang serupa didapatkan si ai jhj xi = 1. Berikut ini langkah-langkah ilustratif dari proposisi 3.10. Tanpa mengurangi keumuman, diambil nilai n = 3 1. Untuk i = 3, dide…nisikan sebuah masalah subhimpunan yang baru, yaitu (b2 ; s2 ) b2 s2
= fa1 ; a2 g = s x3 a3
dari proposisi didapatkan jika s maka x3 = 1 sehingga s2
= s = s
a3 ,
x3 a3 a3
Jika s < a3 , maka x3 = 0 sehingga s2
= s = s
x3 a3
2. Untuk i = 2, dide…nisikan sebuah masalah subhimpunan yang baru, yaitu (b1 ; s1 ) b1 s1
= fa1 g = s2 x2 a2
dari proposisi didapatkan jika s2 maka x2 = 1 sehingga s1
= s2 = s2
x2 a 2 a2
x2 a2
3. Untuk i = 1, dari proposisi didapatkan jika s1 a1 , maka x2 = 1 dan jika s1 < a1 , maka x2 = 0. Berdasarkan pola dari 3 langkah tersebut, berikut merupakan algoritme untuk menyelesaikan masalah jumlah subhimpunan.
i=1
n X1
= s2 = s2
a2 ,
Algoritme 3.7 Input: Barisan supernaik yang terdiri dari n bilangan intejer positif a = fa1 ; a2 ; : : : ; an g dan intejer positif s. Output: x = fx1 ; x2 ; : : : ; xn g yang merupakan solusi dari masalah jumlah subhimpunan (a; s). 1. Untuk i = n; n 1; : : : ; 1, lakukan: (a) Jika s ai , maka lakukan: i. xi := 1 ii. s := s ai (b) Selainnya, xi := 0 2. return(x = fx1 ; x2 ; : : : ; xn g) Berikut merupakan deskripsi sistemkripto knapsack Merkle-Hellman. Algoritme 3.8 (Pembangkitan Kunci) Ringkasan: Entitas A membuat kunci publik dan kunci privat dengan langka-langkah sebagai berikut, 1. Pilih barisan supernaik r = fr1 ; r2 ; : : : ; rn g 2. Pilih intejer positif p dan q dengan syarat q 2rn dan gcd(p; q) = 1 3. Hitung barisan a = fa1 ; a2 ; : : : ; an g dengan ai = pri mod q 4. Kunci publik: a; Kunci privat: (r; p; q) Algoritme 3.9 (Enkripsi) Ringkasan: Entitas B mengenkripsi pesan bermakna m dengan kunci publik a menjadi pesan tersandi c untuk dikirim ke entitas A. B melakukan langkah-langkah berikut 1. Bentuk pesan bermakna m dalam bentuk n-bit m1 m2 : : : mn , dimana mi 2 f0; 1g 2. Gunakan kunci publik a untuk menghitung intejer c dimana c=
n X i=1
ai mi
3. Kirim c ke entitas A Algoritme 3.10 (Dekripsi) Ringkasan: Entitas A menerima pesan tersandi c dari B dan mendekripsi c menjadi pesan bermakna m dengan kunci pribadi (r; p; q) A melakukan langkah-langkah berikut 1. Gunakan kunci p untuk menghitung intejer s dengan s = p 1 c mod q 2. Gunakan kunci r dan terapkan algoritme dengan input r dan s untuk menghitung b = fb1 ; b2 ; : : : ; bn g 3. Pesan bermakna yang didapatkan adalah b1 b2 : : : bn 3.6 Pembongkaran Sistemkripto Knapsack Merkle-Hellman Sekarang akan dibahas bagaimana aplikasi algoritme LLL dalam pembongkaran sistemkripto knapsack Merkle-Hellman. Kembali pada de…nisi masalah jumlah subhimpunan a1 x1 + a2 x2 +
+ an xn = s.
Dengan mengasumsikan bahwa masalah jumlah subhimpunan di atas memiliki minimal satu penyelesaian. Maka penyelesaian yang didapat adalah sebuah vektor biner m = (m1 ; m2 ; : : : ; mn ). Maka dengan demikian dapat dide…nisikan
sebuah matriks intejer 0 2 0 B 0 2 B B .. . . B = B ... . . B @ 0 0 a1 a2
0 0 .. . 2 an
1 1 .. .
1
C C C C C 1 A s
Misalkan B = fb1 ; b2 ; : : : ; bn ; sg adalah basis latis dengan bj adalah kolom ke-j dari matriks B untuk j = 1; 2; : : : ; n dan s adalah kolom ke-(n + 1) matriks B, maka dalam latis tersebut jelas terdapat sebuah vektor w = (m1 b1 +m1 b1 +
+mn bn s) 2 L(B)
Kemudian perhatikan bahwa 0 1 0 2m1 w1 B w2 C B 2m2 B C B B C B .. w = B ... C = B . B C B @ wn A @ 2mn 0 wn+1
1 1 1 C C C C C 1 A
dan karena mj 2 Z2 , maka wj 2 f 1; 1g untuk j = p 1; 2; : : : ; n, sehingga didapatkan n. Hal ini mengakibatkan kwk = bahwa w adalah vektor terpendek dalam latis L(B) dan algoritme LLL dapat diaplikasikan untuk mencari vektor w.
IV SIMPULAN DAN SARAN 4.1 Simpulan Algoritme LLL merupakan algoritme untuk mencari hampiran dari vektor terpendek dalam suatu latis. Walaupun demikian, algoritme LLL seringkali mampu mencari solusi eksak dalam mencari vektor terpendek. Hal ini membuat algoritme LLL dapat digunakan sebagai alat untuk membongkar sistemkripto knapsack Merkle-Hellman. Sehingga sistemkripto Merkle-Hellman sudah
mengalami keruntuhan. 4.2 Saran Algoritme LLL terbukti dapat digunakan dalam berbagai masalah. Bagi yang berminat, dapat dicari terapan-terapan lain dari algoritme LLL. Kemudian dilakukan modi…kasi-modi…kasi sehingga algoritme LLL dapat mencari solusi eksak dalam mencari vektor terpendek secara lebih sempurna.
DAFTAR PUSTAKA Anton H. 2000. Elementary Linear Algebra. Canada: Wiley. Bartle RG. 1964. The Elements of Real Analysis. Canada: Wiley. Bremner MR. 2012. Lattice Basis Reduction. London: CRC Press.
Guritman S. 2012. Latis dan Aplikasinya. Bogor: Departemen Matematika FMIPA IPB. Nguyen PQ, Vallee B. 2009. The LLL Algorithm. New York: Springer-Verlag. Stark HM 1970. An Introduction to Number Theory. Cambridge: MIT Press.
LAMPIRAN
27 Lampiran 1: Sintaks Mathematica Algoritme LLL
28 Lampiran 2. Sintaks Mathematica Pembangkitkan kunci
Lampiran 3: Sintaks Mathematica Enkripsi
Lampiran 4: Sintaks Mathematica menentukan solusi masalah jumlah subhimpunan
29
Lampiran 5: Sintaks Mathematica Dekripsi
