0

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).

Mr. Llama
  • 103
  • 2
    Can you clarify your notation? As written it looks like gibberish. – Adam Hughes Jul 22 '14 at 21:45
  • Remember not everyone here will know about how things look in computer notation, though they may know about finite fields, so you might need to explain your notation a bit. – DavidButlerUofA Jul 22 '14 at 21:47
  • @AdamHughes - Sorry about that, I've edited the post. Hopefully it's a bit more clear now. – Mr. Llama Jul 22 '14 at 21:58
  • @Mr.Llama in any field of characteristic $2$, $7=2\cdot 3+1=0\cdot 3+1=1$, so $7p=p$. – Adam Hughes Jul 22 '14 at 22:02
  • 3
    @AdamHughes But in this context, 7 is not 7 times 1. It is the element of GF(2^8) represented by the hexadecimal number 07, which is not the same thing! – DavidButlerUofA Jul 22 '14 at 22:06
  • The main issue here is that in any field when you write down an integer $n$, the assumption is always that it means $1$ added to itself $n$ times. The mistakes you've done here is what you get when you don't follow that convention. In this case using them to denote the element of the field that their base-2 representation represents. – Edvard Fagerholm Jul 22 '14 at 22:16
  • I share Gro-Tsen's gripe. For us to verify the results of multiplications it is imperative that you give the minimum polynomial of $x$. This is equivalent to saying what $x^8$, or if you prefer $0x100=0x10\cdot 0x10$, is equal to? – Jyrki Lahtonen Jul 23 '14 at 08:40

2 Answers2

3

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.

Gro-Tsen
  • 5,541
  • So when you say 8 - 1 = 8 + 1, you don't mean 7 = 9, you mean quite literally subtracting one gives the same results as adding one. – Mr. Llama Jul 22 '14 at 22:12
  • I mean that $8-1$ is not $7$ in $\mathbb{F}_{256}$ (represented as you put it). – Gro-Tsen Jul 22 '14 at 23:34
2

$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.

NovaDenizen
  • 4,216
  • 15
  • 23
  • 2
    Ok, that makes sense! That also explains why 5 + 2 works (101 ^ 010) as well as 4 + 2 + 1 (100 ^ 010 ^ 001). I'll probably get the hang of this once I stop thinking of the values as numbers and start grasping them as polynomials. – Mr. Llama Jul 22 '14 at 22:08
  • 1
    It might help to represent all numbers other than 0 and 1 as their hexadecimal to remind you that they are not ordinary numbers. So don't say "7", say "0x07" – DavidButlerUofA Jul 22 '14 at 22:10