Cryptography Reference
In-Depth Information
Definition 4.3.3
Extension field addition and subtraction
Let A
(
x
)
,
B
(
x
)
GF
(2
m
)
. The sum of the two elements is then com-
puted according to:
∈
m
−
1
i
=0
c
i
x
i
,
c
i
≡
a
i
+
b
i
mod 2
C
(
x
)=
A
(
x
)+
B
(
x
)=
and the difference is computed according to:
m
−
1
i
=0
c
i
x
i
,
c
i
≡
a
i
−
b
i
≡
a
i
+
b
i
mod 2
.
C
(
x
)=
A
(
x
)
−
B
(
x
)=
Note that we perform modulo 2 addition (or subtraction) with the coefficients. As
we saw in Chap. 2, addition and subtraction modulo 2 are the same operation. More-
over, addition modulo 2 is equal to bitwise XOR. Let's have a look at an example in
the field
GF
(2
8
) whichisusedinAES:
Example 4.5.
Here is how the sum
C
(
x
)=
A
(
x
)+
B
(
x
) of two elements from
GF
(2
8
)
is computed:
A
(
x
)=
x
7
+
x
6
+
x
4
+ 1
B
(
x
)=
x
4
+
x
2
+ 1
C
(
x
)=
x
7
+
x
6
+
x
2
Note that if we computed the difference of the two polynomials
A
(
x
)
−
B
(
x
) from
the example above, we would get the same result as for the sum.
4.3.5 Multiplication in
GF
(2
m
)
Multiplication in
GF
(2
8
) is the core operation of the MixColumn transformation of
AES. In a first step, two elements (represented by their polynomials) of a finite field
GF
(2
m
) are multiplied using the standard polynomial multiplication rule:
B
(
x
)=(
a
m
−
1
x
m
−
1
+
(
b
m
−
1
x
m
−
1
+
A
(
x
)
·
···
+
a
0
)
·
···
+
b
0
)
C
(
x
)=
c
2
m
−
2
x
2
m
−
2
+
+
c
0
,
···
where:
c
0
=
a
0
b
0
mod 2
c
1
=
a
0
b
1
+
a
1
b
0
mod 2
.
c
2
m
−
2
=
a
m
−
1
b
m
−
1
mod 2
.