Tiza said:
Hi,
Anybody have an idea on how to start writing a C code for generating
the inverse of finite field GF(2^8) using extended Euclidean algorithm?
What I mean is how to represent a polynomial, e.g. f(x)=x^8+x^4+x^3+x+1
in C? How to represent the multiplication & division process of
polynomial?
Let the bits in a variable represent powers of x so that, for example,
x^8+x^4+x^3+x+1 is represented by bits *, 4, 3, 1 and 0. In this case
we obtain 0x11b as the represntation of this polynomial.
Now if we want to add or subtract two such values, all we have to do is
to xor them together so that, for example:
'x + 1' + 'x^2 + x' ==> 0x003 xor 0x006 = 0x005 ==> x^2 + 1.
And multiplication by x is a shift left by one position. Finally if bit
8 is set after an operation we have to subtract (xor) 0x11b into the
result (assuming that 0x11b is our modular polynomial). Division can
then be represented by repeated subtraction.
If we want to divide GF(2^8) element T by element B, we shift left the B
variable until its top bit matches the top bit of T. We then xor the
result into T so that the top bit of T becomes zero. Now we can repeat
this again for the new value of T until T has fewer bits than B. The
resulting T value is the remainder of the division, while the quotient
is the 1 bits representing the multiples of B that we take away from T
in this process
The US FIPS document for the AES encryption algorithm explains this in
more detail.
Brian Gladman