Como funciona a criptografia RSA de forma simples

A criptografia consiste em enviar uma informação cifrada, de modo que apenas o recipiente consiga decifrar.

Alice envia para Bob um texto cifrado.

Ação a fazer: Texto normal -> Texto cifrado

Um espião, Eva, não pode ser capaz de decifrar a mensagem enviada.

Bob, e apenas Bob, deve ser capaz de decifrar, ou seja, realizar a operação:

Texto cifrado -> Texto decifrado

No caso do exemplo acima, foi utilizada uma cifra de substituição simples, a Cifra de César (porque é usada desde o Império Romano). Esta consiste apenas em substituir uma letra do alfabeto por outra, e é extremamente frágil para métodos criptográficos modernos (não use a mesma para criptografar sua senha do banco!).

A mensagem decriptada é “boa tarde para todos!”.

Para baixar o código desta cifra simples, vide https://ferramentasexcelvba.wordpress.com/2020/10/19/pequena-rotina-de-criptografia/

Métodos simétricos e assimétricos modernos

Dá para separar os métodos de criptografia em:

- chaves simétricas: as chaves de encriptação e decriptação são as mesmas

- chaves assimétricas: as chaves são diferentes, porém relacionadas

=========

Chaves simétricas

O método de chaves simétricas é o mais simples, e é o historicamente mais utilizado. exemplos são os padrões DES (Data encryption standard) e AES (Advanced encryption standard).

Este método necessita de uma chave de uso único, chamada de one-time pad. Como essa chave é usada para tanto encriptar como decriptar, esta deve ser mantida em segredo absoluto. Nesse caso, o problema muda de lugar: ao invés da mensagem, o ponto fraco passa a ser o compartilhamento da chave. Como Alice e Bob podem combinar o one-time pad sem interceptação de um espião? Eles podem se encontrar fisicamente, por exemplo. Resolver este problema não é nada prático. Imagine a era moderna da internet, onde compramos e vendemos sem nunca ter encontrado nem o banco que intermedeia a transação, muito menos o comprador ou vendedor.

=========

Chaves assimétricas

O método de chaves públicas é do tipo assimétrico, e foi desenvolvido nos anos 1970 por vários grupos.

Há o protocolo Diffie-Hellman, de 1976, por exemplo. O mais famoso é o algoritmo RSA, de Ronald Rivest, Adi Shamir e Len Adleman, de 1978.

Uma chave pública é utilizada para encriptar, e uma chave privada para decriptar. Ambas mensagens estão relacionadas matematicamente. A segurança do método baseia-se na dificuldade computacional de obter a chave privada a partir da chave pública.

O truque é utilizar funções de mão única. São funções onde é fácil fazer a computação numa direção, porém difícil fazer a operação inversa.

O método RSA baseia-se na dificuldade da fatoração dos números primos. É muito fácil fazer a*b= N, porém é bastante mais complicado obter a e b a partir de N.

Exemplos.

É muito simples calcular 19 * 13 = 247.

É mais difícil, a partir de 247, encontrar os fatores primos 19 e 13.

O valor 247 ainda é pequeno — é possível resolver no braço. Porém, à medida que o número aumenta, fica mais difícil.

Como exercício, tente encontrar os fatores primos de 8633.

Num código mais próximo à realidade, o número a fatorar é:

25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357

Encara?

Para saber porque a complexidade da fatoração é exponencial, vide link:

https://informacaoquantica.wordpress.com/2020/08/27/por-que-a-complexidade-computacional-da-fatoracao-de-numeros-inteiros-e-expraizn/

================

Como o algoritmo RSA funciona?

Suponha que Bob queira mandar uma mensagem para Alice.

Bob pede a Alice uma chave pública.

Alice envia sua chave pública (e,N) (sem revelar a chave privada d).

Bob encripta a mensagem m utilizando a chave pública de Alice (e, N), e envia a mensagem encriptada c de volta a Alice.

Suponha Eva ser a espiã monitorando a linha de comunicação. Ela pode conseguir uma cópia da chave pública transmitida e da mensagem criptografada. Mesmo com ambas as informações, ela não vai conseguir decriptar a mensagem.

A segurança baseia-se que é bastante difícil conseguir encontrar a chave privada, somente a partir da chave pública.

Alice, com a chave privada, pode trivialmente decifrar a mensagem enviada por Bob.

Se Alice quiser enviar uma mensagem de volta a Bob, o caminho é o inverso. Ela pede a chave pública de Bob, encripta e envia.

A grande beleza é que este método resolve o problema da troca de chaves. Ninguém precisa se encontrar secretamente para trocar essa informação, como no método simétrico. Este é o método utilizado atualmente para transações seguras e comunicação.

A desvantagem: o método RSA envolve complexidade bem maior do que o método de chaves simétricas, resultando em uma operação mais lenta. Portanto, é muito comum utilizar o método RSA para fazer a troca de chaves tipo one time pad, e depois, utilizar os métodos simétricos tradicionais para a comunicação de forma segura.

Exemplo numérico do método RSA

O método RSA é baseado na exponenciação modular.

Lembrando, o operador módulo é o resto da divisão.

10 mod 3 = 1, porque 10 dividido por 3 tem quociente 3 e resto 1.

Ou, escrevendo de outra forma:

10 = 1 mod 3

Cabe ressaltar que a mensagem original deve ser codificada em números inteiros para as operações serem aplicadas.

Dada uma mensagem m, podemos encontrar números e, d e N de forma que a operação abaixo seja verdadeira.

Bob pode encriptar a mensagem m, obtendo a mensagem cifrada c, segundo a receita:

E Alice decripta a mensagem c recebida, utilizando a sua chave privada d:

Por exemplo, com as chaves N = 143, e = 7, Alice quer encriptar a mensagem 14.

c = 14 ^7 mod 143 = 53.

A mensagem encriptada 53 é enviada a Bob.

Para números pequenos, é possível fazer essas contas no Excel. Para números grandes, não é possível, porque esbarra no limite de representação de números inteiros do Excel.

É mais jogo usar o Wolfram Alpha ( https://www.wolframalpha.com/)

Basta digitar 14⁷ mod 143 e teclar Enter.

Para decriptar a mensagem, é necessária uma chave privada d, que apenas Alice tem acesso.

Para N = 143 e e = 7, a chave privada d é 103.

A operação de decriptação é dada por:

53¹⁰³ mod 143 = 14

Ou seja, a partir da mensagem codificada “53”, chego à mensagem original “14”, a partir da chave (d, N) dadas.

Apesar de 52¹⁰³ ser um número enorme, não é necessário fazer toda essa conta para descobrir o resto. Como é uma função periódica e não preciso saber o coeficiente (só preciso do resto), há atalhos numéricos que fazem o cálculo ser eficiente.

Como obter as chaves do método RSA?

Números primos são aqueles divisíveis apenas por 1 e por si mesmos.

Para gerar as chaves, partimos de dois primos p e q. Há testes eficientes para verificar se um número qualquer é primo ou não, são os chamados testes de primalidade.

Além disso, os números p e q devem ser gerados aleatoriamente.

A seguir, os números p e q são multiplicados, para gerar o número N.

N = p*q

O próximo passo é obter os fatores d e e.

Isso é obtido a partir da propriedade de periodicidade da exponenciação modular.

Há uma relação o período que a função se repete r e os números p e q.

Imagine a série da potência de 2:
1, 2, 4, 8, 16, 32, 64, …

O que acontece se eu pegar a mesma série, módulo 5?
Dá:
[1, 2, 4, 3, 1, 2, 4, 3, 1, 2, 4, 3]

Note que a série acima é periódica. O [1, 2, 4, 3] se repete indefinidamente, com período r = 4.

Existe uma relação, descoberta por Leonard Euler, o maior matemático de todos os tempos.

Dada a sequência: x mod N, x² mod N, x³ mod N, x⁴ mod N, …

Se N é o produto de dois primos p e q, e x não é divisível por p ou q, a sequência se repete com um período r que divide (p-1)(q-1), e esta é uma divisão par.

A partir de r, é possível determinar os valores e e d.

Escolher um e entre 3 e r, tomando o cuidado de e e r serem primos entre si.

A chave pública será formada pelos números (e, N), e a chave privada, (d, N).

No final das contas, e, d, N terão a propriedade mostrada no começo do texto:

Por enquanto, não há método em computação clássica para resolver o problema da fatoração em primos de forma eficiente. Porém, computadores quânticos, em particular o algoritmo de Shor, podem atacar o problema de forma eficiente, colocando em risco toda a criptografia do mundo moderno: transações bancárias, comunicações secretas entre países, e até criptomoedas como o Bitcoin.

Como o tema aqui é computação quântica, o algoritmo de Shor será melhor detalhado em posts posteriores.

Outra nota é que há inúmeros detalhes de implementação e complementos de segurança, trabalhados pela comunidade de especialistas em criptografia do mundo todo, de forma que as noções acima são apenas uma visão geral.

Veja também:

https://informacaoquantica.wordpress.com/2021/02/03/explicando-o-algoritmo-de-shor-de-forma-simples/ https://informacaoquantica.wordpress.com/2020/10/31/havera-uma-corrida-para-a-criptografia-pos-quantum-na-mesma-escala-do-bug-do-ano-2000/

Originally published at http://informacaoquantica.wordpress.com on March 13, 2021.

Project Manager on Analytics and Innovation. “Samurai of Analytics”. Passionate about Combinatorial Optimization, Philosophy and Quantum Computing.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store