Ataques ao sistema criptográfico RSA

Abstract

O RSA é um sistema criptográfico de chave pública, inventado, em 1978, por Rivest, Shamir e Adleman. Neste trabalho, serão abordadas várias técnicas desenvolvidas desde então para quebrar este sistema. Iremos descrever vários métodos de factorização, de onde destacamos o crivo quadrático, o crivo geral dos corpos de números e o método das curvas elípticas. Iremos também estudar vários ataques ao RSA que, de forma a serem evitados, vieram a permitir uma implementação mais adequada do RSA. Destes ataques destacamos aqueles que quebram o RSA quando o expoente público ou o expoente privado são demasiado pequenos, o ataque dos tempos de Kocher e o ataque com parte da chave privada exposta. Muitos dos métodos descritos são acompanhados, em apêndice, com um algoritmo, construído no software Maple 9.5.

The RSA is a cryptographic system invented in 1978 by Rivest, Shamir and Adleman. In this work, we will study several methods developed since then to break this system. We will describe some factorization methods, of which we highlight the quadratic sieve, the general number field sieve and the elliptic curve method. We will also study several attacks to RSA that, in order to avoid them, a better implementation of the RSA was achieved. In particular, we will describe those that break the RSA when a small public exponent or a small private exponent is used. We will also see the Kocher’s timing attack and partial private key exposure attack. Many of the methods are accompanied, in the appendix, by an algorithm constructed using the software Maple 9.5.