Ataques al RSA mediante curvas elípticas

Abstract

La Criptografía está muy presente en nuestras vidas ya que es imprescindible para garantizar el secreto y la autenticidad de las comunicaciones, particularmente en las comunicaciones online. La criptografía clásica, de clave secreta, no permitía intercambiar claves por medios inseguros, lo que supone un gran problema en la era de Internet, de manera que surgieron nuevos métodos a partir de los años 70. El criptosistema de clave pública RSA, el más extendido actualmente, fue propuesto por Rivest, Shamir y Adleman en 1978. En el presente Trabajo Fin de Grado describimos dicho criptosistema y estudiamos sus posibles vulnerabilidades y ataques. Nos centramos especialmente en el problema de la factorización de números enteros, que es donde reside la seguridad del RSA. Analizamos en profundidad y de manera didáctica los fundamentos matemáticos de los distintos métodos de factorización, con especial énfasis en aquellos basados en curva elíptica, para posteriormente realizar su implementación informática acompañada de una interfaz gráfica sencilla que permita su uso a todo tipo de usuarios. Finalmente, hacemos una comparativa de la eficiencia de los métodos en función de la longitud del número a factorizar, y presentamos el estado del arte de los mayores números factorizados para evaluar la situación actual de la seguridad del RSA, señalando posibles líneas futuras de investigación.---ABSTRACT---Cryptography is part of our lives since it is necessary to guarantee the secrecy and authenticity of communications, particularly online communications. Traditional cryptography, which belongs to the secret-key category, did not allow exchanging keys through insecure channels, which poses a big problem in the Internet age. To circumvent this issue, new methods arose in the ’70s. The public-key RSA cryptosystem was suggested by Rivest, Shamir and Adleman in 1978, and it is the most widespread these days. In the present Final Degree Project, we describe the RSA cryptosystem and study its weaknesses and threats. We primarily focus on the integer factorization problem, where the main security of the RSA rests. We analyze all the different factorization methods indepth and try to explain them in an educational way, paying special attention to the ones based on elliptic curve. Subsequently, we design a computer application with their implementations, including a graphical interface to make it accessible to any kind of user. Finally, we compare the efficiency of the methods depending on the length of the number chosen, and we show the state-of-the-art of the biggest numbers factorized in order to assess the current security of RSA, pointing to possible future lines of research.