McEliece: esconde un mensaje entre errores

Los números con los que trabajamos son los de \mathrm{GF}(2^{4}): polinomios en x con coeficientes 0 o 1, módulo el polinomio primitivo f(x) = x^{4} + x + 1. Tiene 2^{4} = 16 elementos: el 0 y las potencias \alpha^0, \dots, \alpha^{14}, donde \alpha es una raíz de f.

Cada elemento se escribe con 4 bits (los coeficientes de 1, x, x², …). Eso permite convertir una matriz sobre el cuerpo en una matriz binaria.

g(z) = z^{2} + \alpha^{9}\,z + 1. Se prueban polinomios mónicos de grado 2 al azar hasta encontrar uno irreducible (sin factores): han hecho falta 6 intentos. Irreducible garantiza que el código corrige 2 errores y que el algoritmo de Patterson funciona.

L = (\alpha_0, \dots, \alpha_{15}): elementos distintos del cuerpo que no son raíces de g. Cada uno es el «nombre» de una posición del mensaje.

H = \left( \alpha_j^{\,i} / g(\alpha_j) \right)_{0 \le i < t,\quad 0 \le j < n}, de 2 filas y 16 columnas, sobre \mathrm{GF}(2^{4}). Un vector binario c está en el código si y solo si H c^{T} = 0. Cada elemento se desdobla en sus 4 bits y sale una matriz binaria H_{\text{bin}} de 8 × 16 (rango 8).

Sus 8 filas son una base del código: k = n - \operatorname{rango}(H_{\text{bin}}) = 16 - 8 = 8 . Las columnas en verde forman un conjunto de información: ahí G es la identidad, así que el mensaje se lee directamente. Comprobación: H_{\text{bin}}\, G^{T} = 0 ✓.

S mezcla las filas de G (cambia de base el mismo código) y P reordena las columnas. S se elige al azar entre las matrices binarias hasta que sea invertible: 1 intento.

G' = S\,G\,P: sigue generando un código equivalente al de Goppa, pero ya no se ve su estructura; parece una matriz aleatoria. Es la clave pública, junto con t = 2. Ocupa 8 × 16 = 128 bits (16 bytes). La privada es (g, L, S, P).

Hay que averiguar dónde está e P^{-1}. Se calcula el síndrome de y, y con él un polinomio localizador de errores \sigma cuyas raíces (en el soporte) son las posiciones del error.

1. Síndrome S(z) = \sum_{y_j = 1} \frac{1}{z - \alpha_j} \bmod g S(z) = \alpha^{8}\,z + \alpha^{12}
2. Inverso T(z) = S(z)^{-1} \bmod g T(z) = \alpha^{8}\,z + \alpha^{7}
3. T(z) + z \alpha^{2}\,z + \alpha^{7}
4. Se escribe T + z = Q_0^2 + z\,Q_1^2 y se toma la raíz cuadrada R = Q_0 + \sqrt{z}\,Q_1 \bmod g (en característica 2 siempre existe): Q_0 = \alpha^{11},\quad Q_1 = \alpha,\quad \sqrt z = \alpha^{3}\,z + \alpha^{3}
R(z) = \alpha^{4}\,z + \alpha^{13}
5. Euclides extendido sobre (g, R), hasta un resto de grado ≤ ⌊t/2⌋ = 1: aparecen a y b con a \equiv b R \pmod g.

   cociente	resto r	u	v
   	z^2 + α^9·z + 1	1	0
   	α^4·z + α^13	0	1

6. a = \alpha^{4}\,z + \alpha^{13},\quad b = 1
7. El localizador \sigma(z) = a(z)^2 + z\,b(z)^2 \sigma(z) = \alpha^{8}\,z^{2} + z + \alpha^{11}
8. Raíces de \sigma entre los elementos del soporte → posiciones del error: \sigma(\alpha^{5}) = 0 → posición 6\sigma(\alpha^{13}) = 0 → posición 14