2

In Cryptograph, I read some explanation about Exclusive-Or operation in Galois Field.

The five properties of the exclusive-or operation in the $GF(2^n)$ field makes this operation a very interesting component for use in a block cipher: closure, associativity, commutativity, existence of identity, and existence of inverse.

I learned what $GF(2^n)$ is, but I cannot understand the meaning of these properties.
What these properties mean?

haram
  • 147

2 Answers2

1

I. Block cipher (slide source): enter image description here enter image description here

II. Exclusive or:

enter image description here

$A\neq B\implies1$

  • In special when: $A=X$ $\land$ $B=\widetilde{X}\implies A\oplus B\Leftrightarrow X\oplus\widetilde{X}$ is always $1$.

The other properties for one (unknow) element $X$:

  • $(X\oplus0)=X$
  • $(X\oplus1)=\widetilde{X}$

For $n$ inputs we have a Galois field of $2^n$ elements $\iff \forall a_i=0 $ $\vee$ $a_i=1 $

III. XOR block cipher:

  • Closure: The field's addition operation of $GF(2)$ is corresponds to the logical XOR operation of 2 inputs

  • Associativity: Here for $GF(8)$: $$(A\oplus B)\oplus C= A\oplus (B \oplus C)=(A\oplus C )\oplus B $$ enter image description here

  • Communatativity: Short: it's true (table in point II. Also: $GF(4)$)

  • Existance of ideantity:

Question: Does exist an element $E_1$ where: $E_1\oplus X\iff X\oplus E_1 = X$ ? Answer: Yes, for $E_1=0$

  • Existance of inverse: $X\oplus\widetilde{X}=\widetilde{X}\oplus X=E_2=1$

IV. Summary:

XOR- This is sometimes thought of as "one or the other but not both". This could be written as "A or B, but not, A and B".

The field's addition operation for $GF(2^n)$ till each element equal $0$ or $1$ is corresponds to the logical XOR operation.

Krzysztof Myśliwiec
  • 201
1

I answer your question based on the AES block cipher. You know the mixcolumn of AES is based on $GF(2^8)$ which is constructed from the irreducible polynomial $x^8+x^4+x^3+x+1=0$ over $GF(2)$.

Consider we want to obtain $\mathtt{0x57} \cdot \mathtt{0x02}$. First we see this one by polynomial method $$ \begin{array}{lcl}\tag{1} \mathtt{0x57} \cdot \mathtt{0x02}&=&(01010111)_2 \cdot (00000010)_2\\ &=&({x}^{6}+{x}^{4}+{x}^{2}+x+1)\cdot x\\ &=&{x}^{7}+{x}^{5}+{x}^{3}+x^2+x \\ &=& (10101110)_2\\ &=& \mathtt{0xAE} \end{array} $$ The relation $(1)$ means that when an element of $\alpha \in\operatorname{GF}(2^8)$ multiplied by an element $\mathtt{0x02}$ we shift the binary mode of $\alpha$ in the left side.

Now, if the first bit (from left) of $\alpha$ is $1$ we should $\operatorname{XOR}$ the results with $\mathtt{0x1B}= (00011011)_2$ since when the first bit is $1$, it means we have $x^7$ in the representation of $\alpha$ and by multiplying by $x$ we get $x^8$ and we use the polynomial $x^4+x^3+x+1$ instead of $x^8$ in our calculation.

We call this operation x_time(). For instance, let we want to get $\mathtt{0x57} \cdot \mathtt{0x04}$. The element $\mathtt{0x04}=(00000100)_2$ is equal to $x^2$. Therefor to obtain $\mathtt{0x57} \cdot \mathtt{0x04}$ we use the function x_time() two times. In $(1)$ we got $\mathtt{0x57} \cdot \mathtt{0x02}=\mathtt{0xAE}$.

In the rest, to obtain $\mathtt{0xAE} \cdot \mathtt{0x02}$, first we shift the binary mode of $\mathtt{0xAE}=(10101110)_2$ in the left side that implying that $$ (10101110)_2 \stackrel{shift\, to\, left}{\Longrightarrow} (01011100)_2 \tag{2} $$ The first bit of $\mathtt{0xAE}=(10101110)_2$ is $1$ and hence we $\operatorname{XOR}$ the result obtained in $(2)$, with $(00011011)_2$ as follows $$ (01011100)_2 \quad \operatorname{XOR}\quad (00011011)_2=(01000111)_2=71=\mathtt{0x47} $$

user0410
  • 582