Cryptography Reference
In-Depth Information
architectures: an i386 assembler implementation [20] and a C-implementation
[21]. Two implementations of the McEliece PKC on an 8-bits AVR microcon-
troller and an FPGA have been provided by [6]. The microcontroller implemen-
tation encrypts with 3,889 bits/second and decrypts with 2,835 bits/second at a
clock frequency of 32 MHz clock frequency. The main disadvantage of this imple-
mentation is the use of external memory for encryption. As explained above, the
public-key of the McEliece PKC in [6] is 437.75 Kbytes in size such that external
memory has to be used to store the key. The quasi-dyadic variant should solve
the problem of large public keys, increasing the practicability of the McEliece
public-key cryptosystem. To the best of our knowledge, no implementations of
the quasi-dyadic McEliece variant have been proposed targeting an embedded
device.
The remainder of this work is organized as follows. Section 2 introduces the
classical McEliece public key scheme. In further progress we describe how binary
dyadic and quasi-dyadic Goppa codes are constructed. Section 3 gives the scheme
definition of the quasi-dyadic McEliece variant and describes the Kobara-Imai's
specific conversion γ . In Section 4, our implementation of the McEliece PKC with
quasi-dyadic Goppa codes on an 8-bits AVR microcontroller is explained. We
provide the results of our implementation with respect to memory requirements
and performance in Section 5 and conclude in Section 6.
2 Background on the McEliece Cryptosystem
The McEliece cryptosystem [15] was developed by Robert McEliece in 1978 and
was the first proposed public-key cryptosystem (PKC) based on error-correcting
codes.
The idea behind this scheme is to pick randomly a code from a family of codes
with an existing ecient decoding algorithm and to use the description of this
code as private key. To obtain the public key the private key is disguised as a
general linear code by means of several secret transformations. The decoding
of general linear codes is known to be
-hard. Hence, the purpose of these
transformations is to hide any visible structure of the private key which might
be used to identify the underlying code.
The common system parameters for the McEliece PKC are parameters of
the underlying [ n, k, d ] binary Goppa code defined by an (irreducible) polyno-
mial of degree t over GF (2 m ) called Goppa polynomial. Corresponding to each
such polynomial there exist a binary Goppa code of length n =2 m ,dimension
k
NP
mt and minimum distance d =2 t +1 where t is the number of errors
correctable by an ecient decoding algorithm. The public key is K pub =( G ,
t ), where G = S
n
·
G
·
P . The private key is K pr
=( S , G , P ), where G is a
k
×
n generator matrix for the code
C
, S is a k
×
k scrambling matrix and P
is a n
n permutation matrix. The McEliece encryption is done by multiplying
a k -bit message vector by the recipient's public generator matrix G and adding
a random error vector e with Hamming weight at most t . The decoding problem
is the problem of decoding a linear code
×
ˆ
C
equivalent to a binary Goppa code
C
.
 
Search WWH ::




Custom Search