3
Obrigado

Algumas palavras de agradecimento nunca são demais.

Exemplo de algoritmo assimétrico: RSA

Atualmente, o algoritmo RSA é a base da maioria das aplicações que utilizam criptografia assimétrica. Também chamada de criptografia de chave pública, ela utiliza duas chaves distintas. A seguir, veja um exemplo de sua aplicação.



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.


Para criptografar uma mensagem: 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

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 o par de chaves:
Pegue dois números primos aleatórios: p = 29, q = 37
Calcule 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, você tem as chaves:
  • A chave pública é (e,n) = (71,1073) (=chave de criptografia)
  • A chave privada é (d,n) = (1079,1073) (=chave de decodificação)


Criptografe a mensagem "HELLO. Pegue o código ASCII de cada caractere e os coloque lado a lado:
m = 7269767679

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

726 976 767 900
(completamos com zeros)

Depois, criptogrife 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 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 longo e demorado 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 pequenos quanto no exemplo acima. Você deve ser capaz de calcular potências e módulos 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, os softwares PGP (Pretty Good Privacy) ou GPG (GNU Privacy Guard) são recomendados.

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 utilizado que o RSA. (Diffie-Hellman foi rapidamente adotado pela comunidade open source, quando o RSA ainda não era de domínio público).

Foto: © Marcus Spiske - Unsplash

Veja também

Este documento, intitulado 'Exemplo de algoritmo assimétrico: RSA', está disponível sob a licença Creative Commons. Você pode copiar e/ou modificar o conteúdo desta página com base nas condições estipuladas pela licença. Não se esqueça de creditar o CCM (br.ccm.net) ao utilizar este artigo.