Criptografia com resíduos quadráticos

• Ano de defesa: 2017
• Autor(a) principal: Pellegrini, Jerônimo Cordoni
• Orientador(a): Pellegrini, Jerônimo Cordoni
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal do ABC
• Programa de Pós-Graduação: Mestrado Profissional em Matemática em Rede Nacional - PROFMAT
• Link de acesso: http://biblioteca.ufabc.edu.br/index.php?codigo_sophia=107455&midiaext=74910; http://biblioteca.ufabc.edu.br/index.php?codigo_sophia=107455&midiaext=74910/index.php?codigo_sophia=107455&midiaext=74911

Esse trabalho tem como objetivo mostrar como problemas de difícil solução, em especial o problema dos resíduos quadráticos, podem ser usados para desenvolver criptossistema com segurança demonstrável, com algumas aplicações que podem ser desenvolvidas com alunos de ensino fundamental e médio. Faz-se um resumo da história da criptografia, desde a Cifra de César e passando por diversos criptossistemas historicamente famosos, até chegar ao sigilo perfeito do one-time pad. São trabalhados também alguns conceitos matemáticos necessários, como as funções de mão única e uma breve explicação de algumas funções conjecturadas de mão única, que podem ser usadas em sistemas criptográficos seguros. Em seguida, apresenta-se os geradores de números pseudo-aleatórios, em especial o de Blum-Blum-Shub por empregar resíduos quadráticos. A seguir, há uma breve apresentação das funções de hash e do problema do aniversário associado a elas, com uma função de hash construída baseada no gerador de Blum-Blum-Shub. Também importante é a aplicação na encriptação com chave pública, em especial o criptossistema de Rabin, que também é usado para estabelecer um sistema de votação com base no homomorfismo apresentado por esse sistema. Para finalizar, fala-se sobre as provas de conhecimento zero e como as raízes quadradas módulo N podem ser utilizadas para isso, em particular com o Protocolo de Feige-Fiat-Shamir. Uma aplicação para a sala de aula é dada na forma de um leilão, utilizando o conceito da dificuldade da raiz quadrada modular.