Subtraction in GF(2^8) Giving Incorrect Results

352 Views Asked by At

Let me preface this by stating that I'm not normally a math person, but I'm currently dabbling in finite fields to help wrap my head around certain cryptographic topics (specifically those based around AES).

To my understanding, addition and subtraction are the same under finite fields with a characteristic of 2. In addition, these operations are the same as bitwise XOR.


I have the polynomial p = 0x63, I wish to calculate 7*p.

I have the calculated values of 8*p == 0x35 and 7*p == 0x32 which are both correct.

However, 8p - p == 8p XOR p gives me 0x56, not 0x32 as expected.
To make matters more annoying, 5*p + 2*p == 5*p XOR 2*p gives me the correct result.


What am I doing wrong and how can I correct it?

(Here's a quick program I put together to calculate the results, along with the incorrect and correct values.)

Edit: Sorry about the odd notation. I was using this type of notation as a reference. Again, I'm not very familiar with finite fields, so I apologize.
In my case, the 0x63 is 63 in hex, or 01100011 in binary.
That value corresponds to the polynomial of x^6 + x^5 + x + 1.

When I say 7 * p, I mean the polynomial represented by 7 (x^2 + x + 1) multiplied by my polynomial p (mentioned above as x^6 + x^5 + x + 1).

2

There are 2 best solutions below

2
On BEST ANSWER

$8p - p = (8 - 1)p$, it's true. But in this context $(8 - 1) \ne 7$. Here $8 - 1 = 1000 \oplus 0001 = 1001 = 9$.

$5 + 2 = 0101 \oplus 0010 = 0111 = 7$, so this works as you expect.

2
On

First thing: when discussing $\mathbb{F}_{2^8}$ (a.k.a. $GF(2^8)$), when representing its values in binary, you need to specify modulo which irreducible polynomial you are working. Here we can guess that you are working modulo the (AES choice of) irreducible polynomial $x^8+x^4+x^3+x+1 \in \mathbb{F}_2[x]$, and it doesn't really matter for your question, but you shouldn't leave this to be guessed.

The main point: you are wrong in assuming that $8x - x$ should give you $7x$. The thing is, "8" and "7" do not mean the integers 7 and 8 but the elements of $\mathbb{F}_{2^8}$ that (the binary representation of) these integers denote. So $8x - x = 9x$ since $8 - 1 = 8 + 1 = 9$. So there is nothing wrong.