Eksplorasi Masalah Logaritma Diskret pada Finite Field GF(3m)

Abstract

Banyak algoritme kriptografi yang tumpuan keamanannya menggunakan masalah logaritma diskret pada suatu grup siklik. Misal G adalah grup siklik hingga berorder n, a adalah generator dari G, dan j3 E G. Logaritma diskret dari j3, dengan basis a, dinotasikan loga j3 adalah integer tunggal x, O:S x:S n - 1, sedemikian sehingga j3 = 0: (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 a dari G, dan j3 E G, bagaimana menentukan integer x, 0 :s x :s n - 1 sedemikian sehingga of == j3. Algoritme untuk menyelesaikan masalah logaritma diskret adalah exhaustive search, baby-step giant-step, Pollard-rho, Pohlig-Hellman, dan indexcalculus (Menezes et al. 1997). Algoritme-algoritme tersebut dieksplorasi sehingga dapat digunakan padafinite field GF(3m ). Eksplorasi masalah logaritma diskret padafinite field GF(3m ) juga menghasilkan algoritme yakni algoritme naif negatif, baby-step mother-step, baby-step mother free-step dan baby-step freestep.

The security of many public~key algorithms is based on the problem of finding discrete logarithms. The generalized discrete logarithm problem is the following: given a finite cyclic group G of order n, a generator a of G, and an element fl E G, find the integer x, 0 ~ x ~ n - 1, such that 0: = fl. Algorithm for discrete logarithm problem focused on Menezes et al. (1997) that consist of exhaustive search algorithm, the baby-step giant-step algorithm, Pollard's rho algorithm, Pohlig-Hellman algorithm, and index-calculus algorithm. These algorithms are explorated to be used in discrete logarithm problem over finite field GF(3m ). The exploration also produces some algorithms, i.e. naif negative algorithm, baby-step mother-step algorithm, baby-step mother free-step algorithm, and baby-step free-step algorithm. All algorithms implemented using Maple 11. The Pohlig-Hellman and baby-step giant-step algorithms are efficient enough to be used in discrete logarithm problem over finite field GF(3m ) for m < 20.