METODE PENELITIAN Penelitian ini dilakukan dalam beberapa tahap. Tahapan-tahapan tersebut dapat dilihat pada Gambar 1 di bawah ini. . Studi Literatur
Analisis
menggunakan algoritme tertentu. Sebagai contoh, untuk operasi penjumlahan dilakukan dengan menjumlahkan masing-masing array yang dimulai dari array paling tidak signifikan. Implementasi Tahap ini mencakup bagaimana merepresentasikan bilangan besar dalam basis 2W dengan W adalah ukuran mesin dalam W-bit dengan menggunakan bahasa C. Selanjutnya dilakukan proses implementasi algoritme penjumlahan, pengurangan, perkalian, pembagian, invers perkalian, reduksi, dan eksponensial pada bilangan tersebut. Lingkungan Pengembangan
Implementasi
Pengujian Gambar 1 Metodologi Penelitian. Studi Literatur Studi literatur merupakan tahap paling awal dalam metodologi penelitian ini. Tahapan ini diperlukan untuk mempelajari prinsip dasar aritmatik field prima dan kajian umum lain yang berkaitan dengan field prima tersebut. Analisis Pada tahap ini dilakukan analisis bagaimana cara merepresentasikan bilangan besar dalam komputer dengan kapasitas yang jauh lebih kecil dari bilangan tersebut sehingga efisien dalam alokasi memorinya. Setelah itu dilakukan analisis bagaimana komputer dapat melakukan komputasi terhadap operasi penjumlahan, pengurangan, perkalian, pembagian, reduksi, invers perkalian, dan eksponensial pada bilangan besar dengan waktu yang cepat dan hasil yang benar. Hankerson et al. (2004) mengemukakan bahwa untuk dapat melakukan operasi penjumlahan, pengurangan, perkalian, reduksi, dan invers perkalian pada bilangan p yang sangat besar, setiap anggota pada field prima (Fp) dapat dipandang sebagai integer multi-kata dengan basis 2W, W adalah ukuran mesin dalam W-bit. Dalam pemrograman, suatu a ∈ Fp diekspresikan sebagai suatu array dengan array paling kanan merupakan array paling signifikan. Setelah itu dapat dilakukan operasioperasi pada bilangan tersebut dengan
Sistem dibangun dan diuji dengan menggunakan hardware dan software dengan spesifikasi tertentu. Hardware yang digunakan berupa personal computer (PC) dengan spesifikasi: 1. Prosesor AMD Sempron 902 MHz 2. RAM 512 MB Software yang digunakan yaitu: 1. Sistem Operasi Windows XP 2. Bloodshed Dev-C++ 4.9.9.2 3. Maple 12 Pengujian Pengujian pada penelitian ini dilakukan dengan menggunakan metode blackbox. Pengujian dilakukan dengan membandingkan antara output yang dihasilkan sistem pada penelitian ini dan output yang dihasilkan software penguji sehingga dapat diketahui nilai kebenaran dari output tersebut. Selanjutnya dari masing-masing operasi dihitung nilai kecepatan eksekusinya untuk mengukur kinerja dari algoritme yang digunakan. Operasi-operasi yang akan diuji yaitu penjumlahan, pengurangan, perkalian, pembagian, dan eksponensial. Panjang bit bilangan besar yang diuji yaitu 256 bit, 512 bit, dan 1024 bit untuk masing-masing operasi.
HASIL DAN PEMBAHASAN Analisis Mesin yang digunakan pada penelitian ini adalah sebuah komputer 32 bit. Oleh karena itu, basis yang digunakan untuk merepresentasikan bilangan besar dalam komputer adalah 232. Akan tetapi, basis dasar dari bilangan besar adalah 10 sehingga perlu dilakukan proses perubahan basis/konversi dari basis 10 ke dalam basis 232. Proses konversi tersebut dilakukan dengan cara membagi bilangan besar dalam
3
basis 10 tersebut dengan 232 secara berulangulang sampai hasil baginya bernilai 0. Dari setiap proses pembagian tersebut dihasilkan nilai sisa bagi. Nilai sisa bagi inilah yang merupakan hasil representasi bilangan besar tersebut dalam basis 232. Untuk lebih jelasnya dapat dilihat pada algoritme di bawah ini. Input : (a)10 Output : (b)232 = (a)10 1. n 0 2. While a ≠ 0 do bn a mod 232 a a / 232 n n +1 3. Return (b0 b1 b2 . . . bn-1 ) Secara matematis representasi bilangan besar adalah sebagai berikut: b = b0 + 232 b1 +...+ 2(n-1) (32) bn-1, dengan bi ∈ {0, 1, 2,..., 232-1}untuk i = 0, 1, ..., (n-1). Representasi ini menunjukkan bahwa digit array paling kanan (bn-1) merupakan digit array paling signifikan. Hal ini bertujuan memudahkan proses komputasi terutama ketika terjadi carry atau penambahan digit array yang paling signifikan. Representasi bilangan besar dengan basis 232 mempunyai keuntungan yaitu efisien dalam alokasi memori yang terlihat dari banyaknya digit array yang digunakan. Untuk merepresentasikan bilangan 1024 bit hanya dibutuhkan 32 digit array. Semakin sedikit digit array yang digunakan tentu akan mempercepat proses komputasi pada bilangan tersebut. Selain efisien dalam alokasi memori, hasil representasi tersebut merupakan nilai bit dari bilangan besar. Nilai bit ini akan berguna dalam operasi eksponensial terutama yang menggunakan algoritme left to right exponentiation. Tipe data yang digunakan untuk merepresentasikan bilangan besar dalam basis 232 adalah mp_int. Struktur mp_int dalam bahasa C dapat dilihat di bawah ini. typedef struct { int used, alloc, sign; unsigned long *dp; } mp_int; Struktur mp_int tersebut dapat dijelaskan sebagai berikut: • Variabel used menggunakan tipe data int. Variabel ini menunjukkan banyaknya digit array dp yang telah digunakan. Nilai used
harus berupa bilangan positif dan tidak boleh melebihi jumlah nilai variabel alloc. • Variabel alloc menggunakan tipe data int. Variabel ini menunjukkan banyaknya digit array dp yang tersedia dan siap digunakan. Ketika nilai used melebihi nilai alloc maka terjadi penambahan ukuran array dp sehingga dapat merepresentasikan bilangan multipresisi. • Variabel sign menggunakan tipe data int. Variabel ini menunjukkan tanda suatu bilangan mp_int. Nilai variabel ini hanya ada dua yaitu 0 (MP_ZPOS) dan 1 (MP_NEG). MP_ZPOS menandakan bilangan positif dan MP_NEG menandakan bilangan negatif. • Variabel dp menggunakan tipe data unsigned long dan merupakan sebuah pointer. Variabel ini dapat mengalokasikan digit array secara dinamis (dapat mengalami penambahan) sehingga dapat merepresentasikan bilangan multipresisi. Implementasi Operasi-operasi bilangan besar pada aritmatik field prima diimplementasikan dalam bahasa C. Jenis-jenis tipe data dalam bahasa C dapat dilihat pada Tabel 1 di bawah ini. Tabel 1 Tipe data dalam bahasa C Tipe Data
Panjang Bit
char
8
short
16
long
32
long long
64
Tabel 1 di atas menunjukkan bahwa bahasa C mempunyai tipe data long long yang mempunyai panjang 64 bit. Tipe data ini berguna dalam merepresentasikan bilangan besar dalam basis 232. Tipe data ini digunakan dalam proses perkalian yaitu sebagai variabel sementara untuk menyimpan hasil perkalian. Bahasa C merupakan bahasa prosedural sehingga operasi-operasi bilangan besar pada aritmatik field prima diimplementasikan dalam bentuk librari yang berisi fungsi-fungsi. Masing-masing fungsi mempunyai return value yang berguna untuk mendeteksi kesalahan. Jenis-jenis return value yang ada dapat dilihat pada Tabel 2 di bawah ini.
4
Tabel 2 Return value pada fungsi Return Value
Keterangan
MP_OKAY (0)
Jika fungsi berhasil
MP_MEM (-2)
Jika fungsi memori
MP_VAL (-3)
melebihi
Jika nilai input tidak valid
Librari dalam penelitian ini mempunyai beberapa fungsi yang menjadi dasar dalam proses komputasi. Fungsi-fungsi tersebut yaitu: a. init Fungsi init digunakan untuk melakukan inisialisasi terhadap bilangan mp_int. Proses insialisasi ini akan memberikan nilai default pada variabel-variabel yang ada pada tipe data mp_int. Algoritme fungsi init adalah sebagai berikut: Input : mp_int a Output : alokasi memori a sebanyak 10 digit array 1. Alokasi memori untuk 10 digit 2. Jika gagal , return (MP_MEM) 3. For n from 0 to 9 do an 0 4. a.sign MP_ZPOS 5. a.used 0 6. a.alloc 10 7. Return ( MP_OKAY ) Algoritme fungsi init di atas menunjukkan bahwa fungsi tersebut akan mengalokasikan memori sebanyak 10 digit array atau setara dengan bilangan 320 bit. Jika terjadi kegagalan, maka fungsi tersebut akan mengembalikan nilai MP_MEM. Fungsi ini memberikan nilai default pada variabel-varibel yang ada dengan a.sign=MP_ZPOS, a.used=0, a.alloc=10, dan an = 0, untuk n=0,1,...,9. b. mp_free_mem Fungsi mp_free_mem merupakan kebalikan dari fungsi init. Fungsi ini digunakan untuk mengembalikan memori yang telah dialokasikan ke kondisi semula sehingga memori tersebut dapat digunakan kembali. Algoritme fungsi mp_free_mem adalah sebagai berikut:
2. Free alokasi memori pada a 3. a.used 0 4. a.alloc 0 5 a. sign MP_ZPOS 6. Return ( MP_OKAY ) Algoritme fungsi mp_free_mem di atas menunjukkan bahwa fungsi tersebut akan mengembalikan memori yang telah terpakai. Selanjutnya fungsi tersebut akan memberikan nilai pada variabel-varibel yang ada dengan a.sign = MP_ZPOS, a.used = 0, dan a.alloc =0. c. mp_grow Fungsi mp_grow digunakan untuk menambah digit array ketika memori yang akan dipakai melebihi memori yang telah dialokasikan (alloc < used). Algoritme fungsi mp_grow adalah sebagai berikut: Input : mp_int a dan int b Output : alokasi memori a ditambahkan sampai b digit array 1. If a.alloc < b Realokasikan digit array a menjadi b For n from a.used to b do an 0 a.alloc b 2. Return ( MP_OKAY ) Algoritme fungsi mp_grow di atas menunjukkan bahwa fungsi tersebut akan memeriksa banyaknya memori yang dialokasikan terlebih dahulu. Jika banyaknya memori yang ingin ditambahkan lebih besar dari memori yang telah dialokasikan, maka fungsi tersebut akan mengalokasikan kembali memori sebanyak memori yang ingin ditambahkan. d. mp_clear_zero Fungsi mp_clear_zero digunakan untuk menghilangkan semua nilai 0 pada digit array paling signifikan yang merupakan nilai tidak penting. Algoritme fungsi mp_clear_zero adalah sebagai berikut: Input : mp_int a Output : semua nilai 0 yang tidak penting pada a dhilangkan
Input : mp_int a Output : memori a didealokasi
1. If aa.used-1 = 0 While a.used ≠ 0 and aa.used-1 = 0 aa.used aa.used - 1 2. If a.used = 0 a.sign MP_ZPOS 3. Return ( MP_OKAY )
1. For n from 0 to a.used-1 do an 0
Algoritme fungsi mp_clear_zero di atas menunjukkan bahwa fungsi tersebut akan
5
memeriksa nilai pada digit array paling signifikan. Jika bernilai 0, maka fungsi tersebut akan melakukan proses looping sampai digit array tidak bernilai 0. Selama proses looping, nilai a.used berkurang 1. Librari dalam penelitian ini mempunyai beberapa fungsi yang digunakan sebagai operasi dasar dalam proses komputasi. Fungsi-fungsi tersebut yaitu: a. mp_copy Fungsi mp_copy digunakan sebagai operasi “sama dengan” (=) pada bilangan mp_int. Fungsi ini akan melakukan proses copy dari suatu bilangan mp_int ke bilangan mp_int yang lainnya. Algoritme fungsi mp_copy adalah sebagai berikut: Input : mp_int a dan mp_int b Output : b = a 1. If b.alloc < a.used mp_grow ( b, a.used) 2. For n from 0 to a.used bn an 3. b.used a.used 4. b.alloc a.alloc 5 b.sign a.sign Algoritme fungsi mp_copy di atas menunjukkan bahwa fungsi tersebut akan memeriksa jumlah alokasi memori pada bilangan b terlebih dahulu. Jika alokasi memori pada b lebih kecil dari a, maka dilakukan proses penambahan alokasi memori pada b sampai sebanyak a.used. Selanjutnya semua variabel yang ada pada b diberikan nilai yang sama dengan a. b. mp_zero Fungsi mp_zero digunakan untuk memberikan nilai 0 pada bilangan mp_int. Algoritme fungsi mp_zero adalah sebagai berikut: Input : mp_int a Output : a = 0 1. a.used = 0 2. For n from 0 to a.used an 0 3 a. sign MP_ZPOS c. mp_cmp Fungsi mp_cmp digunakan untuk membandingkan dua bilangan mp_int. Fungsi ini mempunyai tiga return value. Ketiga return value tersebut yaitu MP_LT (-1) untuk menyatakan “lebih kecil”, MP_GT (1) untuk menyatakan “lebih besar”, dan M’P_EQ (0)
untuk menyatakan “sama dengan”. Algoritme fungsi mp_cmp adalah sebagai berikut: Input : mp_int a dan mp_int b Output : nilai perbandingan antara |a| dan |b| 1. If a.used > b.used Return ( MP_GT ) 2. Else if a.used < b.used Return ( MP_LT ) 3. Else For n from a.used-1 to 0 If an > bn Return ( MP_GT ) Else if an < bn Return ( MP_LT ) Return ( MP_EQ ) Algoritme fungsi mp_cmp di atas menunjukkan bahwa fungsi tersebut akan membandingkan jumlah memori yang digunakan oleh a dan b . Jika memori yang digunakan a lebih banyak dari memori yang digunakan b, maka a > b dan sebaliknya jika memori yang digunakan b lebih banyak dari memori yang digunakan a, maka a < b. Jika memori yang digunakan keduanya sama, maka akan dibandingkan dari digit array paling signifikan antara keduanya. Jika semua nilai digit array sama, maka a = b. Librari dalam penelitian ini mempunyai beberapa operasi aritmatik dalam field prima. Operasi-operasi tersebut yaitu: a.
Penjumlahan
Operasi penjumlahan yang terdapat dalam librari dibagi menjadi beberapa fungsi. Fungsifungsi tersebut yaitu: 1. s_mp_add Fungsi s_mp_add digunakan untuk melakukan proses penjumlahan dua bilangan mutlak mp_int. Algoritme yang digunakan seperti yang diajarkan di sekolah dasar. Fungsi ini melakukan proses penjumlahan antar digit array sebanyak n sehingga kompleksitasnya adalah O(n) dengan n adalah banyaknya digit array. Algoritme fungsi s_mp_add adalah sebagai berikut: Input : mp_int a dan mp_int b Output : c = |a| + |b| 1. If a.used > b.used min b.used max a.used xa
6
2. Else min a.used max b.used xb 3 If c.alloc < max +1 mp_grow(c,max +1) 4. u 0 5. For n from 0 to min-1 cn ( an + bn + u) mod basis u ( an + bn + u) / basis 6. For n from min to max-1 cn (xn + u) mod basis u (xn + u) / basis 7. If u > 0 cn u c.used max +1 8. Else c.used max 9. Return ( MP_OKAY )
melakukan penjumlahan dua bilangan mp_int dengan melihat tanda dari kedua bilangan tersebut. Jika kedua bilangan mempunyai tanda yang sama, maka operasi yang dilakukan adalah penjumlahan dan hasil yang diperoleh mempunyai tanda yang sama dengan bilangan yang ditambahkan. Akan tetapi, jika kedua bilangan mempunyai tanda yang berbeda, maka operasi yang dilakukan adalah operasi pengurangan dan tanda dari hasil yang diperoleh bergantung pada perbandingan kedua bilangan tersebut.
Algoritme fungsi s_mp_add di atas menunjukkan bahwa fungsi tersebut akan melakukan proses penjumlahan antar digit array yang dimulai dari digit array paling tidak signifikan. Jika hasil penjumlahannya melebihi basis yang digunakan, maka akan menghasilkan nilai carry 1. Nilai carry ini akan ditambahkan ke penjumlahan digit array berikutnya.
Tabel 3 Tanda hasil fungsi mp_add Tanda
2. mp_add Fungsi mp_add merupakan fungsi penjumlahan dua bilangan mp_int dengan melihat tanda dari bilangan tersebut. Beberapa kemungkinan tanda yang dihasilkan dari penjumlahan dua bilangan mp_int dapat dilihat pada Tabel 3. Algoritme fungsi mp_add adalah sebagai berikut:
Algoritme fungsi mp_add di atas menunjukkan bahwa fungsi tersebut akan
Operasi
Tanda c
a
b
+
+
c=a+b
+
-
-
c=a+b
-
+
-
a< b
c=b-a
-
-
+
a
c=b-a
+
+
-
a>b
c=a-b
+
-
+
a>b
c = a- b
-
+
-
a=b
c=0
+
-
+
a=b
c=0
+
3. mp_add_mod Fungsi mp_add_mod merupakan fungsi penjumlahan yang digunakan dalam field prima dimana hasil yang diperoleh harus merupakan anggota field tersebut. Jika hasil penjumlahan yang diperoleh bukan merupakan anggota dalam field prima tersebut, maka hasil tersebut harus dilakukan proses reduksi dengan bilangan p. Algoritme fungsi mp_add_mod adalah sebagai berikut:
Input : mp_int a dan mp_int b Output : c = a + b 1. If a.sign = b.sign c.sign a.sign c |a| + |b| (s_mp_add) 2. Else If | a | < | b | c.sign b.sign c |b| - |a| (s_mp_sub) Else if | a | > | b | c.sign a.sign c |a| - |b| (s_mp_sub) Else c.sign MP_ZPOS c 0 (mp_zero) 3. Return ( MP_OKAY )
Ket
Input : mp_int a, mp_int b dan mp_int p Output : c = (a + b) mod p 1. c a + b (mp_add) 2. If c = p c 0 (mp_zero) 3. Else if c > p c c – p (mp_sub) 4. Return ( MP_OKAY ) b.
Pengurangan
Operasi pengurangan yang terdapat dalam librari dibagi menjadi beberapa fungsi. Fungsifungsi tersebut yaitu:
7
1. s_mp_sub Fungsi s_mp_sub digunakan untuk melakukan proses pengurangan dua bilangan mutlak mp_int. Fungsi ini melakukan pengurangan antar digit array sebanyak n sehingga kompleksitasnya adalah O(n) dengan n adalah banyaknya digit array. Algoritme fungsi s_mp_sub adalah sebagai berikut: Input : mp_int a dan mp_int b Output : c = |a| - |b| 1. min b.used 2. max a.used 3. If c.alloc < max mp_grow(c,max ) 4. u 0 5. For n from 0 to min-1 If an ≥ bn + u cn a n - b n - u u0 Else cn an + basis - bn – u u1 6. For n from min to max-1 If an ≥ u cn a n - u u0 Else cn an + basis – u u1 7. c.used max 8. mp_clear_zero ( c ) 9. Return ( MP_OKAY ) Algoritme fungsi s_mp_sub di atas menunjukkan bahwa fungsi tersebut akan melakukan proses pengurangan antar digit array yang dimulai dari digit array paling tidak signifikan. Jika nilai digit array a lebih besar dari digit array b ditambah carry, maka akan menghasilkan nilai carry 1. Nilai carry ini akan digunakan untuk mengurangi digit array a berikutnya. 2. mp_sub Fungsi mp_sub merupakan fungsi pengurangan dua bilangan mp_int dengan melihat tanda dari bilangan tersebut. Beberapa kemungkinan tanda yang dihasilkan dari pengurangan dua bilangan mp_int dapat dilihat pada Tabel 4. Algoritme fungsi mp_sub adalah sebagai berikut: Input : mp_int a dan mp_int b Output : c = a – b
1. If a.sign ≠ b.sign c.sign a.sign c |a| + |b| (s_mp_add) 2. Else If | a | < | b | c.sign ~ a.sign c |b| - |a| (s_mp_sub) Else if | a | > | b | c.sign a.sign c |a| - |b| (s_mp_sub) Else c.sign MP_ZPOS c 0 (mp_zero) 3. Return ( MP_OKAY ) Algoritme fungsi mp_sub di atas menunjukkan bahwa fungsi tersebut akan melakukan pengurangan dua bilangan mp_int dengan melihat tanda dari kedua bilangan tersebut. Jika kedua bilangan mempunyai tanda yang berbeda, maka operasi yang dilakukan adalah penjumlahan dan hasil yang diperoleh mempunyai tanda yang sama dengan bilangan yang dikurangi. Akan tetapi, jika kedua bilangan mempunyai tanda yang sama, maka operasi yang dilakukan adalah operasi pengurangan dan tanda dari hasil yang diperoleh bergantung pada perbandingan kedua bilangan tersebut. Tabel 4 Tanda hasil fungsi mp_sub Tanda
Ket
Operasi
Tanda c
a
b
+
-
c=a+b
+
-
+
c=a+b
-
+
+
a
c=b-a
-
-
-
a
c=b-a
+
+
+
a>b
c=a-b
+
-
-
a>b
c = a- b
-
+
+
a=b
c=0
+
-
-
a=b
c=0
+
3. mp_sub_mod Fungsi mp_sub_mod merupakan fungsi pengurangan yang digunakan dalam field prima dimana hasil yang diperoleh harus merupakan anggota field tersebut. Jika hasil yang diperoleh bukan merupakan anggota dalam field prima tersebut, maka hasil tersebut harus dilakukan proses reduksi dengan bilangan p. Algoritme
8
fungsi mp_sub_mod berikut:
adalah
sebagai
Input : mp_int a, mp_int b dan mp_int p Output : c = (a - b) mod p 1. c a - b (mp_sub) 2. Else if c.sign = MP_NEG c c + p (mp_add) 3. Return ( MP_OKAY ) c.
Perkalian
Operasi perkalian yang terdapat dalam librari dibagi menjadi beberapa fungsi. Fungsifungsi tersebut yaitu: 1. s_mp_mul Fungsi s_mp_mul merupakan fungsi perkalian dua bilangan mutlak mp_int yang menggunakan algoritme schoolbook. Jika dua bilangan mp_int a dan b mempunyai digit array yang sama sebanyak n, maka banyaknya perkalian antar digit array adalah n2 dan banyaknya penjumlahan adalah (n-1)2 (Weimerskirch & Paar 2006). Algoritme fungsi s_mp_mul adalah sebagai berikut: Input : mp_int a dan mp_int b Output : c = |a| |b| 1. Inisialisasi x dan y 2. For n from 0 to b.used-1 u0 For m from 0 to a.used-1 xm+n (am bn+ u) mod basis u (am bn+ u) / basis If u > 0 xm+n u x.used m + n +1 Else x.used m + n y y + x (mp_add) x 0 (mp_zero) 3. c y 4. Bersihkan variabel sementara 5. Return ( MP_OKAY ) Algoritme fungsi s_mp_mul di atas menunjukkan bahwa fungsi tersebut melakukan perkalian bilangan a dengan seluruh digit array b dimana setiap perkalian menghasilkan bilangan x. Hasil akhir dari fungsi ini merupakan penjumlahan seluruh bilangan x yang dihasilkan. 2. s_mp_sqr Fungsi s_mp_sqr merupakan fungsi kuadrat atau fungsi perkalian khusus
dimana nilai multiplicand sama dengan nilai multiplier. Untuk bilangan n-digit array, diperlukan (n2 + n)/ 2 perkalian tunggal. Hal ini tentu akan lebih baik jika dibandingkan dengan perkalian biasa yang memerlukan n2 perkalian tunggal. Algoritme fungsi s_mp_sqr adalah sebagai berikut: Input : mp_int a Output : b = a2 1. Inisialisasi c (init) 2. c.used 2 a.used 3. For i from 0 to a.used-1 r c2i + ai2 c2i r mod basis u r / basis k1 For j from i + 1 to a.used-1 r 2 ai aj + u + c2i + k c2i + k r mod basis u r / basis k k +1 While u > 0 do r u + c2i + k c2i + k r mod basis u r / basis k k +1 4. mp_clear_zero(c) 5. b c 6. Bersihkan variabel sementara 7. Return ( MP_OKAY ) 3. mp_mul Fungsi mp_mul merupakan fungsi perkalian dua bilangan mp_int dengan melihat tanda dari kedua bilangan tersebut. Algoritme fungsi mp_mul adalah sebagai berikut: Input : mp_int a dan mp_int b Output : c = a b 1. c = |a| |b| (s_mp_mul) 2. If a.sign = b.sign c.sign MP_ZPOS 3. Else If c= 0 c.sign MP_ZPOS Else c.sign MP_NEG 4. Return ( MP_OKAY ) Algoritme fungsi mp_mul di atas menunjukkan bahwa fungsi tersebut akan mengalikan dua bilangan mp_int dengan melihat tanda dari kedua bilangan tersebut. Jika kedua bilangan mempunyai tanda yang sama, maka hasil yang diperoleh bernilai
9
positif. Akan tetapi, jika kedua bilangan mempunyai tanda yang berbeda maka hasil yang diperoleh bernilai negatif tetapi jika salah satu bilangannya bernilai 0 maka hasil yang diperoleh bernilai positif.
B adalah basis yang digunakan. Jika pada persamaan di atas nilai bn-1 ≥ a / b, maka q’-2 ≤ q ≤ q’ (Knuth 1998, diacu dalam Welschenbach 2005). Dengan asumsi bahwa nilai bn-1 mendekati nilai B, maka nilai q’ adalah q’-2 ≤ q ≤ q’.
4. mp_mul_mod
Proses normalisasi pada fungsi mp_div hanya akan mengubah nilai sisa bagi pada proses pembagian tanpa mengubah nilai hasil bagi. Oleh karena itu, untuk mendapatkan nilai sisa bagi yang sebenarnya diperlukan proses denormalisasi yaitu dengan membagi sisa bagi dengan k. Algoritme fungsi mp_div dapat dilihat pada Lampiran 1.
Fungsi mp_mul_mod merupakan fungsi perkalian yang digunakan dalam field prima dimana hasil yang diperoleh harus merupakan anggota field tersebut. Jika hasil yang diperoleh bukan merupakan anggota dalam field tersebut, maka hasil tersebut harus dilakukan proses reduksi. Algoritme fungsi mp_mul_mod adalah sebagai berikut:
2. mp_div_mod
Input : mp_int a, mp_int b, dan mp_int p Output : c =( a b) mod p
Fungsi mp_div_mod merupakan fungsi pembagian yang digunakan dalam field prima dimana pembagian suatu bilangan a oleh b merupakan perkalian bilangan a dengan b-1. Jika hasil yang diperoleh bukan merupakan anggota dalam field tersebut , maka hasil tersebut harus dilakukan proses reduksi. Algoritme fungsi mp_div_mod adalah sebagai berikut:
1. c = a b (mp_mul) 2. If c = a c 0 ( mp_zero) 3. Else if c > p c c mod p (mp_mod) 4. Return ( MP_OKAY ) d.
Pembagian
Input : mp_int a, mp_int b, dan mp_int p Output : c =( a / b) mod p
Operasi pembagian yang terdapat dalam librari dibagi menjadi beberapa fungsi. Fungsifungsi tersebut yaitu:
1. Inisialisasi d 2. d b-1 (mp_invmod) 3. c a b-1 (mp_mul) 4. If c = a c 0 ( mp_zero) 5. Else if c > a c c mod p (mp_mod) 6. Return ( MP_OKAY )
1. mp_div Fungsi mp_div digunakan untuk melakukan operasi pembagian antara bilangan mutlak mp_int a dan bilangan mutlak mp_int b. Fungsi ini akan menghasilkan nilai hasil bagi dan sisa bagi. Algoritme yang digunakan pada fungsi ini adalah algoritme pembagian klasik seperti yang diajarkan di sekolah dasar hanya saja sebelum dilakukan proses pembagian terdapat proses normalisasi. Proses normalisasi dilakukan agar nilai digit array paling signifikan b lebih besar atau sama dengan basis/2 (bn ≥ basis/2) dengan mengalikan suatu konstanta k pada a dan b. Nilai k sebaiknya merupakan kelipatan 2 sehingga operasinya hanya shift. Dengan adanya proses normalisasi ini, nilai perkiraan hasil bagi (q’) akan mendekati nilai hasil bagi sebenarnya (q). Jika digit array a = digit array b + 1 maka nilai q’ diperoleh dari persamaan :
e.
Reduksi
Reduksi merupakan operasi yang dilakukan untuk mencari nilai sisa bagi dari pembagian dua bilangan mp_int sehingga hasil yang diperoleh merupakan anggota field prima. Fungsi dalam librari yang digunakan untuk melakukan operasi reduksi yaitu: mp_mod Algoritme fungsi mp_mod menggunakan algoritme pembagian klasik sama seperti pada fungsi mp_div dimana output dari fungsi mp_div adalah nilai hasil bagi dan nilai sisa bagi. Nilai sisa bagi inilah yang diperlukan oleh fungsi mp_mod.
a B + a n−1 q ' = min n , B − 1 bn−1
10
f.
Invers Perkalian
Invers perkalian suatu bilangan mp_int a adalah a-1 dengan a a-1 = 1. Nilai invers tersebut diperlukan dalam operasi pembagian pada field prima. Fungsi dalam librari yang digunakan untuk melakukan operasi invers perkalian yaitu: mp_invmod Fungsi mp_invmod digunakan untuk mencari nilai invers perkalian pada suatu bilangan mp_int a pada field prima p. Algoritme yang digunakan fungsi ini adalah extended Euclidean. Algoritme ini menggunakan operasi pembagian dalam prosesnya sehingga membutuhkan cost yang cukup tinggi. Algoritme fungsi mp_invmod adalah sebagai berikut: Input : mp_int a dan mp_int p Output : c = a-1 1.Inisialisasi q, r, y1, y2, mul, y, ta, dan tb 2. ta p 3. tb a 4. y2 1 5. If b=0 Return (MP_VAL) 6. While tb ≠ 0 q ta / tb r ta mod tb y y1 – q y2 ta tb tb r y1 y2 y2 y 7. c y1 mod p 8. Bersihkan variabel sementara 9. Return ( MP_OKAY ) g.
Eksponensial
Operasi eksponensial merupakan operasi yang berperan penting dalam kriptografi kunci asimetrik. Operasi ini digunakan dalam proses enkripsi dan dekripsi. Fungsi dalam librari yang digunakan untuk melakukan operasi eksponensial yaitu: mp_exp_mod Fungsi mp_exp_mod merupakan fungsi eksponensial yang digunakan pada field prima. Algoritme yang digunakan pada fungsi ini adalah left to right exponentiation. Algoritme ini bekerja dengan menggunakan nilai biner dari bilangan pemangkatnya (b). Algoritme ini melakukan proses perkalian multipresisi sebanyak n + t dengan n adalah panjang bit b dan t adalah banyaknya bit b yang
bernilai 1. Algoritme fungsi mp_exp_mod adalah sebagai berikut: Input : mp_int a, mp_int b, dan mp_int p Output : c = ab mod p 1. c 1 2. x 1 << bitlength(basis) -1 3. For i from b.used-1 to 0 temp bi For j from 0 to bitlength(basis)-1 c c2 mod p If temp & x ≠ 0 c (c a) mod p temp temp << 1 4. Return ( MP_OKAY ) Pengujian Pengujian dilakukan dengan cara membandingkan output yang dihasilkan sistem dengan output yang dihasilkan oleh software pembanding sehingga dapat diketahui nilai kebenaran dari output tersebut. Software yang digunakan sebagai pembanding adalah MAPLE 12. Pengujian dilakukan sebanyak 10 kali untuk masing-masing operasi dan dihasilkan output yang benar. Untuk mengetahui kinerja sistem, dihitung nilai total waktu eksekusinya. Total waktu eksekusi dari hasil pengujian terhadap masing-masing fungsi aritmatik field prima dapat dilihat pada tabel-tabel di bawah ini. Tabel
Bit
5 Total waktu eksekusi penjumlahan pada field prima Total Waktu Konversi Basis (s)
fungsi
Waktu Operasi ( s)
Total Waktu (s)
256
0.000472
0.0000028
0.000475
512
0.001963
0.0000028
0.001966
1024
0.010542
0.0000036
0.010545
Tabel 5 di atas menunjukkan bahwa total waktu konversi basis (dari basis 10 ke basis 232 kemudian dikonversi kembali dari basis 232 ke basis 10) jauh lebih besar dari waktu operasi penjumlahan. Oleh karena itu, proses konversi basis sangat mempengaruhi total waktu eksekusi operasi penjumlahan.
11
Tabel
6 Total waktu eksekusi pengurangan pada field prima Waktu Operasi ( s)
fungsi
Bit
Total Waktu Konversi Basis (s)
256
0.000472
0.0000029
0.000475
512
0.001963
0.0000035
0.001967
1024
0.010542
0.0000041
0.010546
Total Waktu (s)
Tabel 8 di atas menunjukkan bahwa total waktu konversi basis pada operasi pembagian lebih kecil dari pada waktu operasinya tetapi perbedaannya tidak terlalu signifikan. Akan tetapi, jika hanya dilihat pada waktu operasinya, operasi pembagian memerlukan waktu yang jauh lebih besar dari operasi perkalian. Hal ini disebabkan jumlah proses pada operasi pembagian jauh lebih banyak dari operasi perkalian dimana pada operasi pembagian terdapat proses invers dan juga perkalian. Tabel
Tabel 6 di atas menunjukkan bahwa total waktu eksekusi operasi pengurangan sama seperti operasi penjumlahan. Hal ini dikarenakan banyaknya proses pada operasi pengurangan dan operasi penjumlahan adalah sama atau dengan kata lain kedua proses ini memiliki kompleksitas yang sama. Tabel 7 Total waktu eksekusi fungsi perkalian pada field prima Waktu Operasi ( s)
9 Total waktu eksekusi eksponensial pada field prima Waktu Operasi ( s)
fungsi
Bit
Total Waktu Konversi Basis (s)
256
0.000472
0.0121269
0.012599
512
0.001963
0.0614644
0.063428
1024
0.010542
0.4215481
0.432090
Total Waktu (s)
Bit
Total Waktu Konversi Basis (s)
256
0.000472
0.0000353
0.000507
512
0.001963
0.0000977
0.002061
Tabel 9 di atas menunjukkan bahwa waktu operasi pada operasi eksponensial jauh lebih besar dari total waktu konversi basisnya. Hal itu menyebabkan total waktu eksekusi operasi eksponensial tidak berbeda jauh dengan waktu operasinya.
1024
0.010542
0.0003669
0.010909
KESIMPULAN DAN SARAN
Total Waktu (s)
Kesimpulan Tabel 7 di atas menunjukkan bahwa total waktu eksekusi operasi perkalian tidak berbeda jauh dengan operasi penjumlahan dan pengurangan. Hal ini disebabkan perbandingan antara total waktu konversi basis dan waktu operasi sangat besar. Akan tetapi, jika dilihat pada waktu operasinya, waktu operasi pada perkalian jauh lebih besar dari operasi penjumlahan dan pengurangan. Tabel 8 Total waktu eksekusi fungsi pembagian pada field prima
Bit
Total Waktu Konversi Basis (s)
Waktu Operasi ( s)
256
0.000472
0.0043139
0.004786
512
0.001963
0.0065998
0.008563
1024
0.010542
0.0190874
0.029629
Total Waktu (s)
Bilangan besar direpresentasikan dalam basis 232 pada komputer 32 bit. Representasi ini akan membutuhkan jumlah digit array paling sedikit bila dibandingkan dengan representasi lainnya sehingga efisien dalam penggunaan memori. Untuk bilangan 1024 bit hanya dibutuhkan 32 digit array. Semakin sedikit digit array yang dibutuhkan untuk merepresentasikan bilangan besar, maka semakin cepat komputasi pada bilangan besar tersebut. Dari pengujian yang dilakukan sebanyak 10 kali untuk masing-masing operasi pada field prima, sistem menghasilkan output yang benar. Pada bilangan 1024 bit, operasi penjumlahan membutuhkan waktu eksekusi sebesar 0.010545 s, operasi pengurangan membutuhkan waktu eksekusi sebesar 0.010546 s, operasi perkalian membutuhkan waktu eksekusi sebesar 0.010909 s, operasi pembagian membutuhkan waktu eksekusi sebesar 0.029629 s, dan operasi pengurangan membutuhkan waktu eksekusi sebesar 0.432090 s.
12
