Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size blue color orange color green color Sign In

Matematika IPB

 
Data Tesis
 
Judul : EKSPLORASI MASALAH LOGARITMA DISKRET PADA FINITE FIELD GF(3 m )
Jenis :
Penulis : Ai Tusi Fatimah, S.Pd
NRP : G551070331
Tanggal Lulus : 08 May 2010
Tanggal Seminar :
Tanggal Sidang :
Pembimbing : Dr. Sugi Guritman
Dra. Nur Aliatiningtyas, MS.
Dr. Ir. Sri Nurdiati, M.Sc.
Ringkasan : Banyak algoritme kriptografi yang tumpuan keamanann ya menggunakan masalah logaritma diskret pada suatu grup siklik. Misal G adalah grup siklik hingga berorder n,  adalah generator dari G, dan   G. Logaritma diskret dari , dengan basis , dinotasikan log  adalah integer tunggal x, 0  x  n - 1, sedemikian sehingga  = x (Menezes et al. 1997). Jika n besar, maka logaritma diskret menjadi tak layak hitung. Masalah logaritma diskret didefinisikan sebagai berikut : diberikan grup siklik hingga G berorder n, suatu generator  dari G, dan   G, bagaimana menentukan integer x, 0  x  n – 1 sedemikian sehingga x  . Algoritme untuk menyelesaikan masalah logaritma diskret adalah exhaustive search, baby-step giant-step, Pollard-rh o, Pohlig-Hellman, dan indexcalculus (Menezes et al. 1997). Algoritme-algoritme tersebut dieksplorasi sehingga dapat digunakan pada finite field GF(3m). Eksplorasi masalah logaritma diskret pada finite field GF(3m) juga menghasilkan algoritme yakni algoritme naif negatif, baby-step mother-step, baby-step mother free-step dan baby-step freestep. GF(3m) = 3xfx adalah finite field berorder 3m di mana operasi penjumlahan dan perkalian dalam modulo f(x). f(x)  3x merupakan polinomial irreducible atas  berderajat m. GF(3m)* = GF(3m) – {0} merupakan grup siklik perkalian yang berorder n = 3 m – 1. Algoritme exhaustive search (pelacakan lengkap) merupakan algoritme yang berdasarkan definisi masalah logaritma diskret. Pelacakan untuk mendapatkan solusi masalah logaritma diskret dilakukan dengan cara mencoba semua kemungkinan solusi. Untuk order n yang besar, komputasi dengan algoritme ini kurang efisien. Eksplorasi dilakukan untuk efisiensi komputasi dengan menggunakan sifat order GF(3m)* yang selalu bernilai genap. Akibatnya komputasi dapat dilakukan pada setengah order GF(3m)*. Eksplorasi menghasilkan algoritme naif negatif dengan kompleksitas komputasi O (n/2). Terdapat dua fase pada algoritme baby-step giant-step (Hoffstein et al. 2008). Fase baby-step digunakan untuk mengurangi beban komputasi dengan menggunakan memori komputer. Fase giant-step digunakan untuk memperoleh solusi. Untuk order n yang besar, diperlukan memori yang besar juga. Eks plorasi dilakukan sehingga tidak diperlukan memori yang besar untuk order n yang besar. Eksplorasi menghasilkan algoritme baby-step mother-step, baby-step mother-free step, dan baby-step free-step dengan kompleksitas komputasi masing-masing O (n). Ide dasar algoritme Pollard-rho adalah Floyd's Cycle-finding dan Teori Birthday Paradox. Barisan dari suatu fungsi yang dipartisi menjadi tiga bagian dibangkitkan untuk memperoleh solusi. Floyd's cycle-finding digunakan untuk menemukan cycle dalam barisan { x1, x2, x3,…, xk } dengan membandingkan unsurunsur xi dengan x2i sehingga diperoleh pasangan xi = x2i. Birthday paradox digunakan untuk menjamin bahwa adanya satu atau leb ih bilangan yang sama dalam barisan dengan peluang lebih dari setengah sedikitnya setelah langkah ke n 2 ln 2 (Hoffstein et al. 2008). Algoritme Pollard-rho biasanya digunakan pada grup siklik berorder prima. GF(3m)* berorder komposit. Eksplorasi dilakukan dalam pe milihan basis, misalkan p, di mana gcd(n,p ) = 1, sehingga diperoleh algoritme yang dapat digunakan pada finite field GF(3m). Algoritme Pohlig-Hellman pada Menezes et al. (1997) hanya berlaku untuk m ganjil. Algoritme ini dieksplorasi menggunakan sif at-sifat grup siklik sehingga dapat digunakan untuk sembarang m pada finite field GF(3m). Algoritme index-calculus pada Menezes et al. (1997) dapat digunakan untuk masalah logaritma diskret pada finite field GF(3m). Algoritme-algoritme yang dihasilkan diimplementasikan menggunakan sofware Maple 11. Komputasi masalah logaritma diskret pada finite field GF(3m) dapat dilakukan kasus per kasus berdasarkan nilai m. Algoritme Pohlig-Hellman dan algoritme baby-step giant-step cukup efisien untuk masalah logaritma diskret pada finite field GF(3m) dengan m  20. Kata kunci: grup siklik, masalah logaritma diskret, finite field GF(3m)

Random Quotes

Tak seorang pun sempurna. Mereka yang mau belajar dari kesalahan adalah bijak. Menyedihkan melihat orang berkeras bahwa mereka benar meskipun terbukti salah.

anonim