Ejemplo Criptosistema McEliece en SAGE

En el 1978 McEliece presentó un nuevo criptosistema de clave pública, basado en la Teoría de los Códigos. 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 $delta$, y construir una matriz generadora del correspondiente código de Goppa, matriz G, de orden k x n. También ha de calcular la llave pública, que es una matriz generadora del código Goppa. Este código debe ser  tal que no exista un algoritmo computable que corrija los errores con éste código en un tiempo pequeño. La llave pública es obtenida a partir de la multiplicación de una matriz aleatoria no singular de orden 2^m-k*m, y una matriz de permutaciones de orden 2^m. Todos los usuarios del sistema mantienen sus respectivas llaves públicas, mientras que las matrices S,G e P serán secretas.

A continuación presentamos el algoritmo para generación de las llaves, cifrado de un texto plano y descifrado de un texto cifrado, según wikipedia, y su respectiva implementación mediante un ejemplo en SAGE. Es necesario "correr" primero la última de las celdas de este post, la cual contiene los algoritmos auxiliares como por ejemplo el algoritmo de Patterson.

Generación de Llaves

1. Alicia selecciona un código de Goppa binario Gamma com parâmetros (n,k) y capacidad de correción de delta errores; 
2. Alicia gera a matriz geradora $G$, de dimensiones n-m*k x n, del código \Gamma; Selecciona una matriz binaria no singular S, de dimensiones;n-m*k x n-m*k; 
3.  Selecciona una matriz de permutación P, de dimensión n; 
4.  Computa a matriz $G' = SGP; 
5.  La llave pública de Alicia é (G',delta) y su llave privada es (S,G,P).

Configurando los parámetros del código. En este ejemplo hemos considerado el grado del polinomio de Goppa igual a 3. El grado del polinomio para hacer la extensión del cuerpo GF(2), igual a 4.

Creando la matriz de teste de paridad

Creando la matriz generadora del código y multiplicando por S y P.

Algoritmo para el proceso de cifrado:

1. Bob cifra el mensaje m como una cadena binaria de tamaño n-m*delta;
2. Bob computa el vector c' = mG';
3. Bob genera un vector de tamaño n randomico conteniendo hasta delta unos 
4. Bob computa el texto cifrado como c = c' + z.

Algoritmo de decifración.

1. Alice computa el inverso de P
2. Alice computa cP^{-1}. 
3. Alice usa un algoitmo de decodificación para el código G y decodifica c en m' . 
4. Alice computa m'S .

Algoritmos Auxiliares