Cryptography Reference
In-Depth Information
The knowledge of the permutation
P
is necessary to solve this problem. After
reversing the permutation transformation, the decoder for
C
canbeusedtode-
code the permuted ciphertext
c
toamessage
m
=
S
·
m
. The original message
m
is then obtained from
m
by
m
=
mS
−
1
.
2.1 Recommended Parameters and Key Sizes
The parameters influencing the security of the McEliece PKC are the code length
n
, the code dimension
k
, and the number of added errors
t
. In his original paper
[15] McEliece suggests using [
n
=2
m
,k
=
n
mt, d
=2
t
+ 1] = [1024
,
524
,
101]
Goppa codes over
GF
(2
m
)where
m
=10and
t
= 50. In [4] the authors
present an improved attack on the McEliece scheme. This new attack reduces the
number of operations needed to break the McEliece scheme with original pa-
rameters to about 2
60
instead of 2
80
which was assumed before. To achieve 80-
bit, 128-bit, and 256-bit security level the authors suggest using [2048,1751,55],
[2960,2288,113], and [6624,5129,231] binary Goppa codes, respectively.
Table 1 summarizes all suggested parameters as well as the resulting key
sizes for specific security levels. It is very common to give the public key in
systematic form as a (
n
−
k
matrix. But all published implementations
targeting embedded devices choose to store the full (
n
−
k
)
×
k
) public key. This
has the advantage of a smaller secret key, which cannot be stored in external
memory. If the public key is non systematic, the matrix
S
in the secret key is
completely random and can be generated at runtime form a small seed. For this
reason column four gives the size of non-systematic public keys.
×
Table 1.
Recommended parameters and key sizes for the original McEliece PKC
Security
[n,k,d]-Code Added Size of
K
pub
Size of
K
pr
=(
G
(
x
)
,P,S
)
Level
errors
in Kbits
in Kbits
hardly 80-bit
[1632,1269,67]
34
2022
(0.34,15.94,1573)
80-bit
[2048,1751,55]
27
3502
(0.30,22,2994)
128-bit
[2960,2288,113]
56
6614
(0.61,31.80,5112)
256-bit
[6624,5129,231]
117
33178
(1.38,77.63,25690)
The major disadvantage of the McEliece public-key cryptosystem is its very
large public key of several hundred thousand bits. The complete public generator
matrix
G
of an (
n, k
) linear code occupies
n
k
bits storage space. For this reason,
the McEliece PKC has achieved little attention in the practice. Particularly with
regard to bounded memory capabilities of embedded devices, it is essential to
improve the McEliece cryptosystem by finding a way to reduce the public key
size.
·
2.2 Goppa Codes
Goppa codes were introduces by V. D. Goppa in 1970 [9]. Binary Goppa
codes form a family of binary linear codes generated by a Goppa polynomial
