Galois Field in Cryptography

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

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

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

4 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. The mostfrequently used ASCII codes and their values are given in the following tableDecChrDecChrDecChrDecChrDecChrDecCh r32 Space48064@80P96 112p33!

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

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

7 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). The reduced polynomial can be calculatedeasily with long division while the best way to compute the multiplicativeinverse is by using Extended Euclidean Algorithm.

8 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. Sincethe product is 1, it follows that 84 and 13 are multiplicative inverse pretend that we do not know the multiplicative inverse of 84. Thento calculate the multiplicative inverse we will use Extended Euclidean Algo-rithm.

9 Unlike long division, we need to keep track of the auxiliary when wework with Extended Euclidean Algorithm as followsRemainderQuotientAuxiliary28+ 26+ 25+ 21+ 20026+ 24+ 22125+ 24+ 21+ 2022222021+ 2023+ 22+ 1 The first two rows in the Remainder column are always the modulo poly-nomial followed by the polynomial we wish to invert. The first two rows in6the Auxiliary are always 0 and 20. The remainder and the quotient in rownis then calculated from the division of the remainders in rown 1 andn 2 while the auxiliary in rownis given by the sum of the auxiliary in rown 2 and the product of the quotient and the auxiliary in rown 1 untilthe last remainder equals to 20. The final entry in Auxiliary happens to bethe multiplicative inverse of the product, thus the multiplicative inverse of84 is 23+ 22+ 20= 13 which agrees with the preceding Application in CryptographyThe most popular and widely used application of Galois Field is in Cryptog-raphy.

10 Since each byte of data are represented as a vector in a finite Field ,encryption and decryption using mathematical arithmetic is very straight-forward and is easily the 1970 s, IBM developed data Encryption Standard (DES). However,given that DES uses humble 56-bit key and technology advances rapidly, asupercomputer was able to break the key in less than 24 hours thus a moresophisticated algorithm was necessary. In 2001, Vincent Rijmen and JohnDaemon came up with a more complicated algorithm called Rijndael and ithas been the Advanced Encryption Standard (AES) ever Advanced Encryption Standard (AES)Before data scrambling and encryption can begin, the data must first be ar-ranged in a state or a matrix of bytes. The algorithm for Advanced Encryp-tion Standard (AES) consists of smaller, sub-algorithms namely SubBytes,ShiftRows, MixColumns, and AddRoundKey, where each method will be ex-plained in details below.