Galois fields (polynomial operations)This page outlines a few basic principles around the usage of Galois fields and polynomial operations. In 1832, Évariste Galois died of duelling wounds at the age of 20 but left a great legacy. While he was a teenager he worked on polynomials and laid down the principles of Galois theory, along with defining the concept of a finite field. In cryptography, the finite field is one of the major concepts and involves limiting the number of possible values to a limiting factor (\(p\)). The values of the field then range from 0 to p-1. Within a field, we can operate on values in the field using arithmetic operations. We can thus have an infinite field, and where we could include all of the possible integers. A finite field or Galois field of GF(\(2^n\)) has \(2^n\) elements. If \(n\) is four, we have 16 output values. Let’s say we have a number \(a∈{0, ... ,2^{n−1}}\), and represent it as a vector in the form of a polynomial: \( a=a0+a_1 x+a_2 x^2 ... a_{n−1} x^{n−1}\) If we use \(a_n∈{0,1}\), this is exactly the same as representing a binary number modulo \(2^n\). In this \(x^n\) represents bit position \(n\) and \(a_n\) is the value of the bit at position \(x^n\). If a bit is a zero at a given position, it will be not included in the polynomial equation. So, 1011 can be represented by \(x^3+x+1\) and 1010 is represented as \(x^3+x\). We can then perform arithmetic operations on these polynomial values. So, to add two values of 1010+1100 we can represent this as \((x^3+x)+(x^3+x^2)\) and which is \(x^2+x\) as we are using modulo 2 addition, and where \(x^3+x^3=0\). With modulo 2 addition, 0+0=0, 0+1=1, 1+0=1, and 1+1=1. An example of Galois Fields is within AES (Advanced Encryption Standard) and which uses a finite field GF(\(2^8\)). With AES we operate on bytes (8 bits) in the form of \(b_7 b_6 b_5 b_4 b_3 b_2 b_1 b_0\) and which are operated on a a polynomial of \(b_7x^7+b_6x^6+b_5x^5+b_4x^4+b_3x^3+b_2x^2+b_1x^1+b_0\).
|
Presentations