Cryptography Reference
In-Depth Information
Table 11-1. Elements of
F
2
3
Polynomials in
F
2
3
3-Tuples in
F
2
3
Numerical Value
0
0
0
0
'00'
1
0
0
1
'01'
x
0
1
0
'02'
x
+1
0
1
1
'03'
x
2
1
0
0
'04'
x
2
+1
1
0
1
'05'
x
2
+
x
1
1
0
'06'
x
2
+
x
+1
1
1
1
'07'
Z
2
and is not to be confused with binary
addition, which can involve a carry. This process is reminiscent of our XOR
function in Section 7.2, which executes the same operation in
The addition of digits takes place in
Z
n
for large
n
.
F
2
3
is accomplished by multiplying each term of the first
polynomial by each term of the second and then summing the partial products.
The sum is then reduced by an irreducible polynomial of degree 3 (in our example
modulo
m
(
x
):=
x
3
+
x
+1
):
3
Multiplication in
g
(
x
)=
x
2
+
x
x
2
+
x
+1
mod
x
3
+
x
+1
=
x
4
+2
x
3
+2
x
2
+
x
mod
x
3
+
x
+1
=
x
4
+
x
mod
x
3
+
x
+1
f
(
x
)
·
·
=
x
2
.
This corresponds to the product of 3-tuples
(110)
•
(111)=(100)
,or,
'07'
=
'04'.
The abelian group laws hold in
•
expressed numerically, '06'
F
2
3
with respect to addition and in
F
2
3
\{
0
}
with respect to multiplication (cf. Chapter 5). The distributive law holds as well.
The structure and arithmetic of
F
2
3
can be carried over directly to the field
F
2
8
, which is the field that is actually of interest in studying Rijndael. Addition and
multiplication are carried out as in our above example, the only differences being
that
F
2
8
has 256 elements and that an irreducible polynomial of degree 8 will be
used for reduction. For Rijndael this polynomial is
m
(
x
):=
x
8
+
x
4
+
x
3
+
x
+1
,
which in tuple representation is
(100011011)
, corresponding to the
hexadecimal number '011B'.
Multiplication of a polynomial
f
(
x
)=
a
7
x
7
+
a
6
x
6
+
a
5
x
5
+
a
4
x
4
+
a
3
x
3
+
a
2
x
2
+
a
1
x
+
a
0
3
A polynomial is said to be
irreducible
if it divisible (without remainder) only by itself and
1
.
