Finite field arithmetic

From Free net encyclopedia

Arithmetic in a finite field is different from standard arithmetic. All operations must always yield results that remain within the field. There are a limited number of numbers in the finite field; all operations performed in the finite field result in a number within that field. Finite fields are used in a variety of applications, including in cryptography, such as the Rijndael encryption algorithm. In computer science applications, the operations are simplified for finite fields of characteristic 2, also called GF(2n) Galois fields, making these fields especially popular choices for applications.

There are infinitely many different finite fields.

Contents

[edit]

Notation

Elements of a finite field are often expressed as polynomials with integer coefficients modulo a prime, the characteristic of the field. When the prime is 2, it is conventional to express them as binary numbers, with each term in a polynomial represented by one bit in the corresponding element's binary expression. Braces ( "{" and "}" ) or similar delimiters are commonly added to binary numbers, or to their hexadecimal equivalents, to indicate that the value is an element of a field. For example, the following are equivalent representations of the same value in a characteristic 2 finite field:

Polynomial: x6 + x4 + x + 1
Binary: {01010011}
Hexadecimal: {53}
[edit]

Addition and subtraction

Addition and subtraction are performed by adding or subtracting two of these polynomials together, and reducing the result modulo the characteristic.

In a finite field with characteristic 2, addition and subtraction are identical, and are accomplished using the XOR operator. Thus,

Polynomial: (x6 + x4 + x + 1) + (x7 + x6 + x3 + x) = x7 + x4 + x3 + 1
Binary: {01010011} + {11001010} = {10011001}
Hexadecimal: {53} + {CA} = {99}

Notice that under regular addition of polynomials, the sum would contain a term 2x6, but that this term becomes 0x6 and is dropped when the answer is reduced modulo 2.

Here is a table with both the normal algebraic sum and the characteristic 2 finite field sum of a few polynomials:

p1p2 p1 + p2 (normal algebra)p1 + p2 in GF(2n)
x3 + x + 1x3 + x2 2x3 + x2 + x + 1 x2 + x + 1
x4 + x2x6 + x2 x6 + x4 + 2x2 x6 + x4
x + 1x2 + 1 x2 + x + 2x2 + x
x3 + xx2 + 1 x3 + x2 + x + 1 x3 + x2 + x + 1
x2 + xx2 + x 2x2 + 2x 0
[edit]

Multiplication

Multiplication in a finite field is multiplication modulo an irreducible reducing polynomial used to define the finite field. (I.e., it is multiplication followed by division using the reducing polynomial as the divisor—the remainder is the product.) The symbol "•" may be used to denote multiplication in a finite field.

[edit]

Rijndael's finite field

Rijndael uses a characteristic 2 finite field with 8 terms, which can also be called the Galois field GF(28). It employs the following reducing polynomial for multiplication:

x8 + x4 + x3 + x + 1.

For example, {53} • {CA} = {01} in Rijndael's field because

(x6 + x4 + x + 1)(x7 + x6 + x3 + x) =

x13 + x12 + x9 + x7 + x11 + x10 + x7 + x5 + x8 + x7 + x4 + x2 + x7 + x6 + x3 + x =

x13 + x12 + x9 + x11 + x10 + x5 + x8 + x4 + x2 + x6 + x3 + x =

x13 + x12 + x11 + x10 + x9 + x8 + x6 + x5 + x4 + x3 + x2 + x

and

x13 + x12 + x11 + x10 + x9 + x8 + x6 + x5 + x4 + x3 + x2 + x modulo x8 + x4 + x3 + x + 1 (= 11111101111110 mod 100011011) = 1, which can be demonstrated through long division (shown using binary notation, since it lends itself well to the task): 

                  111101
100011011)11111101111110
          100011011     
           1110000011110
           100011011    
            110110101110
            100011011   
             10101110110
             100011011  
              0100011010
              000000000 
               100011010
               100011011
                00000001

(The elements {53} and {CA} happen to be multiplicative inverses of one another since their product is 1.)

Multiplication in this particular finite field can also be done as follows:

  • Take two eight-bit numbers, a and b, and an eight-bit product p. The reason for eight bits is because this finite field can only have eight elements in the polynomial.
  • Set the product to zero.
  • Make a copy of a and b, which we will simply call a and b in the rest of this algorithm
  • Run the following loop eight times:
    1. If the low bit of b is set, exclusive or the product p by the value of a
    2. Keep track of whether the high (leftmost) bit of a is set to one
    3. Rotate a one bit to the left, discarding the high bit, and making the low bit have a value of zero
    4. If a's high bit had a value of one prior to this rotation, exclusive or a with the hexadecimal number 0x1b (27 in decimal). 0x1b corresponds to the irreducible polynomial x8 + x4 + x3 + x + 1.
    5. Rotate b one bit to the right, discarding the low bit, and making the high (leftmost) bit have a value of zero.
  • The product p now has the product of a and b

This algorithm generalizes easily to multiplication over other fields of characteristic 2, changing the lengths of a, b, and p and the value 0x1b appropriately.

[edit]

Multiplicative inverse

The multiplicative inverse for an element n of a finite field can be calculated a number of different ways:

  • By multiplying n by every number in the field until the product is one. This is a Brute-force search
  • By making a logarithm table of the finite field, and performing subtraction in the table. Subtraction of logarithms is the same as division.
[edit]

Primitive finite fields

A finite field is considered a primitive finite field if the element x is a generator for the finite field. In other words, if the powers of x assume every nonzero value in the field, it is a primitive finite field. As it turns out, the GF(28) finite field with the reducing polynomial x8 + x4 + x3 + x + 1 is not primitive, although x + 1 is a generator in this field. The GF(28) finite field with the reducing primitive polynomial x8 + x4 + x3 + x2 + 1, however, is a primitive field.

Primitive finite fields are used, for example, by Linear feedback shift registers.

[edit]

Program examples

Here is some C code which will add, subtract, and multiply numbers in Rijndael's finite field: 

/* Add two numbers in a GF(2^8) finite field */
unsigned char gadd(unsigned char a, unsigned char b) {
	return a ^ b;
}

/* Subtract two numbers in a GF(2^8) finite field */
unsigned char gsub(unsigned char a, unsigned char b) {
	return a ^ b;
}

/* Multiply two numbers in the GF(2^8) finite field defined 
 * by the polynomial x^8 + x^4 + x^3 + x + 1 */
unsigned char gmul(unsigned char a, unsigned char b) {
	unsigned char p = 0;
	unsigned char counter;
	unsigned char hi_bit_set;
	for(counter = 0; counter < 8; counter++) {
		if((b & 1) == 1) 
			p ^= a;
		hi_bit_set = (a & 0x80);
		a <<= 1;
		if(hi_bit_set == 0x80) 
			a ^= 0x1b; /* x^8 + x^4 + x^3 + x + 1 */
		b >>= 1;
	}
	return p;
}

Note that this code is vulnerable to timing attacks when used for cryptography.

[edit]

External links

Retrieved from "http://www.netipedia.com/index.php/Finite_field_arithmetic"