• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Disertación de Maestría
DOI
10.11606/D.45.2011.tde-14032012-213011
Documento
Autor
Nombre completo
Dionathan Nakamura
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2011
Director
Tribunal
Terada, Routo (Presidente)
Barreto, Paulo Sergio Licciardi Messeder
Hernandez, Julio Cesar Lopez
Título en portugués
Segurança do bit menos significativo no RSA e em curvas elípticas
Palabras clave en portugués
Criptografia
Curvas Elípticas
Diffie-Hellman
RSA
Resumen en portugués
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.
Título en inglés
Least significant bit security of the RSA and elliptic curves
Palabras clave en inglés
Cryptography
Diffie-Hellman
Elliptic Curves.
RSA
Resumen en inglés
Cryptographic systems like RSA and Elliptic Curve Diffie-Hellman (DHCE) is based on computational problems that are considered hard, e.g. the discrete logarithm (PLD) and integer factorization (PFI) problems. Many papers investigated the relationship between the security of these systems to the computational difficulty of the underlying problems. Moreover, they relate the bit security, actually the LSB (Least Significant Bit), of the secret key in the DHCE and the LSB of the message in the RSA, to the security of the whole key. In these papers, algorithms are presented to invert these cryptographic systems making use of oracles that predict the LSB. In this dissertation we implement two of them. Critical parameters are identified and the original sampling is changed. With the modified sampling we achieve an improvement in the execution times. For practical values of the RSA, the algorithm ACGS becomes faster than the PFI. Moreover, we show how theoretical proofs may lead to inaccurate timing estimates.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
dissertacao.pdf (609.36 Kbytes)
Fecha de Publicación
2012-03-19
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
Centro de Informática de São Carlos
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2020. Todos los derechos reservados.