• 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
 
 
Mémoire de Maîtrise
DOI
10.11606/D.45.2011.tde-14032012-213011
Document
Auteur
Nom complet
Dionathan Nakamura
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2011
Directeur
Jury
Terada, Routo (Président)
Barreto, Paulo Sergio Licciardi Messeder
Hernandez, Julio Cesar Lopez
Titre en portugais
Segurança do bit menos significativo no RSA e em curvas elípticas
Mots-clés en portugais
Criptografia
Curvas Elípticas
Diffie-Hellman
RSA
Resumé en portugais
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.
Titre en anglais
Least significant bit security of the RSA and elliptic curves
Mots-clés en anglais
Cryptography
Diffie-Hellman
Elliptic Curves.
RSA
Resumé en anglais
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.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
dissertacao.pdf (609.36 Kbytes)
Date de Publication
2012-03-19
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
Centro de Informática de São Carlos
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2022. Tous droits réservés.