Cryptography Reference
In-Depth Information
The coecients of this polynomial are components of the
i
th
column of the
Vandermonde parity-check matrix for the Goppa code
Γ
(
G
(
x
)
,L
∗
). Hence, to
compute the syndrome of a ciphertext
c
we perform the on-the-fly computation
of the rows of the parity-check matrix. As the Goppa polynomial is a sparse
−
monic polynomial of the form
G
(
x
)=
G
0
+
6
i
=0
G
2
i
x
2
i
with
G
64
=1,wecan
simplify the Equation 1, and thus, reduce the number of operations needed for
the syndrome computation. The main advantage of this computation method is
that it is performed on-the-fly such that no additional storage space is required.
To speed-up the syndrome computation the parity-check matrix can be precom-
puted at the expense of additional
n
(
n
k
) = 288 KBytes memory. As the size
of the Flash memory of ATxmega256A1 is restricted to 256 Kbytes, we cannot
store the whole parity-check matrix. It is just possible to store 52 coecients of
each syndrome polynomial at most, and to compute the remaining coecients
on-the-fly. A better possibility is to work with the systematic quasi-dyadic pub-
lic parity-check matrix
H
=[
Q
T
−
|
I
n−k
] from which the public generator matrix
G
=[
I
k
|
Q
] is obtained. To compute a syndrome the vector matrix multipli-
cation
H
H
T
is performed. For the transpose parity-check matrix
c
T
=
c
·
·
H
T
=[
Q
T
I
n−k
]
T
holds, where
Q
is the quasi-dyadic part composed of dyadic
submatrices. Hence, to compute a syndrome we proceed as follows. The first
k
bits of the ciphertext are multiplied by the part
Q
which can be represented
by the signatures of the dyadic submatrices. The storage space occupied by this
part is 2
.
5 KBytes. The multiplication is performed in the same way as encryp-
tion of a plaintext (see Section 4.2) and results in a binary vector
s
of length
n
|
k
bits of the ciphertext are multiplied by the identity matrix
I
n−k
. Hence, we can omit the multiplication and just add the last
n
−
k
.Thelast
n
−
k
bits
of
c
to
s
. To obtain a syndrome for the eciently decodable code the vector
s
first has to be multiplied by a scrambling matrix
S
. We stress that this matrix
brings the Vandermonde parity-check matrix for the private code
Γ
(
G
(
x
)
,L
∗
)
in systematic form which is the same as the public parity-check matrix. Hence,
S
has to be kept secret. We generate
S
over
F
2
and afterwards represent it over
F
2
16
. Thus, the multiplication of a binary vector
s
by
S
results in a polynomial
S
c
(
x
)
−
∈
F
2
16
[
x
] which is a valid syndrome. The matrix
S
is 128 KBytes in size and
canbestoredintheFlashmemoryofthemicrocontroller. The next step, which
is computing the error locator polynomial
σ
(
x
), is implemented straightforward
using Patterson's algorithm.
Searching for roots of
).
The last and the most computationally expen-
sive step of the decoding algorithm is the search for roots of the error locator
polynomial
σ
(
x
). For this purpose, we first planed to implement the Berlekamp
trace algorithm [3] which is known to be one of the best algorithm for finding
roots of polynomials over finite fields with small characteristic. Considering the
complexity of this algorithm we found out that it is absolutely unsuitable for
punctured codes over a large field, because of the required computation of traces
and gcds. The next root finding method we analyzed is the Chien search [5]
which has a theoretical complexity of
σ
(
x
t
)if
n
=2
m
. The Chien search scans
O
(
n
·
automatically all 2
m
−
1 field elements, in a more sophisticated manner than the
