Determinação em tempo constante de raízes de polinômios sobre corpos finitos para códigos de correção de erros

Abstract

Os sistemas de criptografia mais populares atualmente são Rivest-–Shamir-–Adleman (RSA) e criptografia de curvas elípticas, os quais se baseiam em problemas que algoritmos quânticos conseguem resolver em tempo polinomial. Por este motivo diferentes propostas de criptossistemas vêm sendo estudadas na área criptografia pós-quântica, para que as informações continuem seguras mesmo contra um adversário com um computador quântico. O esquema de McEliece é um esquema de criptografia de chave pública proposto em 1978. A sua segurança se baseia no fato de que a chave pública é indistinguível de uma matriz aleatória e no problema de decodificação geral, o que leva o esquema a resistir a ataques de computadores quânticos e que o categoriza como um criptossistema pós-quântico. O criptossistema de McEliece faz uso de código de Goppa em sua proposta original. Atualmente, diferentes estudos demonstraram a vulnerabilidade da decodificação dos códigos de Goppa em relação a ataques de temporização, onde a variabilidade do tempo de execução traz insegurança para uma implementação.

Este trabalho tem como objetivo apresentar os códigos de Goppa, seu uso no esquema de McEliece e analisar diferentes implementações para a determinação de raízes de polinômios, um passo crucial na decodificação dos códigos. Para isso, o esquema original de McEliece será apresentado juntamente com os códigos de Goppa. O principal algoritmo para decodificação dos códigos, o algoritmo de Patterson, será descrito e implementado fazendo o uso de diferentes métodos para a determinação de raízes de polinômios. Por fim, estas implementações serão comparadas em relação a sua vulnerabilidade a ataques de temporização.