 Open Access
 Total Downloads : 413
 Authors : Tun Myat Aung, Ni Ni Hla
 Paper ID : IJERTV6IS080209
 Volume & Issue : Volume 06, Issue 08 (August 2017)
 DOI : http://dx.doi.org/10.17577/IJERTV6IS080209
 Published (First Online): 31082017
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Implementation of Finite Field Arithmetic Operations for Large Prime and Binary Fields using java BigInteger Class
Ni Ni Hla
University of Computer Studies, Yangon Myanmar
Tun Myat Aung
University of Computer Studies, Yangon Myanmar
AbstractMany cryptographic protocols are based on the difficulty of factoring large composite integers or a related problem. Therefore, we implement the finite field arithmetic operations for large prime and binary fields by using java BigInteger class to study our research under large integers for public key cryptosystems and elliptic curve.
Keywords Finite Field Arithmetic; Prime Field; Binary Field, Large Integer

INTRODUCTION
The origins and history of finite fields can be traced back to the 17th and 18th centuries, but there, these fields played only a minor role in the mathematics of the day. In more recent times, however, finite fields have assumed a much more fundamental role and in fact are of rapidly increasing importance because of practical applications in a wide variety of areas such as coding theory, cryptography, algebraic geometry and number theory.
Nowadays, a finite field is very important structure in cryptography. Many cryptographic applications use finite field arithmetic. Public key systems based on various discrete logarithm problems are frequently implemented over finite fields to provide structure and efficient arithmetic.
The finite field arithmetic operations need to be implemented for the development and research of stream ciphers, block ciphers, public key cryptosystems and cryptographic schemes over elliptic curves. Many cryptographic protocols are based on the difficulty of factoring large composite integers or a related problem. Therefore, we implement the finite field arithmetic operations for large prime and binary fields by using java BigInteger class to study our research under large integers.
The organization of this paper is as follows: section 2 is devoted to finite fields and their properties. In section 3, how to implement finite field arithmetic operations under prime field and binary field are described. Some algorithms applied in the implementation are listed in section 4. The results of implementation for finite field arithmetic operations under prime field and binary field are shown in section 5. Finally, we conclude our discussion in section 6.

INTRODUCTION TO FINITE FIELDS
A finite field is a field containing a finite number of elements. Fields are abstractions of familiar number systems (such as the rational numbers Q, the real numbers R, and the complex numbers C) and their essential properties. They consist of a set F together with two operations, addition (denoted by +) and multiplication (denoted by Â·), that satisfy the usual arithmetic properties:

(F,+) is an abelian group with (additive) identity denoted by 0.

(F\{0}, Â·) is an abelian group with (multiplicative) identity denoted by 1.

The distributive law holds: (a+b) Â· c = (a Â· c) + (b Â· c) for all a, b, c F.
If the set F is finite, then the field is said to be finite. Galois showed that for a field to be finite, the number of elements should be pm , where p is a prime number called the characteristic of F and m is a positive integer. The finite fields are usually called Galois fields and also denoted as GF(pm). If m = 1, then GF is called a prime field. If m 2, then F is called an extension field. The order of a finite field is the number of elements in the field. Any two fields are said to be isomorphic if their orders are the same[4].

Field Operations
A field F is equipped with two operations, addition and multiplication. Subtraction of field elements is defined in terms of addition: for a,b F, a b = a +(b) where b is the unique element in F such that b+(b) = 0 (b is called the negative or additive inverse of b). Similarly, division of field elements is defined in terms of multiplication: for a,b F with b = 0, a/b = a Â· b1 where b1 is the unique element in F such that b Â· b1 = 1. (b1 is called the multiplicative inverse of b.)

Prime Field
Let p be a prime number. The integers modulo p, consisting of the integers {0,1,2, . . ., p 1} with addition and multiplication performed modulo p, is a finite field of order p. We shall denote this field by GF(p) and call p the modulus of GF(p). For any integer a, a mod p shall denote the unique integer remainder r, 0 r p1, obtained upon dividing a by p; this operation is called reduction modulo p.
Example 1. (prime field GF(29)) The elements of GF(29) are {0,1,2, . . .,28}. The following are some examples of arithmetic operations in GF(29).

Addition: 17+20 = 8 since 37 mod 29 = 8.

Subtraction: 1720 = 26 since 3 mod 29 = 26.

Multiplication: 17 Â· 20 = 21 since 340 mod 29 = 21.

Inversion: 171 = 12 since 17 Â· 12 mod 29 = 1.


Binary Field
Finite fields of order 2m are called binary fields or characteristictwo finite fields. One way to construct GF(2m) is to use a polynomial basis representation. Here, the elements of GF(2m) are the binary polynomials (polynomials whose coefficients are in the field GF(2) = {0,1}) of degree at most m
1:
(2) = 11 + 22 + + 22 + 1 +
0: {0,1}.
An irreducible binary polynomial f (x) of degree m is chosen. Irreducibility of f(x) means that f(x) cannot be factored as a product of binary polynomials each of degree less than m. Addition of field elements is the usual addition of polynomials, with coefficient arithmetic performed modulo 2. Multiplication of field elements is performed modulo the reduction polynomial f(x). For any binary polynomial a(x), a(x) mod f(x) shall denote the unique remainder polynomial r(x) of degree less than m obtained upon long division of a(x) by f(x); this operation is called reduction modulo f(x).
Example 2. (binary field GF(24)) The elements of GF(24)
are the 16 binary polynomials of degree at most 3:
0 2 3 3 + 2
1 2 + 1 3 + 1 3 + 2 + 1
2 + 3 + 3 + 2 +
+ 1 2 + + 1 3 + + 1 3 + 2 + + 1
The following are some examples of arithmetic operations in GF(24) with reduction Polynomial () = 4 + + 1.
(i). Addition: (3 + 2 + 1) + (2 + + 1) = 3 +
(ii). Subtraction: (3 + 2 + 1) (2 + + 1) = 3 +
(iii).Multiplication: (3 + 2 + 1). (2 + + 1) = 2 + 1
since (3 + 2 + 1). (2 + + 1) = 5 + + 1 and

Arithmetic Operations of Prime Field
The arithmetic operations of prime field need to be implemented to study our research under prime fields. Therefore, we implement a PrimeField class with methods of arithmetic operations for addition, subtraction, multiplication and division of elements (a, b) in the prime field GF(p). The methods of PrimeField class are implemented as follows.

The addition method is implemented by add and mod
methods of BigInteger class for the logic statement: a + b
= ( a + b ) mod p.

The subtraction method is implemented by add, subtract, and mod methods of BigInteger class for the logic statement: a – b = (a + ( b )) mod p. In this case, b is an additive inverse of prime number p. The logic statement of additive inverse b is (p b).

The multiplication method is implemented by multiply and mod methods of BigInteger class for the logic statement: . = ( Ã— ) .

The division method is implemeted by multiply and modInverse methods of BigInteger class for the logic statement: Ã· = ( Ã— 1) . In this case, b1 is a multiplicative inverse of prime number p.

The multiplicative inverse method is adopted from the
modInverse method.


Arithmetic Operations of Binary Field
The arithmetic operations of binary field need to be implemented to study our research under prime fields. Therefore, we implement a BinaryField class with methods of arithmetic operations for addition, subtraction, multiplication and division of elements (a, b) in the binary field GF(2m) with reduction polynomial p. The methods of BinaryField class are implemented as follows.

The addition method is implemented by xor method of BigInteger class for the logic statement: + = . In this case, The addition operation is implemented by bitwise XOR operation of all bits of the two operands.

The subtraction method is identical to the addition
method as above.
(iii).The multiplication method is implemented by shifLeft and xor methods of BigInteger class for the logic statement: . = ( Ã— ) . The algorithm for
(5 + + 1) (4 + + 1) = 2 + 1.
(iv). Inversion: (3 + 2 + 1)1 = 2 since
(3 + 2 + 1). 2 (4 + + 1) = 1.


IMPLEMENTATION OF FIELD OPERATIONS The finite field arithmetic operations: addition, subtraction,
division, multiplication and multiplicative inverse, need to be implemented for the development and research of stream ciphers, public key cryptosystems and cryptographic schemes over elliptic curves. We implement the finite field arithmetic operations by using java BigInteger class to study our research under large numbers.
multiplication of two polynomials in GF(2m) is given in Algorithm (1)[ 1].
(iv). The quotientAndRemainder method is implemented by shifLeft and setBit methods of BigInteger class for the logic statement:(, ) = ( Ã· ). The algorithm to find quotient (q) and remainder (r) from division of two polynomials in GF(2m) is given in Algorithm (2).
(v). The multiplicativeInverse method is implemented by quotientAndRemainder and multiplication methods of BinaryField class and xor method of BigInteger for the logic statement: b Â· b1 mod p= 1. The multiplicative inverse b1 is computed by using Extended Euclidean GCD algorithm given in Algorithm (3)[ 2].
(vi). The division operation is implemented by multiplication and multiplicativeInverse methods of BinaryField class for the logic statement: Ã· = ( Ã— 1) . In this case, b1 is a multiplicative inverse of prime
polynomial p. The multiplicative inverse is adopted from the multiplicativeInverse method.

ALGORITHMS Algorithm (1). shiftandxor method Input: a, b, p as polynomials
Output: result Begin
Set result= 0;
For( i=0; i<bitLength of b; i++) begin
If(bi == 1)
Set result = result xor a. endIf
Set a = shiftLeft(1) of a. If(aLSB == 1)
Set a = a xor p.
endIf end
Return Result End
Algorithm (2). shiftandsetBit method Input: a, b as polynomials
Output: quotient, remainder Begin
Set q = 0.
for ( term = bitLength of a bitLength of b; term >= 0; term–)
begin
if (bitLength of a == bitLength of b + term) Set a = a xor shiftLeft(term of b).
Set quotient = setBit(term of quotient). endIf
end
Set remainder = a. Return quotient, remainder End
Algorithm (3). Extended Euclidean GCD algorithm Input: x, p as polynomials
Output: a
Begin
Set y = x. Set x = p.
Set a = 0.
Set b = 1. while ( 0) begin

RESULTS OF IMPLEMENTATION
We measure the performance of finite field arithmetic operations: addition, subtraction, division, multiplication and multiplicative inverse, under prime field and binary field for comparison of execution time on the processor Intel Core i5@1.60GHz, 2.30GHz. The finite field arithmetic operations use the large integers of the prime field and the binary field defined by NIST recommended elliptic curve for federal government [6]. The results are listed in Table (1).
Prime Field (P192)
P= 627710173538668076383578942320766641608390870039
0324961279.
X = 188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012. Y = 07192b95ffc8da78631011ed6b24cdd573f977a11e794811.
Addition
Z = X + Y.
Z = 7760966146693106881630710328677455222807224655
64271335459.
Subtraction Z = X – Y.
Z = 4279959500820666253533559283073067015526754877
09498034177.
Multiplication Z = X . Y.
Z = 4639807044776303443638933838541143505414608
422678862314472.
Division
Z = X % Y.
Z = 10202314840632689983978512977265729012862841272
07709149774.
Multiplicative Inverse of X
Z = 4501487661668459201131201625760338945286855411
592992703750.
Binary Field (K163)
() = 163 + 7 + 6 + 3 + 1
X = 2fe13c0537bbc11ac aa07d793de4e6d5e5c94eee8 Y = 289070fb05d38ff58321f2e800536d538ccdaa3d9 Addition
Z = X + Y.
Z = 7714cfe32684eef49818f913db78b866904e4d31
Subtraction Z = X – Y.
Z = 7714cfe32684eef49818f913db78b866904e4d31
Multiplication Z = X . Y.
Z = 4d741872162b253d5a381f1f680b47e5c0ad3aa2a Division
Z = X % Y.
Z = 498d03bb544d83614e0b5963052f604eb8ec8d0cd Multiplicative Inverse of X
Z = 63f514f39f4587684f96c8dd6558e69339a1efed9 Table (1). The results of performance
end
Set = / . Set = . Set x = y.
Finite Field
Arithmetic Operations
Prime Field
(ms/100000times)
Binary Field
(ms/100000times)
Addition
31
16
Subtraction
62
16
Division
2262
70497
Multiplication
156
2808
Multiplicative inverse
2028
70153
Set y = r.
Set = ( Ã— ). Set a = b.
Set b = temp;
End
if (x = 1) return a. endIf

CONCLUSION
This is the first step to study our research under large integers for public key cryptosystems and elliptic curve. The performance of addition and subtraction operations of binary field are more efficient than prime field. The performance of division, multiplication and multiplicative inverse operations of prime field are more efficient than binary field. Therefore, a java BigInteger class is more efficient for the software implementation of finite field arithmetic operations in prime field.
REFERENCES
[1]. Annabell Kuldmaa, Efficient Multiplication in Binary Fields, 2015. [2]. Behrouz A. Forouzan, Cryptography and Network Security,McGrawHill press, International Edition, 2008.
[3]. Darrel Hankerson, Alfred Menezes, Scott Vanstone. Guide to Elliptic Curve Cryptography, Springer press, 2004. [4]. Dave K. Kythe, Prem K. Kythe. Algebraic and Stochastic Coding Theory, CRC Press, 2012. [5]. Rudolf Lidl and Harald Niederreiter, Introduction to Finite Field Arithmetic and their Applications, Cambridge University Press, 1986. [6]. Recommended Elliptic Curves for Federal Government Use, NIST, 1999.