RSA

Se procura a empresa, veja RSA Data Security, Inc.

Adi Shamir, um dos criadores do RSA

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.), Ronald Rivest, Adi Shamir e Leonard Adleman, que inventaram este algoritmo — até a 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.

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.

Geração das chaves

No RSA as chaves são geradas desta maneira:

1. Escolha de forma aleatória dois números primos grandes $p \,$ e $q \,$, da ordem de $10^{100}$ no mínimo.
2. Compute $n = p q \,$
3. Compute a função totiente em $n \,$: $\phi(n) = (p-1)(q-1) \,$.
4. Escolha um inteiro $e \,$ tal que 1 < $e\,$ < $\phi(n)\,$, de forma que $e\,$ e $\phi (n)\,$ sejam primos entre si.
5. Compute $d \,$ de forma que $d e \equiv1\pmod{\phi(n)}\,$, ou seja, $d \,$ seja o inverso multiplicativo de $e \,$ em $\pmod{\phi(n)}\,$.

• 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 $n \,$ e $e \,$
A chave privada: o par de números $n \,$ e $d \,$

Cifração

Para transformar uma mensagem $m \,$, onde $0 \,$ $< \,$ $m \,$ $< \,$ $n \,$, numa mensagem $c \,$ cifrada usando a chave pública do destinatário $n \,$ e $e \,$ basta fazer uma potenciação modular:

$c = m^e\mod{n}$

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

Decifração

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

$m = c^d\mod{n}$

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 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 (se divide por 8 para conseguir em bytes).

RSA é usado comumente para transferir senhas RC4 por ser mais rápido. A senha, geralmente, tem apenas 128 bits (16 bytes) 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 decriptografar.

Em Java

SecureRandom random = new SecureRandom(); //gera um numero aleatório seguro
 
KeyPairGenerator generator = KeyPairGenerator.getInstance("RSA", "BC"); 
 
generator.initialize( 2048, random); //chaves de 2048 bits
KeyPair pair = generator.generateKeyPair(); //Gera as chaves pública e privada
PublicKey pubKey = pair.getPublic(); //chave pública
PrivateKey privKey = pair.getPrivate(); //chave privada
 
Cipher cipher = Cipher.getInstance("RSA");
cipher.init(Cipher.ENCRYPT_MODE, pubKey, random); //cifra com a chave pública
 
byte[] cipherText = cipher.doFinal(input); //mensagem cifrada
 
cipher.init(Cipher.DECRYPT_MODE, privKey); //decifra com a chave privada
byte[] plainText = cipher.doFinal(cipherText); //mensagem decifrada

Correio Anônimo

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

Ver 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:

$s = m^d \mod{n}$

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:

$s^e = (m^d)^e \mod{n} = m \mod{n}$

Como tal, o receptor consegue validar a assinatura do emissor calculando s^e 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).

Ver também

• Assinatura digital
• Complexidade computacional
• Criptografia Quântica

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.
• http://alexm.unetvale.com.br/blog/2009/07/criptografia-rsa-em-simples-passos/ RSA em scripts PHP.
• http://www.java2s.com/Tutorial/Java/0490__Security/BasicRSAexample.htm RSA em Java tutorial em inglês