Extensões do criptossistema ElGamal aos inteiros gaussianos e aos anéis de polinômios

Abstract

Originalmente o sistema de criptografia ElGamal é descrito usando o grupo multi plicativo dos inteiros módulo um primo p, Z?p, que possui uma grande relevância na criptografia, mas este não é o único grupo finito em que esse esquema decriptografia pode ser formulado. Neste trabalho, baseado em[4] vamos estender o algoritmo ElGamal para o grupo das unidades do domínio dos inteiros gaussianos, Z[i], e para o grupo das unidadesdoaneldepolinômiossobreumcorpodeordemprimaquocientadopelo ideal gerado pelo polinômio x2, Fq[x] <x2>. Para escrever o algoritmo do sistema ElGamal sobre o domínio dos inteiros gaussianos é necessário estudar quais são os tipos de primos que podem ser encontrados neste anel e caracterizaremos dois tipos de primos em Z[i] a partir de um número primo inteiro ímpar p. Veremos que se p ? 3 (mod4), então p também é primo nos inteiros gaussianos, e se p ? 1 (mod4), então existem únicos a e b inteiros tais que p = a2 + b2 e a + bi é um primo nos inteiros gaussianos. Quando quocientarmos o anel dos inteiros gaussianos pelo ideal gerado por um desses dois tipos de primos diferentes ficará evidente que o último tipo não causa mudança no algoritmo ElGamal, diferentemente dos primos da forma 4k + 3. Antes de estender o algoritmo ElGamal nas unidades do anel de polinômios sobre um corpo de ordem prima quocientado por ?x2?, vamos determinar o grupo das unidades de um anel de polinômios sobre um corpo finito quocientado por um ideal principal qualquer. Caracterizaremos esse grupo como o produto de grupos cíclicos finitos, com este resultado vamos analisar quando o grupo das unidades será cíclico. Escolhemos o anel de polinômios sobre um corpo de ordem prima quocientado por ?x2? para estender o sistema ElGamal justamente por ser um dos casos em que seu grupo de unidades é cíclico. Ao final deste trabalho, teremos estendido o criptossistema ElGamal para dois outros algoritmos similares ao original, com o custo computacional similar, que são descritos usando grupos cíclicos de ordens p2 ? 1 e p2 ? p. Em comparação com o algoritmo clássico, que é descrito em um grupo cíclico de ordem p ? 1, aumentamos v consideravelmente o número possível de mensagens que podem ser criptografadas.