Cryptography Reference
In-Depth Information
done by adding the rows of
M
corresponding to the non-zero bits of
p
.Aswe
do not store
M
but just its compressed representation, only the bits
p
it
for all
0
1) can be encrypted directly by adding the corresponding sig-
natures. To encrypt all other bits of
p
the corresponding rows of
M
have to be
reconstructed from
K
pub
first. The components
h
i,j
of a dyadic matrix
Δ
(
h, t
)
are normally computed as
h
i,j
=
h
i⊕j
which is a simple reordering of the ele-
ments of the signature
h
. Unfortunately, we cannot use this equation directly
because the public key is stored as an array of (
n
≤
i
≤
(
l
−
d
−
d
)
/
8elementsoftype
uint8_t
. Furthermore, for every
t
= 64 bits long substring of the plaintext a
different length-(
n
−
k
)(
l
−
−
k
) signature has to be used for encryption.
Decryption.
For decryption we use the equivalent shortened Goppa code
Γ
(
L
∗
,
G
(
x
)) defined by the Goppa polynomial
G
(
x
) and a (permuted) support se-
quence
L
∗
⊂
F
2
16
. The support sequence consists of
n
= 2304 elements of
F
2
16
and is 4
.
5 KBytes in size. We store the support sequence in an array of
type
gf16_t
and size 2304. The Goppa polynomial is a monic separable poly-
nomial of degree
t
= 64. As
t
is a power of 2, the Goppa polynomial is sparse
and of the form
G
(
x
)=
G
0
+
6
i
=0
G
2
i
x
2
i
. Hence, it occupies just 8
16 bits
storage space. We can store both the support sequence and the Goppa polyno-
mial in the SRAM of the microcontroller. Furthermore, we precompute the se-
quence
Diag
(
G
(
L
0
)
−
1
,...,G
(
L
n−
1
)
−
1
) for the parity-check matrix
V
t,n
(
L
∗
,D
).
·
Due to the construction of the Goppa polynomial
G
(
x
)=
t−
1
z
i
)where
z
i
=1
/h
i
+
ω
with a random offset
ω
, the following holds for all
G
(
L
jt
+
i
)
−
1
.
i
=0
(
x
−
G
(
L
jt
+
i
)
−
1
=
t−
1
(
L
jt
+
i
+
z
r
)
−
1
=
t−
1
(1
/h
jt
+
i
+1
/h
r
+1
/h
0
)
−
1
=
t−
1
h
jt
+
r
=
jt
+
t−
1
h
r
r
=0
r
=0
r
=0
r
=
jt
h
∗
denotes a signature obtained by puncturing and permuting the signature
h
for the large code
C
dyad
such that
h
∗
=
h
P
where
P
is the secret permutation
matrix. Hence, the evaluation of the Goppa polynomial on any element of the
support block (
L
jt
,...,L
jt
+
t−
1
)where
j
·
leads
to the same result. For this reason, only
n/t
=
l
=36valuesoftype
gf16_t
need
to be stored. Another polynomial we need for Patterson's decoding algorithm is
W
(
x
) satisfying
W
(
x
)
2
∈{
0
,...,l
−
1
}
,
i
∈{
0
,...,t
−
1
}
x
mod
G
(
x
). As the Goppa polynomial
G
(
x
)issparse,
the polynomial
W
(
x
) is also sparse and of the form
W
(
x
)=
W
0
+
5
≡
i
=0
W
2
i
x
2
i
.
W
(
x
) occupies 7
·
16 bits storage space.
Syndrome Computation.
The first step of the decoding algorithm is the syn-
drome computation. Normally, the syndrome computation is performed through
solving the equation
S
c
(
x
)=
S
e
(
x
)
1
≡
mod
G
(
x
)where
E
denotes a
L
i
x
−
i∈E
1
x−L
i
set of error positions. The polynomial
satisfies the equation
t
1
1
G
(
L
i
)
G
j
L
i
j−s−
1
L
i
≡
mod
G
(
x
)
,
∀
0
≤
s
≤
t
−
1
(1)
x
−
j
=
s
+1