Implementasi dan Analisis Sederhana Protokol Megrelishvili pada Bahasa Pemograman Java

OPEN ACCESS Ind. Symposium on Computing Sept 2016. pp. 59-76

ISSN 2460-3295

doi:10.21108/indosc.2016.118

socj.telkomuniversity.ac.id/indosc

Implementasi dan Analisis Sederhana Protokol Megrelishvili pada Bahasa Pemograman Java Hafidz Sohihudin Ahmad #1, Fahmi Alfiansyah*2, Adrian Eka Febrianto#3 Computing Laboratory, School of Computing Telkom University Bandung, Indonesia 40257 1 [email protected] 2 [email protected] 3 [email protected]

Abstrack Megrelishvili key exchange protocol has been discovered in 2006, but the practical implementation of these protocols has not been studied exhaustively. This paper discusses the implementation of the protocol in the Java language using optimal public key parameters. The design of this system is presented by applying UML. In addition, we perform numerical experiments for analyzing the execution time and memory requirements on Megrelishvili protocol. From the results of experiments conducted, obtained two important things. First, the size of the matrix used is directly proportional to the time and amount of memory. Second, the size of the Galois Field used inversely proportional to the time, but is directly proportional to the amount of memory. Keywords: Megrelishvili protocol, UML, numerical experiments

Abstrak Protokol pertukaran kunci Megrelishvili sudah ditemukan pada tahun 2006, namun implementasi praktis penggunaan protokol tersebut masih belum dipelajari secara mendalam. Makalah ini membahas implementasi protokol dalam bahasa java menggunakan parameter kunci publik yang optimal. Perancangan sistem ini disajikan dalam bentuk UML. Selain itu, kami melakukan eksperimen numerik untuk menganalisis waktu eksekusi dan kebutuhan memori pada protokol Megrelishvili. Dari hasil eksperimen yang dilakukan, diperoleh dua hal penting. Pertama, ukuran matriks yang digunakan berbanding lurus dengan waktu dan jumlah memori. Kedua, ukuran Galois Field yang digunakan berbanding terbalik dengan waktu, namun berbanding lurus dengan jumlah memori. Kata Kunci: protokol Megrelishvili, UML, eksperimen numerik

Received on August 2016. Accepted on Sept 2016

Hafidz Sohihudin Ahmad et.al. Implementasi dan Analisis Sederhana ...

I.

60

PENDAHULUAN

P

ROTOKOL pertukaran kunci Megrelishvili diajukan oleh Richard Megrelishvili pada tahun 2006 dengan memanfaatkan pengaplikasian matriks yang menggunakan Galois Field dalam penyusunan kunci rahasianya [1]. Kelebihan dalam penggunaan sistem ini adalah besarnya kemungkinan kunci yang dipertukarkan oleh kedua pihak sehingga serangan brute force untuk mencari kunci yang dipertukarkan akan memakan waktu yang sangat lama. Pentingnya pengamanan data yang dipertukarkan oleh kedua belah pihak tanpa mengalami gangguan untuk melakukan komunikasi merupakan tujuan dari sebuah sistem kriptografi yang baik. Kebutuhan dunia terhadap kriptografi tidak hanya membahas tentang skema kriptografi itu sendiri, melainkan juga membahas tentang desain produk dan membangun sebuah sistem nyata yang bekerja untuk penggunanya. Hal ini tidak terlepas dengan sistem kriptografi Megrelishvili yang penggunaannya masih belum diimplementasikan lebih lanjut. Oleh karena itu, kami mencoba untuk mengimplementasikan protokol pertukaran kunci Megrelishvili ini dalam bahasa Java dan menganalisis lama waktu eksekusi beserta jumlah memori yang dibutuhkan untuk memberikan gambaran mengenai efisiensi penerapan prototokol sehingga dapat menjadi referensi penggunaannya di masa yang akan datang.

II.

STUDI LITERATUR

A. Dasar Matematika Dasar teori matematika pada makalah ini diambil dari [1] [2]. Di dalam makalah tersebut dijelaskan bahwa protokol Megrelishvili memanfaatkan penggunaan teori aljabar linear dalam pembuatan kunci publik, kunci rahasia, proses pertukaran kunci, dan formula perhitungan kunci rahasia bersamanya. Matriks dan ruang vektor yang digunakan dalam proses pertukaran kunci ini didefinisikan pada Galois Field q (GF(q)) tertentu. Misal nilai q=3, maka kita memiliki 𝐺𝐹(3) = {0,1,2}. Kita lambangkan ruang vektor berdimensi n pada sebuah ruang vektor GF(q) dengan 𝐺𝐹(𝑞)𝑛 , kumpulan dari semua matriks n x n pada GF(q) dengan 𝑀𝑛 (𝑞) , dan kumpulan dari seluruh matriks non singular n x n pada 𝐺𝐹(𝑞) dengan 𝐺𝐿𝑛 (𝑞). Semua vektor disimbolkan dengan notasi panah seperti 𝑣⃑, sementara matriks disimbolkan dengan huruf kapital tebal. Vektor diperlakukan sebagai vektor baris, dan oleh karena itu, perkalian matriks-vektor 𝑣⃑𝑴 terdefinisi ketika vektor 𝑣⃑ memiliki n komponen dan M adalah matriks n x n. Diberikan sebuah matriks 𝑴 ∈ 𝐺𝐿𝑛 (𝑞), orde perkalian dari M yang disimbolkan dengan 𝑜𝑟𝑑(𝑴) adalah bilangan bulat terkecil l sehingga 𝑴𝑙 = 𝑰 dengan I adalah matriks identitas n x n. Dapat dibuktikan dengan mudah bahwa 𝑜𝑟𝑑(𝑴) terdefinisi jika dan hanya jika 𝐌 ∈ 𝐺𝐿𝑛 (𝑞). Lalu, I. Niven pada [3] membuktikan bahwa orde perkalian dari Matriks 𝑴 ∈ 𝐺𝐿𝑛 (𝑞) adalah lebih kecil atau sama dengan 𝑞 𝑛 − 1. Diberikan sebuah Galois Field (𝐺𝐹(𝑞)), kita simbolkan 𝐺𝐹(𝑞)[𝑥] sebagai ring polinom {∑𝑛𝑖=0 𝑎𝑖 𝑥 𝑖 : 𝑛 ≥ 0 𝑑𝑎𝑛 𝑎𝑖 ∈ 𝐺𝐹(𝑞) 𝑢𝑛𝑡𝑢𝑘 0 ≤ 𝑖 ≤ 𝑛 }. Derajat 𝑓(𝑥) ∈ 𝐺𝐹(𝑞)[𝑥] yang tidak nol, disimbolkan dengan deg(𝑓), didefinisikan sebagai eksponen dari pangkat tertinggi dari x yang muncul pada 𝑓(𝑥). Sebuah Polinom 𝑓(𝑥) tidak tereduksi jika dan hanya jika 𝑓(𝑥) tidak memiliki faktor trivial (sebuah konstanta polinom sebagai sebuah faktor); selain itu, polinom tersebut bisa direduksi. Sebuah polinom 𝑓(𝑥) ∈ 𝐺𝐹(𝑞)[𝑥] dengan deg(𝑓) = 𝑑 ≥ 1 bisa disebut polinom primitif dalam 𝐺𝐹(𝑞) jika 𝑓 adalah polinom dalam 𝐺𝐹(𝑞) dengan derajat terkecil yang menyebabkan 𝑓(𝛼) = 0 dengan 𝛼 adalah elemen primitif dari 𝐺𝐹(𝑞)𝑑 . Jelas bahwa seluruh polinom primitif juga bisa direduksi. Untuk penjelasan teori lebih lanjut, dapat merujuk pada [4] [5] [6]. B. Protokol Megrelishvili

Ind. Symposium on Computing

Sept 2016

61

Protokol pertukaran kunci Megrelishvili pertama kali diperkenalkan oleh R. Megrelishvili, M. Chelidze, dan K. Chelidze di [7]. Protokol ini mengadaptasi protokol Diffie-Hellman [8] dengan memanipulasi perpangkatan matriks dan perkalian vektor matriks pada Galois Field. Berdasarkan pada [7] [9] [10] [11], kita memisahkan protokol ini kedalam dua tipe. Tipe pertama hanya menggunakan perpangkatan matriks dan perkalian vektor-matriks pada konstruksi kunci privat, pertukaran kunci publik, dan perhitungan kunci rahasia bersamanya. Tipe yang kedua dari protokol ini menggabungkan penjumlahan matriks ke dalam operasi aljabar linear yang digunakan pada tipe pertama. Pada makalah ini, kami mefokuskan pada protokol tipe pertama. Berikut akan dijelaskan otentikasi kunci bersama pada protokol Megrelsihvili berdasarkan [11]. Misalkan ada dua orang, yaitu Alice dan Bob, yang ingin bertukar kunci melalui jalur terbuka. Awalnya, mereka harus sepakat pada sebuah 𝐺𝐹(𝑞) tertentu, sebuah matriks non-singular 𝑴 yang berukuran n x n pada 𝐺𝐹(𝑞), dan sebuah vektor tidak nol 𝑣⃑ ∈ 𝐺𝐹(𝑞)𝑛 berdimensi n. Nilai dari q, n, M, dan 𝑣⃑ adalah parameter publik. Untuk perhitungan kunci rahasia, Alice dan Bob bersama-sama memilih bilangan bulat positif acak 𝛼 dan 𝛽 dan tetap merahasiakan bilangan tersebut, dan secara terpisah membangkitkan 𝑨 = 𝑴𝜶 dan 𝑩 = 𝑴𝜷 sebagai matriks pribadi mereka. Matriks M dipilih sedemikian sehingga 𝑜𝑟𝑑(𝑴) memiliki nilai yang cukup besar. Selama proses pertukaran nilai, Alice menghitung 𝑎⃑ = 𝑣⃑𝑨 dan mengirimkannya kepada Bob, sementara Bob menghitung 𝑏⃑⃑ = 𝑣⃑𝑩 dan mengirimkan 𝑏⃑⃑ kepada Alice. Setelah itu, Alice dan Bob masing-masing mengitung ⃑⃑⃑⃑ 𝑎′ = 𝑏⃑⃑ 𝑨 dan ⃑⃑⃑⃑ 𝑏 ′ = 𝑑⃑ 𝑩 . Kita dapat melihat sebuah persamaan bahwa 𝑨𝑩 = 𝑴𝜶+𝜷 = 𝑴𝜷+𝜶 = 𝑩𝑨 yang ⃑⃑⃑⃑ menyebabkan 𝑎′ = ⃑⃑⃑⃑ 𝑏 ′ sehingga ⃑⃑⃑⃑ 𝑎′ dan ⃑⃑⃑⃑ 𝑏 ′ dapat digunakan sebagai kunci rahasia bersama untuk melakukan komunikasi. Protokol ini dapat dirangkum pada Tabel 1.

TABEL 1 PROSES PERTUKARAN KUNCI MEGRELISHVILI

1. Penentuan Parameter Publik Pihak – pihak yang melakukan komunikasi sepakat dan saling membagikan:  Sebuah ukuran Galois Field 𝐺𝐹(𝑞)  Sebuah angka n  Sebuah matriks non-singular n x n M pada 𝐺𝐹(𝑞); dan  Sebuah vektor berdimensi n yang tidak nol 𝑣⃑ dalam 𝐺𝐹(𝑞)𝑛 2. Pembuatan kunci rahasia Alice Bob  Memilih sebuah bilangan bulat 𝛼  Memilih sebuah bilangan bulat 𝛽  Menghitung 𝑨 = 𝑴𝜶  Menghitung 𝑩 = 𝑴𝜷  Menghitung nilai 𝑎⃑ = 𝑣⃑𝑨  Menghitung nilai 𝑏⃑⃑ = 𝑣⃑𝑩 Pertukaran Kunci Alice mengirimkan nilai 𝑎⃑ ke Bob Bob mengirimkan nilai 𝑏⃑⃑ ke Alice Alice menghitung nilai ⃑⃑⃑⃑ 𝑎′ = 𝑏⃑⃑ 𝑨 Bob menghitung nilai ⃑⃑⃑⃑ 𝑏 ′ = 𝑑⃑ 𝑩 ′ ′ ⃑⃑⃑⃑ ⃑⃑⃑⃑ Kunci bersama mereka adalah 𝑎 = 𝑏 C. Optimasi Parameter Matriks Publik Optimasi matriks yang akan digunakan sebagai parameter publik dibahas pada [1] [2]. Pada makalah tersebut dijelaskan bahwa kita membutuhkan sebuah matriks M yang memiliki orde yang besar pada 𝐺𝐿𝑛 (𝑞) agar protokol menghasilkan lebih banyak kemungkinan kunci yang berbeda. Pembuatan matriks tersebut secara eksplisit pertama kali dibahas di [9] dan selanjutnya metode ini juga dibahas di [11] dan [12]. Namun, pembuatan matriks pada [9] tersebut masih memiliki tiga kekurangan. Pertama, metode tersebut hanya terdefinisi untuk matriks publik pada 𝐺𝐹(2). Kedua, metode ini secara eksplisit hanya memberikan prosedur pembuatan matriks yang berukuran ganjil. Terakhir, orde perkalian dari beberapa matriks tidak optimal (contoh: orde perkaliannya lebih kecil dari 2𝑛 − 1).


62

Pada [1] dijelaskan suatu metode untuk menghasilkan matriks publik yang optimal untuk protokol Megrelishvili. Metode tersebut mengatasi masalah keterbatasan pembuatan matriks pada Galois Field tertentu yang telah disebutkan sebelumnya dan kita dapat memiliki ukuran matriks yang bersifat bebas. Untuk membuatnya, kita mengambil Teorema 2 yang ada pada [1]. Teorema tersebut menyatakan bahwa untuk setiap polinom 𝑓(𝑥) berderajat n pada 𝐺𝐹(𝑞)[𝑥], ada matriks 𝐂 ∈ 𝐺𝐿𝑛 (𝑞) yang minimal polinom adalah 𝑓(𝑥). Matriks yang memenuhi syarat tersebut disebut dengan matriks kompanion. Teorema pada [4] menunjukkan bahwa untuk setiap 𝑛 ∈ ℕ, ada sebuah polinom primitif berderajat n pada 𝐺𝐹(𝑞). Jika Teorema ini digabungkan dengan Teorema 2 dan Definisi 2 pada [1], maka kita mendapatkan sebuah matriks kompanion C berukuran n x n dari sebuah polinom primitif pada 𝐺𝐹(𝑞). Oleh karena itu, sebuah matriks 𝐌 ∈ 𝐺𝐿𝑛 (𝑞) memiliki orde yang optimal jika dan hanya jika polinom minimal dari M adalah sebuah polinom primitif di 𝐺𝐹(𝑞)[𝑥]. Kita menggunakan prosedur yang digunakan pada [1] untuk menghasilkan sebuah matriks primitif pada 𝐺𝐿𝑛 (𝑞). Algoritma ini membutuhkan polinom primitif berderajat n sebagai input dan menggunakan [13] sebagai dasar pembuatan algoritmanya. Algoritma yang dipakai dapat dilihat pada bagan di bawah. TABEL 2 ALGORITMA UNTUK MENGHASILKAN MATRIKS PRIMITIF

generate_public_matrices (f(x)) 1. Tetapkan C sebagai matriks kompanion dari f yang terdefinisi pada Definisi 2 di [1] 2. Bangkitkan sebuah matriks 𝑸 ∈ 𝐺𝐿𝑛 (𝑞) 3. return 𝑴 ← 𝑸𝑪𝑸−𝟏 III.

Mulai

Studi literatur

METODE PENELITIAN

Perancangan desain sistem Implementasi sistem

Selesai

Penarikan kesimpulan

Melakukan pengujian

Gambar 1 Flow Chart Metode Penelitian

Metode penelitian yang kami lakukan sampai makalah ini selesai disusun diilustrasikan pada Gambar 1 dan dijelaskan sebagai berikut. 1.

Studi Literatur Pencarian berbagai referensi terkait pembahasan tentang dasar kriptografi, protokol Megrelishvili, analisis matriks, dan desain perancangan sistem serta pengujiannya.

2.

Perancangan desain sistem


Sept 2016

63

Pembuatan beberapa diagram UML umum terkait sistem yang akan dibangun berdasarkan algoritma protokol pertukaran kunci Megrelishvili sesuai panduan referensi yang telah dipahami. 3.

Implementasi sistem Proses implementasi sistem berdasarkan diagram UML yang telah dirancang sebelumnya ke dalam bahasa Java.

4.

Melakukan pengujian Menguji implementasi sistem yang telah dibangun dengan metode black box untuk memastikan hasil keluaran sistem sesuai dan melakukan analisis waktu eksekusi dan ukuran memori yang dibutuhkan terhadap parameter ukuran matriks dan ukuran Galois Field yang telah ditentukan.

5.

Penarikan Kesimpulan Melakukan penarikan kesimpulan terhadap hasil keluaran sistem saat dilakukan pengujian terhadap parameter ukuran matriks dan ukuran Galois Field yang telah ditentukan.

IV.

DESAIN SISTEM

Desain dari implementasi sistem yang dibangun disajikan menggunakan Unified Modelling Language (UML) sebagai bahasa permodelan standar dalam membangun sistem. Pada bagian ini, kami memberikan beberapa UML umum dalam membangun sebuah sistem seperti diagram use case, diagram kelas, dan diagram aktivitas terkait sistem protokol Megrelishvili yang telah dibangun. A. Use Case Diagram Use case diagram sistem protokol Megrelishvili yang kami buat dapat digambarkan pada Gambar 2 sebagai berikut.

Melihat proses pertukaran kunci

Menganalisis waktu yang digunakan

User

Menganalisis memori yang digunakan Gambar 2 Use Case diagram

Aktor pada use case ini adalah user yang mengoperasikan dan melakukan analisis sederhana terhadap proses sistem protokol Megrelishvili. Adapun use case yang dapat dilakukan user ini adalah: 1.

Melihat proses pertukaran kunci yang bertujuan untuk melihat bagaimana dan apakah sudah sesuai proses pertukaran kunci pada protokol Megrelishvili dengan Tabel 1.


2. 3.

64

Analisis waktu yang digunakan, bertujuan supaya user dapat melihat perbedaan waktu pada setiap proses terhadap parameter publik yang digunakan yaitu ukuran matriks dan ukuran Galois Field. Analisis memori yang digunakan, bertujuan supaya user dapat melihat perbedaan memori pada setiap proses terhadap parameter publik yang digunakan yaitu ukuran matriks dan ukuran Galois Field.

B. Class Diagram Class diagram yang digunakan dalam sistem ini dapat dilihat pada Gambar 3. Field +zero() : T +one() : T +add(x:T, y:T) : T +multiply(x:T, y:T) : T +negate(x:T) : T +reciprocal(x:T) : T +subtract(x:T, y:T) : T +divide(x:T, y:T) : T +equals(x:T, y:T) : boolean

PrimeField -size:integer +PrimeField(size:integer) +zero() : Integer +one() : Integer +add(x:Integer, y:Integer) : Integer +multiply(x:Integer, y:Integer) : Integer +negate(x:Integer) : Integer +reciprocal(x:Integer) : Integer +equals(x:Integer, y:Integer) : boolean -check(x:Integer) : integer

Megrelishvili_protocol -db : database -n : integer -gf : integer +Megrelishvili_protocol(n:integer, gf:integer) +generateQ(n:integer, gf:integer) : Jama.Matrix +getP(n:integer, gf:integer) : Jama.Matrix +generateV(n:integer) : Vector +generateInvers(Q:Jama.Matrix, n:integer, gf:integer) : Jama.Matrix +multiply(A:Jama.Matrix, B:Jama.Matrix, n:integer, gf:integer) : Jama.Matrix +multiply(A:Vector, B:Jama.Matrix, n:integer, gf:integer) : Vector +exponentiationMatrix(M:Jama.Matrix, n:integer, gf:integer) : Jama.Matrix +display_process() +display_time(alpha:int, beta:int) +display_memory(alpha:int, beta:int)

Matrix -values : Object[][] -f : Field +Matrix(rows:integer, cols:integer, f:Field) +rowCount() : integer +columnCount() : integer +get(row:integer, col:integer) : T +set(row:integer, col:integer, val:T) +clone() : Matrix +swapRows(row0:integer, row1:integer) +multiplyRows(row:integer, factor:T) +addRows(srcRow:integer, destRow:integer, factor:T) +multiply(other:Matrix) : Matrix +reducedRowEchelonForm() +invert() +determinantAndRef() : T

MainApplication +display_memory() +display_time() +main(args:String[])

Gambar 3 Class diagram

database -dbuser : String -dbpassword : String -statement : java.sql.Statement -connection : java.sql.Connection -resultSet : java.sql.ResultSet +connect() +getData(query:String) : ResultSet +execute(query:String) -getStatement() : java.sql.Statement -getConnection() : java.sql.Connection -getResultSet() : java.sql.ResultSet -setStatement( statement:java.sql.Statement) -setConnection( connection:java.sql.Connection) -setResultSet( resultSet:java.sql.ResultSet)


Sept 2016

65

Daftar kelas yang terdapat pada sistem yang kami bangun terdiri dari: 1.

Kelas Field Kelas ini merupakan kelas abstrak yang digunakan sebagai acuan kelas turunannya dalam melakukan penghitungan dalam Field tertentu. Kelas ini mengatur fungsi-fungsi yang berkaitan dengan operator aritmatik pada Field tertentu seperti penjumlahan, pengurangan, perkalian, pembagian, dan lain-lain.

2.

Kelas PrimeField Kelas ini merupakan kelas turunan dari kelas Field yang digunakan untuk melakukan penghitungan pada Filed tertentu dengan nilai Field harus berupa bilangan prima. Kelas ini berisi fungsi-fungsi implementasi dari kelas Field yang menerapkan operasi aritmetika dengan nilai Field haruslah bilangan prima.

3.

Kelas Matrix Kelas ini merupakan kelas untuk melakukan penghitungan-penghitungan terhadap suatu matriks. Kelas ini berisi fungsi-fungsi yang berhubungan dengan matriks pada Field tertentu seperti perkalian, invers, dan determinan dari suatu matriks. Objek matriks membutuhkan parameter berupa ukuran baris, kolom dan nilai field yang digunakan ketika melakukan inisialisasi.

4.

Kelas Megrelishvili_protocol Kelas ini merupakan kelas yang berisi proses-proses pada protokol Megrelishvili seperti pembuatan kunci rahasia, dan pertukaran kunci. Kelas ini berisi fungsi-fungsi yang berkaitan dengan protokol Megrelishvili seperti fungsi-fungsi untuk melakukan pembuatan kunci publik yang digunakan berdasarkan parameter berupa ukuran matriks dan ukuran Galois Field yang digunakan. Selain itu, kelas ini juga mengatur fungsi-fungsi yang berkaitan dalam proses pertukaran kunci seperti perkalian matriks dengan vektor, perkalian antar matriks, perpangkatan matriks, dan lain-lain.

5.

Kelas database Kelas ini merupakan kelas yang diguankan untuk terhubung ke dalam database. Database digunakan untuk menyimpan matriks kompanion yang sepengetahuan penulis masih belum dapat diimplementasikan pada Bahasa pemrograman Java.

6.

Kelas MainApplication Kelas ini merupakan kelas utama untuk menjalankan sistem protokol Megrelishvili yang menampilkan proses pertukaran kunci, analisis waktu, dan analisis memori. Kelas ini mengatur fungsifungsi yang menampilkan menu-menu yang dapat diplih oleh user.


66

C. Activity Diagram Activity diagram merupakan gambaran alur kerja tertentu dari subjek-subjek yang memiliki peran dalam sebuah sistem. Bagan pada Gambar 4 berikut akan menjelaskan daftar Activity diagram dalam implementasi sitem kami. 1) Activity Diagram Melihat Proses Pertukaran Kunci Activity Diagram Melihat Proses Pertukaran Kunci Aktor

Sistem

memilih menu tampilkan proses pertukaran kunci

menampilkan menu utama

memberi input parameter publik (n & gf)

membuat kunci rahasia

Tahapan

melakukan pertukaran kunci

menampilkan proses pertukaran kunci beserta hasilnya

Gambar 4 Activity diagram proses pertukaran kunci

Penjelasan Gambar 4: Setelah sistem telah siap dan menampilkan menu utama, maka user dapat memilih menu untuk menampilkan proses pertukaran kunci dan sistem kemudian akan meminta user untuk memasukkan parameter publik berupa ukuran matriks dan ukuran Galois Field yang digunakan dalam protokol ini. Masukan dari user tadi akan digunakan selanjutnya dalam pembuatan kunci rahasia dan sampai ke tahap pertukaran kunci, lalu sistem akan menampilkan setiap proses tadi dan juga hasil pertukaran kunci yang diperoleh.


Sept 2016

67

2) Activity Diagram Analisis Waktu yang Digunakan Activity Diagram Analisis Waktu yang Digunakan Aktor memilih menu tampilkan analisis waktu yang digunakan

Sistem


membuat list percobaan parameter publik (n & gf)



menghitung waktu proses pertukaran kunci

[iterasi belum selesai]

Tahapan

[iterasi selesai] menampilkan waktu setiap proses pertukaran kunci dengan parameter berbeda-beda

Gambar 5 Activity diagram analisis waktu yang digunakan

Penjelasan Gambar 5: Setelah sistem telah siap dan menampilkan menu utama, maka user dapat memilih menu untuk menampilkan waktu pada setiap proses pertukaran kunci. Sistem yang kami buat saat ini menggunakan list ukuran matriks berukuran 3, 5, dan 7, sementara list ukuran Galois Field yang digunakan adalah 2, 3, dan 5. Sistem akan melakukan proses pembuatan kunci rahasia, pertukaran kunci, dan penghitungan waktu yang digunakan pada setiap iterasi parameter publik tadi. User dapat melihat hasil waktu dari setiap proses pada setiap akhir iterasi dalam satuan nanosecond (ns).


68

3) Activity Diagram Analisis Memori yang Digunakan Activity Diagram Analisis Memori yang Digunakan Aktor

memilih menu tampilkan analisis waktu yang digunakan

Sistem


membuat list percobaan parameter publik (n & gf)



menghitung memori proses pertukaran kunci

[iterasi belum selesai]

Tahapan

[iterasi selesai]

menampilkan memori yang digunakan setiap proses pertukaran kunci dengan parameter berbedabeda

Gambar 6 Activity diagram analisis memori yang digunakan

Penjelasan Gambar 6: Aktivitas yang dilakukan oleh user dan sistem pada proses ini hampir sama dengan activity diagram pada analisis waktu hanya saja menu yang dipilih user adalah untuk menampilkan memori dan hasil yang dihitung oleh sistem adalah memori yang digunakan pada setiap proses. Memori yang dihitung ditampilkan dalam satuan byte (B).


Sept 2016

69

V. KETERKAITAN ANTAR PROSES Perancangan aplikasi protokol Megrelishvili memiliki keterkaitan antar proses sebagaimana dijelaskan dalam Gambar 7 berikut. Proses menampilkan pertukaran kunci Proses pemilihan parameter publik

Proses pembuatan kunci rahasia

Proses pertukaran kunci

Sistem Analisis Protokol Megrelishvili

Proses menampilkan waktu pertukaran kunci Proses pemilihan beberapa parameter publik Proses pembuatan kunci rahasia


Proses perhitungan waktu setiap proses Proses menampilkan memori pertukaran kunci Proses pemilihan beberapa parameter publik Proses pembuatan kunci rahasia


Proses perhitungan memori setiap proses

Gambar 7 Keterkaitan antar proses


70

Proses pada Gambar 7 terdiri dari: 1.

Proses menampilkan pertukaran kunci Proses ini menampilkan demo pertukaran kunci yang dilakukan menggunakan parameter berupa ukuran matriks dan ukuran Galois Field dari User. Proses ini memiliki tiga proses di dalamnya yaitu proses pemilihan parameter publik, proses pembuatan kunci rahasia, dan proses pertukaran kunci.

2.

Proses pemilihan parameter publik Proses ini merupakan pemilihan parameter publik yang dimulai pada saat User memberikan parameter yang dibutuhkan yaitu ukuran matriks (n) dan ukuran Galois Field. Langkah berikutnya merupakan pembuatan matiks non-singular n x n M pada 𝐺𝐹(𝑞) dan vektor berdimensi n yang tidak nol 𝑣⃑ dalam 𝐺𝐹(𝑞)𝑛 oleh sistem.

3.

Proses pembuatan kunci rahasia Proses ini merupakan proses pembuatan kunci rahasia yang ditunjukkan pada Tabel 1 menggunakan nilai-nilai parameter publik yang telah dibuat dengan nilai 𝛼 dan 𝛽 menggunakan bilangan bulat yang dipilih otomatis oleh sistem secara acak. Proses ini diakhiri dengan menghasilkan 𝑎⃑ dan 𝑏⃑⃑.

4.

Proses pertukaran kunci Proses ini merupakan proses pertukaran kunci yang ditunjukkan pada Tabel 1 menggunakan nilai 𝑎⃑ dan 𝑏⃑⃑ untuk menghasilkan kunci bersama yaitu ⃑⃑⃑⃑ 𝑎′ dan ⃑⃑⃑⃑ 𝑏 ′ yang memiliki nilai sama.

5.

Proses menampilkan waktu pertukaran kunci Proses ini menampilkan waktu yang digunakan pada proses pertukaran kunci yang dihitung pada setiap proses dengan beberapa parameter publik yang diatur oleh sistem, yaitu ukuran matriks dengan nilai 3, 5, dan 7, sedangkan ukuran Galois Field yang digunakan adalah 2, 3 dan 5.

6.

Proses pemilihan beberapa parameter publik Proses pemilihan parameter publik oleh sistem berisi uku ukuran matriks dengan nilai 3, 5, dan 7, dengan ukuran Galois Field yang digunakan adalah 2, 3 dan 5. Nilai-nilai ini nantinya akan diiterasi masing-masing kombinasinya untuk digunakan sebagai parameter publik.

7.

Proses perhitungan waktu setiap proses Proses ini diawali dengan membuat inisialisasi timer sebelum proses pembuatan kunci rahasia, dan dihentikan setelah proses pertukaran kunci. Nilai pada timer saat dimulai dan dihentikan akan dihitung untuk mengetahui waktu eksekusi proses dengan satuan nanosecond.

8.

Proses menampilkan memori pertukaran kunci Proses ini menampilkan jumlah memori yang digunakan pada proses pertukaran kunci yang dihitung pada setiap proses dengan beberapa parameter publik yang diatur oleh sistem, yaitu ukuran matriks dengan nilai 3, 5, dan 7, sedangkan ukuran Galois Field yang digunakan adalah 2, 3 dan 5.


9.

Sept 2016

71

Proses perhitungan memori setiap proses Proses ini diawali dari insialisasi penghitung memori dengan menjalankan garbage collector terlebih dahulu, lalu di akhir proses akan melakukan penghitungan pengurangan total memori terhadap memori yang tersisa pada sistem dengan menghasilkan memori yang digunakan pada proses tersebut dengan satuan byte. VI.

HASIL PENGUJIAN

A. Pengujian Black Box Metode black box digunakan untuk mengetahui apakan suatu aplikasi sudah dapat beroperasi dengan baik. Hal ini dilakukan dengan cara melihat apakah suatu parameter input dan output yang dihasilkan suatu proses pada sistem sudah sesuai dengan harapan. Pengujian black box aplikasi protokol Megrelishvili adalah sebagai berikut. 1.

Pengujian black box diawali dengan mengecek kesesuaian hasil proses yang dilakukan. TABEL 3 TABEL PENGUJIAN BLACK BOX – HASIL PROSES

Parameter Publik Ukuran Galois matriks (n) Field (gf) 2 3 3

5

7

Hasil

Kesimpulan

⃑⃑⃑⃑ 𝑎′

⃑⃑⃑⃑ 𝑏′

[1, 1, 1] [2, 0, 2]

[1, 1, 1] [2, 0, 2]

5 2

[4, 1, 2] [0, 0, 1, 1, 1]

[4, 1, 2] [0, 0, 1, 1, 1]

3 5

[2, 1, 2, 2, 1] [4, 2, 3, 1, 4]

[2, 1, 2, 2, 1] [4, 2, 3, 1, 4]

2

[0, 0, 1, 0, 0, 1, 1]

[0, 0, 1, 0, 0, 1, 1]

3 5

[2, 1, 1, 0, 2, 1, 2] [3, 0, 2, 4, 1, 0, 4]

[2, 1, 1, 0, 2, 1, 2] [3, 0, 2, 4, 1, 0, 4]

⃑⃑⃑⃑ ⃑⃑⃑⃑ sama, maka hasil sesuai 𝑎′ dan 𝑏′ ⃑⃑⃑⃑ 𝑎′ dan ⃑⃑⃑⃑ 𝑏′ sama, maka hasil sesuai ⃑⃑⃑⃑ 𝑎′ dan ⃑⃑⃑⃑ 𝑏′ sama, maka hasil sesuai ⃑⃑⃑⃑ 𝑎′ dan ⃑⃑⃑⃑ 𝑏′ sama, maka hasil sesuai ⃑⃑⃑⃑ 𝑎′ dan ⃑⃑⃑⃑ 𝑏′ sama, maka hasil sesuai ⃑⃑⃑⃑ ⃑⃑⃑⃑ sama, maka hasil sesuai 𝑎′ dan 𝑏′ ⃑⃑⃑⃑ 𝑎′ dan ⃑⃑⃑⃑ 𝑏′ sama, maka hasil sesuai ⃑⃑⃑⃑ 𝑎′ dan ⃑⃑⃑⃑ 𝑏′ sama, maka hasil sesuai ⃑⃑⃑⃑ ⃑⃑⃑⃑ sama, maka hasil sesuai 𝑎′ dan 𝑏′

Kesimpulan pada Tabel 3 akan dikatakan sesuai apabila pengujian diperoleh nilai akhir ⃑⃑⃑⃑ 𝑎′ yang sama ⃑⃑⃑⃑, yang menandakan proses pertukaran kunci berjalan dengan baik. dengan 𝑏′ 2.

Pengujian kesesuaian proses yang dilakukan Proses yang akan diuji merupakan tiga proses utama dengan hasil sebagai berikut.


a.

72

Proses menampilkan pertukaran kunci

Gambar 2 Proses pertukaran kunci

Dari Gambar 7 dapat diketahui bahwa proses menampilkan pertukaran kunci berjalan dengan baik yang ditandakan dengan adanya pembuatan parameter publik diikuti dengan pembuatan kunci rahasia dan diakhiri dengan pertukaran kunci yang menghasilkan nilai yang sama antara ⃑⃑⃑⃑ 𝑎′ b.

dan ⃑⃑⃑⃑ 𝑏′. Proses menampilkan waktu pertukaran kunci

Gambar 3 Hasil tampilan waktu eksekusi


Sept 2016

73

Proses pada Gambar 8 menampilkan waktu pertukaran setiap proses dengan n adalah ukuran matriks dan gf adalah ukuran Galois Field yang berjalan dengan baik, hal ini ditandai dengan adanya variasi waktu untuk setiap parameter yang berbeda. c.

Proses menampilkan memori pertukaran kunci

Gambar 4 Hasil tampilan jumlah memori yang dibutuhkan

Proses pada Gambar 9 menampilkan memori pertukaran setiap proses dengan n adalah ukuran matriks dan gf adalah ukuran Galois Field yang berjalan dengan baik, hal ini ditandai dengan adanya variasi memori untuk setiap parameter yang berbeda. B. Analisis Waktu Eksekusi Proses Pertukaran Kunci pada Protokol Megrelishvili Hasil analisis waktu eksekusi sistem yang telah dilakukan dapat dilihat pada tabel di bawah. TABEL 4 TABEL ANALISIS WAKTU EKSEKUSI SISTEM

Galois Field (gf)

2

3

5

Ukuran Matriks (n)

waktu (nanosecond) Percobaan Percobaan Percobaan 2 3 4

Percobaan 5

Rata-rata waktu

3

Percobaan 1 2510324

1809401

1318882

1300494

1182461

1624312.4

5

3936121

3277534

2678392

1989870

2264424

2829268.2

7

6614086

5462843

3387869

3755651

4607537

4765597.2

3

2128858

1781175

1104201

1098641

1676828

1557940.6

5

3498204

3239901

2196427

2914029

2057867

2781285.6

7

5808386

5136971

3414383

3759072

3737262

4371214.8

3

2281958

1850455

1903057

1096931

1076831

1641846.4

5

5130128

2155800

2723296

2112179

4884656

3401211.8

7

6061129

4931698

4757642

3727853

5408959

4977456.2


74

Berdasarkan tabel di atas, dilakukan penghitungan rata-rata untuk membuat kesimpulan pengaruh masingmasing parameter yang disajikan pada Tabel 5 dan Tabel 6 berikut. TABEL 5 RATA-RATA WAKTU EKSEKUSI TERHADAP UKURAN MATRIKS PADA MASING-MASING UKURAN GALOIS FIELD

Ukuran matriks (n)

Rata-rata waktu (nanosecond)

3

1608033

5

3003922

7

4704756

Tabel 5 di atas didapatkan dengan merata-rata waktu yang dibutuhkan pada Galois Field yang berbeda pada masing-masing ukuran matriks dengan rumus: Rata-rata waktu (n) =

𝑡𝑜𝑡𝑎𝑙 𝑤𝑎𝑘𝑡𝑢 𝑑𝑒𝑛𝑔𝑎𝑛 𝑢𝑘𝑢𝑟𝑎𝑛 𝑚𝑎𝑡𝑟𝑖𝑘𝑠 𝑛

(1)

3

dengan n adalah ukuran matriks dan 3 adalah jumlah Galois Field yang digunakan, yaitu terdapat tiga Galois Field dengan nilai 2, 3, dan 5. Kesimpulan yang diperoleh adalah semakin besar ukuran matriks yang digunakan, maka semakin besar juga waktu proses yang dibutuhkan dan sebaliknya. TABEL 6 RATA-RATA WAKTU EKSEKUSI TERHADAP UKURAN GALOIS FIELD PADA MASING-MASING UKURAN MATRIKS

Galois Field (gf)

Rata-rata waktu (nanosecond)

2

3073059

3

3050935

5

3034941

Tabel 6 di atas didapatkan dengan merata-rata waktu yang dibutuhkan pada ukuran matriks yang berbeda pada masing-masing ukuran Galois Field dengan rumus: Rata-rata waktu (gf) =

𝑡𝑜𝑡𝑎𝑙 𝑤𝑎𝑘𝑡𝑢 𝑑𝑒𝑛𝑔𝑎𝑛 𝑛𝑖𝑙𝑎𝑖 𝐺𝑎𝑙𝑜𝑖𝑠 𝐹𝑖𝑒𝑙𝑑 𝑔𝑓

(2)

3

dengan gf adalah ukuran Galois Field dan 3 adalah jumlah ukuran matriks yang digunakan, yaitu terdapat tiga ukuran matriks dengan nilai 3, 5, dan 7. Kesimpulan yang diperoleh adalah semakin besar ukuran Galois Field yang digunakan, maka waktu proses yang dibutuhkan cenderung semakin kecil dan sebaliknya. C. Analisis Jumlah Memori saat Proses Pertukaran Kunci pada Protokol Megrelishvili Hasil analisis terkait memori yang digunakan selama sistem melakukan prosesnya dapat dilihat pada tabel di bawah TABEL 7 TABEL ANALISIS MEMORI YANG DIGUNAKAN

Galois Field (gf)

2

Ukuran Matriks (n)

memori (byte) Percobaan Percobaan 3 4

Percobaan 5

Rata-rata memori (byte)

Percobaan 2

3

Percobaan 1 2893072

2893392

2894248

2894304

2896736

2894350.4

5

2892944

2893320

2894176

2894232

2896960

2894326.4

7

2892992

2893312

3226200

2896416

2896952

2961174.4


Galois Field(gf)

3

5

Ukuran Matriks (n)

Sept 2016

75

Percobaan 2

3

Percobaan 1 2893072

2893392

5

3060736

3061056

7

2893376

3 5 7

memori(byte) Percobaan 3


Percobaan 4

Percobaan 5

2894248

2896496

2897032

2894848

2894120

2896368

2896904

2961836.8

3061872

3226200

2896416

2896952

2994963.2

2893456

2894248

2894248

3064288

2897032

2928654.4

2893264

2894120

3061912

2896608

2896904

2928561.6

2893312

2894168

3226256

2896656

2896952

2961468.8

Berdasarkan tabel di atas, dilakukan penghitungan rata-rata untuk membuat kesimpulan pengaruh masingmasing parameter sebagai berikut. TABEL 8 RATA-RATA MEMORI TERHADAP UKURAN MATRIKS PADA MASING-MASING UKURAN GALOIS FIELD

Ukuran matriks (n)


3

2905951

5

2928242

7

2972535

Tabel 8 di atas didapatkan dengan merata-rata memori yang dibutuhkan pada Galois Field yang berbeda pada masing-masing ukuran matriks dengan rumus: Rata-rata memori(n) =

𝑡𝑜𝑡𝑎𝑙 𝑚𝑒𝑚𝑜𝑟𝑖 𝑑𝑒𝑛𝑔𝑎𝑛 𝑢𝑘𝑢𝑟𝑎𝑛 𝑚𝑎𝑡𝑟𝑖𝑘𝑠 𝑛 3

(3)

dengan n adalah ukuran matriks dan 3 adalah jumlah Galois Field yang digunakan, yaitu terdapat tiga Galois Field dengan nilai 2, 3, dan 5. Kesimpulan yang diperoleh adalah semakin besar ukuran matriks yang digunakan, maka semakin besar juga jumlah memori yang dibutuhkan dan sebaliknya. TABEL 9 RATA-RATA MEMORI TERHADAP UKURAN GALOIS FIELD PADA MASING-MASING UKURAN MATRIKS

Galois Field (gf)


2

2916617

3

2916783

5

2939286

Tabel 9 di atas didapatkan dengan merata-rata waktu yang dibutuhkan pada ukuran matriks yang berbeda pada masing-masing ukuran Galois Field dengan rumus: Rata-rata memori(gf) =

𝑡𝑜𝑡𝑎𝑙 𝑚𝑒𝑚𝑜𝑟𝑖 𝑑𝑒𝑛𝑔𝑎𝑛 𝑛𝑖𝑙𝑎𝑖 𝐺𝑎𝑙𝑜𝑖𝑠 𝐹𝑖𝑒𝑙𝑑 𝑔𝑓 3

(4)

dengan gf adalah ukuran Galois Field dan 3 adalah jumlah ukuran matriks yang digunakan, yaitu terdapat tiga ukuran matriks dengan nilai 3, 5, dan 7. Kesimpulan yang diperoleh adalah semakin besar ukuran Galois Field yang digunakan, maka semakin besar juga jumlah memori yang dibutuhkan dan sebaliknya.


76

VII. KESIMPULAN Hasil yang dapat disimpulkan dari eksperimen yang telah dilakukan adalah sebagai berikut. 1.

2.

Ukuran matriks yang digunakan pada pertukaran kunci berbanding lurus dengan waktu dan jumlah memori yang dibutuhkan saat eksekusi sistem, yaitu semakin besar ukuran matriks yang digunakan, maka semakin lama waktu eksekusi dan semakin besar jumlah memori yang dibutuhkannya. Ukuran Galois Field yang digunakan pada pertukaran kunci berbanding terbalik dengan waktu, namun berbanding lurus dengan jumlah memori yang dibutuhkan saat eksekusi sistem, yaitu semakin besar ukuran Galois Field yang digunakan, maka semakin cepat waktu eksekusi dan semakin sedikit jumlah memori yang dibutuhkan oleh sistem.

REFERENSI [1] M. Arzaki and B. Wahyudi, "2016 On The Construction of Secure Public Parameters for Megrelishvili Protocol," in 4th International Conference on Information and Communication Technology (ICoICT 2016), Bandung, Indonesia, May 2016. [2] M. Arzaki, "Elementary Algorithm Analysis of Megrelishvili Protocol," Indonesian Journal on Computing (Indo-JC), Vols. 1, no. 1, pp. 11-23, 2016. [3] I. Niven, "Fermat`s Theorem for matrices," Duke Mathematical Journal, pp. 823-826, 1948. [4] R. Lidl and Niederreiter, "Introduction to Finite Fields and their applications," no. Cambridge University Press, 1994. [5] J. Hoffsein, J. Pipher and J. SIlverman, "An Introduction to mathematical cryptography,2nd ed," no. Springer, 2014. [6] R. Horn and C. Johnson, "Matrix Analysis," no. Cambridge University Press, 2012. [7] R. Megrelishvili, M. Chelidze and K. Chelidze, "On the Contruction of secret and public-key cryptosystem," 2006. [8] W. Diffie and M. Hellman, "New directions in cryptography," Information Theory,IEEE Transactions, pp. 644-654, 1976. [9] R. Megrelishvili and A. Sikharulidze, "New matrix sets generation and the cryptosystem," Proceedings of the European Computing Conference and the Third INternational Conference on Computational Itelligence, Tbilist, Georgia, pp. 253-255, 2009. [10] R. Megrelishvili, "On the original one-way function and the new digital signature scheme,," Applied Mathematics Informatics and Mechanism, vol 16, pp. 43-48, 2011. [11] A. Beletsky, A. Beletsky and R. Kandyba, "Matrix analogues of the Diffie-Hellman protocol," ICTERI, pp. 352-359, 2013. [12] R. Megrelishvili, M. Chelidze and G. Besiashvili, "Investigation of new matrix-key function for the public cryptosystems," Proceedings of The Third International Conference, Problems of Cybernetics and Information vol 1, vol. 1, pp. 6-8, 2010. [13] N. Saxena and E. McClusky, "Primitive polinomial generation algorithms-implementation and performance analysis," CRC Technical Report 2004, 2004.

Implementasi dan Analisis Sederhana Protokol Megrelishvili pada Bahasa Pemograman Java

Recommend Documents