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:

  1. Escolha de forma aleatória dois números primos grandes p \, e q \,da ordem de 〖10〗^100 no minimo
  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)}\,.

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 \,

[editar] Cifração

Para transformar uma mensagem m \, 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.

[editar] Decifração

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

m = c^d\mod{n}

[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

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

Obtido em "http://pt.wikipedia.org/wiki/RSA"
Ferramentas pessoais
Criar um livro