Criptosistema de McEliece

En 1978 McEliece presentó un nuevo criptosistema de clave pública, basado en la Teoría de la Codificación algebraica. Dado que esta teoría es muy compleja, los expertos recomiendan una familiarización matemática preliminar con la Teoría de la Codificación, los Códigos de Goppa, y los Cuerpos de Galois.

En el sistema de McEliece, cada usuario ha de elegir un polinomio irreducible de grado , y construir una matriz generadora del correspondiente código de Goppa, matriz , de orden . También ha de calcular , matriz generadora de código lineal tal que no exista un algoritmo computable que corrija los errores con éste código en un tiempo pequeño; esta matriz es obtenida a partir de la expresión

con una matriz aleatoria no singular de orden , y una matriz de permutaciones de orden . Todos los usuarios del sistema mantienen sus respectivos y públicos, mientras que las matrices , y serán secretas.

Supongamos que un emisor A quiere enviar un mensaje al receptor B. Para ello, representará el mensaje como un conjunto de cadenas binarias, , de longitud bits, y enviará el mensaje cifrado de bits

,

siendo un vector de longitud y peso que dificulta el criptoanálisis de un potencial atacante, por razones en las que no vamos a entrar.

Cuando B recibe el mensaje, ha de calcular

utilzando sus matrices , y (que recordemos son privadas). El vector se calcula como

y tiene también un peso inferior a .

Llamando , el receptor B puede calcular ahora el mensaje original, a partir de

(<recordemos una vez más que ha de ser privada para cada usuario!). Hay que resaltar, por último, que aunque el criptosistema de McEliece no ha sido completamente acogido por la comunidad criptológica, es muy importante el estudio que desde la presentación del sistema en 1978 se está haciendo para el desarrollo de sistemas de clave pública basados en la Teoría de la Codificación.