Segurança do bit menos significativo no RSA e em curvas elípticas

Detalhes bibliográficos
Ano de defesa: 2011
Autor(a) principal: Nakamura, Dionathan
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
RSA
Link de acesso: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-14032012-213011/
Resumo: Sistemas criptográficos como o RSA e o Diffie-Hellman sobre Curvas Elípticas (DHCE) têm fundamento em problemas computacionais considerados difíceis, por exemplo, o problema do logaritmo (PLD) e o problema da fatoração de inteiros (PFI). Diversos trabalhos têm relacionado a segurança desses sistemas com os problemas subjacentes. Também é investigada a segurança do LSB (bit menos significativo) da chave secreta no DHCE (no RSA é o LSB da mensagem) com relação à segurança de toda a chave. Nesses trabalhos são apresentados algoritmos que conseguem inverter os sistemas criptográficos citados fazendo uso de oráculos que predizem o LSB. Nesta dissertação, fazemos a implementação de dois desses algoritmos. Identificamos parâmetros críticos e mudamos a amostragem do formato original. Com essa mudança na amostragem conseguimos uma melhora significativa nos tempos de execução. Um dos algoritmos (ACGS), para valores práticos do RSA, era mais lento que a solução para o PFI, com nosso resultado passou a ser mais veloz. Ainda, mostramos como provas teóricas podem não definir de maneira precisa o tempo de execução de um algoritmo.