Mc Eliece

[Mc Eliece]

Error correcting codes in a public key algorithm

Entropy/RSA doesn't use this algorithm, but RSA

By looking at the easy to follow fact that intentionally induced errors in a crypto text make it much harder for a crypto-analyst to decipher the message, Mc Eliece in 1978 had the idea to use error correcting codes as a basis for a crypto system. In this system the generator matrix of a Goppa code is converted into a linear code of your choice by matrix multiplication. Since decoding a linear code is NP-hard [1], where a Goppa code takes linear time, one can see the matrix multiplication as a one way function and the secret dissection into single matrices as the trap door information.

Key creation

The private key consists of the binary matrices (S, G, P)
S is a random, inversible k×k (scrambler-) matrix
P is a random n×n permutation matrix and
G is the k×n generator matrix of a Goppa codes that corrects up to t errors.
By choosing t all other parameters are depeding on m alone:
```
	n = 2^m, k = n - mt
```
The public key is the matrix product of the three private matrices, so it is a k×n binary matrix Ĝ = SGP.
All operations are modulo 2 so the result is a binary matrix, too. Additionally a number t' ≤ t has to be advertized which stands for the number of errors that a sender of a message is allowed to add to his message. So the public key is (Ĝ, t').

Encryption

The plain text is dissected into blocks of size k bits. For every block a random error vector of size n that has at most t' entries is chosen and is added to the encoding Ĝ:

	c = m·Ĝ + z

Decryption

The receiver multiplies the cipher text with the inverse of the permutation matrix:

	c' = c P^-1 = m Ĝ P^-1 + z P^-1 = m S G + z P^-1

Since G is a t error correcting code and z P^-1 will contain at most the t' ≤ t intentional errors, he can quickly Goppa decode into c' and already has the result m·S. To get the plain text messages he will then multiply with the inverse of S.

	m = m S · S^-1

Security

To be able to use a trap door Goppa code to decipher a message, the inverse matrices of P and S have to be known. If some unauthorized person does not have this information, she will face the problem to solve a linear code. With an average choice of t > 50 and m > 10 this is a very difficult problem. It is sad that with growing values for the parameters t and m not only the security, but also the key size grows a lot. Any public key consists of 2^m · (2^m - m·t) bits, so for a 50 error correcting code the public key would already have a unpractical size of about 67K bytes.

Example

First we produce a generating matrix of a 2 error correcting code:

	t = 2, m = 3	=>	n = 2³, k = 2³ - 6 = 2

	G =
		(1 0 1 0 0 0 1 1)
		(0 1 0 0 1 1 1 1)

The other two matrices are chosen at random:

S =				S^-1 =
	( 1 1 )			 	S
	( 0 1 )

P =				P^-1 =
	( 0 1 0 0 0 0 0 0 )		( 0 0 0 0 0 1 0 0 )
	( 0 0 0 0 0 0 0 1 )		( 1 0 0 0 0 0 0 0 )
	( 0 0 0 1 0 0 0 0 )		( 0 0 0 1 0 0 0 0 )
	( 0 0 1 0 0 0 0 0 )		( 0 0 1 0 0 0 0 0 )
	( 0 0 0 0 0 1 0 0 )		( 0 0 0 0 0 0 1 0 )
	( 1 0 0 0 0 0 0 0 )		( 0 0 0 0 1 0 0 0 )
	( 0 0 0 0 1 0 0 0 )		( 0 0 0 0 0 0 0 1 )
	( 0 0 0 0 0 0 1 0 )		( 0 1 0 0 0 0 0 0 )

So the public key is:

	Ĝ = SGP =
		( 1 1 0 1 0 1 0 1 )
		( 1 0 0 0 1 1 1 1 )

If someone wants to send us the message m = ( 1 1 ) he would e.g. evaluate:

	c = m Ĝ + z =
		( 0 1 0 1 1 0 1 0 ) +
		( 0 0 0 0 1 0 0 1 ) =
		( 0 1 0 1 0 0 1 1 )

We receive c and evaluate

	c' = c P^-1 = ( 1 1 1 0 0 0 0 1 )

Then we decode this into

	m S = ( 1 0 )	and
	m = m S S^-1 = ( 1 1 )

[1] Arto Salomaa, Public-Key-Cryptography. Springer, EATCS Monographs on Theoretical Computer Science Vol. 23, (1990)