ARITMETIKA FIELD BINER MENGGUNAKAN GMP LIBRARY DALAM PEMROGRAMAN PROSEDURAL C
IKI LOBO
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2010
ARITMETIKA FIELD BINER MENGGUNAKAN GMP LIBRARY DALAM PEMROGRAMAN PROSEDURAL C
IKI LOBO
Skripsi Sebagai salah satu syarat untuk memperoleh gelar Sarjana Komputer pada Departemen Ilmu Komputer
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2010
ABSTRACT
IKI LOBO. Binary Field Arithmetic using GMP Library in C Procedural Programming. Under the direction of SUGI GURITMAN. Almost all cryptographic algorithms involve the construction of integer arithmetic operations. The operations is referred to huge operation to an integer value in order to support the level of security of a cryptosystem. Related to this, the arithmetic operations in binary field is needed to construct various cryptographic algorithms. Binary field arithmetic implementation starts with the representation of its members, who then will be done by operating the addition, multiplication, reduction, and inversion. Each operation is simulated in 1024 bit length or more. Unlike the addition of polynomial operations that are directly applicable in the binary field , multiplication operations require reduction step necessary to build . Through experiments conducted for three types of reduction each Trinomial, Pentanomial, and Full Polynomial, apparently Full Polynomials provide the most high-speed reduction.
Keywords : arithmetic, binary field, gnu multi precision (GMP), c programming.
Judul Nama NRP
: Aritmetika Field Biner Menggunakan GMP Library dalam Pemrograman Prosedural C : Iki Lobo : G64060450
Menyetujui Pembimbing
Dr. Sugi Guritman 1962092719922031004
Mengetahui: Ketua Departemen Ilmu Komputer,
Dr. Ir. Sri Nurdiati, M.Sc. NIP. 19601126 198601 2 001
Tanggal Lulus:
RIWAYAT HIDUP Penulis dilahirkan pada tanggal 19 April 1988 di Atambua, NTT, dari pasangan Bapak Lodywik Lobo dan Ibu Bertha Bale. Penulis lulus dari Sekolah Menengah Atas (SMA) Negeri 1 Atambua pada tahun 2006 dan di tahun yang sama diterima sebagai mahasiswa Institut Pertanian Bogor. Pada tahun 2007 penulis diterima sebagai mahasiswa Departemen Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA), Institut Pertanian Bogor. Selanjutnya, di tahun 2009 penulis terpilih menjadi finalis Lomba Data Mining Contest Gemastik II, Direktorat Penelitian dan Pengabdian kepada Masyarakat (DP2M) Direktorat Jendral Pendidikan Tinggi (DIKTI).
KATA PENGANTAR Segala puji syukur penulis panjatkan ke hadirat Tuhan Yesus Kristus atas berkat dan karunia-Nya sehingga penulis dapat menyelesaikan skripsi yang berjudul Aritmetika Field Biner Menggunakan GMP Library dalam Pemrograman Prosedural C. Pembuatan tulisan ini tentu tidak lepas dari bantuan dan dukungan berbagai pihak, oleh karena itu penulis ingin menyampaikan ucapan terima kasih kepada: 1. 2. 3. 4. 5. 6. 7. 8.
Bapak Dr. Sugi Guritman selaku dosen pembimbing yang telah meluangkan waktu serta memberi bimbingan dan pengarahan sehingga penulis dapat menyelesaikan tugas akhir ini. Bapak Endang Purnama Giri, S.Kom, M.Kom, dan Bapak Hendra Rahmawan, S.Kom, M.T selaku dosen penguji. Papa dan Mama, serta saudaraku Abba, Lia, Ary, Rio, dan Ani, atas doa dan kasih sayang, serta dukungan materiil selama ini. Orang terkasih yang selalu memberi semangat dan dukungan doa. Rekan-rekan satu bimbingan Lukman, Haryadi, Abi dan semua rekan di Lab NCC. Terima kasih atas semangat dan kerja sama serta kebersamaannya selama penyelesaian tugas akhir ini. Keluarga besar Ilkomerz 43. Terima kasih atas motivasi dan kebersamaan yang telah dilalui selama 3 tahun ini. Saudara-saudara Gamanusratim, terima kasih buat dukungannya. Seluruh pihak yang turut membantu baik secara langsung maupun tidak langsung dalam penyelesaian tugas akhir ini.
Penulis menyadari dalam penulisan tugas akhir ini masih terdapat banyak kekurangan. Penulis berharap adanya saran atau kritik yang bersifat membangun dari pembaca. Semoga tugas akhir ini bermanfaat.
Bogor, Agustus 2010
Iki Lobo
DAFTAR ISI Halaman DAFTAR GAMBAR ..............................................................................................................
v
DAFTAR LAMPIRAN ...........................................................................................................
v
PENDAHULUAN Latar Belakang ................................................................................................................... Tujuan ................................................................................................................................ Ruang Lingkup ................................................................................................................... Manfaat Penelitian ..............................................................................................................
1 1 1 1
TINJAUAN PUSTAKA Field .................................................................................................................................. Field Berhingga .................................................................................................................. Field Biner ......................................................................................................................... GMP Library ...................................................................................................................... Polinomial Atas ..............................................................................................................
1 1 1 2 2
METODE PENELITIAN Studi Literatur ................................................................................................................... Implementasi ..................................................................................................................... Pengujian ..........................................................................................................................
2 2 4
HASIL DAN PEMBAHASAN Representasi anggota Field Biner ................................................................................. Operasi Adisi Field Biner ............................................................................................ Operasi Multiplikasi dan Kuadrat Polinomial ...................................................................... Operasi Reduksi pada Field Biner ................................................................................ Operasi Inversi pada Field Biner .................................................................................. Aritmetik dalam .........................................................................................................
4 5 5 6 8 8
PENUTUP Kesimpulan ....................................................................................................................... Saran .................................................................................................................................
9 9
DAFTAR PUSTAKA .............................................................................................................
9
LAMPIRAN ...........................................................................................................................
10
iv
DAFTAR GAMBAR Halaman 1. 2. 3. 4. 5. 6.
Waktu Operasi Rata-rata Simulasi Representasi ................................................................ Waktu Rata-rata Simulasi Operasi Adisi ........................................................................... Waktu Rata-rata Simulasi Operasi Multiplikasi dan Kuadrat Polinomial ............................ Waktu Rata-rata Simulasi Operasi Reduksi Trinomial dan Polinomial Penuh .................... Waktu Rata-rata Simulasi Operasi Reduksi Pentanomial dan Polinomial Penuh ................. Waktu Rata-rata Simulasi Operasi Inversi .........................................................................
5 5 6 7 7 8
DAFTAR LAMPIRAN Halaman 1. 2.
Keluaran Program Representasi Anggota Field Biner dengan Panjang 1024 bit ................. Hasil Uji Metode Black Box ............................................................................................. 3. Waktu Rata-rata Simulasi .................................................................................................
11 12 13
v
PENDAHULUAN Latar Belakang Kajian kriptografi yang berkembang saat ini memacu kerja dari berbagai algoritme kriptografi yang telah atau yang akan diciptakan, sehingga algoritme tersebut dapat melakukan komputasi aritmetika yang rumit dan mampu mengolah perhitungan yang panjang. Namun, penting diperhatikan bahwa tingkat kerumitan dalam pemrosesan yang dilakukan sebuah algoritme akan berpengaruh pada kerja perangkat yang diimplementasi. Perangkat komputer dengan prosesor 32 bit atau 64 bit saat ini hanya mampu melakukan operasi aritmetika dan memberikan hasil sepanjang bit tersebut, sehingga diperlukan bantuan perangkat lunak dengan algoritme aritmetika tertentu untuk mengerjakan perhitungan yang memberikan hasil lebih dari itu. Hampir semua konstruksi algoritme kriptografi melibatkan operasi aritmetika integer, dan operasi yang dimaksudkan di sini adalah operasi aritmetika untuk integer bernilai besar yang diperlukan demi menunjang tingkat keamanan dari suatu algoritme kriptografi yang akan dibangun. Terkait dengan hal ini, operasi dalam aritmetik field biner diperlukan yang selanjutnya digunakan untuk mengonstruksi berbagai algoritme kriptografi. Penelitian ini mengimplementasikan operasi dalam aritmetika field biner menggunakan bahasa pemrograman C, oleh karena kecepatan komputasi yang diberikan bahasa ini cukup baik dalam mengerjakan perhitungan, khususnya integer bernilai besar yang operasinya sendiri dalam penelitian ini menggunakan GMP Library untuk bahasa pemrograman C.
digunakan untuk konstruksi algoritme kunci publik, fungsi hash, digital signature, dan algoritme lain yang dipakai dalam sebuah kriptosistem.
TINJAUAN PUSTAKA Field Suatu himpunan yang didefinisikan oleh operasi jumlah ( + ) dan operasi kali ( * ) disebut field, notasi ( , + ,*) jika memenuhi sifat-sifat berikut. 1 ( ,+) merupakan grup komutatif terhadap +, yaitu memenuhi sifat-sifat: asosiatif: ( a,b,c ) (a+b)+c = a+(b+c), mempunyai unsur identitas: (∃!0 )( a ) 0+a = a+0, setiap unsur dari mempunyai invers: ( a ) (∃!b ) b+a = a+b = 0, b = (–a), dan komutatif: ( a,b ) a+b = b+a. 2 ( *, .) dimana * = \ { 0 }, merupakan grup komutatif terhadap * bersifat: asosiatif: ( a,b,c ) (ab)c = a(bc), * mempunyai unsur identitas: (∃!1 *) ( a *) 1.a = a.1 = a, setiap unsur dari * mempunyai invers: ( a *) (∃!b ) ba = ab = 1, b = (a–1), dan komutatif: ( a,b ) a.b = b.a. 3 Berlaku sifat distributif * terhadap + : ( a,b,c ) a(b+c) = ab+ac atau (b+c)a = ba+ca.
Tujuan
(Hankerson et al. 2004).
Tujuan utama dari penelitian ini adalah implementasi operasi-operasi aritmetika field biner untuk bilangan yang besar.
Field Berhingga
Ruang Lingkup Ruang lingkup penelitian ini difokuskan pada implementasi operasi adisi, multiplikasi, reduksi, dan inversi pada aritmetik field biner, dengan kajian implementasinya sendiri adalah melihat tingkat kecepatan dari setiap operasi yang disimulasikan. Manfaat Penelitian Penggunaan aritmetika field biner dapat memberikan efisiensi komputasi, dan diharapkan melalui implementasi aritmetika field biner dapat mempercepat perhitungan bilangan-bilangan besar untuk pembangkitan algoritme kriptografi. Motivasinya ke depan adalah aritmetika ini dapat
Konsep field berhingga terkait dengan pengertian polinomial dan operasinya. Jika p adalah prima, f(x) p[x] adalah tak-teruraikan atas p dan berderajat n, maka ekstensi field p[x]/f(x) dari p disebut field berhingga. Lebih khusus lagi untuk p = 2, disebut field biner (Hankerson et al. 2004). Field Biner Field berhingga 2m disebut field biner atau characteristic-two finite fields merupakan suatu himpunan yang terdiri atas elemen-elemen polinomial biner, yakni polinomial yang koefisien dalam field F2 berderajat m-1: =
Sebagai ilustrasi, dipilih polinomial takteruraikan atas 2 (biner), yaitu f(x)=x4+x+1. Anggota dari field biner dalam empat representasi: polinomial, vektor koordinat, grup siklik, dan himpunan yang saling berpadanan satu-satu disajikan dalam tabel berikut (Menezes et al. 2004). Tabel 1 Representasi
a(x)b(x) = c(x) = c(x) =
, dengan , dimana
deg(a(x)b(x)) = deg(a(x)) + deg(b(x)). GMP Library GNU Multi Precision Library atau disingkat GMP Library merupakan sebuah pustaka yang didistribusikan secara gratis untuk mengolah aritmetika bilangan besar. Operasinya dapat dikerjakan untuk tipe bilangan bulat bertanda, bilangan rasional, dan bilangan float. Target utama dari library ini adalah aplikasi kriptografi dan penelitian, maupun aplikasi keamanan internet. Penulis aslinya adalah Torbjörn Granlund yang merupakan pengembang utama dari library ini (http://gmplib.org).
METODE PENELITIAN Penelitian ini dilakukan melalui tahapantahapan berikut. Polinomial Atas
Studi Literatur
Jika diberikan field notasi a(x) berbentuk
, suatu ekspresi, dalam
=a0+a1x+a2x2+…+anxn+…
a(x)=
disebut sebagai polinomial dalam x atas jika , dimana ai disebut koefisien i=0,1,2,…,ai ke-i dari suku ke-i (aixi ), dan x merupakan simbol sebagai placeholder. Polinomial a(x) dikatakan berderajat n, notasi deg(a(x)) = n, jika an ≠ 0 dan ai = 0 untuk setiap i>n. Dengan demikian an disebut koefisien pemimpin, dan sukunya anxn disebut suku pemimpin. Polinomial
a(x) =
dan
b(x) = dikatakan sama, notasi a(x) = b(x) jika deg(a(x)) = deg(b(x)) = n dan ai=bi, Selanjutnya, jika i=0,1,2,…,n. didefinisikan [x] sebagai himpunan semua polinomial atas , maka dapat dituliskan [x]=
.
Berikutnya, jika dimisalkan a(x) dan b(x) adalah sembarang dua anggota [x], maka operasi adisi pada [x] didefinisikan sebagai a(x) + b(x) =
, dimana
deg(a(x)+b(x)) = max{deg(a(x)), deg(b(x))} dan multiplikasi didefinisikan sebagai
Tahapan ini diperlukan untuk mempelajari prinsip dasar aritmetika, field, aritmetika field biner dan kajian umum lain yang berkaitan dengan aritmetika tersebut seperti aplikasi yang menggunakan kriptografi kurva eliptik. Implementasi Pada tahapan ini akan dilakukan implementasi terhadap algoritme operasi-operasi aritmetika field biner. Berikut metodologi yang akan dikerjakan dalam tahapan ini. 1. Representasi Anggota Field Biner Jika diasumsikan platform implementasi menggunakan mesin W-bit t kata dengan nilai W kelipatan 8, dan misalkan a = (am–1, am–2, …, a1, a0) , dengan t = , maka representasi t kata W-bit disajikan dalam bentuk larik berikut. A[t – 1]
…
A[2]
A[1]
A[0]
Larik ini juga merupakan representasi polinomial berderajat paling banyak m-1 yang dituliskan mengikuti struktur polinomial berikut, a(x)=A[t–1]x(t-1)W+…+A[2]x2W+A[1]xW+A[0], dimana A[i], untuk i = 0,1,…,(t – 1) adalah bitstring dengan panjang W sebagai representasi polinomial berderajat paling banyak W–1. Sebagai ilustrasi, jika diberikan field biner dengan 2
a(x)= x9+ x6+ x4+ x2+ x+1 maka representasi binernya [1 0 0 1 0 1 0 1 1 1]. 2. Implementasi Operasi Adisi pada Field Biner Operasi adisi mengikuti definisi jumlah polinomial, yakni menjumlahkan masing-masing dari setiap suku tanpa ada pengaruh simpan, dan dimaknai sebagai operasi per satuan bit dalam kasus biner. Layaknya sebuah operasi adisi, dibutuhkan minimal dua operand yang akan dioperasi, dengan mengikuti aturan penjumlahan polinomial. Jadi, operasi adisi pada field biner menerapkan operasi XOR (exclusive or). Notasi memaknai XOR. Operasi adisi dikembangkan dari algoritme adisi berikut.
a(x)b(x) = am-1xm-1b(x)+…+a1b(x)+a0b(x). Operasi ini memerlukan dua input sebagai operand pertama dan kedua yang akan dioperasi mengikuti definisi sebelumnya. Pengembangan algoritme berikut menjadi landasan dari operasi multiplikasi. Input: a=(am-1,…,a1,a0), b=(bn-1,…,b1,b0) Output: c=a*b 1. c←0, m≥n, ctemp=0 2. for i=0 to n–1 if bi=1, ci←a else bi=0, c←0 ctemp=ctemp<<1 ctemp=ctemp ci 3. return c Sebagai ilustrasi, dipilih dua polinomial dari anggota (Tabel 1) a(x) = x3+x, dan
Input: a=(am-1,…,a1,a0), b=(bn-1,…,b1,b0) Output: c=a+b 1. c←a, m≥n 2. for i=0 to i=n ci =ci bi 3. return c
maka operasi multiplikasi polinomial a(x) dan b(x) menghasilkan c(x), suatu polinomial hasil multiplikasi dengan c(x) = a(x)b(x),
Sebagai ilustrasi, dipilih dua polinomial dari anggota (Tabel 1)
Representasi biner untuk multiplikasi sebagai berikut,
a(x) = x3+x, dan b(x) = x2+x+1, maka operasi multiplikasi polinomial a(x) dan b(x) menghasilkan c(x), suatu polinomial hasil adisi dengan c(x) = a(x)+b(x), c(x) = x3+x2+1. Representasi biner untuk operasi adisi sebagai berikut, a = [1 0 1 0], b = [1 1 1], dan c = [1 1 0 1]. Terkait operasi adisi pada , maka dapat dipakai juga untuk operasi substraksi, karena metode operasi adisi dan substraksi pada adalah sama. 3. Implementasi Operasi Multiplikasi pada Field Biner Jika dalam operasi adisi polinomial secara langsung dapat diterapkan pada field biner tanpa mengalami proses reduksi, maka operasi multiplikasi pada memerlukan dua tahap perhitungan yaitu perkalian polinomial dan dilanjutkan ke reduksi. Tahap reduksi dibahas tersendiri dalam operasi reduksi. Operasi multiplikasi polinomial, sebagaimana adisi polinomial, dikerjakan per satuan bit mengikuti definisi berikut,
b(x) = x2+x+1,
c(x) = x5+x4+x2+x. operasi
a = [1 0 1 0], b = [1 1 1], dan c = [1 1 0 1 1 0]. 4. Implementasi Operasi Kuadrat Melalui operasi multiplikasi pada dapat dibentuk operasi perpangkatan yang memberikan kecepatan komputasi yang lebih baik dibanding perkalian biasa, yakni perhitungan a2 akan lebih baik daripada a*a. Operasi kuadrat polinomial memberikan kecepatan komputasi yang lebih baik dari perkalian biasa, yang didasarkan pada fakta bahwa multiplikasi polinomial dalam 2 untuk (x+y)2=x2+y2, sehingga jika diberikan, a(x) = am-1xm-1+…+ a2x2+a1x+a0, maka [a(x)]2= am-1x2m-2+…+ a2x4+a1x2+a0, dimana dalam kalkulasinya, cukup disisipkan bit "0" pada vektor a = (am-1… a2,a1,a0), maka representasi bit dari a(x) menjadi vektor a = (0,am-1…0,a2,0,a1,0,a0). dan dalam simulasinya hanya dibutuhkan satu input m sebagai operand yang akan dikerjakan melalui operasi perpangkatan.
3
5. Implementasi Operasi Reduksi pada Field Biner
tak-teruraikan atas berderajat m yang digunakan untuk mengonstruksi field . Oleh karena itu, setiap a(x) merupakan polinomial berderajat paling banyak m – 1 dan dijamin mempunyai invers, yang dinotasikan a–1 , sehingga aa–1 = 1 dalam , artinya
Proses reduksi, yakni menghitung c(x) mod p(x), merupakan lanjutan dari aritmetika yang telah menghasilkan suatu polinomial c(x) melalui operasi multiplikasi atau penguadratan, dan p(x) adalah polinomial tak-teruraikan yang digunakan untuk membangun .
aa–1 ≡ 1(mod p(x)). Ide dasar inversi menggunakan metode Biner, yakni menghitung secara berulang untuk memperbarui nilai u dan v sampai u=1 atau v=1 dari persamaan ag1+ph1 ≡ u(mod p(x)) dan ag2+ph2≡ v(mod p(x)) sedemikian sehingga gcd(u,v) = gcd(a,p) dengan u = a, g1 = 1, h1 = 0, dan v = p, g2 = 0, h2 = 1
Jika p(x), polinomial tak-teruraikan berderajat m yang didefinisikan sebagai, p(x) = pmxm+pm-1xm-1+…+p1x+p0, dan c(x) merupakan polinomial hasil multiplikasi atau penguadratan yang berderajat paling banyak (2m-2) didefinisikan sebagai, c(x) = c2m-2x2m-2+…+cmxm+cm-1xm-1+…+c1x+c0, maka proses reduksi umum dilakukan per bit berdasarkan rumusan berikut.
Rumusan gcd(u,v) = gcd(a,p) didasarkan pada sifat berikut.
Analogikan, p(x) =xm+d(x), dimana
1.
d(x) = pm-1xm-1+…+p1x+p0, berderajat paling banyak (m-1), dan c(x) dapat dituliskan sebagai, c(x) = (c2m-2xm-2+…+cm)xm + (cm-1xm-1+…+c1x+c0), c(x)
2.
q(x)d(x) + r(x) (mod p(x)), dimana
Pengujian
q(x) = c2m-2xm-2+…+cm r(x) = cm-1xm-1+…+c1x+c0 Sebagai ilustrasi, jika polinomial hasil multiplikasi,
c(x)
Jika u habis dibagi x dan v tidak, maka gcd(u,v) = gcd( ,v), dan sebaliknya apabila v habis dibagi x dan u tidak, maka gcd(u,v) = gcd(u, ) Jika u dan v tidak habis dibagi x, maka gcd(u,v) = gcd(u–v ,v).
suatu
Tahap ini dilakukan menggunakan metode black box, untuk mengetahui hasil dari input yang diberikan, apakah keluaran yang diberikan telah sesuai seperti yang diharapkan.
c(x) = x8+x7+x5+x4+x2+1 direduksi oleh suatu polinomial tak-teruraikan
HASIL DAN PEMBAHASAN
p(x) = x5+x2+1
Analisis hasil implementasi, menghitung kecepatan rata-rata dari tiap-tiap operasi yang disimulasikan mengikuti persamaan berikut.
maka melalui mekanisme berikut, c(x) (x3+x2+1)x5 + (x4+x2+1) (x3+x2+1)(x2+1) + (x4+x2+1) 3 2 (x +x +1)(x2+1) = x5+x4+x3+1 sehingga c(x) x5 + [(x4+x2+1) + (x4+x3+1)] (x2+1) + (x3+x2) (x3+1). Jadi, c(x) mod p(x) = x3+1
1.
Representasi Anggota Field Biner
Mekanisme representasi ini adalah pembangkitkan sebuah bilangan bulat acak antara 0 sampai dengan 2m-1 dan direpresentasikan dalam anggota (digit 0 dan 1),
c = [1 1 0 1 0 0 1 0 1], p = [1 0 0 1 0 1], dan c mod p = [1 0 0 1]. 6. Implementasi Operasi Inversi pada Field Biner Mekanisme operasi inversi mengikuti aturan berikut. Jika p(x) adalah polinomial
. Potongan fungsinya sebagai berikut. int acak(int m){ mpz_t hasil_acak; mpz_init(hasil_acak); gmp_randstate_t rand_state; gmp_randinit_default(rand_state); gmp_randseed_ui(rand_state,time(NULL));
4
mpz_rrandomb(hasil_acak,rand_state, m); final = mpz_get_str(NULL, 2, hasil_acak); r=mpz_sizeinbase (hasil_acak, 2); }
Fungsi ini membangkitkan bilangan acak antara 0 sampai dengan 2m-1 melalui mpz_rrandomb(hasil_acak, rand_state,m); dimana m merupakan panjang bit yang akan direpresentasi, rand_state merupakan seed atau bibit pembangkitkan bilangan acak yang akan dibangkitkan, dalam hal ini seed untuk pembangkitkan berdasarkan waktu, gmp_randseed_ui (rand_state, time(NULL));.
mpz_t hasil_acak,hasil_acak2,hasil_exor; mpz_init(hasil_acak); mpz_init(hasil_acak2); mpz_init(hasil_exor); mpz_xor (hasil_exor, hasil_acak, hasil_acak2); final = mpz_get_str(NULL, 2, hasil_xor); }
Fungsi ini melakukan operasi XOR oleh operand pertama, hasil_acak terhadap operand kedua, hasil_acak2 yang selanjutnya disimpan dalam variabel baru, hasil_xor dan direpresentasikan sebagai anggota field biner melalui final = mpz_get_str (NULL, 2, hasil_xor);.
waktu operasi (dtk)
Simulasi untuk memperlihatkan representasi dari anggota field biner yang diperagakan melalui fungsi int acak (unsigned m), dengan waktu operasi rata-rata 0.0156 detik. Nilai ini diperoleh dari rata-rata waktu sepuluh kali perulangan untuk simulasi representasi dengan panjang bit input adalah 1024 bit. Berikut, waktu operasi simulasi dengan sepuluh pengulangan yang disajikan dalam Gambar 1. 0.017
Simulasi untuk operasi adisi yang diperagakan melalui fungsi int exor (unsigned m, unsigned m2), memiliki waktu operasi rata-rata 0.0374 detik. Gambar 2 menunjukkan waktu rata-rata simulasi operasi adisi untuk input m pertama sepanjang 1024 bit dan input m kedua sepanjang 512 bit dengan sepuluh kali pengulangan.
0.015 0.014
1 2 3 4 5 6 7 8 9 10 Ulangan keGambar 1 Waktu operasi rata-rata simulasi representasi Gambar 1 menunjukkan waktu rata-rata sepuluh kali pengulangan untuk simulasi representasi, dan dari grafik tersebut terlihat bahwa waktu komputasi yang diberikan cenderung konstan di kisaran nilai 0.015 dan 0.016 detik. Dengan demikian, melalui iterasi ini dapat diketahui bahwa representasi anggota field biner sebelum dikenai operasi aitmetikanya memerlukan waktu sebanyak rata-rata dari pengulangannya. 2.
Operasi Adisi pada Field Biner Simulasi operasi adisi memerlukan dua input m sebagai panjang bit yang direpresentasi sebagai anggota field biner, yang mana input m pertama menyatakan panjang bit operand pertama dan input m yang kedua menyatakan panjang bit operand kedua. Setelah kedua operand tersebut direpresentasi, dilanjutkan dengan operasi XOR. Cuplikan fungsinya sebagai berikut. int exor(int m, int m2){
waktu operasi (dtk)
0.016
0.05 0.04 0.03 0.02 0.01 0 1 2 3 4 5 6 7 8 9 10 Ulangan ke-
Gambar 2 Waktu rata-rata simulasi operasi adisi 3. Operasi Multiplikasi Polinomial
dan
Kuadrat
Operasi multiplikasi polinomial dikerjakan per satuan bit mengikuti definisi berikut, a(x)b(x) = am-1xm-1b(x)+…+a1b(x)+a0b(x). Simulasi operasi multiplikasi pada membutuhkan dua operand yang akan dioperasi dengan mengikuti aturan perkalian polinomial sesuai dengan definisi sebelumnya, dan perhitungannya dapat diimplementasi pada fungsi berikut. int multi(int m, int m2){ mpz_t hasil_acak,hasil_acak2,hasil_multi; mpz_init(hasil_acak); mpz_init(hasil_acak2); mpz_init(hasil_multi);
5
mpz_mul (hasil_multi, hasil_acak, hasil_acak2); final = mpz_get_str(NULL, 2, hasil_multi); }
Operasi multiplikasi polinomial oleh operand pertama, hasil_acak dan operand kedua, hasil_acak2 menghasilkan nilai polinomial baru, hasil_multi yang selanjutnya akan direduksi oleh polinomial tak-teruraikan yang digunakan untuk membangun . Waktu rata-rata operasi selama sepuluh kali pengulangan untuk proses ini adalah 0.0627 s, terlihat dalam Gambar 3. Selanjutnya, operasi kuadrat polinomial yang pengerjaannya mengikuti fungsi berikut. int multix(int m){ mpz_t hasil_acak,hasil_multi; mpz_init(hasil_acak); mpz_init(hasil_multi); mpz_mul(hasil_multi, hasil_acak,hasil_acak); final = mpz_get_str(NULL, hasil_multi); }
waktu operasi (dtk)
c(x)
q(x)(x+1) + r(x) (mod p(x)).
Oleh karena deg(q(x)) ≤ m-2, maka deg (xq(x)) ≤ m-1. Hal ini menunjukkan bahwa pergeseran q(x) ke kiri 1 bit tanpa reduksi, sehingga c(x) mod p(x) = xq(x)+q(x)+r(x), yang berarti perhitungan c(x) mod p(x) memerlukan sekali operasi pergeseran ke kiri sejauh satu bit dan dua operasi adisi. Simulasi reduksi Trinomial menghitung m≥1024 yang diberikan dalam himpunan M={1366}, nilai himpunan M mengacu pada daftar Trinomial tak-teruraikan (Menezes, et al 1996). Berikut cuplikan fungsinya. int multi3(int m, int m2){
2,
Pada dasarnya, operasi kuadrat polinomial mengacu pada pengerjaan operasi multiplikasi untuk polinomial yang bernilai sama, hasil_acak yang selanjutnya disimpan dalam variabel baru, hasil_multi dan selanjutnya direpresentasi ke format biner. Operasi kuadrat memberikan waktu proses yang lebih cepat dibandingkan operasi multiplikasi, yakni 0.0312 s. Gambar 3 memperlihatkan perbandingan waktu proses untuk operasi multiplikasi dan kuadrat polinomial dengan panjang 1024 bit. 0.07 0.06 0.05 0.04 0.03 0.02 0.01 0 1 2 3 4 5 6 7 8 9 10 Ulangan keMultiplikasi Kuadrat Gambar 3
reduksi sangat baik pada k=1. Ide dasar reduksi c(x) oleh p(x) untuk k=1, sehingga d(x)=x+1, dan dapat dituliskan
Waktu rata-rata simulasi operasi multiplikasi dan kuadrat polinomial
4. Operasi Reduksi pada Field Biner Reduksi Trinomial Bentuk umum dari polinomial ini adalah p(x)=xm+xk+1, yang memiliki kecepatan
mpz_mul(hasil_multi, hasil_acak, hasil_acak2); mpz_ui_pow_ui(hasil_pangkat, 2, 1366); mpz_ui_pow_ui(hasil_pangkat_kx, 2, 1); mpz_add_ui (hasil_pangkat_k, hasil_pangkat_kx, 1); mpz_xor (hasil_exor, hasil_pangkat, hasil_pangkat_k); mpz_mod (hasil_mod, hasil_multi, hasil_exor); final = mpz_get_str(NULL, 2, hasil_mod); }
Reduksi Trinomial untuk m=1366 dimulai dengan menghitung multiplikasi polinomial dengan m pertama, hasil_acak sepanjang 1366 bit dan m kedua, hasil_acak2 sepanjang 1024 bit, yang selanjutnya direduksi dengan trinomial tak-teruraikan dengan nilai m=1366. Bentuk Trinomial ini adalah p(x)=x1366+x1+1, yang disimpan dalam hasil_exor. Selanjutnya polinomial hasil multiplikasi c(x) yang disimpan dalam hasil_multi direduksi oleh Trinomial p(x)=x1366+x1+1, dan hasilnya disimpan ke dalam hasil_mod dan direpresentasi ke format biner. Proses reduksi Trinomial yang diuji pada m=1366 memberikan waktu rata-rata komputasi 0.0563 s. Waktu ini tidak berbeda signifikan jika dibandingkan dengan reduksi Polinomial Penuh untuk nilai m yang sama, yakni 0.0516 s. Gambar 4 menunjukkan perbandingan waktu rata-rata simulasi operasi reduksi Trinomial dan Polinomial Penuh.
6
waktu operasi (dtk)
mpz_xor(hasil_exor_kk1, hasil_pangkat_k, hasil_pangkat_k1); mpz_xor(hasil_exor_k2k3, hasil_pangkat_k2,hasil_pangkat_k3); mpz_xor(hasil_exor, hasil_exor_kk1, hasil_exor_k2k3); mpz_mod (hasil_mod, hasil_multi, hasil_exor); final = mpz_get_str(NULL, 2, hasil_mod); }
0.07 0.06 0.05 0.04 0.03 0.02 0.01 0
Proses reduksi dimulai dengan menghitung multiplikasi polinomial pertama, hasil_acak dan kedua, hasil_acak2 masing-masing sepanjang 229 bit dan 128 bit, yang selanjutnya direduksi oleh Pentanomial tak-teruraikan dengan nilai m=229, k=63, dan l=1. Selanjutnya Pentanomial p(x)=x229+x64+x63+x1+1 mereduksi polinomial hasil multiplikasi c(x), hasil_multi yang hasilnya disimpan ke hasil_mod dan direpresentasi ke biner.
1 2 3 4 5 6 7 8 9 10 Ulangan keTrinomial
Polinomial Penuh
Gambar 4 Waktu rata-rata simulasi operasi reduksi Trinomial dan Polinomial Penuh Reduksi Pentanomial Polinomial bersuku lima ini mempunyai bentuk umum p(x)= xm+xk+l+xk+xl+1, dimana d(x)= xk+l+xk+xl+1. Polinomial ini mempunyai kecepatan reduksi yang cukup , jika tinggi untuk nilai l=1 dan k≤ demikian maka d(x) dapat ditulis sebagai
Waktu proses dari simulasi yang dilakukan adalah 0.0252 s. Hal ini menunjukkan bahwa rata-rata waktu proses dengan reduksi ini jika dibandingkan dengan Polinomial Penuh tidak berbeda jauh, meski reduksi Polinomial Penuh memberikan waktu ratarata yang lebih baik, yakni 0.0189 s. Perbandingan waktu rata-rata simulasi operasi reduksi Pentanomial dan Polinomial Penuh ditunjukkan Gambar 5.
d(x) = xk+1+xk+x+1 = xk(x+1)+ (x+1), dan c(x)
q(x)( xk(x+1)+(x+1))+r(x)(mod p(x))
c(x)
xk[q(x) (x+1)] + [q(x) (x+1)] + r(x)(mod p(x))
k
c(x) mod p(x) = x s(x) mod p(x) + s(x) mod p(x) + r(x) Oleh karena derajat q(x) ≤ m-2, maka derajat s(x) ≤ m-1, artinya bahwa pergeseran q(x) ke kiri 1 bit tanpa reduksi, sehingga c(x) mod p(x) = xks(x) mod p(x)+s(x)+r(x). Simulasi reduksi Pentanomial menghitung m = 229, k=63, dan l=1. Berikut potongan fungsinya. int multi5(int m, int m2){ mpz_mul(hasil_multi, hasil_acak, hasil_acak2); mpz_ui_pow_ui(hasil_pangkat, 2, 229); mpz_ui_pow_ui(hasil_pangkat_k1, 2, 64); mpz_ui_pow_ui(hasil_pangkat_k2, 2, 63); mpz_ui_pow_ui(hasil_pangkat_k3, 2, 1); mpz_add_ui (hasil_pangkat_k, hasil_pangkat, 1);
waktu operasi (dtk)
c(x) xks(x)+ s(x) + r(x) (mod p(x)), dimana s(x) = [q(x) (x+1)], sehingga
0.035 0.03 0.025 0.02 0.015 0.01 0.005 0 1 2 3 4 5 6 7 8 9 10 Ulangan kePentanomial Polinomial Penuh
Gambar 5 Waktu rata-rata simulasi operasi reduksi Pentanomial dan Polinomial Penuh Reduksi Polinomial Penuh Polinomial p(x)=xm+d(x) disebut Polinomial Penuh apabila d(x)= xm-1+…+ x2+x+1. Secara umum, Polinomial Penuh memilki kecepatan reduksi yang paling baik dibandingkan polinomial jenis lain. Polinomial tak-
7
teruraikan bersuku tiga, Trinomial akan memiliki kecepatan reduksi yang tinggi pada k=1, dan polinomial tak-teruraikan bersuku lima, Pentanomial bekerja dengan baik pada nilai l=1 dan k≤ .
5. Operasi Inversi pada Field Biner Simulasi operasi inversi dilakukan pada input m-1 sepanjang 1024 bit, dengan p(x) merupakan Trinomial berderajat m. Potongan fungsinya sebagai berikut. int invers(int m){ mpz_ui_pow_ui(hasil_pangkat, 2, 1025); mpz_add_ui(hasil_pangkatx, hasil_pangkat, 1); mpz_ui_pow_ui(hasil_pangkat2, 2, 294); mpz_xor (hasil_exor, hasil_pangkatx, hasil_pangkat2); mpz_invert (hasil_inv, hasil_acak, hasil_exor); mpz_get_ui(hasil_inv); final = mpz_get_str(NULL, 2, hasil_inv); }
Simulasi proses reduksi oleh Polinomial Penuh diujikan pada polinomial dengan derajat yang sama untuk reduksi Trinomial dan Pentanomial. Waktu rata-rata prosesnya dibandingkan dengan Trinomial dan Pentanomial lebih baik meski Trinomial diuji pada nilai k=1, dan Pentanomial diuji pada l=1, k≤ . Cuplikan fungsi reduksi polinomial penuh sebagai berikut.
Proses inversi dimulai dengan pembangkitkan sebuah bilangan acak, hasil_acak sepanjang m bit, yang kemudian dicari inversnya setelah dimodularkan oleh polinomial tak-teruraikan, hasil_exor yang disimpan ke dalam hasil_inv, dan selanjutnya direpresentasi ke format biner. Berikut Gambar 6 memperlihatkan waktu rata-rata simulasi operasi inversi untuk input m sepanjang 1024 bit dalam sepuluh kali pengulangan, dan waktu rata-rata yang diperoleh adalah 0.0282s.
int multi1(int m, int m2){ mpz_mul(hasil_multi, hasil_acak, hasil_acak2); mpz_ui_pow_ui(hasil_pangkat, 2, m); mpz_sub_ui (hasil_pangkatx, hasil_pangkat, 1); mpz_mod (hasil_mod, hasil_multi, hasil_pangkat); final = mpz_get_str(NULL, 2, hasil_mod);
Proses reduksi dimulai dengan menghitung multiplikasi polinomial pertama, hasil_acak dan kedua, hasil_acak2 dengan panjang masingmasing bit sesuai input. Selanjutnya direduksi oleh Polinomial Penuh yang hasilnya disimpan ke hasil_mod dan direpresentasi ke format biner. Waktu proses pada simulasi untuk reduksi Polinomial Penuh lebih baik dibandingkan reduksi Trinomial maupun Pentanomial, meski simulasi diuji pada polinomial unggulan untuk Trinomial dan Pentanomial. Waktu perbandingannya terlihat pada Gambar 4 untuk Trinomial dan Gambar 5 untuk Pentanomial. Hal tersebut dipengaruhi oleh mekanisme reduksi ini yang mengikuti rumusan berikut. xm+1 mod p(x)= 1, akibatnya xi untuk m+1≤ i ≤ 2m-2 direduksi oleh p(x) menjadi xi mod(m+1). Jadi, xi mod p(x) = xi mod(m+1). Jika, c(x) = [q(x), r(x)], dengan q(x) = c2m-2xm-2+c2m-1xm-1 +…+cm+1x+cm, maka c(x) mod p(x) = (c2m-2xm-3+ c2m-1xm-2+…+ cm+2x+cm+1)+cmd(x)+r(x).
waktu operasi (dtk)
}
0.04 0.03
0.02 0.01 0 1 2 3 4 5 6 7 8 9 10 Ulangan ke-
Gambar 6 Waktu rata-rata simulasi operasi inversi Aritmetika dalam Jika dikonstruksi dari polinomial takteruraikan p(x), maka adisi dalam dapat secara langsung didefinisikan sesuai dengan adisi polinomial. Berbeda dengan multiplikasi dalam yang harus melalui proses reduksi. Misalkan, a, b , dengan derajat paling banyak m-1, maka fungsi multiplikasi dari a dan b, dinotasikan sebagai Multi (a,b) didefinisikan dengan Multi (a,b) = ab mod p. Hal ini berarti Multi (a,b) adalah hasil reduksi oleh p dari perkalian polinomial a dan b.
8
Selanjutnya, definisi yang sama untuk fungsi kuadrat dalam jika dimisalkan, a , maka Sqr (a) = a2 mod p. Motivasi selanjutnya dari fungsi multiplikasi dan kuadrat adalah digunakan untuk mendefinisikan fungsi eksponensial dalam . Jika dimisalkan n merupakan integer tak-negatif, maka Exp (a,n) = an mod p. Semua operasi yang telah dibahas sebelumnya dapat dipadukan untuk mendapatkan mana yang mempunyai kecepatan terbaik terkait dengan model komputasi. Berikutnya adalah konsep invers dalam yakni untuk mendefinisikan sebagai pembagian dalam = b-1a mod p. Definisi ini berarti menghitung b-1 melalui operasi inversi, dan selanjutnya dikalikan hasilnya dengan a menggunakan operasi multiplikasi, dan direduksi oleh p melalui operasi reduksi.
merupakan hal penting dalam aritmetika . Saran Saran yang dapat diberikan untuk penelitian selanjutnya antara lain: Pengembangan aritmetika field biner untuk merancang sebuah kriptosistem, seperti Kriptografi Kurva Eliptik. Implementasi aritmetika field biner menggunakan library jenis lain. DAFTAR PUSTAKA Deitel H M. 2005. C How To Program. New Jersey: Prentice Hall. Hankerson et al. 2004. Guide to Elliptic Curve Cryptography. New York: Springer. Juhana Nana. 2005. Implementasi Elliptic Curves Cryptosystem (ECC) pada Proses Pertukaran Kunci Diffie-Hellman dan Skema Enkripsi Elgamal [tesis]. Bandung: Program Pascasarjana, Institut Teknologi Bandung.
PENUTUP
Menezes et al. “Hand book of Applied Cryptography”. CRC Press, Inc., 1997.
Beberapa kesimpulan yang dapat diambil dari penelitian ini, antara lain:
Rosing, Michael.1999. Implementing Elliptic Curve Cryptography. Greenwich: Manning Publications Co.
Kesimpulan
Simulasi operasi adisi, multiplikasi, reduksi, dan inversi pada field biner dapat membantu dalam merancang sebuah algoritme kriptografi yang akan dibangun nantinya. Pemilihan polinomial tak-teruraikan p(x) yang tepat untuk mereduksi suatu polinomial c(x) hasil multiplikasi atau penguadratan
Stallings, William. 2005. Cryptography and Network Security Principles and Practices. New Jersey: Prentice Hall.
9
LAMPIRAN
Lampiran 1 Keluaran program representasi anggota field biner dengan panjang 1024 bit
11
No
Deskripsi uji
1
Representasi
2
Adisi
3
Multiplikasi
4
Kuadrat
5
Reduksi
6
Inversi
Lampiran 2 Hasil uji metode black box Hasil yang Kondisi awal Skenario uji diharapkan Membangkitkan Representasi Belum ada bilangan acak dalam format m input panjang sepanjang 2 dan biner sepanjang bit m direpresentasi ke m bit input format biner Adisi dua bilangan Representasi Belum ada acak sepanjang m dalam format input panjang bit pertama dan m biner sepanjang bit m pertama bit kedua dan bit m pertama dan bit m hasilnya dan bit m kedua, kedua direpresentasi ke dan hasil format biner adisinya Multiplikasi dua Representasi Belum ada bilangan acak dalam format input panjang sepanjang m bit biner sepanjang bit m pertama pertama dan m bit bit m pertama dan bit m kedua dan hasilnya dan bit m kedua, kedua direpresentasi ke dan hasil format biner multiplikasinya Mengudratkan Representasi sebuah bilangan Belum ada dalam format acak sepanjang m input panjang biner sepanjang bit dan hasilnya bit m bit m dan hasil direpresentasi ke kudratnya format biner Multiplikasi dua bilangan acak Representasi Belum ada sepanjang m bit dalam format input panjang pertama dan m bit biner sepanjang bit m pertama kedua kemudian bit m pertama dan bit m direduksi dan dan bit m kedua, kedua hasilnya dan hasilnya direpresentasi ke setelah reduksi format biner Menghitung invers Representasi sebuah bilangan Belum ada dalam format acak sepanjang m input panjang biner sepanjang bit dan hasilnya bit m bit m dan hasil direpresentasi ke inversnya format biner
Hasil uji
Berhasil
Berhasil
Berhasil
Berhasil
Berhasil
Berhasil
12
Lampiran 3 Waktu rata-rata simulasi sepuluh kali pengulangan (dalam detik) ulangan
rep
add
multi
eksp
tri (1366 bit)
penta (229 bit)
1
0.015
0.032
0.063
0.031
0.063
2
0.015
0.031
0.062
0.031
3
0.015
0.047
0.063
4
0.016
0.031
5
0.016
6
full
inv
tri
penta
0.031
0.047
0.016
0.031
0.063
0.031
0.047
0.016
0.031
0.031
0.047
0.032
0.046
0.015
0.016
0.063
0.032
0.062
0.016
0.047
0.016
0.032
0.031
0.062
0.031
0.047
0.016
0.063
0.032
0.031
0.015
0.047
0.063
0.031
0.062
0.031
0.047
0.016
0.031
7
0.016
0.047
0.063
0.031
0.046
0.016
0.047
0.031
0.032
8
0.016
0.031
0.063
0.031
0.063
0.031
0.062
0.015
0.031
9
0.016
0.046
0.062
0.032
0.047
0.032
0.063
0.016
0.016
10
0.016
0.031
0.063
0.031
0.063
0.016
0.047
0.016
0.031
rata-rata
0.0156
0.0374
0.0627
0.0312
0.0563
0.0252
0.0516
0.0189
0.0282
13
