juaninf - notas de psudoprogramador

Monday, October 10, 2011

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!

4 comments:

Jorge Valverde-Rebaza said...

bien ahi Juan!! poco a poco van a ir saliendo los resultados :D dale nomas!!

Unknown said...

gracias JCW

Vania said...

hola!! visité tu blog y está genial, Me gustaría enlazarlo en mis blogs y por mi parte te pediría un enlace hacia el mío tambien y de esta forma ambos nos ayudamos a difundir nuestras páginas.

Si puedes escríbeme a ariadna143@gmail.com

saludos

Unknown said...

Dear Mathias,

The implementation was done using the simplification [1].
To calculate the key equation in SAGE you need the extend euclidean algorithm modify.
This algorithm is implemented in my post. All basic steps are in my post.


[1]K. Hubber. Note on decoding binary goppa codes. Electronics Letters, 32(2):
102–103, 1996.

Related Posts Plugin for WordPress, Blogger...