Exemplo de algoritmo assimétrico: RSA

Novembro 2016


Existem diferentes algoritmos assimétricos. Um dos mais conhecidos é o RSA (devido aos seus desenvolvedores Rivest, Shamir, e Adleman). Este algoritmo é amplamente utilizado nos navegadores, para sites seguros e para criptografar e-mails. É de domínio público.
L'algorithme est remarquable par sa simplicité. Il est basé sur les nombres premiers.
Para criptografar uma mensagem, fazemos: c = m^e mod n
Para descriptografá-la: m = c^d mod n

m = texto simples
c = mensagem criptografada
(e, n) = chave pública
(d, n) = chave privada
n = é o produto de dois números primos
^ = é a operação de exponenciação (a^b: a potência b)
mod = é a operação de módulo (resto da divisão inteira)

Criar um par de chaves


É muito simples, mas cuidado ao escolher e, d e n. E saiba que o cálculo desses três números é delicado.

Veja como fazer:

1. Pegar dois números primos p e q (tamanho aproximadamente igual). Calcular n = pq.
2. Pegar um número e que não tem nenhum fator em comum com (p-1)(q-1).
3. Calcular d como ed mod (p-1)(q-1) = 1.

O par (e,n) é a chave pública. (d,n) é a chave privada.

Exemplo:


Em primeiro lugar, vamos criar nosso par de chaves:
Pegar dois números primos aleatórios: p = 29, q = 37
Calcular n = pq = 29 * 37 = 1073
e deve ser escolhido de forma aleatória de modo que e não tenha nenhum fator em comum com (p-1) (q-1):
(p-1)(q-1) = (29-1)(37-1) = 1008
Pegar e = 71
Escolher d como 71*d mod 1008 = 1
Vamos encontrar d = 1079
Agora temos as nossas chaves:
  • A chave pública é (e,n) = (71,1073) (=chave de criptografia)
  • A chave privada é (d,n) = (1079,1073) (=chave de decodificação)


Vamos criptografar a mensagem "HELLO. Vamos pegar o código ASCII de cada caractere e colocá-los lado a lado:
m = 7269767679

Então, temos que recortar a mensagem em blocos contendo menos dígitos do que n. n tem 4 dígitos, então vamos recortar a nossa mensagem em blocos de três dígitos:

726 976 767 900
(completamos com zeros)

Depois, vamos criptografar cada bloco:

726^71 mod 1073 = 436
976^71 mod 1073 = 822
767^71 mod 1073 = 825
900^71 mod 1073 = 552
A mensagem criptografada é 436 822 825 552. Ela pode ser descriptografada com gras>d</gras>:
436^1079 mod 1073 = 726
822^1079 mod 1073 = 976
825^1079 mod 1073 = 767
552^1079 mod 1073 = 900
Ou seja, a sequência de números 726976767900.

Encontramos a nossa mensagem em texto simples 72 69 76 76 79: "HELLO".

Na prática


Na prática, não é tão fácil de programar:
  • É preciso encontrar números primos grandes (isso pode ser muito longodemorado para calcular)
  • É preciso obter números primos p e q realmente aleatórios (o que não é fácil).
  • Não se usa blocos tão pequeno quanto no exemplo acima: você deve ser capaz de calcular potências e modulos com números muito grandes.


Na verdade, nunca se usam algoritmos assimétricos para criptografar todos os dados, porque eles são muito demorados para calcular: criptografam-se os dados com um algoritmo simétrico cuja chave é escolhida aleatoriamente, e é esta chave que é descriptografada com um algoritmo assimétrico, como o RSA.

P.G.P.


Se você quiser criptografar seus arquivos, eu recomendo o excelente software PGP (Pretty Good Privacy) ou o GPG (GNU Privacy Guard).
Outros algoritmos, outros programas...
Existem outros algoritmos assimétricos, incluindo o ECC (Elliptic Curve Cryptosystems, por curva elíptica). Este sistema é baseado em uma curva paramétrica que passa por um certo número de pontos de coordenadas inteiras. Ainda não está bem desenvolvido, mas é promissor.

Também existe o Diffie-Hellman , cada vez mais preferido que o RSA. (Diffie-Hellman foi rapidamente adotado pela comunidade open source, quando o RSA ainda não era de domínio público).

Artigo original publicado por sebsauvage

Tradução feita por Lucia Maurity y Nouira

Veja também :
Este documento, intitulado « Exemplo de algoritmo assimétrico: RSA »a partir de CCM (br.ccm.net) está disponibilizado sob a licença Creative Commons. Você pode copiar, modificar cópias desta página, nas condições estipuladas pela licença, como esta nota aparece claramente.