RSA
Origem: Wikipédia, a enciclopédia livre.
-
- Se procura a empresa, veja RSA Data Security, Inc.
RSA é um algoritmo de criptografia de dados, que deve o seu nome a três professores do Instituto MIT (fundadores da actual empresa RSA Data Security, Inc.), Ron Rivest, Adi Shamir e Len Adleman, que inventaram este algoritmo — até à data (2008), a mais bem sucedida implementação de sistemas de chaves assimétricas, e fundamenta-se em teorias clássicas dos números. É 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.
Índice |
[editar] Funcionamento
O RSA envolve um par de 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 é codificado e recodificado pela criptografia RSA.
[editar] Geração das chaves
No RSA as chaves são geradas desta maneira:
- Escolha de forma aleatória dois números primos grandes
e
da ordem de 〖10〗^100 no minimo - Compute

- Compute a função totiente em
:
. - Escolha um inteiro
tal que 1 <
<
, de forma que
e
sejam primos entre si. - Compute
de forma que
, ou seja,
seja o inverso multiplicativo de
em
.
- 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 de números
e 
A chave privada: o par de números
e 
[editar] Cifração
Para transformar uma mensagem
numa mensagem
cifrada usando a chave pública do destinatário
e
basta fazer uma potenciação modular:
A mensagem então pode ser transmitida em canal inseguro para o receptor. Há um algoritmo para realizar esta potência rapidamente.
[editar] Decifração
Para recuperar a mensagem
da mensagem cifrada
usando a respectiva chave privada do receptor
e
, basta fazer outra potenciação modular:
[editar] 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, se bem que encontrar dois números primos de grandes dimensões (p.e. 100 dígitos) é computacionalmente fácil, conseguir factorizar o produto de tais dois números é considerado 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 cerca de 350 bits, e as implementações atuais superam os 512 e mesmo os 1024 bits.
[editar] 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:

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:

Como tal, o receptor consegue validar a assinatura do emissor calculando se 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).
[editar] Ver também
[editar] Ligações externas
- 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;".
- 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.
- Publicação inicial do esquema RSA.



