Estudo comparativo de algoritmos de decodificação para códigos de Goppa aplicados no Mcliece

• Ano de defesa: 2012
• Autor(a) principal: Grados Vásquez, Juan del Carmen
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Laboratório Nacional de Computação Científica; Coordenação de Pós-Graduação e Aperfeiçoamento (COPGA); Brasil; LNCC; Programa de Pós-Graduação em Modelagem Computacional
• Palavras-chave em Português: Algoritmos (Computação); Criptografia de dados (Computação); Códigos corretores de erros; Códigos de Goppa; Algoritmos de decodificação; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::ANALISE DE ALGORITMOS E COMPLEXIDADE DE COMPUTACAO
• Link de acesso: https://tede.lncc.br/handle/tede/291

Em 1976, Diffie e Hellman, mudaram os rumos da criptografia criando a criptografia de chave pública ou criptografia assimétrica. Apareceram, logo, outros sistemas criptográficos assimétricos práticos, eficientes e seguros como RSA, sistemas baseados em curvas elípticas, etc. Em 1994 aparecere o algoritmo quântico de Shor, que quebra alguns destes sistemas criptográficos. No livro “Post-Quantum Crypto- graphy” de Bernstein, Dahmen, e Buchmann, classifica-se os sistemas criptográficos em clássicos e pós-quânticos. Isto em função da aparente resistência destes últimos aos ataques provenientes dos algoritmos quânticos. Segundo essa classificação temos, por exemplo, que dentro dos sistemas criptográficos clássicos estão: RSA, Diffie-Hellman, sistemas cripgráficos baseados em curvas elípticas, etc, e candidatos, dentro dos sistemas criptográficos pós-quânticos estão: McEliece, N-th degree Truncated Polynomial Ring-NTRU, Merkle Hash tree, etc. Neste trabalho, descrevemos, implementamos e fazemos uma análise comparativa de alguns algoritmos de decodificação usados no processo de decifração do sistema criptográfico McEliece. Especificamente, a análise consiste em um estudo comparativo dos tempos de decodificação medidos em cycles per byte, dos algoritmos de Patterson, Barreto, Berlekamp-Massey e do algoritmo alternante apresentado por Sloane para os códigos de Goppa e alternantes binários, aplicados ao McEliece, em relação ao melhor ataque de decodifica ̧c ̃ao conhecido e do tamanho da chave pública deste sistema. Para o correto entendimento, os conceitos algébricos necessários, tais como os relacionados `a teoria da codificação, códigos de Goppa e alternantes são apresentados. Por fim, são feitas considerações quanto sua implementação híbrida, usando o software HyMES e o CAS (Computer Algebra System) SAGE, cujos recursos foram usados para dar suporte ao nosso estudo e aos nossos experimentos.