Mceliece Cryptosystem

The algorithm uses Goppa Code s, which are a type of Error-correcting Code (see Coding Theory ). The algorithm disguises a Goppa code made from the plaintext as a general linear code. Goppa codes are easy to decode, but distinguishing them from a general linear code is hard. This is McEliece's hard problem.

The private and public keys are large matrices, which is one of the main disadvantages of the algorithm. The public key is very large: 2¹⁹ bits long.

Attempts have been made to cryptanalyze McEliece, but none have been successful. However, the algorithm is never used in practice because of the massive keys and because the ciphertext is twice as large as the plaintext. The similarity between this algorithm and the Knapsack Problem (which has been proven insecure) also worries some.

SCHEME DEFINITION

McEliece consists of three algorithms: a probabilistic key generation algorithm which produces a public and a private key, a probabilistic encryption algorithm, and a deterministic decryption algorithm.

All users in a McEliece deployment share a set of common security parameters:

n, t, k

. Recommended values for these parameters are

n=1024, t=38, k=644

(source: Handbook of Applied Cryptography).

Key generation

#Users select a binary

(n, k)

-linear code

C

capable of correcting

t

errors. This code must possess an efficient decoding algorithm.
#Alice generates a

k 	imes n

generator matrix

G

for the code

C

.
#Select a random

k 	imes k

binary non-singular matrix

S

.
#Select a random

n 	imes n

permutation matrix P.
#Compute the

k 	imes n

matrix

{\hat G} = SGP

.
#Alice’s public key is

({\hat G}, t)

; her private key is

(S, G, P)

.

Message encryption

Suppose Bob wishes to send a message ''m'' to Alice whose public key is

({\hat G}, t)

:

#Encode the message as a binary string of length

k

.
#Compute the vector

c^{\prime} = m{\hat G}

.
#Generate a random

n

-bit vector

z

containing at most

t

ones.
#Compute the ciphertext as

c = c^{\prime} + z

.

Message decryption

#Compute the inverse of

P

P^{-1}

.
#Compute

{\hat c} = cP^{-1}

.
#Use the decoding algorithm for the code

C

to decode

{\hat c}

{\hat m}

.
#Compute

m = {\hat m}S^{-1}

.

REFERENCES

Alfred J. Menezes, Scott A. Vanstone, A. J. Menezes and Paul C. van Oorschot, Handbook of Applied Cryptography.

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

	CATEGORIES ABOUT MCELIECE CRYPTOSYSTEM

	asymmetric-key cryptosystems

	electronic commerce

Information About

Mceliece Cryptosystem