Cryptography Reference
In-Depth Information
of elements of
F
2
8
. Each table occupies only 256 bytes, therefore both tables
can smoothly be copied into the fast SRAM memory of the microcontroller at
startup time. The next question is how to realize the mapping
ϕ
:
A
→
(
a
1
,a
0
)
of an element
A
∈
F
2
16
to two elements (
a
1
,a
0
)
∈
F
2
8
, and the inverse mapping
ϕ
−
1
:
a
1
,a
0
→
A
such that
A
=
a
1
β
+
a
0
. Both mappings can be implemented
by means of a special transformation matrix and its inverse, respectively [18].
As the input and output for the McEliece scheme are binary vectors, field ele-
ments are only used in the scheme internally. Hence, we made an informed choice
against the implementation of both mappings. Instead, we represent each field
element
A
of
F
2
16
as a structure of two uint8 t values describing the elements of
F
2
8
and perform all operations on these elements directly.
4.2
Implementation of the QD-McEliece Variant
Encryption.
The first step of the McEliece encryption is codeword computa-
tion. This is performed through multiplication of a plaintext
p
by the public
generator matrix
G
which serves as public key. In our case the public generator
G
=[
I
k
|
matrix
M
] is systematic. Hence, the first
k
bits of the codeword are the
plaintext itself, and only the submatrix
M
of
G
is used for the computation of
t×t
2
)
d×
(
l−d
)
can be considered as a composition of
the parity-check bits.
M
∈
(
F
d
t
each, represented by a signature
h
xy
of length
t
each. It also can be seen as a composition of
l
·
(
l
−
d
) dyadic submatrices
Δ
(
h
xy
)ofsize
t
×
−
d
dyadic matrices
Δ
(
h
x
,t
)ofsize
dt
×
t
each, represented by a signature of length
dt
=
n
−
k
each.
⎛
⎝
⎞
⎠
⎫
⎬
m
0,0
···
m
0,n-k-1
.
.
.
.
.
Δ
(
h
0
,t
)
⎭
m
t−
1
,
0
···
m
t−
1
,n−k−
1
⎫
⎬
m
t,0
···
m
t,n-k-1
.
.
.
.
.
Δ
(
h
1
,t
)
⎭
M
:=
m
2
t−
1
,
0
···
m
2
t−
1
,n−k−
1
.
.
.
.
.
⎫
⎬
m
(l-d-1)t,0
···
m
(l-d-1)t,n-k-1
.
.
Δ
(
h
l−d
,t
)
.
.
.
⎭
m
(
l−d
)
t−
1
,
0
···
m
(
l−d
)
t−
1
,n−k−
1
In both cases the compressed representation of
M
serving as public key
K
pub
for the McEliece encryption is
K
pub
=[(
m
0
,
0
,
···
,m
0
,n−k−
1
)
,
···
,
(
m
(
l−d−
1)
t,
0
,
···
,m
(
l−d
)
t−
1
,n−k−
1
)]
.
The public key is 2
.
5KBytesinsizeandcanbecopiedintotheSRAMof
the microcontroller at startup time for faster encryption. The plaintext
p
=
(
p
0
,
···
,p
t−
1
,p
t
,
···
,p
2
t−
1
,
···
,p
(
l−d−
1)
t
,
···
,p
(
l−d
)
t−
1
) is a binary vector of
length
k
= 1280 = 20
·
64 = (
l
−
d
)
t
. Hence, the codeword computation is
