# Implementing the Mceliece Encryption - making the Generator Matrix

I am working on an implementation of the Mceliece Encryption system (MCE) and the Niederreiter encryption system. I have been through the basics of finite fields, polynomial arithmetic and some coding theory to understand it.

In brief given MCE parameters $n, k, t$, such that it is over $GF(2^m)$, $n = 2^m$, $k = n - mt$ is the dimension of the linear code and $t$ is the no. of errors the code will correct, the public key is $X = S.G.P$, where $S$ is a $k$ x $k$ non-singular matrix, $G$ is the $k$ x $n$ generator matrix for the linear code and $P$ is a $n$ x $n$ permutation matrix.

Figuring out how to get $G$ is the reason for the question. I'd like to better understand how the generator matrix is built such that its elements are only $0$ or $1$, once we have the irreducible polynomial of degree $t$, support $L$ and parity check matrix $H$. $L$ & $H$ are composed of the elements of $GF(2^m)$ represented as polynomials in binary form, e.g. $x^4 + x^2 + 1$ is represented as $10101$.

I understand there are many methods of getting to the generator matrix but found limited information online. I'd welcome a simplified explanation of the maths/algorithm or any pointers to sites/books which would help out on this.

• Are you looking for an effective implementation, or an implementation that teaches you about the system? Aug 29 '14 at 21:55
• Also, when you say your code is over $GF(2^m)$, do you mean your code is a binary Goppa code with support in $GF(2^m)^n$ that is intersected with $GF(2)^n$, or do you mean that your code is actually over $GF(2^m)$ (which is a generalisation of the system McEliece originally proposed). Aug 29 '14 at 22:09

I'm going to assume you are using binary Goppa codes. That means, that you take a support $\mathbf{L} \in \mathbb{F}_{2^m}$, a Goppa polynomial $\Gamma$ of degree t with coefficients in $\mathbb{F}_{2^m}$ and build all codewords of a GRS code, and then intersect these with $\mathbb{F}_2^n$, resulting in a code that is actually a subset of $\mathbb{F}_2^n$ (and not of $\mathbb{F}_{2^m}^n$). This is the classical definition used by McEliece in his original proposition.

As you might have already read, the binary Goppa code has a check matrix (there is an error in the Wikipedia article, this one is correct): $$H_{grs} = \begin{pmatrix} 1 & \dots & 1 \\ L_0 & \dots & L_{n-1}\\ L_0^2 & \dots & L_{n-1}^2\\ \vdots & & \vdots\\ L_0^{t-1} & \dots & L_{n-1}^{t-1}\end{pmatrix} \begin{pmatrix} \frac{1}{\Gamma(L_0)} & & \\ & \ddots & \\ & & \frac{1}{\Gamma(L_{n-1})} \end{pmatrix}$$

Now, are you are well aware, this is a $t \times n$ matrix in $\mathbb{F}_{2^m}$ and will thus give you codewords in $\mathbb{F}_{2^m}^n$. But we are interesed in code words only in $\mathbb{F}_{2}^n$. One can get a check matrix that gives only codewords in $\mathbb{F}_2$ by expanding every entry in the matrix in a basis of $\mathbb{F}_{2^m}$.

This means, if your entry of the matrix is represented as as vector $0101$ in $\mathbb{F}_2^4$ (for $m=4$), you would expand this entry as four entries and write them in four rows: 0, 1, 0, 1.

Example: Let one of your rows of your check matrix $H_{grs}$ be $$\begin{pmatrix}0101& 1010 &0001& 1000\end{pmatrix}$$ then you would write this as $$\begin{pmatrix} 0 & 1 & 0 & 1\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 1 & 0 & 1 & 0\end{pmatrix}$$ You do this for all your rows and you will end up with a check matrix $H$ of size $mt \times n$, since you are expanding every row by $m$ rows. From now on, you only work over $\mathbb{F}_2$; using this check matrix, you'll get code words in $\mathbb{F}_2^n$. Note: You will have to do Gauss elimination at this point to get rid of rows that give the same equation. This will reduce your row number and give you a reduced check matrix of size $(n-k) \times n$, where k is the dimension of your binary code.

Now, to get a generator matrix $G$ for that code, you look for a full-rank matrix with $H^\top G=0$. There are many ways to achieve this, and you should find enough material on this. For example: http://en.wikipedia.org/wiki/Parity-check_matrix. Keep in mind, that if $H$ is a check matrix for $G$, then $G$ is a check matrix for $H$. So you build $G$ by pretending $H$ is a generator and you want to find a check matrix for that code.

I hope this is what you asked for.

• I can give mathematical reasonings for the different claims if you're interested. Aug 29 '14 at 22:31
• Looking at the wikipedia page $H = [-P^T|I_{n-k}]$ and $G = [I_k|P]$, so if I reduce $H$ to the standard form, extract $P$ and transpose it, I can construct $G$. A few questions though, for binary goppa codes generally $k = n - mt$, so wouldn't a $mt$ x $n$ matrix be the same $n-k$ x $n$ matrix? I guess if the $H$ I get doesn't have $n-k = mt$ I should discard it and try another code? Aug 30 '14 at 14:10