Galois Field in Cryptography - University of Washington

1 Galois Field in CryptographyChristoforus Juan BenvenutoMay 31, 2012 AbstractThis paper introduces the basics of Galois Field as well as its im-plementation in storing data. This paper shows and helps visualizesthat storing data in Galois Fields allows manageable and effectivedata manipulation, where it focuses mainly on application in com-puter Cryptography . Details on the algorithm for Advanced Encryp-tion Standard (AES), which is an examples of computer cryptographythat utilizes Galois Field , will also be Introduction22 Galois Field .. Binary System .. Bit and Byte .. ascii .. Finite Field Arithmetic .. and Subtraction.

2 And Multiplicative Inverse ..53 Application in Advanced Encryption Standard (AES) .. 1011 IntroductionGalois Field , named after Evariste Galois , also known as finite Field , refers toa Field in which there exists finitely many elements. It is particularly useful intranslating computer data as they are represented in binary forms. That is,computer data consist of combination of two numbers, 0 and 1, which are thecomponents in Galois Field whose number of elements is two. Representingdata as a vector in a Galois Field allows mathematical operations to scrambledata easily and Galois FieldThe elements of Galois Fieldgf(pn) is defined asgf(pn) = (0,1,2.)

3 , p 1) (p, p+ 1, p+ 2, .. , p+p 1) (p2, p2+ 1, p2+ 2, .. , p2+p 1) .. (pn 1, pn 1+ 1, pn 1+ 2, .. , pn 1+p 1)wherep Pandn Z+. The order of the Field is given bypnwhilepiscalled the characteristic of the Field . On the other hand,gf, as one may haveguessed it, stands for Galois Field . Also note that the degree of polynomialof each element is at mostn (5) = (0,1,2,3,4)which consists of 5 elements where each of them is a polynomial of degree 0(a constant) whilegf(23) = (0,1,2,2 + 1,22,22+ 1,22+ 2,22+ 2 + 1)= (0,1,2,3,4,5,6,7)which consists of 23= 8 elements where each of them is a polynomial ofdegree at most 2 evaluated at Binary SystemIn the binary numeral system or base-2 number system, we represents eachvalue with 0 and 1.

4 To convert a decimal numeral system or base-10 numbersystem into binary system, we need to represent a decimal in terms of sumsofan2n. That is, ifxis the said decimal number then we wish to havex= n Nan2nThe coefficientsanis then written in descending order ofnand all leadingzeros are then omitted. The final result becomes the binary representationof the decimalx. Ultimately, binary system offers an alternative way ofrepresenting the elements of a Galois Field . Both the polynomial and binaryrepresentation of an element have their own advantages and =..+ 1 24+ 0 23+ 0 22+ 1 21+ 1 20so the binary representation of 19 is 10011 while the elements ofgf(23) inbinary aregf(23) = (001,010,011,100,101,110,111) Bit and ByteEach 0 or 1 is called a bit, and since a bit is either 0 or 1, a bit is an elementofgf(2).

5 There is also a byte which is equivalent to 8 bits thus is an elementofgf(28). Since we will be focusing on computer Cryptography and as eachdatum is a series of bytes, we are only interested in Galois Field of order 2and 28in this computer stores data in bytes, each binary number must be 8 bitslong. For number that is less than 8 bits long, leading zeros are follows as well that the biggest number 1 byte can store is 11111111 =27+ 26+ 25+ 24+ 23+ 22+ 21+ 20= 255. Following from the precedingexample, 19 is stored as 00010011 in ASCIIASCII stands for american Standard code for information there are exactly 255 characters in ascii , we can uniquely assign3each character to an element ingf(28) or represent it as a byte.

6 The mostfrequently used ascii codes and their values are given in the following tableDecChrDecChrDecChrDecChrDecChrDecCh r32 Space48064@80P96 112p33!49165A81Q97a113q34 50266B82R98b114r35#51367C83S99c115s36$52 468D84T100d116t37%53569E85U101e117u38&54 670F86V102f118v39 55771G87W103g119w40(56872H88X104h120x41) 57973I89Y105i121y42*58:74J90Z106j122z43+ 59;75K91[107k123{44,60<76L92\108l124|45-61=77M93]109m125} >78N94 110n126 47/63?79O95111owhere Dec indicates the decimal representation (which can be converted tobinary and stored as a byte) and Chr stands for Finite Field ArithmeticUnlike working in the Euclidean space, addition (and subtraction) and mul-tiplication in Galois Field requires additional Addition and SubtractionAn addition in Galois Field is pretty straightforward.

7 Supposef(p) andg(p)are polynomials ingf(pn). LetA=an 1an 2.. a1a0,B=bn 1bn 2.. b1b0,andC=cn 1cn 2.. c1c0be the coefficients off(p),g(p), andh(p) =f(p) +g(p) respectively. Ifak,bk, andckare the coefficients ofpkinf(p),g(p), andh(p) respectively thenck=ak+bk(mod p)Similarly, ifh(p) =f(p) g(p) thenck=ak bk(mod p)where 0 k n 1. Since computer works ingf(28), ifakandbkrefer tothekthbit in the bytes we wish to add thenck, thekthbit in the resulting4byte, is given byck=ak+bk(mod2)Since 0 + 1 = 1 + 0 = 1 (mod2) = 1 and 0 + 0 = 0 (mod2) = 1 + 1 =2 (mod2) = 0, we may think of addition as exclusive-or operation which isalso known as XOR operation.

8 That is, XOR operation returns 0 if bothentries are equal and returns 1 otherwise which also means that subtractionand addition is the same in Galois Field whose characteristic Field is 2. Dueto the nature of Galois Field , addition and subtraction of two bytes will notgo any bigger than 11111111 = 255, the biggest value one byte can store,and is therefore a safe we are working ingf(28), then 83 + 249 is83 + 249 = (26+ 24+ 21+ 20) + (27+ 26+ 25+ 24+ 23= 27+ 2 26+ 25+ 2 24+ 23+ 21+ 2 20= 27+ 25+ 23+ 21= 169 Alternatively, from binary numeral system perspective,83 + 249 = 01010011 + 11111001= 10101010= 169and the results Multiplication and Multiplicative InverseMultiplication in Galois Field , however, requires more tedious work.)

9 Sup-posef(p) andg(p) are polynomials ingf(pn) and letm(p) be an irreduciblepolynomial (or a polynomial that cannot be factored) of degree at leastningf(pn). We wantm(p) to be a polynomial of degree at leastnso that theproduct of twof(p) andg(p) does not exceed 11111111 = 255 as the productneeds to be stored as a byte. Ifh(p) denotes the resulting product thenh(p) = (f(p) g(p)) (mod m(p))On the other hand, the multiplicative inverse off(p) is given bya(p) suchthat(f(p) a(p)) (mod m(p)) = 15 Note that figuring out the product of two polynomials and the multiplicativeinverse of a polynomial requires both reducing coefficients modulopand re-ducing polynomials modulom(p).

10 The reduced polynomial can be calculatedeasily with long division while the best way to compute the multiplicativeinverse is by using extended Euclidean Algorithm. The details on the calcu-lations ingf(28) is best explained in the following we are working ingf(28) and we take the irreducible polynomialmodulom(p) to bep8+p6+p5+p1+p0. To calculate 84 13, we need to gothrough several steps. First, we compute the product of the polynomial andreduce the coefficients modulo 13 = ((26+ 24+ 22) (23+ 22+ 20)) (mod m(p))= (29+ 28+ 27+ 2 26+ 25+ 2 24+ 22) (mod m(p))= (29+ 28+ 27+ 25+ 22) (mod m(p))Then we use long division to compute the reduced polynomial as followsRemainderQuotient29+ 28+ 27+ 25+ 2228+ 26+ 25+ 21+ 202021+ 20 Where the last entry in the first column is the product we seek for.