KONSTRUKSI ALGORITME FUNGSI HASH HLI
RACHMAWATI DWI ESTUNINGSIH
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2014
PERNYATAAN MENGENAI TESIS DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA* Dengan ini saya menyatakan bahwa tesis berjudul Konstruksi Algoritme Fungsi Hash HLI adalah benar karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir disertasi ini. Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut Pertanian Bogor. Bogor, Januari 2014 Rachmawati Dwi Estuningsih NIM G551110011
RINGKASAN RACHMWATI DWI ESTUNINGSIH. Konstruksi Algoritme Fungsi Hash HLI. Dibimbing oleh SUGI GURITMAN dan BIB PARUHUM SILALAHI. Kriptografi adalah studi teknik matematik yang berkaitan dengan aspek keamanan informasi seperti kerahasiaan, integritas data, autentikasi entitas, dan autentikasi asal data. Integritas data adalah suatu layanan yang berkaitan dengan pengubahan data dari pihak-pihak yang tidak berwenang. Kriptografi yang terkait dengan tujuan keamanan integritas data adalah fungsi hash. Fungsi hash merupakan fungsi yang secara komputasi efisien memetakan bitstring dengan panjang sembarang ke bitstring dengan panjang tetap yang disebut sebagai nilai hash. Penggunaan fungsi hash dalam menjaga integritas dan autentikasi informasi antara lain dalam pembuatan digital signature, virus protection, dan distribusi software. Gambaran sederhana fungsi hash dalam menjaga integritas dan autentikasi informasi yang dikirim adalah pengirim mengirim informasi dan nilai hash kepada penerima. Jika nilai hash informasi yang dikirim sama dengan nilai hash yang dikirim oleh pengirim, maka informasi tidak mengalami perubahan. Jika sebaliknya, maka berarti pesan telah mengalami perubahan. Fungsi hash harus memiliki sifat satu arah dan tahan tumbukan. Fungsi hash dikatakan bersifat satu arah apabila secara komputasi tak layak menentukan input jika diketahui nilai hash sehingga . Sedangkan, sifat tahan tumbukan dari fungsi hash adalah secara komputasi tak layak menentukan pasangan input dan dengan sehingga outputnya sama, . Tujuan dari penelitian ini adalah membuat konstruksi algoritme fungsi hash yang diberi nama HLI, menganalisis kecepatan dan keamanan dari fungsi hash hasil konstruksi. Selanjutnya, dibandingkan dengan fungsi hash yang telah ada sebelumnya yaitu SWIFFT. Fungsi hash HLI dikonstruksi dengan operasi polinomial modular dengan . Ring polinomial modular yang dinotasikan sebagai adalah himpunan semua polinomial berderajat paling banyak dengan koefisien dalam . Representasi yang lebih sederhana dari dan lebih memudahkan jika diimplementasikan dalam komputer adalah bahwa dapat dipandang sebagai himpunan semua vektor intejer modulo berdimensi . Sedangkan terhadap operasi vektor, adalah latis . Selanjutnya latis yang didefinisikan dari ring polinomial disebut latis ideal. Fungsi hash HLI melibatkan algoritme adisi dan multiplikasi dari ring . Algoritme adisi melibatkan sebanyak operasi jumlah modulo dan algoritme multiplikasi melibatkan sebanyak operasi kali modulo . Jadi secara umum algoritme fungsi hash HLI melibatkan operasi kali modulo dan operasi jumlah modulo . Namun, jika inputnya biner maka algoritme multiplikasi hanya melibatkan operasi kali modulo , sehingga algoritme fungsi hash melibatkan operasi kali modulo dan operasi jumlah modulo . Keamanan dari fungsi hash dapat dilihat dari terpenuhinya dua sifat yaitu satu arah dan tahan tumbukan. Pembuktian bahwa fungsi hash HLI bersifat satu arah mengikuti pembuktian dari Micciancio. Fungsi hash HLI bersifat tahan
tumbukan karena telah dipilih polinomial yang tak teruraikan atas dan monik. Selain itu terbukti bahwa untuk setiap vektor satuan hasil kali ring dari dan merupakan vektor pendek. Jika input dari fungsi hash merupakan bilangan biner maka fungsi hash HLI hanya melibatkan operasi penjumlahan modulo . Sehingga waktu yang digunakan hampir sama dengan SWIFFT. Keunggulan fungsi hash HLI adalah mempunyai ukuran kunci yang lebih kecil daripada SWIFFT. Hal ini berpengaruh pada memori untuk penyimpanan kunci lebih kecil.
Kata kunci: fungsi hash, ring polinomial modular, latis
SUMMARY RACHMAWATI DWI ESTUNINGSIH. Algorithm Construction of HLI Hash Function. Supervised by SUGI GURITMAN and BIB PARUHUM SILALAHI. Cryptography is a study of mathematical techniques related to aspects of information security regarding on confidentiality, data integrity, entity authentication, and data origin authentication. Data integrity is a service, which is associated with the conversion of data carried out by unauthorized parties. To maintain data integrity, one can use hash functions. An hash function is a computationally efficient function to map an arbitrary length bitstring to a fixed length bitstring called as hash value. The use of hash function in maintaining the information integrity and authentication is in digital signatures, virus protection, and software distribution. Illustration of the hash function in the integrity and authentication of information that is emailed as follow. The sender sends the information and hash value to the recipient. If the hash value of the information is equal to the hash value that is sent by the sender, then information has not been changed. Otherwise the information has been changed. An hash function has two properties, one way and collision resistance. An hash function is called one way if it is computationally infeasible to find any input such that when given any hash value . Meanwhile an hash function is called collision resistant if it is computationally infeasible to find any where such that . two inputs The purpose of this study is to construct a HLI hash function algorithm, to analyze the speed and security of the hash functions as a results of construction. Furthermore, it is to compare it with SWIFFT. Hash function is constructed based on the result of algebraic operations on modular polynomial ringwith . Modular polynomial ring noted as is a set of all polynomials of degree at most with can be represented as a set of integer vector of modulo in coefficients in . dimension . So, it is simple to implement in a computer. In vector operations, is lattice . Furthermore, alattice that is defined from certain polynomial ring is called ideal lattice. HLI hash function is consists of addition and multiplication algorithm in the ring. Addition algorithm consists of sumation operations of modulo and multiplication consists of multiplication operations of modulo . Generally, algorithm of HLI hash function consists of multiplication operations of modulo and addition operations of modulo . However, if the input is binary number then multiplication algorithm only consists of multiplication operation of modulo , so algorithm of HLI hash function consists of multiplication operations of modulo and addtion operations of modulo . An hash function is secured if it has two properties, i.e., one way and collision resistance. HLI hash function hash is one way, it is following the proof of Micciancio. It is has collision resistant because of polynomial is irreducible over and monic. Moreover, it is proved that for every unit vector
, the vector is small vector. If the input of hash function is a binary number then HLI hash function only involves addition operations of modulo . So the time that used almost same with SWIFFT. The excellence of HLI hash function is the key size smaller than SWIFFT. This effect on memory for key storage is smaller.
Keywords: hash function, modular polynomial ring, lattice
© Hak Cipta Milik IPB, Tahun 2013 Hak Cipta Dilindungi Undang-Undang Dilarang mengutip sebagian atau seluruh karya tulis ini tanpa mencantumkan atau menyebutkan sumbernya. Pengutipan hanya untuk kepentingan pendidikan, penelitian, penulisan karya ilmiah, penyusunan laporan, penulisan kritik, atau tinjauan suatu masalah; dan pengutipan tersebut tidak merugikan kepentingan IPB Dilarang mengumumkan dan memperbanyak sebagian atau seluruh karya tulis ini dalam bentuk apa pun tanpa izin IPB
KONSTRUKSI ALGORITME FUNGSI HASH HLI
RACHMAWATI DWI ESTUNINGSIH
Tesis sebagai salah satu syarat untuk memperoleh gelar Magister Sains pada Program Studi Matematika Terapan
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2014
Penguji Luar Komisi pada Ujian Tesis: Dr Ir Fahren Bukhari, MSc
Judul Tesis : Konstruksi Algoritme Fungsi Hash HLI Nama : Rachmawati Dwi Estuningsih NIM : G551110011
Disetujui oleh Komisi Pembimbing
Dr Sugi Guritman Ketua
Dr Ir Bib Paruhum Silalahi, Mkom Anggota
Diketahui oleh
Ketua Program Studi Matematika Terapan
Dekan Sekolah Pascasarjana
Dr Jaharuddin, MS
Dr Ir Dahrul Syah, MScAgr
Tanggal Ujian: 5 Desember 2013
Tanggal Lulus:
PRAKATA Puji dan syukur penulis panjatkan kepada Allah subhanahu wa ta’ala atas segala karunia-Nya sehingga karya ilmiah ini berhasil diselesaikan. Tema yang dipilih dalam penelitian ini ialah kriptografi, dengan judul Konstruksi Algoritme Fungsi Hash HLI. Terima kasih penulis ucapkan kepada Bapak Dr Sugi Guritman dan Bapak Dr Ir Bib Paruhum Silalahi, MKom selaku pembimbing, serta Bapak Dr Ir Fahren Bukhari, MSc selaku penguji luar yang telah banyak memberi saran. Di samping itu, penghargaan penulis sampaikan kepada Direktur Akademi Kimia Analisis Bogor yang telah memberikan kesempatan untuk melanjutkan studi. Ungkapan terima kasih juga disampaikan kepada suami, anak, ibu, ayah, serta seluruh temanteman, atas segala doa dan kasih sayangnya. Semoga karya ilmiah ini bermanfaat.
Bogor, Januari 2014 Rachmawati Dwi Estuningsih
DAFTAR ISI DAFTAR TABEL
vi
DAFTAR GAMBAR
vi
DAFTAR LAMPIRAN
vi
1 PENDAHULUAN Latar Belakang Tujuan Penelitian Manfaat Penelitian
1 1 2 2
2 TINJAUAN PUSTAKA Fungsi Fungsi Hash Aljabar Latis Kompleksitas Waktu Polinomial Atas Ring Polinomial Modular Penelitian Terkait
3 3 3 6 8 9 10 11 13
3 METODE Mengkonstruksi algoritme fungsi hash berbasis latis Menganalisis kecepatan dari algoritme fungsi hash hasil konstruksi Menganalisis keamanan dari fungsi hash hasil konstruksi
16 16 16 16
4 HASIL DAN PEMBAHASAN Konstruksi Algoritme Fungsi Hash HLI Analisis Kecepatan Analisis Keamanan Perbandingan dengan SWIFFT
18 18 20 22 23
5 SIMPULAN DAN SARAN Simpulan Saran
25 25 25
DAFTAR PUSTAKA
26
RIWAYAT HIDUP
33
DAFTAR TABEL 1 2 3 4
Bentuk Oh-besar Hasil Program Fungsi Hash HLI Perbandingan Ukuran Kunci dari SWIFFT dan HLI Perbandingan Umum SWIFFT dan HLI
10 22 24 24
DAFTAR GAMBAR 1 Hubungan antara Panjang Input dan Waktu Running Program
22
DAFTAR LAMPIRAN 1 Program Fungsi Hash HLI 2 Hasil Program Fungsi Hash 3 Pembuktian bahwa - - Bersifat Tak Teruraikan
27 30 32
1 PENDAHULUAN Latar Belakang Perkembangan teknologi komputer dan telekomunikasi pada saat ini mempengaruhi cara masyarakat dalam berkomunikasi. Salah satunya adalah cara masyarakat melakukan pertukaran informasi atau pesan, yang dahulu biasanya melalu pos sekarang banyak yang beralih dengan menggunakan email melalui jaringan internet. Karena email menggunakan jaringan internet yang merupakan infrastruktur telekomunikasi yang dapat dipergunakan oleh banyak pihak maka terbuka peluang penyadapan informasi oleh pihak lain. Oleh karena itu aspek keamanan dalam pertukaran informasi menjadi sangat penting. Kriptografi adalah studi teknik matematik yang berkaitan dengan aspek keamanan informasi seperti kerahasiaan, integritas data, autentikasi entitas, dan autentikasi asal data. Integritas data adalah suatu layanan yang berkaitan dengan pengubahan data dari pihak-pihak yang tidak berwenang. Untuk menjamin integritas data, kita harus mampu mendeteksi manipulasi data dari pihak-pihak yang tidak berwenang. Manipulasi data diartikan sebagai hal-hal yang berkaitan dengan penghapusan, penyisipan, dan penggantian data. Untuk menjaga integritas data dapat digunakan fungsi hash. Fungsi hash merupakan fungsi yang secara komputasi efisien memetakan bitstring dengan panjang sembarang ke bitstring dengan panjang tetap yang disebut sebagai nilai hash. Penggunaan fungsi hash dalam menjaga integritas dan autentikasi informasi antara lain dalam pembuatan digital signature, virus protection, dan distribusi software. Gambaran sederhana fungsi hash dalam menjaga integritas dan autentikasi informasi yang dikirim adalah pengirim mengirim informasi dan nilai hash kepada penerima. Jika nilai hash informasi yang dikirim sama dengan nilai hash yang dikirim oleh pengirim, maka informasi tidak mengalami perubahan. Jika sebaliknya, maka berarti pesan telah mengalami perubahan. Fungsi hash yang banyak digunakan dewasa ini umumnya dirancang berbasis aritmetik boolean, mirip dengan pola konstruksi algoritme sistemkripto kunci simetrik. Namun, fungsi hash tersebut telah mendapat banyak serangan untuk melemahkan sifat keamanannya. Beberapa contoh metode serangan yang dimaksud seperti; kriptanalisis linear, kriptanalis diferensial, dan kriptanalis tanggal lahir yang umumnya berbasis teori kombinatorika dan peluang. Efektifitas serangan-serangan itu dikarenakan konstruksi fungsi yang bersangkutan umumnya tidak disertai bukti keamanan teoritik yang berlandaskan pada problem komputasi matematik. Sebenarnya telah dicoba konstruksi fungi hash yang tumpuan keamanannya berlandaskan problem komputasi dalam area teori bilangan. Karena kinerja algoritmenya sangat lambat maka fungsi hash tersebut kurang aplikatif. Hal inilah yang menarik minat para peneliti kriptografi untuk merancang algoritme fungsi hash yang efisien dan didukung bukti keamanan teoritik berlandaskan problem komputasi matematik. Problem komputasi latis diharapkan dapat menjadi dasar untuk mendapatkan fungsi hash yang ideal. Pada dasa warsa terakir ini penelitian di bidang kriptografi berbasis latis meningkat.
2 Sistemkripto berbasis problem latis mulai diperkenalkan pada pertengahan tahun 1990-an. Pengenalan ini berdasarkan pada keunggulan dari problem latis, yaitu menjanjikan pembuktian keamanan kuat yang berdasarkan worst-case hardness, implementasi yang efisien, dan kriptografi berbasis latis diyakini aman terhadap komputer kuantum. Konstruksi kriptografi berbasis latis pertama kali disajikan oleh Ajtai pada tahun 1996. Ajtai mendefinisikan keluarga fungsi satu arah yang keamanannya bertumpu pada problem komputasi kasus terburuk dari aproksimasi SVP dengan faktor nc, dimana n adalah dimensi latis dan konstanta c>0. Selanjutnya, Goldreich (1996) menunjukkan bahwa fungsi satu arah tersebut merupakan fungsi hash yang tahan tumbukan. Pada tahun 2002, Micciancio menggunakan latis cyclic sebagai sumber kerumitan baru dan membentuk fungsi satu arah yang efisien dari asumsi kompleksitas kasus terburuk. Peikert (2005) memodifikasi asumsi dari fungsi yang dibentuk Micciancio dapat ditunjukkan bahwa fungsi tersebut merupakan fungsi hash yang tahan tumbukan. Lyubashevsky (2008) mengkonstruksi algoritme fungsi hash berbasis latis yang mengutamakan efisiensi yang disebut SWIFFT. Pada dasarnya fungsi hash SWIFFT adalah varian yang sangat optimal dari fungsi hash dan sangat efisien dalam praktek karena penggunaan Fast Fourier Transform (FFT) di Zq. Dalam penelitian ini akan dikonstruksi algoritme keluarga fungsi hash sebagai varian dari SWIFFT, kemudian dilakukan analisis kecepatan dan keamanan dari fungsi hash hasil konstruksi.
Tujuan Penelitian Tujuan dari penelitian ini adalah: 1. Melakukan konstruksi algoritme fungsi hash berbasis latis. 2. Menganalisis kecepatan dari fungsi hash hasil konstruksi. 3. Menganalisis keamanan dari fungsi hash hasil konstruksi.
Manfaat Penelitian 1. 2. 3. 4.
Manfaat dari penelitian ini antara lain: Memberikan rangkuman mengenai fungsi hash berbasis latis. Memberikan varian baru dari fungsi hash berbasis latis. Menjadi acuan bagi pengguna fungsi hash dalam hal kecepatan dan keamanan dari fungsi hash berbasis latis. Metode untuk pembuktian keamanan fungsi hash dapat digunakan sebagai acuan pembuktian dari fungsi hash yang lain.
3
2 TINJAUAN PUSTAKA Fungsi Definisi 2.1.1 (Fungsi) Suatu fungsi dari himpunan ke himpunan , dinotasikan , didefinisikan sebagai suatu aturan yang memetakan setiap anggota ke tepat satu anggota (Menezes et al. 1996). Dalam hal ini , disebut domain dan disebut kodomain dari . Jika dan adalah hasil pemetaan dari oleh , maka disebut imej dari dan disebut preimej dari oleh , dan dinotasikan . Himpunan imej dari semua anggota disebut imej dari dan dinotasikan . Jelas bahwa Ada tiga sifat fungsi yaitu injektif (satu-satu), surjektif (onto), dan bijektif (korespondensi satu-satu) Definisi 2.1.2 (Injektif) Suatu fungsi disebut fungsi injektif jika setiap anggota dari adalah imej dari paling banyak satu anggota (Menezes et al. 1996). Dari definisi tersebut maka (kardinalitas harus sama atau kurang dari kardinalitas ). Definisi 2.1.3 (Surjektif) Suatu fungsi disebut fungsi surjektif jika untuk setiap anggota merupakan imej dari paling sedikit satu anggota A, atau . Dengan kata lain, dan kardinalitas lebih kecil dari kardinalitas (Menezes et al. 1996). Definisi 2.1.4 (Bijektif) Suatu fungsi disebut fungsi bijektif jika merupakan fungsi injektif dan juga fungsi surjektif (Menezes et al. 1996).
Fungsi Hash Definisi 2.2.1 (Fungsi hash) Fungsi hash adalah fungsi yang secara komputasi efisien memetakan bitstring dengan panjang sembarang ke bitstring dengan panjang tetap yang disebut dengan nilai hash (Menezes et al. 1996). Secara umum fungsi hash dibagi menjadi dua, yaitu: fungsi hash tak berkunci dan fungsi hash berkunci. Fungsi hash tak berkunci mempunyai spesifikasi mengatur parameter input tunggal (pesan). Sedangkan fungsi hash berkunci mempunyai spesifikasi mengatur dua parameter input berbeda (pesan dan kunci). Fungsi hash juga dapat didefinisikan sebagai berikut: Definisi 2.2.2 (Fungsi hash) Fungsi hash adalah fungsi yang mempunyai minimal dua sifat berikut: 1. Kompresi: memetakan input dengan sembarang panjang bit yang berhingga, ke output dengan panjang bit tetap . 2. Kemudahan komputasi: diketahui dan suatu input , mudah dihitung (Menezes et al. 1996).
4 Sedangkan berdasarkan kegunaannya fungsi hash dibedakan menjadi dua, yaitu: 1. MDC (Manipulation Detection Code), merupakan subkelas dari fungsi hash tak berkunci. MDC bertujuan untuk memberikan jaminan integritas data sebagaimana diperlukan dalam aplikasi khusus. Dua bahasan yang termasuk dalam MDC adalah: a. Fungsi hash satu arah (one way hash function/OWHF):fungsi hash ini bersifat bahwa jika diketahui suatu nilai hash, maka untuk menentukan sembarang inputnya adalah tak layak. b. Fungsi hash tahan tumbukan (collision resistant hash function/CRHF): fungsi hash ini mempunyai sifat bahwa jika diketahui suatu nilai hash, maka untuk menentukan sembarang dua inputnya adalah tak layak. 2. MAC (Massage Authentication Code), merupakan subkelas dari fungsi hash berkunci. MAC mempunyai dua parameter berbeda, yaitu: input pesan dan kunci rahasia. MAC bertujuan untuk menjamin integritas data dan asal data. Berikut ini tiga sifat fungsi hash tak berkunci dengan input dan : output 1. Ketahanan preimej (preimage resistance), jika diketahui sembarang nilai hash , maka secara perhitungan tak layak mencari sehingga . Istilah lain untuk ketahanan preimej adalah satu-arah (one-way). 2. Ketahanan preimej kedua (2nd-preimage resistance), jika diketahui , maka secara perhitungan tak layak mencari sehingga . Istilah lain untuk ketahanan preimej kedua adalah ketahanan tumbukan lemah (weak collision resistance). 3. Ketahanan tumbukan (collision resistance), secara perhitungan tak layak mencari dua input berbeda sehingga . Istilah lain untuk ketahanan tumbukan adalah ketahanan tumbukan kuat (strong collision resistance). Hubungan logika dari ketiga sifat tersebut dinyatakan dalam proposisi berikut ini: Proposisi 2.2.3 Fungsi hash yang mempunyai sifat ketahanan tumbukan, maka dijamin mempunyai sifat ketahanan preimej kedua. Kontraposisinya, fungsi hash yang gagal bersifat ketahanan preimej kedua, maka pasti tidak tahan tumbukan. Bukti: Andaikan mempunyai sifat ketahanan tumbukan dan ambil satu input . Karena tahan tumbukan, maka tak layak mencari dengan sehingga . Ini berarti bersifat tahan preimej kedua. Proposisi 2.2.4 Fungsi hash yang tidak tahan preimej kedua, tidak ada jaminan tahan preimej. Begitu pula sebaliknya, fungsi hash yang gagal bersifat tahan preimej, juga tidak menjamin tahan preimej kedua. Berdasarkan sifat-sifat di atas, berikut ini dipertegas mengenai definisi OWHF dan CRHF.
5 Definisi 2.2.5 (OWHF) OWHF adalah fungsi hash dengan dua sifat pada definisi fungsi hash ditambah sifat ketahanan preimej dan ketahanan primej kedua. Istilah lain OWHF adalah fungsi hash satu arah lemah (Menezes et al. 1996). Definisi 2.2.6 (CRHF) CRHF adalah fungsi hash yang bersifat kompresi dan kemudahan komputasi ditambah sifat ketahanan preimej dan ketahanan tumbukan. Istilah lain untuk CRHF adalah fungsi hash satu arah kuat (Menezes et al. 1996). Sedangkan definisi lengkap untuk MAC diberikan berikut ini: Definisi 2.2.7 (Algoritme MAC) Algoritme MAC adalah keluarga fungsi dengan parameter kunci rahasia k mempunyai sifat: 1. Kemudahan komputasi (ease of computation): diketahui fungsi , mudah dihitung. Hasil fungsi ini diberikan nilai dan input , maka disebut nilai-MAC atau MAC saja. 2. Kompresi (compression): memetakan input dengan sembarang panjang bit berhingga, ke output dengan panjang bit tetap . Selanjutnya diberikan suatu deskripsi dari keluarga fungsi , untuk setiap (musuh tidak boleh mengetahui), sifat nilai tetap yang dibolehkan keamanan berikut dipenuhi: 3. Ketahanan komputasi (computation resistance): diberikan nol atau lebih pasangan teks-MAC , secara komputasi tak layak menghitung untuk sembarang input baru sembarang pasangan (termasuk mungkin untuk suatu (Menezes et al. 1996). Jika ketahanan komputasi tidak dipenuhi, algoritme MAC disebut pemalsuan MAC. Ketahanan komputasi mengakibatkan secara perhitungan tak layak menentukan kunci jika diketahui satu atau lebih pasangan teks-MAC . Sebaliknya, ketahanan kunci tidak harus mengakibatkan ketahanan komputasi. Hubungan logika sifat keamanan fungsi hash yang berkunci dan yang tak berkunci diberikan dalam proposisi berikut: Proposisi 2.2.8 Jika adalah fungsi hash yang tahan komputasi (berarti tahan terhadap serangan pilih teks tanpa tahu kunci ), maka: 1. pasti tahan tumbukan 2. tahan preimej. Bukti: Misalkan adalah tahan komputasi, maka: 1. Jika telah dipilih pasangan , tanpa tahu tidak layak menghitung (memilih) pasangan dengan sehingga . 2. Andaikan tidak tahan preimej, tanpa tahu bisa dipilih pasangan dengan adalah preimej dari . Kebanyakan fungsi hash didisain melalui proses iteratif yang menginputkan bitstring dengan panjang sembarang dan mengoutputkan bitstring dengan panjang tetap. Misalkan adalah bitstring dengan panjang sembarang , nilai hash adalah bitstring dengan panjang tetap dihitung melalui tahapan proses berikut:
6 1. Proses penambahan bit ekstra (padding). Input dibagi menjadi blok, , Yang setiap blok mempunyai panjang Jika bukan kelipatan dari , maka dilakukan penambahan bit ekstra (padding) agar blok terakhir mempunyai panjang . Sering juga ditambahkan blok ekstra sebagai representasi biner rata kanan dari . Blok ini menyimpan informasi panjang yang asli. 2. Proses kompresi. Setiap blok akan bertindak sebagai input dari fungsi kompresi yang menghitung secara iteratif dengan rumusan . adalah vektor inisial yang nilainya didefinisikan sebelumnya, adalah nilai berantai yang disebut variabel berantai (channing variable) merupakan bitstring dengan panjang . Output dari proses ini adalah . 3. Proses finalisasi. Proses ini sifatnya opsional, yaitu mentransformasikan oleh fungsi ke bitstring dengan panjang m, . Jika proses ini tidak dilakukan berarti adalah fungsi identitas, yaitu .
Aljabar Di sini akan diberikan definisi dari ruang vektor dan basis sebagai dasar aljabar dari latis. Nantinya dapat dilihat bahwa latis yang dibangkitkan oleh suatu yang direntang basis mempunyai kemiripan dengan subruang vektor dalam oleh basis . Definisi 2.3.1 (Ruang Vektor) Diberikan sembarang himpunan dan sembarang field . Pada didefinisikan aturan jumlah dan aturan perkalian skalar vektor. disebut ruang vektor atas jika terhadap aturan-aturan tersebut memenuhi 10 aksioma-aksioma berikut: 1. . 2. . 3. . 4. , dalam hal ini . 5. . 6. . 7. . 8. . 9. . 10. dimana 1 adalah unsur identitas dari terhadap operasi kali (Anton and Rorres 2000). Definisi 2.3.2 (Subruang) Misalkan adalah ruang vektor atas skalar dan . disebut subruang dari jika juga merupakan ruang vektor atas terhadap operasi yang sama dengan (Anton and Rorres 2000).
7 Definisi 2.3.3 (Kombinasi Linear) Misalkan adalah ruang vektor atas skalar . Didefinisikan himpunan terdiri atas vektor dalam . Suatu vektor disebut kombinasi linear dari jika sehingga (Anton and Rorres 2000). Teorema 2.3.4 Misalkan adalah ruang vektor atas skalar , dan adalah himpunan yang terdiri atas vektor dalam . Himpunan yang anggotanya semua kombinasi linear dari , dinotasikan , yaitu , merupakan subruang dari (Anton and Rorres 2000). Dalam hal ini disebut subruang yang direntang oleh . Selanjutnya, 〈A〉 merupakan subruang terkecil yang memuat , artinya untuk setiap subruang dari yang memuat , pasti . Definisi 2.3.5 (Bebas Linear) Misalkan adalah ruang vektor atas skalar , dan adalah himpunan yang terdiri atas vektor dalam . disebut bebas linear jika . Ingkarannya, disebut terpaut linear jika
(Anton and Rorres 2000). Definisi 2.3.6 (Basis) Misalkan adalah ruang vektor atas skalar , dan adalah himpunan berhingga vektor-vektor di dalam . Dikatakan adalah basis untuk (Anton and Rorres 2000). jika bebas linear dan Definisi 2.3.7 (Ring) Ring adalah himpunan dengan dua operasi biner, yaitu dan perkalian yang memenuhi aksioma-aksioma berikut : penjumlahan a. bukan himpunan kosong b. c. d. e. f. g. h. (Anton and Rorres 2000). Definisi 2.3.8 (Ideal) Diketahui ring komutatif dengan elemen satuan dan . Himpunan disebut ideal pada jika dan hanya jika memenuhi ketiga aksioma berikut: a. b. c. (Anton and Rorres 2000).
8 Misalkan
merupakan suatu ideal dari R. Dibentuk koleksi himpunan = dan disebut sebagai koset. Diperhatikan bahwa I juga merupakan koset, yaitu . Diperhatikan juga bahwa karena dan berakibat . Lemma 2.3.9 (Ring kuosen) Diketahui ring komutatif dengan elemen satuan dan ideal sejati pada . Didefinisikan penjumlahan dan perkalian koset sebagai berikut: a. b. maka merupakan ring komutatif dengan elemen satuan dan ring tersebut dinamakan ring kuosen terhadap (Anton and Rorres 2000). Definisi 2.3.10 (Homomorfisme) Diberikan ring dan . homomorfisme ring jika memenuhi a. b. . Selanjutnya, jika surjektif disebut epimorfisme dan jika isomorfisme.
adalah
bijektif disebut
Latis Latis merupakan objek geometrik dalam ruang dimensi- yang dapat diilustrasikan sebagai himpunan titik-titik dengan susunan yang teratur dan periodik. Berikut ini definisi latis secara matematik: Definisi 2.4.1 (Latis) Misalkan bebas linear dalam ruang vektor himpunan
adalah himpunan . Latis yang dibangkitkan oleh
vektor adalah
beranggotakan semua kombinasi linear dari anggota-anggota . Dalam hal ini, disebut dengan basis untuk dan dapat dinyatakan sebagai matriks . Definisi 2.4.2 (Parallelepiped dasar) Untuk sembarang latis dapat didefinisikan himpunan
dengan basis
yang disebut parallelepiped dasar atau daerah fundamental dasar dari latis . Paralellepiped merupakan bangun pejal setengah terbuka. Jika diilustrasikan dalam ruang berdimensi dua, maka paralellepiped merupakan bidang jajaran genjang setengah terbuka.
9 Definisi 2.4.4 (Dual latis) Dual dari latis sebagai
, dinotasikan
, didefinisikan .
Dalam pendefinisian masalah latis digunakan aproksimasi dengan faktor dan kualitas dari solusinya diukur dengan sembarang fungsi aproksimasi dari latis yaitu . Definisi 2.4.5 (Shortest independent vectors problem yang diperumum, notasi: ) Diberikan basis latis , carilah buah vektor latis yang bebas linear dengan ). Definisi 2.4.6 (Guaranteed distance decoding, notasi: ) Diberikan basis , carilah titik latis dengan latis dan sebuah titik target , dimana adalah rank dari latis. Definisi 2.4.7 (Incremental guaranteed distance decoding problem, notasi: ) Diberikan basis latis berdimensi, himpunan -vektor latis yang bebas linear , titik target , dan bilangan real , carilah vektor latis dengan . Definisi 2.4.8 ( monik berderajat , carilah Definisi 2.4.9 ( dengan
) Diberikan ideal dan
, carilah
) Diberikan ideal dan
dengan
polinomial
. dan .
Kompleksitas Waktu Fungsi kompleksitas waktu adalah ukuran matematis berapa lama algoritme adalah mampu menyelesaikan suatu masalah. Fungsi kompleksitas waktu yang mengambil nilai input integer positif dan mempunyai sifat akan membesar jika membesar. Berikut diberikan pengertian dominasi fungsi sebagai dasar dalam mempelajari fungsi kompleksitas waktu. Definisi 2.5.1 (Dominasi fungsi) Misalkan . Kita katakan bahwa mendominasi (atau didominasi ) jika ada konstanta dan sedemikian sehingga , dimana . Definisi 2.5.2 (Fungsi kompleksitas waktu) Fungsi kompleksitas waktu adalah fungsi yang mengukur banyaknya operasi dalam suatu algoritme yang mempunyai variabel input . Berikut ini beberapa bentuk Oh-besar yang sering muncul dalam analisis algoritme:
10 Tabel 1 Bentuk Oh-Besar Bentuk Oh-besar O(1) O( O(n) O( O( ) O( ) O( ), m=0, 1, 2, … O( ), c>1 O(n!)
Definisi 2.5.3 (Big Oh) Suatu fungsi
Nama Konstan Logaritmik Linear Kuadratik Kubik Polinomial Eksponensial Faktorial
jika .
Polinomial Atas Definisi 2.6.1 (Polinomial atas ) Diberikan field , suatu ekspresi dalam notasi , berbentuk
disebut polinomial dalam x atas jika . Polinomial dikatakan berderajat n, notasi deg , jika dan untuk setiap . Dalam hal demikian, disebut koefisien disebut suku pemimpin. Polinomial pemimpin (leading) dan sukunya dengan koefisien pemimpin disebut monik. Didefinisikan sebagai himpunan semua polinomial atas , maka dapat dituliskan . , Definisi 2.6.2 (Pembagian polinomial) Misalkan dikatakan membagi habis , notasi , jika ada sehingga . Dalam hal demikian, disebut pula faktor atau pembagi dari , atau disebut kelipatan dari . Proposisi 2.6.3 (Algoritme pembagian) Untuk selalu bisa ditemukan sepasang polinomial dimana
dan , sehingga berlaku .
Definisi 2.6.4 (Polinomial teruraikan dan tak-teruraikan) Polinomial dikatakan teruraikan (reducible) atas jika ada keduanya tak-konstan (berderajat positif) sehingga . Polinomial tak-teruraikan (irreducible) atas merupakan ingkaran dari
11 polinomial teruraikan atas . Jadi, dikatakan tak-teruraikan atas jika hanya mempunyai faktor konstan atau dirinya sendiri. Dengan kata lain, konstan atau konstan.
Ring Polinomial Modular Misalkan adalah suatu ideal dalam , berarti untuk setiap dan berlaku . Proposisi berikut menegaskan bahwa struktur beranalog dengan . Proposisi 2.7.1 memiliki struktur daerah ideal utama. Artinya, untuk setiap ideal dalam , ada tepat satu polinomial monik dan berderajat terkecil dalam sehingga , terkadang . dinotasikan Berdasarkan proposisi 2.7.1, untuk selanjutnya setiap disebut ideal dalam dimaksudkan monik dan berderajat terkecil dalam . Untuk suatu , himpunan disebut koset dari yang memuat . Keluarga koset dinotasikan Ketika pada
dan jelas merupakan subhimpunan dari
. didefinisikan operasi jumlah koset dan kali koset:
Maka diperoleh proposisi sebagai berikut Proposisi 2.7.2
merupakan ring dan disebut ring kuosen.
Dengan memandang bahwa J adalah subgrup normal, maka
adalah grup terhadap operasi jumlah dan merupakan partisi dari .
Proposisi 2.7.3 (Teorema Dasar Homomorfisme) Diberikan ring dan , jika adalah epimorfisme ring, maka isomorfik dengan (notasi: dengan pemadanan isomorfisme . Untuk intejer positif , ambil polinomial monik . Didefinisikan pemetaan , Dengan dihitung sebagai sisa dari lemma berikut Lemma 2.7.4
adalah homomorfisme ring.
dengan deg dengan rumus untuk setiap
dibagi
, sehingga diperoleh
12 Bukti: Ambil
,
berdasarkan
proposisi
2.6.3,
berarti
ada
sehingga
Akibatnya ada
sehingga
Dan ada sehingga
. Teorema 2.7.5 Ring dan adalah isomorfik. Bukti: Berdasarkan Lemma 2.7.4, adalah epimorfisme ring. Akibatnya, dengan Proposisi 2.7.3 diperoleh . Dalam hal ini, . Sedangkan
. Karena deg
dan dari definisi mod, maka bisa dinyatakan . dan
Sehingga, dari Teorema 2.7.5, pemadanan isomorfisme bisa dinyatakan sebagai berikut. Jika dan maka dan . Akibatnya diperoleh proposisi berikut Proposisi 2.7.6 Aritmetik ring aritmetik polinomial modular , yaitu
dapat dibawa (diisomorfismekan) ke
dengan operasi jumlah dan kali polinomial modulo
.
13 Ambil sembarang , maka dapat dipandang sebagai anggota berderajat , akibatnya untuk setiap diperoleh . Perkalian ini, kemudian didefinisikan sebagai aturan kali skalar di dalam . Karena adalah grup komutatif terhadap operasi jumlah ring, maka diperoleh teorema berikut Teorema 2.7.7 Terhadap operasi jumlah ring dan aturan kali skalar, merupakan ruang vektor atas dengan basis baku . Selanjutnya, dan adalah dua ruang vektor yang isomorfik dengan pemadanan isomorfisme .
Penelitian Terkait Konstruksi kriptografi berbasis latis pertama kali disajikan oleh Ajtai pada tahun 1995. Ajtai merepresentasikan keluarga fungsi satu arah yang keamanannya bergantung pada worst-case hardness dari nc-aproksimasi SVP untuk beberapa konstan . Berikut algoritme fungsi hash dari Ajtai: Paramater : bilangan bulat Kunci : matriks Fungsi hash :
diberikan oleh
.
Selanjutnya, Goldreich (1996) menunjukkan bahwa fungsi hash yang dikemukakan oleh Ajtai merupakan fungsi hash yang tahan tumbukan dengan memilih parameter . Namun fungsi hash ini mempunyai ukuran kunci yang besar sehingga kurang efisien dalam prakteknya. Pada tahun 2002, Micciancio menggunakan latis cyclic sebagai sumber kerumitan baru dan membentuk fungsi satu arah yang efisien dari asumsi kompleksitas kasus terburuk. Sembarang matriks A diganti dengan blok matriks dengan setiap blok
adalah matriks seperti berikut
,
Dengan menggunakan notasi matriks bisa ditulis dengan ,
dan
.
14 Berikut ini algoritmenya: Parameter : bilangan bulat Kunci : m/n vektor Fungsi hash :
dengan dan vektor . diberikan oleh .
.
Peikert (2005) menunjukkan bahwa fungsi tersebut merupakan fungsi hash yang tahan tumbukan. Selanjutnya, Lyubashevsky (2008) mengkonstruksi algoritme fungsi hash berbasis latis yang mengutamakan efisiensi yang disebut SWIFFT. Pada dasarnya fungsi hash SWIFFT adalah varian yang sangat optimal dari fungsi hash dan sangat efisien dalam praktek karena penggunaan Fast Fourier Transform (FFT) di Zq. Berikut ini algoritme dari SWIFFT: Parameter : Bilangan bulat dan Kunci : m/n vektor Input : m/n vektor Output : vektor
dengan
, q bilangan prima,
. . . .
Keluarga fungsi hash berbasis latis mempunyai aspek keamanan yang bertumpu pada masalah komputasi kasus terburuk dari aproksimasi latis. Analisis keamanan dari keluarga fungsi hash berbasis latis meliputi sifat satu arah dan tahan tumbukan yaitu dengan menunjukkan bahwa untuk menemukan invers dan tumbukan dari fungsi hash serumit menyelesaikan masalah aproksimasi latis yang mendasarinya. Hal ini diharapkan dapat memberikan keamanan yang lebih kuat daripada pendekatan klasik yang berlandaskan pada teori kombinatorika dan peluang. Sebuah fungsi hash berbasis latis memiliki sifat satu arah jika dapat dibuktikan bahwa masalah menemukan invers dari fungsi tersebut dapat direduksi dengan waktu polinomial dari masalah latis yang tidak dapat diselesaikan dengan waktu polinomial. Selanjutnya, untuk membuktikan bahwa fungsi hash hasil konstruksi bersifat satu arah, akan ditunjukkan untuk mencari invers dari fungsi hash serumit menyelesaikan masalah latis dalam kasus terburuk yaitu masalah SIVP (Shortest Independent Vector Problem). Peikert dan Rossen (2006) menunjukkan sifat satu arah melalui dua langkah, yaitu: ) dapat direduksi menjadi 1. Masalah latis dalam kasus terburuk ( masalah kasus terburuk menengah yaitu incremental GDD (
)
2. Masalah kasus terburuk menengah ( ) dapat direduksi menjadi masalah mencari invers dari fungsi hash hasil konstruksi. Sebuah fungsi hash berbasis latis terbukti tahan tumbukan jika masalah menemukan tumbukan dari fungsi tersebut dapat direduksi dengan waktu polinomial dari masalah latis yang tidak dapat diselesaikan dengan waktu polinomial. Hal ini berarti jika dapat ditemukan tumbukan dari fungsi hash dengan waktu polinomial, maka dengan algoritme reduksi dengan waktu polinomial yang menggunakan algoritme menemukan tumbukan dapat diperoleh
15 solusi untuk masalah latis yang tidak dapat diselesaikan dengan waktu polinomial. Ini merupakan kontradiksi, sehingga untuk menemukan tumbukan tidak semudah menyelesaikan masalah latis tersebut. Lyubashevsky dan Micciancio (2006) telah menunjukkan bahwa fungsi hash berbasis latis bersifat tahan tumbukan dengan menunjukkan Lemma 2.8.1 dan Teorema 2.8.2 sebagai berikut: Lemma 2.8.1 Ada reduksi dari polinomial. Teorema 2.8.2 Misalkan dan
ke
dengan waktu
keluarga fungsi hash yang dikonstruksi dengan . Untuk , ada reduksi
dengan waktu polinomial dari untuk suatu ke masalah menemukan tumbukan dari fungsi hash hasil konstruksi.
16
3 METODE Penelitian ini merupakan telaah pustaka sehingga tahap pertama dari penelitian ini adalah mengkaji beberapa jurnal dan buku yang terkait dengan fungsi hash dan konsep latis yang mendasarinya. Selanjutnya dilakukan konstruksi fungsi hash berbasis latis sebagai varian dari fungsi hash berbasis latis yang sudah dikembangkan. Fungsi hash harus memenuhi sifat kemudahan komputasi sehingga fungsi hash hasil konstruksi akan dianalisis kecepatannya. Selain itu harus memenuhi sifat one way dan collision resistant sehingga fungsi hash hasil konstruksi juga akan dianalisis keamanannya.
Mengkonstruksi algoritme fungsi hash berbasis latis Tahap pertama adalah telaah pustaka dari jurnal dan buku yang terkait dengan fungsi hash berbasis latis, selanjutnya dirangkum dan dikembangkan menjadi algoritme fungsi hash berbasis latis yang baru. Berikut langkahlangkahnya: 1. Mempelajari landasan teori mengenai -ary latis. 2. Mengkaji konstruksi fungsi hash dari Ajtai dan pengembangannya. 3. Mengkaji fungsi hash berbasis latis ideal dan latis cyclic. 4. Mengkaji fungsi hash SWIFFT. 5. Mengkonstruksi algoritme keluarga fungsi hash dengan membuat kunci fungsi hash yang lebih kecil ukurannya memilih polinomial tak terurai yang berbeda dengan SWIFFT.
Menganalisis kecepatan dari algoritme fungsi hash hasil konstruksi Fungsi hash hasil konstruksi akan dianalisis kecepatannya dengan cara: 1. Mempelajari landasan teori mengenai analisis algoritme. 2. Mendefinisikan fungsi kompleksitas waktu dari fungsi hash hasil konstruksi dengan menghitung banyaknya operasi dalam fungsi hash hasil konstruksi yang terdiri dari banyaknya operasi dasar (jumlah, kurang, kali, bagi), operasi assignment, dan perbandingan (ekspresi logika). 3. Menentukan order atau bentuk Oh-besar dari fungsi kompleksitas waktu sebagai ukuran efisiensi fungsi hash hasil konstruksi.
Menganalisis keamanan dari fungsi hash hasil konstruksi Keamanan dari fungsi hash sangat penting, sehingga perlu dianalisis kemananan dari fungsi hash hasil konstruksi dengan cara sebagai berikut: 1. Menganalisis sifat satu arah (one way) dari fungsi hash berbasis latis, yang terkait dengan salah satu masalah komputasi dalam latis yaitu Shortest Independent Vector Problem (SIVP). SIVP adalah jika
17 diberikan suatu basis latis , maka tentukan vektor bebas linear dengan yang meminimalkan . 2. Menganalisis sifat tahan tumbukan (resistant collision) dari fungsi hash berbasis latis, yang terkait dengan salah satu masalah komputasi dalam latis yaitu Shortest Vector Problem (SVP). SVP adalah jika diberikan suatu basis latis , maka tentukan vektor terpendek tak nol yang berada dalam latis . 3. Menganalisis sifat tahan tumbukan dengan menunjukkan bahwa polinomial yang tak teruraikan atas dan monik serta untuk setiap vektor satuan hasil kali ring dari dan merupakan vektor pendek.
18
4 HASIL DAN PEMBAHASAN Konstruksi Algoritme Fungsi Hash HLI Misalkan bilangan prima ganjil, dinotasikan sebagai field intejer bilangan prima. Selanjutnya diambil polinomial yang bersifat monik berderajat . Polinomial dapat ditulis sebagai vektor intejer bilangan prima . Ring polinomial modular adalah himpunan semua polinomial berderajat paling banyak dengan koefisien dalam , yaitu . Untuk sembarang yang ditulis
didefinisikan operasi penjumlahan sebagai berikut
dan operasi perkalian yaitu . Representasi yang lebih sederhana dari dan lebih memudahkan jika dapat dipandang sebagai diimplementasikan dalam komputer adalah bahwa himpunan semua vektor intejer berdimensi , yaitu . Selanjutnya, suatu latis berdimensi yang didefinisikan dari ring polinomial modular secara umum disebut latis ideal. Untuk mendapatkan latis ideal sebagai berikut: untuk suatu maka ada ideal dan . Sehingga diperoleh . Lemma 4.1.1 Setiap ideal dengan polinomial berderajat-n yang monik dan tak teruraikan, isomorph dengan latis berdimensi penuh dalam . Bukti: Misalkan dengan dan berderajat paling banyak . Jelas bahwa polinomial bebas linear pada . Jika polinomial bebas linear pada , maka latis memuat n vektor bebas linear yaitu . Jika polinomial tidak bebas linear, maka ada polinomial tak nol sehingga . Jadi untuk suatu polinomial . Karena polinomial berderajat- dan tak teruraikan maka
19 atau , padahal dan polinomial berderajat maka hal tersebut tidak mungkin kecuali kalau dan adalah 0. Dari sini dapat dikonstruksi sebuah keluarga fungsi hash berbasis latis, yaitu adalah bilangan bulat dimana habis dibagi oleh dengan memilih parameter dan adalah bilangan prima. Input dari fungsi hash ini adalah dengan . Kunci dari fungsi hash adalah dua vektor sembarang . Dari kunci inilah nantinya akan dibangkitkan vektor-vektor yang lain yaitu untuk . Selanjutnya, dapat didefinisikan keluarga fungsi hash: dimana . Berikut algoritme fungsi hash berbasis latis secara umum: 1. Parameter : dan adalah bilangan bulat dan adalah bilangan prima. 2. Kunci : dua vektor sembarang 3. Input : dengan . 4. Output: . Fungsi hash ini harus bersifat kompresi yang artinya panjang output harus lebih kecil dibanding panjang input. Panjang input dari fungsi hash HLI adalah Sedangkan panjang output adalah Jadi agar fungsi hash HLI memenuhi sifat kompresi maka parameter yang dipilih di atas harus memenuhi . Dalam penelitian ini dipilih yang merupakan polinomial monik dan tak teruraikan. Pemilihan modulo pada perkalian menyebabkan multiplikasi dari sembarang dua anggota polinomial dalam dalam representasi vektor menjadi lebih sederhana dan lebih mudah jika diimplementasikan dengan komputer. Berikut ini ilustrasinya: . Dari hasil ini, diambil
, maka
dan berikutnya diperoleh
Secara umum, untuk
berlaku
Sehingga algoritme multiplikasi dalam Input: vektor
adalah sebagai berikut:
Output: vektor sebagai hasil multiplikasi dari dan 1. Inisialisasi dan . 2. Untuk intejer s.d , hitung:
dalam dalam
.
20 a.
dimana
menotasikan putaran dari
ke kanan satu
satuan. b.
dimana adalah vektor yang semua komponennya 0 yaitu . selain komponen ke3. Jika , hitung . 4. Return Langkah-langkah dalam algoritme di atas pada dasarnya merupakan perkalian matriks intejer modular , yaitu
Sehingga algoritme untuk fungsi hash ini adalah sebagai berikut: Kunci : dua vektor sembarang Input : dengan Output: vektor dalam ring . 1. Inisialisasi . 2. Untuk bilangan bulat a. b. c. d. 3. Return
.
sebagai hasil multiplikasi dan adisi
s/d
, hitung:
Analisis Kecepatan Analisis kecepatan di sini maksudnya adalah menghitung banyaknya operasi dalam algoritme fungsi hash yang dikonstruksi. Pertama akan dihitung banyaknya , yaitu sebagai berikut: operasi dalam algoritme penjumlahan dalam ring 1. Sebuah operasi assigment sebagai statemen awal untuk variabel s yang merupakan banyaknya elemen vektor yang akan dijumlahkan. 2. Inti dari operasi penjumlahan di sini ada dalam blok statemen ‘if’ yaitu sebuah operasi untuk mengecek apakah salah satu vektor yang akan dijumlahkan merupakan vektor nol kemudian: a. Jika salah satu vektor merupakan vektor nol maka ada sebuah assigment yang menyatakan hasil penjumlahan merupakan vektor yang satunya. Dengan kata lain di sini tidak perlu operasi penjumlahan modulo .
21 b. Jika kedua vektor bukan vektor nol maka untuk dilakukan sebanyak kali operasi penjumlahan modulo . Selanjutnya, dalam algoritme multiplikasi dalam ring ada algoritme perkalian skalar dan vektor modulo dan algoritme memutar vektor ke kanan satu satuan. Oleh karena itu sebelum menghitung banyak operasi perkalian dalam ring, sebagai akan dihitung operasi dalam perkalian skalar dan vektor modulo berikut: 1. Sebuah operasi assigment yang menyatakan variabel awal adalah banyak elemen vektor. 2. Dalam menghitung hasil perkalian ada buah operasi perkalian modulo . Sedangkan banyak operasi dalam algoritme memutar vektor satu satuan ke kanan adalah: 1. Sebuah operasi assigment yang menyatakan variabel awal adalah banyak elemen vektor. 2. Dalam memutar vektor ada dua operasi yaitu mengambil elemen terakhir dari vektor kemudian menyisipkan elemen tersebut sebagai elemen pertama dari vektor. Perhitungan banyak operasi dari dua algoritme di atas dapat digunakan untuk menghitung banyaknya operasi dari algoritme perkalian dua vektor dalam ring yaitu: 1. Ada 2 operasi assigment sebagai statemen awal untuk variabel dan T, variabel merupakan banyak elemen dari vektor. 2. Variabel H sebagai hasil perkalian skalar dan vektor modulo yang melibatkan operasi perkalian modulo . 3. Dalam blok statement ‘for’ yang diulang a. Ada empat buah operasi yaitu variabel S sebagai hasil memutar vektor, variabel c sebagai hasil penjumlahan, variabel T sebagai hasil penyisipan c ke vektor S, dan variabel b. b. Jika b bukan nol maka ada operasi perkalian modulo dan operasi penjumlahan modulo . Algoritme fungsi hash dapat dihitung banyak operasinya adalah sebagai berikut: 1. Ada lima buah operasi assigment sebagai statement awal untuk variabel n, m, k, H dan C. 2. Dalam blok statemen ‘for’ yang diulang kali, yaitu: a. Empat buah assigment untuk variabel a, b, K dan C yang melibatkan operasi b. Sebuah multiplikasi dalam ring perkalian modulo . c. Dua buah adisi dalam ring yang masing-masing melibatkan operasi penjumlahan modulo . Jika diambil parameter maka dalam algoritme fungsi hash tidak melibatkan multiplikasi dalam ring . Sehingga hanya melibatkan penjumlahan dalam ring yang terdiri operasi penjumlahan modulo yang diulang sebanyak kali. Jadi algoritme fungsi hash dengan parameter dan input dengan panjang terdiri dari operasi modulo . Selain dihitung kompleksitas algoritme, juga dilakukan percobaan menghitung waktu lamanya program dalam menghitung nilai hash. Dalam
22 percobaan ini diambil parameter , sedangkan panjang input ( ) diambil dalam 6 titik. Untuk memperoleh nilai waktu, di sini setiap nilai m diulang sebanyak 5 kali kemudian dihitung rata-ratanya sehingga diperoleh hasil sebagai berikut: Tabel 2 Hasil Program Fungsi Hash HLI Panjang Input (bit) 1024 2048 4096 8192 16384 32768
Waktu (detik) 0,33 0,643 1,373 2,718 5,357 10,745
Jika disajikan dalam grafik sebagai berikut: 12 W a 10 k t 8 u 6 ( d e t i k
4 2
)
0 0
5000
10000
15000
20000
25000
30000
35000
Panjang Input (bit)
Gambar 1 Hubungan antara Panjang Input dan Waktu Running Program Dari Gambar 1 dapat dilihat bahwa untuk input dengan bilangan biner dihasilkan waktu yang linear dengan panjang input. Dari Tabel 2 dilakukan uji linearitas untuk mengetahui apakah panjang input dan waktu mempunyai hubungan yang linear atau tidak. Uji linearitas dengan menggunakan program Minitab menghasilkan nilai . Karena nilai kurang dari 5%=0,05 maka dapat disimpulkan bahwa terdapat hubungan yang linear antara panjang input dan waktu.
Analisis Keamanan Keamanan dari fungsi hash dapat dilihat dari terpenuhinya dua sifat yaitu satu arah dan tahan tumbukan. Fungsi hash bersifat satu arah jika diketahui suatu
23 nilai hash maka untuk menentukan inputnya adalah tidak layak. Pembuktian bahwa fungsi hash berbasis latis bersifat satu arah mengikuti pembuktian dari Micciancio (2002). Selanjutnya, fungsi hash disebut bersifat tahan tumbukan jika diketahui suatu nilai hash maka untuk menentukan sembarang dua input yang berbeda adalah tak layak. Pembuktian fungsi hash dengan tak teruraikan atas bersifat tahan tumbukan telah ditunjukkan oleh Lyubashevsky (2006). Menurut Lyubashevsky(2006) untuk mendapatkan sifat tahan tumbukan maka polinomial harus bersifat: a. adalah polinomial monik, berderajat , tak teruraikan atas , b. Untuk setiap vektor satuan , hasil kali ring dari dan merupakan vektor pendek, artinya terbatas . Polinomial merupakan polinomial berderajat n dan monik karena koefisien dari suku pemimpin adalah satu. Dalam penelitian ini dipilih parameter n yang sesuai untuk aplikasi nyata, umumnya dipilih nilai n adalah kuasa 2 ( disesuaikan dengan ukuran mesin. Telah diperiksa untuk n=8, 16, 32, 64, 128, 256, 512, 1024 dengan menggunakan software matematika bahwa polinomial bersifat tak teruraikan. Untuk sifat kedua ditunjukkan dengan teorema berikut Teorema 4.3.1 Jika dan adalah sembarang dua vektor satuan anggota dan , maka . Bukti: Ambil sembarang vektor satuan dan , maka representasi polinomial bisa dituliskan sebagai dan dengan sehingga diperoleh representasi dari adalah jika , maka bukti selesai karena . Jika vektor satuan sehingga sehingga dengan sehingga
Karena diperoleh
yang berarti adalah , maka bukti juga selesai karena . Jika , maka ada
maka jelas bahwa dan . Dari sini diperoleh
sehingga .
Walaupun dalam teorema 4.3.1 menyatakan bahwa terbatas ke , akan tetapi dari buktinya nilai adalah yang lebih kecil dibandingkan dengan untuk .
Perbandingan dengan SWIFFT Perbandingan fungsi hash HLI dan SWIFFT secara khusus dengan parameter disajikan dalam Tabel 3. Sedangkan perbandingan secara umum dapat dilihat dalam Tabel 4.
24 Tabel 3 Perbandingan Ukuran Kunci dari SWIFFT dan HLI dengan Ukuran (bit) Input Kunci Output
SWIFFT 1024 8192 513
HLI 1024 1025 513
Tabel 4 Perbandingan umum SWIFFT dan HLI Keterangan Kunci
SWIFFT HLI vektor sembarang dalam 2 vektor sembarang dalam
Perhitungan Menggunakan Fast Fourier Menggunakan operasi dalam Transform ring polinomial modular . Waktu Tabel 3 menunjukkan bahwa untuk parameter yang sama antara fungsi hash SWIFFT dan HLI diperoleh ukuran kunci dari fungsi hash HLI lebih kecil ukurannya dibandingkan kunci dari fungsi hash SWIFFT. Ukuran kunci ini berpengaruh dalam penyimpanannya. Ukuran kunci yang lebih pendek membutuhkan memori penyimpanan yang lebih kecil sehingga dapat meringankan kinerja dari mesin. Tabel 4 memperlihatkan perbedaan antara SWIFFT dan HLI adalah pada proses perhitungannya. SWIFFT menggunakan Fast Fourier Transform dan HLI menggunakan operasi dalam ring polinomial modular. Operasi dalam ring polinomial modular lebih sederhana dibandingkan Fast Fourier Transform, sehingga dipercaya bahwa fungsi hash HLI kecepatannya lebih baik dibanding SWIFFT walaupun waktunya sama-sama linear.
25
5 SIMPULAN DAN SARAN Simpulan Fungsi hash HLI dikonstruksi dengan parameter bilangan bulat bilangan prima adalah
dan
dimana input dari fungsi hash adalah dan kuncinya . Dengan input dari fungsi hash merupakan bilangan biner maka fungsi hash HLI hanya melibatkan operasi penjumlahan modulo . Sehingga waktu yang digunakan hampir sama dengan SWIFFT. Keunggulan fungsi hash HLI adalah mempunyai ukuran kunci yang lebih kecil daripada SWIFFT.
Saran Fungsi hash HLI dapat dianalisis lebih lanjut mengenai pembuktian keamanannya berdasarkan kerumitan kasus terburuk (worst case hardness) sehingga diperoleh fungsi hash dengan keamanan kuat.
26
DAFTAR PUSTAKA Anton H, Rorres C. 2000. Elementary Linear Algebra 10th Edition. John Wiley and Sons. Canada. Atjai M. 1995. Generating Hard Instances of Lattice Problems. 28th ACM Symposium on Theory of Computing, 98-108. Philadelphia. Cai J Y, Nerurkar. 1997. An Improved Worst-case Connection for Lattice Problems. Proc. 38th IEEE Symp. On Found. Of Comp. Science, 468-477. Goldreich O, Goldwasser S, Halevi S. 1996. Collision-free Hashing from Lattice Problems. Technical report TR96-056, Electonic Colloquium on Computational Complexity. Guritman S. 2003. Pengantar Kriptografi. Handout mata kuliah Pengantar Kriptografi. Fakultas Matematika dan Ilmu Pengetahuan Alam IPB. Bogor. Guritman S, Supriyo P T. 2004. Modul Matematika Diskret. Departemen Matematika FMIPA IPB, Bogor. Guritman S. 2009. Kriptografi Kurva Eliptik. Departemen Matematika FMIPA IPB, Bogor. Guritman S. 2012. Latis dan Aplikasinya. Lecture Note Pelatihan di Lembaga Sandi Negara. Bogor. Lyubashevsky V, Micciancio D. 2006. Generalized Compact Knapsacks are Collision Resistant. ICALP(2) pages 144-155. Lyubashevsky V, Micciancio D, Peikert C, Rosen A. 2008. SWIFFT: A Modest Proposal for FFT Hashing. Proceedings of Fast Software Encryption. Menezes A, van Oorschot P, Vanstone S. 1996. Handbook of Applied Cryptography. CRC Press. Micciancio D. 2002. Generalized Compact Knapsack, Cyclic Lattice, and Efficient One-way Function from Worst-case Complexity Assumptions. Preliminary versions in FOCS. Micciancio D, Regev O. 2004. Worst-case to Average-case Reduction Based on Gaussian Measures. Proc. 45th Annual IEEE Symp. On Foundations of Science, 372-381. Nguyen PQ, Valee B. 2010. The LLL Algoritm: Survey and Applications. Springer –Verlag. Berlin. Peikert C, Rosen A. 2006. Efficient Collision-resistant Hashing from Worst-case Assumptions on Cyclic Lattice. 3rd Theory of Cryptography Conference (TCC). Pinter C C. 1990. A Book of Abstract Algebra. McGraw-Hill Inc.
27 Lampiran 1 Program Fungsi Hash HLI > restart: > with(LinearAlgebra):
Prosedur Aljabar Vektor Intejer Modular AcakVM membangkitkan vektor intejer dalam ruang dimensi m secara acak dengan komponen dalam range intejer > AcakVM:=proc(m::posint,M::posint) local AcIn::procedure, p::integer, L::list: AcIn:=rand(M): L:=[seq(AcIn(),i=1..m)]: return(L); end proc: Contoh: > m:=8: M:=11: > A:=AcakVM(m,M);
AddV menjumlahkan 2 vektor. > AddV:=proc(V::list,W::list) local m::integer, L::list: m:=nops(V): L:=[seq(V[i]+W[i],i=1..m)]: return(L); end proc: AddVM menjumlahkan 2 vektor modulo M. > AddVM:=proc(S::list,T::list,M::posint) local R::list, s,j,t::integer: s:=nops(S): t:=s: if S=[0] then return(T); elif T=[0] then return(S); elif s=nops(T) then R:=[seq((S[i]+T[i]) mod M,i=1..s)]; elif nops(S)<nops(T) then subsop(seq(i=(S[i]+T[i]) mod M,i=1..nops(S)),T); else subsop(seq(i=(S[i]+T[i]) mod M,i=1..nops(T)),S); end if: end proc: Contoh: > m:=5: M:=7: > V:=AcakVM(m,M); > W:=AcakVM(m,M);
28 > U:=AddVM(V,W,M);
MultSVM mengalikan skalar dengan vektor modulo prima M. > MultSVM:=proc(k::integer,V::list,M::posint) local m::integer, L,H::list: m:=nops(V): L:=[seq((k*V[i]) mod M,i=1..m)]: return(L); end proc: Contoh: > m:=5: M:=7: > V:=AcakVM(m,M); > U:=MultSVM(4,V,M);
PutarV memutar vektor V ke kanan 1 satuan. > PutarV:=proc(V::list) local H::list, n::integer: n:=nops(V): H:=[V[n],op(1..n-1,V)]: return(H); end proc: Contoh: > m:=5: M:=8: > V:=AcakVM(m,M); > H:=PutarV(V);
MultRM mengalikan dua vektor sebagai anggota ring R mod M. > MultRM:=proc(A::list,B::list,M::posint) local L,H,S,T::list, m,j,b,c::integer: m:=nops(A): T:=A: H:=MultSVM(B[1],T,M): for j from 2 to m do S:=PutarV(T): c:=S[1]+S[2]: T:=subsop(2=c,S): b:=B[j]: if b<>0 then L:=MultSVM(b,T,M): H:=AddVM(H,L,M):
29 end if: end do: return(H); end proc: > n:=4: m:=5: > V:=AcakVM(n,m); > >
FHash menghitung nilai hash > FHash:=proc(X::list,Y::list,Z::list,M::posint) local C,H,K,L,N::list, a,b,m,n,j,p::integer: n:=nops(Y): p:=nops(X): m:=p/n: H:=[seq(0,i=1..n)]: C:=Y: for j from 1 to m do a:=(j-1)*n+1: b:=j*n: K:=[op(a..b,X)]: L:=MultRM(C,K,M): N:=AddVM(L,Z,M): C:=N: H:=AddVM(H,N,M): end do: return(H); end proc:
30 Lampiran 2 Hasil Program Fungsi Hash Contoh:
>
31
>
>
> >
>
32 Lampiran 3 Pembuktian bahwa
Bersifat Tak Teruraikan
> irreduc(x^8-x-1); true > irreduc(x^16-x-1); true > irreduc(x^32-x-1); true > irreduc(x^64-x-1); true > irreduc(x^128-x-1); true > irreduc(x^256-x-1); true > irreduc(x^512-x-1); true > irreduc(x^1024-x-1); true
33
RIWAYAT HIDUP
Penulis dilahirkan di Karanganyar pada tanggal 25 Mei 1985 sebagai anak dari pasangan Sutardi dan Siti Maryami. Penulis merupakan anak kedua dari dua bersaudara. Pendidikan sarjana ditempuh mulai tahun 2003 di Program Studi Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam UGM, lulus pada tahun 2007. Pada tahun 2011, penulis mendapat beasiswa dari Akademi Kimia Analisis Bogor untuk melanjutkan studi di Sekolah Pascasarjana Mayor Matematika Terapan IPB. Penulis bekerja sebagai dosen di Akademi Kimia Analisis Bogor sejak tahun 2008. Mata kuliah yang diampu adalah matematika dasar dan komputasi data.
