Una propuesta híbrida para el criptoanálisis RSA

Abstract

[ES] Dada la importancia actual de los algoritmos de cifrado de clave pública en protocolos criptográficos y por lo tanto de los problemas que se utilizan para proporcionar la seguridad computacional necesaria, la factorización de números enteros es un problema interesante ya que no se conoce algoritmo eficiente para resolverla y tampoco se conoce con certeza la clasificación del problema. El objetivo de este trabajo consiste en proponer un algoritmo de factorización híbrido para el criptoanálisis RSA. Para este fin, se partirá de los algoritmos de Dixon y de Pollard Rho. La hipótesis de este estudio de basa en modificar el algoritmo de Dixon, incorporando características del algoritmo de Pollard Rho, para intentar conseguir los valores correctos para la factorización con menor costo temporal. Las conclusiones de este documento se basarán en la rapidez y la efectividad del nuevo algoritmo comparado con los otros dos utilizados

[EN] Because of the current importance of public-key algorithms in cryptographic protocols and, hence, of the problems used to provide the computational security needed, integer factorization is an interesting problem, because neither an efficient algorithm is known to solve it nor the problem’s classification isn't known. The goal of this work is to propose a new hybrid factorization algorithm for RSA cryptanalysis. To achieve this, we will consider Dixon’s and Pollard’s Rho algorithms. The hypothesis of this study is based on modifying Dixon’s algorithm, incorporating characteristics of Pollard Rho’s algorithm, in order to obtain the the factorization with lower temporal cost. Conclusions will be based on compared efficiency of the algorithms.

[CA] Donada la importància actual dels algoritmes de xifrat de clau pública en protocols criptogràfics i per tant dels problemes que s'utilitzen per a proporcionar la seguretat computacional necessària, la factorització de nombres sencers és un problema interessant ja que no es coneix algoritme eficient per a resoldre-la i tampoc es coneix amb certesa la classificació del problema. L’objectiu d'este treball consisteix a proposar un algoritme de factorització híbrid per al criptoanàlisis RSA. Per a este fi, es partirà dels algoritmes de Dixon i de Pollard Rho. La hipòtesi d'este estudi de basa a modificar l'algoritme de Dixon, incorporant característiques de l'algoritme de Pollard Rho, per a intentar aconseguir els valors correctes per a la factorització amb menor cost temporal. Les conclusions d'este document es basaran en la rapidesa i l'efectivitat del nou algoritme comparat amb els altres dos utilitzats.