4

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?

Saf
  • 125
  • 2
  • 10
  • 1
    Remember: "subtraction" and "division" are not defined on their own, they are always defined by reference to addition and multiplication. That is, A "-" B is simply A+(-B), and -B is simply the thing you need to *add* to B to make it zero. In GF(2^) that thing is simply B. That's why A-B is equal to A+B. Similarly, A/B is defined as A*(1/B), where 1/B is the thing you must *multiply* B by to make it 1. However, there is nothing you can multiply by 0 to get 1. You can't divide by zero. Division is more complicated, and @frieu has given an excellent explanation of ways to compute 1/B. – President James K. Polk Feb 21 '20 at 13:43
  • For a simple explanation on these arithmetic operations, try taking a look at this: https://stackoverflow.com/a/13224531/10763533 – Haren S Jun 24 '20 at 08:17
  • @PresidentJamesK.Polk, you might want to make your comment an answer. It is very helpful! – M. Al Jumaily Jul 30 '20 at 15:30

1 Answers1

4

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.
fgrieu
  • 2,724
  • 1
  • 23
  • 53
  • 1
    sorry, the polynomial was x^8+x^4+x^3+x+1, missed out the last 1 – Saf Feb 21 '20 at 13:47
  • as i said, i'm given a bit sequence, say 11001100 - how do i raise it to the power of 255 to get the inverse? – Saf Feb 21 '20 at 14:52
  • @Saf: The question mentions _"accomplished addition and multiplication"_. One prepares an input bitstring just like for these operations, and then raising it to the power 254 (not 255) so as to obtain the inverse involves multiplications. Essentially, the preparation goes: you start from zero (equivalently, empty bitstring), and for each bit of the input bitstring multiply by `x` (equivalently, left-shift) then add the input bit. If there's more than 8 input bits, you likely want to reduce, just like in multiplication. – fgrieu Feb 21 '20 at 15:18
  • i can multiply two polynomials in this field, so would it be an elegant choice to perform the multiplication 254 times? – Saf Feb 21 '20 at 15:27
  • @Saf: 253 multiplications by B starting from B would work; but the elegant options involve 13 multiplications alternatively with the previous result and with B (as in the linked [answer on crypto.SE](https://crypto.stackexchange.com/a/40140/555)); or 11 multiplications per the method that I explain. – fgrieu Feb 21 '20 at 15:36