Cryptography Reference
In-Depth Information
by
x
(corresponding to a multiplication
•
'
02
') is particularly simple:
x
=
a
7
x
8
+
a
6
x
7
+
a
5
x
6
+
a
4
x
5
+
a
3
x
4
+
a
2
x
3
+
a
1
x
2
+
a
0
x
mod
m
(
x
)
,
f
(
x
)
·
where the reduction modulo
m
(
x
)
is required only in the case
a
7
=0
,and
then it can be carried out by subtracting
m
(
x
)
, that is, by a simple XOR of the
coefficients.
For programming one therefore regards the coefficients of a polynomial
as binary digits of integers and executes a multiplication by
x
byaleftshift
of one bit, followed by, if
a
7
=1
, a reduction by an XOR operation with the
eight least-significant digits '1B' of the number '011B' corresponding to
m
(
x
)
(whereby
a
7
is simply “forgotten”). The operation
a
'
02
' for a polynomial
f
,
or its numerical value
a
, is denoted by Daemen and Rijmen by
b
= xtime(
a
)
.
Multiplication by powers of
x
can be executed by successive applications of
xtime()
.
For example, multiplication of
f
(
x
)
by
x
+1
(or '03') is carried out by shifting
the binary digits of the numerical value
a
of
f
one place to the left and XOR-ing
the result with
a
. Reduction modulo
m
(
x
)
proceeds exactly as with
xtime
.Two
lines of C code demonstrate the procedure:
•
f
ˆ
= f << 1; /* multiplication of f by (x + 1) */
if (f & 0x100) f
ˆ
= 0x11B;
/* reduction modulo m(x) */
Multiplication of two polynomials
f
and
h
in
F
2
8
\{
0
}
can be speeded up by
using logarithms: Let
g
(
x
)
be a generating polynomial
4
F
2
8
\{
0
}
.Thenthere
exist
m
and
n
such that
f ≡ g
m
and
h ≡ g
n
. Thus
f · h ≡ g
m
+
n
mod
m
(
x
)
.
From a programming point of view this can be transposed with the help of
two tables, into one of which we place the 255 powers of the generator polynomial
g
(
x
):=
x
+1
and into the other the logarithms to the base
g
(
x
)
(see Tables
11-2 and 11-3). The product
f · h
is now determined by three accesses to these
tables: From the logarithm table are taken values
m
and
n
for which
g
m
=
f
and
g
n
=
h
. From the table of powers the value
g
((
n
+
m
)mod255)
is taken (note that
g
ord(
g
)
=1
). Table 11-2 contains the powers of
g
twice in succession, and so one
can avoid having to reduce the exponent of
g
in
f
of
h
=
g
n
+
m
.
With the help of this mechanism we can also carry out polynomial division in
F
2
8
. Thus for
f, g
·
∈
F
2
8
\{
0
}
,
f
h
=
fh
−
1
=
g
m
(
g
n
)
−
1
=
g
m
−
n
=
g
(
m
−
n
)mod255
.
This procedure for polynomial multiplication in
F
2
8
is illustrated in the
function
polymul()
:
4
g
generates
F
2
8
\{
0
}
if
g
has order 255. That is, the powers of
g
run through all the elements
of
F
2
8
\{
0
}
.
