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:
================
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.
