McEliece in magma

from this pdf.

Introduction

Magma also contains coding theory functions, including :

1. Construction of general cyclic codes
2. Construction of standard linear, cyclic, and alternant codes
3. Combining codes : sum, intersection, (external) direct sum, Plotkin sum, concatenation
4. Modifying a code : augment, extend, expurgate, lengthen, puncture, shorten, etc
5. Changing the alphabet : extend field, restrict field, subfield subcode, trace code
6. Construction of basic codes : Hamming, Reed-Muller, Golay, QR
7. Construction of BCH codes and their generalizations : Alternant, BCH, Goppa, Reed-Solomon, generalized Reed-Solomon, Srivastava, generalized Srivastava
8. Properties : cyclic, self-orthogonal, weakly self-orthogonal, perfect, etc .
9. Minimum weight, words of minimum weight
10. Weight distribution, weight enumerator, MacWilliams transform
11. Complete weight enumerator, MacWilliams transform
12. Coset weight distribution, covering radius, diameter
13. Syndrome decoding, Alternant decoding
14. Bounds : upper and lower bounds on the cardinality of a largest code having given length and minimum distance
15. Automorphism groups of linear codes over GF(p) (prime p), GF(4)
16. Testing pairs of codes for isomorphism over GF(p) (prime p), GF(4)

McEliece Cryptosystem

We demonstrate how these functions can be useful to the cryptographer by implementing the
McEliece public key cryptosystem, and showing an attack on the system when certain precautions
are not taken.
The attack comes from Tom Berson’s Crypto ’97 paper Failure of the McEliece
Public-Key Cryptosystem Under Message-Resend and Related-Message Attack.
Below is the Magma code for implementing this cryptosystem. This code was written by Damien
Fisher, however some small style changes were made.
The first function generates a random Goppa code using the minimal polynomial of a random
element from a degree 50 extension of GF(210). The generator matrix for this code will have
524 rows, 1024 columns, and will be able to correct up to 50 errors. These are the parameters
originally suggested by McEliece.

The function below creates the private and public keys using the RandomCode function. The private
key consists of the tuple < C ; S ; P > where C is the Goppa code, S is an invertible 524 by 524
scrambler matrix, and P is a 1024 by 1024 permutation matrix over GF(2). The public key G is
a 524 by 1024 matrix over GF(2).

Next, we give the functions to encrypt and decrypt. Encryption of a 1024-bit message m is done
by multiplying m (treated as a vector over GF(2)) by G and then adding a random error vector
e having t 1’s in it. Decryption is done by first multiplying the ciphertext by P¡1, then decoding
the Goppa code, and finally multiplying by S^-1.

And now, we test it. This example uses an error of weight t = 10, which is not large enough for
true cryptographic applications, but good enough for illustrative purposes.

Attacking McEliece using message resend

Following Tom Berson’s article, we explain how to attack the McEliece system when not properly
implemented. The general idea is that if we could guess 524 locations where the product m ∈ G
is not changed by the error vector e, then we can look at those corresponding 524 columns of G
to get a relation that doesn’t involve any error between the ciphertext and the plaintext. If these
columns are linearly independent, then square matrix associated with them can be inverted, and
consequently m can be retrieved.
It takes too much expected work to guess 524 correct columns if nothing is known about where
the errors are. However, if the same message is encrypted twice using different random vectors,
then the exclusive-or of the ciphertexts equals the exclusive-or of the error vectors, hence revealing where most of the errors are. The only errors which are not revealed are those that occur in the
same place for both encryptions. Berson showed that for t = 50, you expect to find around 95.1 of
the 100 errors, and then the probability of correctly guessing 524 good values is very reasonable
(i.e. 5 or 12 attempts is often enough).
Since in our example we are only allowing t = 10, we expect to find approximately 19.8 errors. In
fact, most of the time we will find 20, and this simplifies our code slightly because we usually only
need one attempt.
Here is the Magma code for attacking McEliece under message-resend.

Here is a sample output :

Notice that the sum of the two ciphertexts had exactly twenty 1’s in it (as expected).