Mostrar código-fonte de RSA (sistema criptográfico)

{{Se procura|a empresa|RSA Data Security, Inc.}}
[[Imagem:Adi Shamir 2009.jpg|thumb|150px|direita|[[Adi Shamir]], um dos criadores do RSA]]
'''RSA''' ('''Rivest-Shamir-Adleman''') é um dos primeiros [[Criptografia de chave pública|sistemas de criptografia de chave pública]] e é amplamente utilizado para transmissão segura de dados. Neste [[Sistema criptográfico|sistema de criptografia]], a [[Chave (criptografia)|chave de encriptação]] é pública e é diferente da [[Encriptação|chave de decriptação]] que é secreta (privada). No RSA, esta assimetria é baseada na dificuldade prática da [[Fatoração|fatorização]] do produto de dois [[Número primo|números primos]] grandes, o "[[Fatoração de inteiros|problema de fatoração]]". O [[acrônimo]] RSA é composto das letras iniciais dos sobrenomes de [[Ron Rivest]], [[Adi Shamir]] e [[Leonard Adleman]], fundadores da atual empresa [[RSA Data Security, Inc.]], os quais foram os primeiros a descrever o algoritmo em 1978. [[Clifford Cocks]], um [[matemático]] Inglês que trabalhava para a agência de inteligência britânica [[Government Communications Headquarters]] (GCHQ), desenvolveu um sistema equivalente em 1973, mas ele não foi [[Informação confidencial|revelado]] até 1997.<ref>{{citar web|url=http://www.bristol.ac.uk/pace/graduation/honorary-degrees/hondeg08/cocks.html |primeiro =Nigel |último =Smart |título=Dr Clifford Cocks CB |acessodata=14 de agosto de 2011 |data=19 de fevereiro de 2008 |publicado=[[Bristol University]]}}</ref>

É considerado dos mais seguros, já que mandou por terra todas as tentativas de quebrá-lo. Foi também o primeiro algoritmo a possibilitar criptografia e assinatura digital, e uma das grandes inovações em [[criptografia de chave pública]].

Um usuário do RSA cria e publica uma chave ('''chave pública''') baseada em dois [[número primo|números primos]] grandes, junto com um valor auxiliar. Os números primos devem ser mantidos secretos. Qualquer um pode usar a chave pública para encriptar a mensagem, mas com métodos atualmente publicados, e se a chave pública for muito grande, apenas alguém com o conhecimento dos números primos pode decodificar a mensagem de forma viável. Quebrar a [[encriptação]] RSA é conhecido como [[problema RSA]]. Se ele for tão difícil quanto o problema de fatoramento, ele permanece como uma questão em aberto.

O RSA é um algoritmo relativamente lento e, por isso, é menos usado para criptografar diretamente os dados do usuário. Mais frequentemente, o RSA passa chaves criptografadas compartilhadas para criptografia de [[Algoritmo de chave simétrica|chave simétrica]] que, por sua vez, pode executar operações de criptografia-descriptografia em massa a uma velocidade muito maior.

== Funcionamento ==
O RSA envolve um par de [[Chave (criptografia)|chaves]], uma [[chave pública]] que pode ser conhecida por todos e uma [[chave privada]] que deve ser mantida em sigilo. Toda mensagem cifrada usando uma chave pública só pode ser decifrada usando a respectiva chave privada.
A criptografia RSA atua diretamente na [[internet]], por exemplo, em mensagens de emails, em compras on-line e o que você imaginar; tudo isso é encriptado e decriptado pela criptografia RSA.

=== Geração das chaves ===
No RSA as chaves são geradas desta maneira:

# Escolha de forma aleatória dois [[número primo|números primos]] grandes <math>p \,</math> e <math>q \,</math>, da ordem de <math>10^{100}</math> no mínimo.
# Calcule <math>n = p q \,</math>
# Calcule a função [[Função totiente de Euler]] em <math>n \,</math>: <math>\phi(n) = (p-1)(q-1) \,</math>.<ref>{{Citar web|url=https://math.stackexchange.com/questions/509436/using-carmichael-function-in-rsa|título=Using Carmichael function in RSA|publicado=Mathematics Stack Exchange|autor= David Lowry|data=30/09/2013|acessodata=01/06/2018|língua=inglês}}</ref>
# Escolha um inteiro <math>e \,</math> tal que 1 < <math>e\,</math> < <math>\phi(n)\,</math>, de forma que <math>e\,</math> e <math>\phi (n)\,</math> sejam relativamente [[primos entre si]].
# Calcule <math>d \,</math> de forma que <math>d e \equiv1\pmod{\phi(n)}\,</math>, ou seja, <math>d \,</math> seja o [[inverso multiplicativo]] de <math>e \,</math> em <math>\pmod{\phi(n)}\,</math>.
* No passo 1 os números podem ser testados probabilisticamente para primalidade
* No passo 5 é usado o [[algoritmo de Euclides estendido]], e o conceito de inverso multiplicativo que vem da [[aritmética modular]]

Por final temos:

A chave pública: o par <math>(n , e)</math>.

A chave privada: a tripla <math>(p, q, d)</math>.  (De fato, para desencriptar, basta guardar <math>d</math> como chave privada, mas os primos <math>p</math> e <math>q</math> são usados para acelerar os cálculos)

=== Encriptação ===
Para transformar uma mensagem <math>m \,</math>, onde <math>1 \,</math> <math>< \,</math> <math>m \,</math> <math>< \,</math> <math>n-1 \,</math>, numa mensagem <math>c \,</math> cifrada usando a chave pública do destinatário <math>n \,</math> e <math>e \,</math> basta fazer uma [[potenciação]] modular:

: <math> m^e \equiv c \mod{n}</math>

A mensagem então pode ser transmitida em canal inseguro para o receptor. Há um algoritmo para realizar esta potência rapidamente.

=== Decriptação ===
Para recuperar a mensagem <math>m \,</math> da mensagem cifrada <math>c \,</math> usando a respectiva chave privada do receptor <math>n \,</math> e <math>d \,</math>, basta fazer outra potenciação modular:

: <math> c^d \equiv m \mod{n}</math>

== Implementação ==
Em traços gerais, são gerados dois pares de números – as chaves – de tal forma que uma mensagem criptografada com o primeiro par possa ser apenas decriptada com o segundo par; mas, o segundo número não pode ser derivado do primeiro. Esta propriedade assegura que o primeiro número possa ser divulgado a alguém que pretenda enviar uma mensagem criptografada ao detentor do segundo número, já que apenas essa pessoa pode decriptar a mensagem. O primeiro par é designado como chave pública, e o segundo como chave secreta.

RSA baseia-se no fato de que, embora seja fácil encontrar dois [[números primos]] de grandes dimensões (p.e. 100 dígitos), conseguir [[factorização|factorizar]] o produto de tais dois números é considerado [[Complexidade computacional|computacionalmente complexo]] (em outras palavras, o tempo estimado para o conseguir ronda os milhares de anos). De fato, este [[algoritmo]] mostra-se computacionalmente inquebrável com números de tais dimensões, e a sua força é geralmente quantificada com o número de bits utilizados para descrever tais números. Para um número de 100 dígitos são necessários 330 bits, e as implementações atuais superam os 1024 e mesmo os 2048 bits (a conversão do sistema decimal para o sistema binário é feito de forma clássica).

RSA é usado comumente para transferir senhas [[RC4]] por ser mais rápido. A senha, geralmente, tem apenas 128 bits (16 [[byte]]s) o que facilita o manuseio, já que os processadores modernos tem tipos de 16 bytes embora restringido pelo número de operações. Geralmente o servidor, como por exemplo o servidor HTTPS, gera um par de chaves, uma chave pública e uma chave privada, transmite a chave pública para o cliente, e este gera uma senha RC4 (ou de qualquer outro padrão), criptografa com a chave pública do servidor e envia de volta para o servidor. Assim, tanto o receptor quanto o servidor podem usar a senha RC4 de forma segura para criptografar e descriptografar.

== Em Java ==
<syntaxhighlight lang="java">
import java.math.BigInteger;
import java.security.SecureRandom;

class RSATest {

  public static void main(String args[]) {
    String msg = "Paz e felicidade a todos!";
    String msgcifrada = null;
    String msgdecifrada = null;
    BigInteger n, d, e;
    int bitlen = 2048;

    //Escolha de forma aleatória dois números primos grandes p e q
    SecureRandom r = new SecureRandom();
    BigInteger p = new BigInteger(bitlen / 2, 100, r); 
    BigInteger q = new BigInteger(bitlen / 2, 100, r); 

    //Compute n = p * q
    n = p.multiply(q);

    //Compute a função totiente phi(n) = (p -1) (q -1)
    BigInteger m = (p.subtract(BigInteger.ONE)).multiply(q.subtract(BigInteger.ONE));

    //Escolha um inteiro  "e"  , 1 < "e" < phi(n) ,  "e" e phi(n) sejam primos entre si.
    e = new BigInteger("3");
    while(m.gcd(e).intValue() > 1) e = e.add(new BigInteger("2"));

    // d seja inverso multiplicativo de "e"
    d = e.modInverse(m);

    System.out.println("p:"+p);
    System.out.println("q:"+q);
    System.out.println("n:"+n);
    System.out.println("e:"+e);
    System.out.println("d:"+d);

    //mensagem cifrada - RSA_encrypt()
    msgcifrada = new BigInteger(msg.getBytes()).modPow(e, n).toString();
    System.out.println("msg cifrada: "+ msgcifrada);

    //mensagem decifrada - RSA_decrypt()
    msgdecifrada = new String(new BigInteger(msgcifrada).modPow(d, n).toByteArray());
    System.out.println("msg decifrada: " +msgdecifrada);
  }
}
</syntaxhighlight>

== Correio Anônimo ==
<!-- Mal redigido -->'''Correio Anônimo''' é uma técnica utilizada para enviar mensagens anonimamente utilizando [[criptografia]] RSA, de forma que seja necessário, vários computadores, usando aplicativos para a estragar o [[anonimato]], para que isto seja possível. Envio a requisição de chave publica, para vários computadores selecionados aleatoriamente. Criptografo na ordem inversa a que eu vou enviar( usando as chaves publicas que recebi ), ou seja, primeiro com a senha do ultimo que irá receber a mensagem, e por ultimo com a senha do primeiro. Envio para o primeiro de forma que ele só saiba o segundo destinatário quando descriptografar. Sendo que se todos os destinatários, estiverem sem criptografia, o segundo pode notificar o ultimo, estragando o sigilo. Seguindo está sequência, descriptografo e envio para o próximo. Como ninguém sabe a rota, só sabem o destinatário atual, e como também não sabem o que há no pacote, dificilmente, alguém poderá encontrar o remetente. Trabalhar usando RSA permite, que, nem mesmo gravando todas as conexões de um determinado computador na rede( inclusive o remetente ), seja possível ler os pacotes transmitidos.

== Assinatura digital ==
{{Artigo principal|[[Assinatura digital]]}}
O algoritmo RSA é extensível a este contexto, pelas suas propriedades. Para implementar um sistema de assinaturas digitais com RSA, o utilizador que possua uma chave privada ''d'' poderá assinar uma dada mensagem (em blocos) ''m'' com a seguinte expressão:

<math> s = m^d \mod{n}</math>

Como se pode deduzir, é difícil descobrir ''s'' sem o conhecimento de ''d''. Portanto, uma assinatura digital definida conforme esta equação é difícil de forjar. Mas o emissor de ''m'' não pode negar tê-la emitido, já que mais ninguém poderia ter criado tal assinatura. O receptor recupera a mensagem utilizando a chave pública ''e'' do emissor:

<math> s^e = (m^d)^e \mod{n} = m \mod{n}</math>

Como tal, o receptor consegue validar a assinatura do emissor calculando ''s<sup>e</sup> mod n''. Podemos verificar então que o algoritmo RSA satisfaz os três requisitos necessários de uma assinatura digital.

É fácil deduzir que a assinatura varia dependentemente da mensagem em si, e que operando sobre mensagens longas o tamanho da assinatura seria proporcional. Para colmatar esta situação, faz-se operar o algoritmo sobre um resumo (''digest'') da mensagem, que identifique essa mensagem como única – geralmente o ''digest'' de uma mensagem varia alterando um único byte –, o que mantém, como consequência, que uma assinatura varia de mensagem para mensagem, para um mesmo emissor. Exemplo de [[função geradora]] do ''digest'' é o Secure Hash ([[SHA-1]]).

== Vulnerabilidades do RSA ==
Por ser um sistema de criptografia muito utilizado, o RSA vem tendo suas vulnerabilidades pesquisadas e analisadas praticamente desde sua publicação inicial. Uma lista bem detalhada de ataques ao sistema pode ser encontrada no artigo de Dan Boneh.<ref>{{Citar periódico|primeiro=Dan|ultimo=Boneh|titulo=Twenty Years of Attacks on the RSA Cryptosystem|jornal=Notices of the AMS|volume=46|data=1999|paginas=203–213}}</ref> Segue um resumo de alguns tipos de ataque discutidos no artigo.

=== Fatorando números inteiros muito grandes ===
Uma primeira abordagem de ataque ao RSA teria como objetivo a chave pública por meio da fatoração do módulo <math>n \,</math>, ou seja, dada uma fatoração de <math>n \,</math>, pode-se chegar ao expoente de descriptografia. Este é um exemplo de [[ataque de força bruta]] ao RSA.

Apesar da melhora constante dos algoritmos de fatoração de números inteiros, esta ainda é uma ameaça considerada distante da realidade, caso o sistema RSA seja corretamente implementado, devido à dificuldade para a fatoração de números inteiros com a tecnologia atual.

A título de ilustração Christof Paar<ref>{{citar livro|último = Paar |primeiro = Christof |título= Understanding cryptography a textbook for students and practitioners |publicado= Springer |local= Berlin London |ano= 2009 | isbn = 9783642041013 }}</ref> apresenta a discussão sobre o módulo de 129 dígitos publicada em um artigo da revista ''Scientific American'' por [[Martin Gardner]] em 1997. Fazendo uso dos métodos de fatoração disponíveis e poder computacional da época foi estimado que seriam necessários 40 trilhões de anos para fatorar um número desta magnitude porém a tarefa levou apenas 30 anos para ser realizada.

A discussão então recai em qual é o tamanho seguro para o módulo usado no RSA? Ainda de acordo com Christof Paar muitas aplicações utilizam módulos de 1024 bits porém hoje em dia acredita-se que será possível fatorar números desta magnitude em 10-15 anos e a agências de inteligência podem ser capazes de fazê-lo ainda mais rápido, já que tipicamente empregam as maiores autoridades em criptografia do mundo. Portanto, já é aconselhado utilizar parâmetros de RSA da ordem de 2048-4096 bits para uma segurança mais duradoura.

=== Módulo comum ===
Para evitar a geração de módulos <math>n \,</math> diferentes poderia ser considerado o uso do mesmo módulo <math>n \,</math> para todos os usuários emitido, por exemplo, por uma autoridade central confiável. Apesar de parecer eficiente em uma primeira análise, um usuário poderia usar seus próprios expoentes para fatorar o módulo <math>n \,</math> de outros usuários. Devido a este fato, um módulo RSA nunca deve ser utilizado por mais de uma entidade.

Este é considerado um ataque elementar pois ilustra o uso errôneo do sistema RSA.

=== Pequeno expoente da chave privada ===
Para reduzir o tempo necessário para decriptar uma mensagem ou o tempo necessário para gerar uma assinatura pode-se tentar usar um valor de <math>d \,</math> pequeno no lugar de um <math>d \,</math> aleatório. Usando um <math>d \,</math> pequeno pode-se alcançar uma melhora no desempenho em torno de fatores de 10 para um módulo de 1024 bits porém Michael Wiener<ref>{{Citar periódico|primeiro=Michael J.|ultimo=Wiener|titulo=Cryptanalysis of short RSA secret exponents|jornal=IEEE Transactions on Information Theory|volume=36|data=1990|paginas=553–558}}</ref> mostra que a escolha de um <math>d \,</math> pequeno pode quebrar completamente o sistema RSA.

=== Pequeno expoente da chave pública ===
Pelos mesmos motivos do item anterior, é comum utilizar um expoente público <math>e \,</math> pequeno. O menor <math>e \,</math> possível é três porém para o sistema ficar protegido de alguns tipos de ataque sugere-se o valor <math>e=2^{16}+1=65537 \,</math> e a especificação do sistema RSA menciona a geração aleatória de <math>e \,</math> para tornar o sistema ainda mais seguro.

Ataques desta natureza, ao contrário dos baseados no método anterior, não levam a uma quebra total do sistema RSA, sendo portanto menos perigosos.

Os ataques mais poderosos relacionados ao pequeno expoente da chave pública utilizam resultados baseados no ''Teorema de Coppersmith''.<ref>{{Citar periódico|primeiro=Don|ultimo=Coppersmith|titulo=Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities|jornal=Journal of Cryptology|volume=10(4)|data=1997|paginas=233–260}}</ref>

=== Exposição parcial da chave privada ===
Imaginemos que um usuário teve acesso a uma fração da chave privada, de tamanho <math>d \,</math> bits. Seria este usuário capaz de reproduzir o restante da chave <math>d \,</math> a partir desta fração? Surpreendentemente a resposta é positiva caso a chave <math>d \,</math> seja pequena o suficiente.

Um artigo de 1998<ref>{{Citar periódico|primeiro=Dan|ultimo=Boneh et al.|titulo=Exposing an RSA Private Key Given a Small Fraction of its Bits|data=1998}}</ref> mostra que sendo <math>e<\sqrt{n} \,</math> é possível reconstruir toda a chave a partir de uma fração da mesma. Este resultado mostra a importância de proteger a chave privada RSA de forma eficiente e completa.

=== Ataques temporais ===
Alguns ataques não são decorrentes de falhas ou artifícios matemáticos. Estes ataques são chamados de ''ataques de implementação'' e buscam vulnerabilidades na implementação computacional do sistema RSA, segue um exemplo de ataques desta natureza.

Imaginemos que a chave privada do RSA está resguardada pelo armazenamento em um ''smartcard'' devidamente protegido. Um potencial ataque não consegue examinar o conteúdo do cartão e portanto não chega a expor a chave. Porém, um artigo de 1996<ref>{{Citar periódico|primeiro=Paul C.|ultimo=Kocher|titulo=Timing Attacks on Implementations of Diffie-Hellman RSA DSS and Other Systems|jornal=Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology|data=1996|paginas=104-113}}</ref> mostra que por meio de uma medição precisa do tempo que o ''smartcard'' demora para executar uma decriptação ou assinatura do RSA é possível descobrir o expoente <math>d \,</math> da chave privada e desta forma deixar exposto todo o sistema.

== Ver também ==
* [[Criptografia]]
* [[Assinatura digital]]
* [[Complexidade computacional]]
* [[Criptografia Quântica]]

{{Referências}}

== Ligações externas ==
* [https://web.archive.org/web/20051029040347/http://rsasecurity.com/rsalabs/node.asp?id=2125 PKCS #1: RSA Cryptography Standard]([[RSA Laboratories]] website)
** O [[standard]] ''[[PKCS]] #1'' ''"tece algumas recomendações para a implementação de [[criptografia de chave pública]], abrangendo os seguintes temas: primitivas criptográficas; métodos de criptografia;".
* [https://web.archive.org/web/20070127130201/http://theory.lcs.mit.edu/~rivest/rsapaper.pdf A Method for Obtaining Digital Signatures and Public-Key Cryptosystems], R. Rivest, A. Shamir, L. Adleman, [[Communications of the ACM]], Vol. 21 (2), 1978, pages 120—126. Publicado pelo [[Instituto MIT]] como um "Memorando Técnico" em Abril de 1977.

{{Portal3|Tecnologias de informação}}

[[Categoria:Algoritmos de criptografia]]
[[Categoria:Esquemas de encriptação de chave pública]]