CODEWITHSUNDEEP
cryptographygalois-field
Saf
Saf

Reputation: 155

How to perform polynomial subtraction and division in galois field

For my Crypto course, I'm given with two polynomials, in compact form and an irreducible polynomial and am asked to perform the 4 basic arithmetic operations in GF(2^8). Accomplished addition and multiplication, I'm now wondering how to approach subtraction and division. For convenience, let's assume the inputs be, in bit sequence, always of 8 bits

1st bit sequence: 11001100
2nd bit sequence: 11110000
irreducible polynomial(fixed): x^8 + x^4 + x^3 + x^1

How do I perform subtraction/division?

Upvotes: 4

Views: 2480

Answers (1)

fgrieu
fgrieu

Reputation: 2912

The polynomial x^8 + x^4 + x^3 + x^1 is not irreducible: x is obviously a factor!. My bets are on a confusion with x^8 + x^4 + x^3 + x + 1, which is the lexicographically first irreducible polynomial of degree 8.

After we correct the polynomial, GF(28) is a field in which every element is its own opposite. This implies subtraction is the same as addition.

Multiplication * in that field less zero forms a group of 255 elements. Hence for any non-zero B, it holds B255 = 1. Hence the multiplicative inverse of such B is B254.

Hence one can compute A / B as B254 * A when B is not zero. If it is taken that division by zero yields zero, the formula works without special case.

B254 can be computed using 13 multiplications by the standard binary exponentiation method (square and multiply), successively raising B to the 2, 3, 6, 7, 14, 15, 30, 31, 62, 63, 126, 127, 254th powers. C code in this answer on crypto.SE. It is possible to get down to 11 multiplications, and build a whole inverse table with 255 multiplications; Try It Online!.

Other slightly faster to obtain (one) modular inverse include the Extended Euclidean GCD algorithm and log/antilog tables, see this this other answer on crypto.SE. However:

  • When speed is an issue, we can pre-tabulate the modular inverses.
  • That's more complex.
  • Computation of the modular inverse as B254 is constant-time (as desirable in cryptography to prevent side-channel timing attacks) under the main condition that multiplication is, when that's next to impossible to insure with other methods, including table on modern hardware and most computer languages, save perhaps assembly.

Upvotes: 5

Related Questions