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).

Livraria LibMC

Introdução

Dentro dos sistemas criptográficos de chave pública existem alguns que, atualmente, têm se destacado devido ao fato de, aparentemente, resistirem aos ataques que são provenientes do uso dos computadores quânticos, formando, assim, uma família denominada de post-quantum cryptosystems. Estes sistemas criptográficos, em sua grande maioria, têm suporte matemático nos códigos códigos de Goppa binário, como apresentado por McEliece e Niederreiter. Neste post, apresento uma livraria para implementar os algoritmos de decodificação algébrica para códigos de Goppa binário com parâmetros $[n,k,d]$ suficientemente grandes. Para conseguir isto, desenvolvemos uma implementação híbrida, usando o CAS(computer algebra system) SAGE para os algoritmos de decodificação e algumas funções modificadas do software HyMES (feito em C) para a geração do polinômio síndrome (de forma randômica), que é uma das entradas para os algoritmos de decodificação. Caso a livraria não fosse usado para gerar o polinômio síndrome, randomicamente, a implementação apenas no SAGE ficaria, obviamente, muito limitada em tempo de decodificação, devido ao carácter simbólico do mesmo. 

Como usar

A livraria esta feita para ser usada em SAGE versão para 32 bits. Para instalar a livraria segue os passos:

1. Descarregar de aqui.
2. Descomprimir o arquivo zipeado.
3. Copiar o arquivo na pasta: local/lib/python/site-packages.
4. Reiniciar o SAGE.

Exemplo de uso

Veja que as entradas do gerador são: $m$ é o grau do polinômio $p(X)$ tal que $F = K/p(X)$, com $K = \mathbb{F}$$_2$, $n$ é o comprimento de cada palavra chave e delta é o grau do polinômio de Goppa. As saídas são: o Polinômio de Goppa, a matriz de teste de paridade do código gerado e o vetor codificado, ou seja $mG+e$.

Este trabalho foi desenvolvido no LNCC, sendo meus orientadores Renato Portugal e Nolmar Melo.

Algoritmo para Decodificação de Códigos de Goppa Binário

Dentre os sistemas criptográficos assimétricos ou de chave pública práticos, eficientes e seguros temos: DSA, RSA, baseados em curvas Elípticas, entre outros. A segurança desses sistemas está ameaçada devido ao advento da computação quântica e do algoritmo quântico desenvolvido por Peter Shor em 1994, que resolve o problema da fatoração de números inteiros em tempo polinomial.

Em 1978 Robert McEliece propôs um sistema criptográfico aleatório que, na época,  não foi posto em prática devido ao fato do tamanho de suas chaves serem consideravelmente grandes. Atualmente esse sistema tem tido muita aceitação por parte da comunidade de pesquisadores em criptografia devido à sua resistência aos ataques provenientes dos algoritmos quânticos, como o algoritmo o de Shor. Outra vantagem deste sistema criptográfico é o fato de que seus algoritmos de cifração e decifração são mais rápidos, no que se refere à complexidade de tempo, em comparação com o sistema consolidado RSA.

Este post está focado na implementação do algoritmo de decodificação para códigos de Goppa [1]. Para isto, apresentarei, embaixo, esta implementação feita no CAS SAGE. Note que o código escrito ali pode ser "rodado" fazendo click no botão Evaluate.

Implementação do Algoritmo do Patterson

[1] N.J Patterson, ``The Algebraic Decoding of Goppa Codes", { IEEE Transactions on Information Theory}, IT-21(2):203-207, 1974. ¿Te ha gustado esta entrada? Entonces échame un cable compartiéndola en Twitter. Gracias!