SIT281-Cryptography-Summative Assessment

Internal Code: MAS4969

Cryptography Assignment (Inverses in Galois Fields)

In Ass2 Q1, you have to find an inverse of an element in GF(32) The elements in the field are all linear polynomials with coefficients in GF(3). A typical element is ax+b, where each of a and b is 0, 1 or 2. If you are asked to find the inverse of an element cx + d, then here is what to do: 1. Assume the inverse is ax+b, where a and b are to be found 2. (ax+b) and (cx + d) are inverses, so (ax+b) * (cx+d) = 1 (modulo the irreducible polynomial IP) 3. Multiply the product out : acx2 + (ad + bc)x + bd 4. Use the IP to get rid of the x2 term : in the assignment you are told the IP is x 2 + 2x + 2. So x2 + 2x + 2 = 0, giving x 2 = - (2x + 2) = -2x -2. We must “reduce” these coefficients modulo 3, to get x 2 = x + 1. So we may replace x 2 by x + 1. 5. The result is a linear polynomial with an x term and a number term. Equate this to the desired result 1. So the x term is zero, and the number term is 1. This gives 2 equations in the 2 unknowns a and b. 6. Solve for a and b to get the required answer.