Implementation of Finite Field Arithmetic Operations for Large Prime and Binary Fields using java BigInteger Class

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

1. 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.

2. 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].

   1. 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.)

   2. 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).

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

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

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

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

   3. Binary Field

   Finite fields of order 2m are called binary fields or characteristic-two 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

   1. 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.

      1. The addition method is implemented by add and mod

         methods of BigInteger class for the logic statement: a + b

         = ( a + b ) mod p.

      2. 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).

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

      4. The division method is implemeted by multiply and modInverse methods of BigInteger class for the logic statement: ÷ = ( × 1) . In this case, b-1 is a multiplicative inverse of prime number p.

      5. The multiplicative inverse method is adopted from the

      modInverse method.

   2. 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.

   1. 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.

   2. 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.

3. 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 b-1 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, b-1 is a multiplicative inverse of prime

   polynomial p. The multiplicative inverse is adopted from the multiplicativeInverse method.

4. ALGORITHMS Algorithm (1). shift-and-xor 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). shift-and-setBit 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

5. 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 (P-192)

   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 (K-163)

   () = 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

6. 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,

McGraw-Hill 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.