Qual chave Alice deve usar para criptografar uma mensagem para Bob?

Cifras como AES são bastante seguras: com uma chave gerada de forma adequada (idealmente de forma completamente aleatória), apenas força bruta permite sua quebra. Com chaves de até 256 bits, e portanto 2²⁵⁶ possíveis chaves, é um problema intratável verificar todas as possibilidades.

Porém, todas cifras descritas até então possuem uma vulnerabilidade crucial: a distribuição da chave. Para iniciar um processo de comunicação segura, é necessário que ambas as partes possuam a mesma chave. Isso envolve um dos lados gerar a chave e transmiti-la para a outra parte. O problema é como fazer esta transmissão. Claramente não se pode enviar a chave por um canal inseguro — se a chave for interceptada, toda comunicação futura será comprometida. Assim, é necessário um grande esforço, e custo, para que este envio ocorra sem vazamentos — talvez a ponto de uma pessoa de confiança decorar a chave e viajar até o destinatário apenas para entregá-la (e, ainda assim, esta pessoa está sujeita a suborno ou ameaças).

O problema da distribuição de chaves permaneceu um dos principais problemas da criptografia por séculos. O primeiro grande avanço, considerado o maior avanço da criptografia, veio no final da década de 70, com o algoritmo de troca de chaves de Diffie-Hellman, nome dado a dois dos criadores — Whitfield Diffie e Martin Hellman. Ralph Merkle também foi um contribuidor e desde os anos 2000 se tem proposto chamar o algoritmo de Diffie-Hellman-Merkle (DHM).

O algoritmo DHM é uma forma radicalmente diferente de realizar a distribuição de chaves. Ao invés de uma parte gerar a chave e enviar para a outra, o algoritmo estabelece um protocolo que permite que ambas as partes construam uma chave de forma conjunta, trocando apenas informações que podem ser compartilhadas publicamente. Uma analogia que ajuda a compreender o processo envolve imaginar que a chave é uma cor específica de tinta que será gerada por este protocolo, como abaixo.

No fluxo acima, Alice e Bob desejam se comunicar de forma segura, por exemplo utilizando AES. Para tanto, eles precisam de uma chave compartilhada. O algoritmo DHM inicia com Alice e Bob possuindo uma tinta comum (amarela), definida pelo algoritmo. Alice agora escolhe aleatoriamente uma cor e mantém esta em segredo (vermelho). Bob faz a mesma coisa (verde). Alice mistura sua cor secreta com a cor comum e envia o resultado para Bob (vermelho+amarelo). Ela não precisa se preocupar com como este envio é feito, a informação pode ser divulgada publicamente. Bob também mistura a sua cor secreta com a cor comum e envia o resultado para Alice (verde+amarelo).

Alice agora possui a mistura de Bob (verde+amarelo) e então mistura sua cor secreta, resultando em verde+amarelo+vermelho (marrom). Bob faz o mesmo com a mistura de Alice (vermelho+amarelo), adicionado sua cor secreta e resultando em vermelho+amarelo+verde, o que também resulta em marrom. Ambos chegaram a mesma cor e podem usá-la como a chave secreta.

A segurança desta transação depende da mistura transmitida entre Alice e Bob ser praticamente inseparável — isto é, não seja viável a partir da cor da mistura deduzir a cor secreta. Se for possível fazer a separação, alguém que intercepte as misturas poderá recuperar a cor secreta e reconstruir a chave final. Porém, se não for possível fazer esta separação, então interceptar a mistura não é de utilidade alguma: sem alguma das cores secretas, não se sabe o que adicionar à mistura para obter a cor final. Passa a ser necessário tentar todas cores possíveis (força bruta), o que é bastante custoso se houver uma grande quantidade de cores.

O grande avanço que Diffie, Hellman e Merkle obtiveram foi encontrar uma formulação matemática para este problema de mistura de cores. A base da formulação é uma função irreversível: uma função f(x) que é trivial de ser calculada sabendo o valor de x mas que, sabendo o valor f(x) não se consegue facilmente obter o valor x de volta.

Considere a função f(x) = 3^x. Se nos disserem que f(x) = 9, sabemos que x=2. Esta função é trivialmente reversível, pois sabemos a função inversa da exponencial. Mesmo se não soubéssemos ainda assim é simples de realizar a reversão por tentativa e erro: podemos chutar que x=5 e calcular f(5), o que resulta em 243, que é um valor maior que 9. Sabemos então que nosso chute foi alto demais e podemos reduzi-lo, talvez chutando x=2. Vemos que o chute é muito baixo e precisamos aumentá-lo, eventualmente chegando no resultado final Isso é possível pois a função é monotonicamente crescente: o resultado da função só cresce com o valores maiores de x.

Porém considere agora a função f(x) = 3^x mod 7, onde o operador mod é o operador de módulo. O operador de módulo funciona como um limitador no resultado de 3^x: ele diz que o resultado não pode ser maior que 6 (7–1). Quando ele for maior que 6, ele "dá a volta" e retorna à 0. Assim:

• 7 mod 7 = 0
• 8 mod 7 = 1
• 9 mod 7 = 2
• 14 mod 7 = 0

Um relógio de ponteiros segue esta lógica: apesar das horas irem de 0 a 23, quando o ponteiro de horas atinge o 12 ele "volta" e começa a contagem novamente, de 1 a 12. Podemos ver que para obter o resultado do módulo, basta fazer a divisão dos valores e retornar o resto.

Se tabelarmos a função f(x) = 3ˆx mod 7, obtemos:

Observe como a função não é monotonicamente crescente. Se nos disserem que f(x)=4, podemos tentar chutar um valor para x, talvez x=3, obtendo f(3) = 6. Infelizmente, agora esta informação não nos diz se devemos aumentar ou reduzir o chute. Para encontrar o valor de x, precisaremos testar todos os valores possíveis. Aqui isto é trivial, mas considere o que acontece se x for um número de 256 bits.

Este tipo de função é chamada de função exponencial modular e é uma candidata perfeita para o ingrediente necessário para tornar realidade o processo de mistura de tintas, dando origem ao algoritmo DHM. O algoritmo funciona como abaixo:

Execute este algoritmo usando quaisquer valores para g, p, a e b. Verifique que tanto Alice como Bob chegam ao mesmo valor. Como nas tintas, a segurança do algoritmo depende que A e B sejam irreversíveis. Como vimos, a exponenciação modular é irreversível e alguém de posse destes valores teria que testar todos possíveis valores para encontrar os números secretos de Alice e Bob.

O algoritmo DHM é um grande marco da criptografia. Pela primeira vez, duas pessoas que desejam se comunicar não precisam se preocupar com a distribuição de chaves: basta que elas tenham um canal público de comunicação e utilizem o DHM para construírem a chave secreta em conjunto. Observe, porém, que este algoritmo não é uma cifra já que ele não criptografa mensagens. Ainda é necessário um algoritmo como o AES para fazer uso da chave gerada.

Inspirados pelo então recente avanço, um outro time propôs, um ano depois do DHM ser publicado, uma cifra baseada nos conceitos primeiro explorados por Diffie, Hellman e Merkle. O algoritmo RSA também recebe seu nome dos seus criadores — Rivest, Shamir e Adleman — mas, diferente do DHM, o RSA é uma cifra, permitindo a codificação e decodificação de mensagens.

A ideia central do RSA também é melhor compreendida com uma analogia. Imagine que Alice deseja enviar uma mensagem secreta para Bob. Para tanto, ela pega uma caixa, coloca a mensagem dentro e a tranca com um cadeado, enviando a caixa trancada para Bob. Ela agora tem o problema de como fazer a chave do cadeado chegar a Bob; do contrário, ele não terá como abrir a caixa. Uma maneira de resolver isso é, no lugar de Alice usar um cadeado próprio, esta pede que Bob envie para ela o seu cadeado. Alice agora pode trancar a caixa com o cadeado de Bob e enviar para ele; Bob não terá problema para abrir a caixa, pois possui a chave para o seu cadeado.

Apesar de trivial, esta analogia é profundamente diferente dos algoritmos tradicionais de criptografia. Há dois elementos distintos: o cadeado e a chave. O cadeado fecha a caixa, mas para abri-la é necessária a chave correspondente. De fato, depois de fechada, Alice não tem mais como abrir a caixa! Apenas Bob poderá abri-la. Em oposição, um algoritmo como AES utiliza um único elemento: a chave privada. Quem tem posse desta chave pode abrir a "caixa" quando quiser e, portanto, a chave não pode ser transmitida por meio inseguro. Mas não há problema para o cadeado da analogia ser transmitido por meio qualquer: ele apenas fecha caixas, não as abre.

O algoritmo RSA implementa esta analogia ao definir chaves assimétricas: uma chave criptografa a mensagem e só é possível decodificar a mensagem cifrada usando outra chave. Estas chaves são "irmãs" — o que uma fecha, a outra abre e vice-versa. Nenhuma outra chave é capaz de decodificar a mensagem. Esta é a chamada Criptografia por Chaves Assimétricas.

Conceitualmente, o RSA é bastante simples. Quando Alice deseja se comunicar com Bob, Bob gera um par de chaves: uma chave privada e uma chave pública. Bob envia para Alice sua chave pública que a utiliza para codificar a mensagem. Alice então envia a mensagem cifrada com a chave pública de Bob de volta para ele, que pode decodificar a mensagem cifrada usando sua chave privada. Alguém que intercepte a chave pública e a mensagem cifrada nada poderá fazer, pois a chave pública não abre a mensagem cifrada, da mesma forma com que um cadeado não abre a si próprio.

O seguintes passos descrevem como as chaves são geradas:

1. Escolhe-se dois números primos diferentes p e q
2. N = pq
3. ϕ = (p-1)(q-1)
4. Escolhe-se um inteiro e maior que 1 e menor que ϕ e que seja co-primo de ϕ
5. Calcula-se d = (1+ xϕ) / e , procurando por um valor x que faça com que d seja um inteiro

A chave pública é o par (e, N) enquanto a chave privada é o par (d, N).

No RSA, mensagens são codificadas como inteiros. Se desejamos encriptar um inteiro M podemos usar a chave pública:

C = M^e mod N

E agora podemos encontrar a mensagem original usando a chave privada:

M = C^d mod N

A segurança do RSA advém de não ser possível obter a chave privada a partir da chave pública. Porém, em princípio a chave pública contém todas informações necessárias para tanto: todo o processo de geração inicia-se com os números primos p e q; e N=pq é parte da chave pública. Assim, se pudermos obter p e q a partir de N, podemos replicar a chave privada. Ou seja, precisamos fatorar N para quebrar o RSA.

Lembre-se de que no DHM, a segurança advém da irreversibilidade da exponenciação modular. Aqui também utiliza-se a exponenciação modular no processo de cifragem e decifragem e a segurança desta etapa é garantida por esta irreversibilidade.

Porém, o quão difícil é fatorar um número inteiro? Aprendemos a fatorar números ainda no ensino fundamental e parece contra-intuitivo que a segurança do RSA dependa de algo que parece trivial.

Podemos adotar um algoritmo direto para fatorar um inteiro N. Basta testar todos inteiros menores do que N, verificando se estes dividem N perfeitamente. Assim, precisaremos fazer O(N) divisões. Ainda que pareça ser uma complexidade linear, observe que N aqui não é o tamanho da entrada do algoritmo. O tamanho da entrada do algoritmo seria o número de dígitos de N ou, de forma mais geral, o tamanho do vetor binário necessário para representar N. Considerando que N precisa de b bits para ser representado, temos que é necessário realizar O(2^b) divisões. Isto é, este algoritmo para fatoração é exponencial.

Não é realmente necessário testar valores até N-1, sendo apenas necessário testar valores até a raiz quadrada de N. Tampouco precisamos testar valores pares, já que sabemos que N é o produto de dois números primos. Indo além, apenas precisamos testar números primos, ainda que isso gere o problema de como gerar estes números primos.

De fato, temos algoritmos substancialmente melhores para fatoração. O melhor algoritmo conhecido é um algoritmo probabilístico denominado General Number Field Sieve (GNFS) e sua complexidade é dada por:

Observe que no expoente apenas aparece o logaritmo de N. Temos algo que cresce rapidamente (exponencial) com algo que cresce lentamente (logaritmo). Isto caracteriza um crescimento sub-exponencial. No entanto, o crescimento claramente não é polinomial. A versão de decisão do problema da fatoração é uma candidata a pertencer a classe NP-Intermediário.

O problema é apenas um candidato pois não foi provado que GNFS é o melhor algoritmo possível para este problema e um algoritmo polinomial pode existir, apenas não foi descoberto ainda. Interessantemente, também não foi provado que o problema de fatoração não é NP-Completo.

Temos então que a segurança do RSA depende de não ser viável fatorar N, mas é possível fatorar N em tempo sub-exponencial. Para garantir a segurança, é necessário que N seja substancialmente grande. Chaves RSA hoje tipicamente variam de 1024 até 4096 bits, muito maiores do que, por exemplo, chaves para o AES (que variam de 128 a 256 bits). Uma chave RSA de 1024 bits tem segurança aproximada de uma chave simétrica de 80 bits.

Adicionalmente, avanços na capacidade de computação e melhorias nos algoritmos de fatoração ao longo dos anos torna chaves RSA incrementalmente maiores necessárias. No início dos anos 2000, chaves de 512 bits eram comuns enquanto hoje são consideradas inseguras.

O fato de ser difícil (mas não tão difícil assim) fatorar números pode nos levar a questionar se é factível afinal gerar as chaves em primeiro lugar. Lembre que o processo de geração inicia criando dois números primos, que devem ser grandes para gerar um N grande. Uma maneira de gerar estes primos é gerar números grandes aleatoriamente e fatorá-los para verificar se não há fatores além dos triviais (1 e o próprio número). Mas se fatorar é um processo intratável para números grandes, então como gerar estes primos?

É possível testar a primalidade de um número sem fatorá-lo diretamente, fazendo uso de propriedades que números primos possuem. Um exemplo é o Teste de Primalidade de Fermat. É um algoritmo probabilístico que gera um número (ímpar) aleatório n e verifica se este atende a seguinte propriedade:

a^(n − 1) mod n == 1

Onde a é um inteiro qualquer co-primo a n (isto é, não possuem fatores comuns), chamado de testemunha. Se a equação não for satisfeita, então n não é primo. Se a equação for satisfeita, então n pode ser primo. Se a equação é satisfeita mas n não é primo, diz-se que n é pseudoprimo em relação a a.

O teste de Fermat quando diz que um número é composto, então ele é realmente composto; porém se diz que o número é primo, há uma chance de ele não ser. Este é um algoritmo de Monte Carlo. Se desejamos aumentar a confiança no resultado quando este indica primalidade, podemos executar o algoritmo novamente, escolhendo outro valor para a.

O teste de Fermat é rápido de ser executado mas um problema é que ele falha para uma classe de números chamados de números de Carmichael. Estes são números compostos que o teste de Fermat diz serem pseudoprimos para qualquer testemunha a. Assim, para estes números não importa quantas vezes executamos o algoritmo, nossa confiança no resultado não se torna maior.

Uma melhoria sobre este algoritmo é o Teste de Primalidade de Miller–Rabin. Como o de Fermat, o algoritmo gera um número aleatório mas adiciona testes adicionais para garantir que o teste não falha para números de Carmichael. Como o algoritmo de Miller-Rabin é mais lento que o de Fermat, é comum que sejam usados em conjunto — primeiro aplica-se o teste de Fermat para descartar números compostos e então aplica-se o de Miller-Rabin para aumentar a confiança na primalidade.

Ambos algoritmos executam em tempo polinomial. O algoritmo de Miller-Rabin executa em O(k (log n)^3), onde k é o número de execuções para aumentar a confiança no resultado, mas pode ser melhorado utilizando algoritmos mais eficientes para multiplicação de grandes números. Assim, o problema de teste de primalidade é um problema pertencente a classe BPP. Por muito tempo apenas suspeitava-se que o problema poderia também pertencer a P e somente em 2002 um algoritmo determinístico polinomial foi descoberto. O algoritmo AKS (iniciais de Agrawal, Kayal e Saxena, os criadores) sempre retorna o resultado correto em tempo polinomial e executa em tempo O((log n)^6) na sua versão mais atual (a inicial tinha 12 como expoente). O algoritmo AKS provou que o teste de primalidade é um problema P, apesar dos algoritmos probabilísticos ainda serem bastante utilizados por serem mais rápidos para grandes números.

O fato do teste de primalidade ser um problema muito mais fácil do que o problema de fatoração de inteiros garante que o RSA é eficiente de ser utilizado na prática e bastante seguro para chaves grandes. O RSA é responsável hoje por garantir a segurança de comunicação entre navegadores e servidores web, por meio do protocolo HTTPS. Quando um navegador deseja se comunicar de forma segura com um servidor, para enviar um cartão de crédito por exemplo, este solicita a chave pública do servidor e a utiliza para iniciar a comunicação segura.

Ironicamente, apesar do RSA ser um algoritmo de criptografia, como ele é muito mais lento do que algoritmos de chave simétrica, o HTTPS tipicamente o utiliza como um meio para distribuição de chave: podemos usar a chave pública do servidor para encriptar uma chave simétrica. A chave criptografada é enviada para o servidor, que a decodifica com a sua chave privada e então inicia um canal criptografado utilizando esta chave simétrica com um algoritmo como o AES.

Chaves assimétricas também permitem assinaturas eletrônicas. Uma assinatura eletrônica é utilizada para identificar o envio de uma mensagem, que pode ou não estar criptografada. Isso é possível pois, assim como o contrário, mensagens cifradas pela chave privada somente podem ser decifradas com a chave pública.

Considere que Alice deseja enviar uma mensagem para Bob, mas Bob gostaria de ter certeza que foi realmente Alice quem escreveu a mensagem. Se Bob possuir a chave pública de Alice, e souber inequivocamente que esta chave é de fato dela, então Alice pode criptografar a mensagem usando sua chave privada e enviar para Bob. Bob então usa a chave pública para decodificar a mensagem cifrada. Se ele tiver sucesso, então há a certeza de que foi Alice quem criou a mensagem, pois a chave pública de Alice somente abre mensagens cifradas com a chave privada dela.

O problema deste cenário é como garantir que Bob sabe que a chave pública é da Alice. De fato, este é um problema mais geral: se Alice deseja enviar uma mensagem criptografada para Bob, ela precisa solicitar sua chave pública — mas como saber que a chave pública recebida é de fato de Bob? Se eles se encontrarem fisicamente e trocarem chaves, talvez haja alguma segurança no processo, mas idealmente gostaríamos de fazer isso pela internet.

Se Bob enviar sua chave pública pela internet para Alice, um ataque conhecido como man in the middle permite que um atacante substitua a chave de Bob por sua própria chave. Alice receberá uma chave pública como solicitado, mas esta não será de Bob. Ao encriptar a mensagem com esta chave, o atacante poderá ler a mensagem sem problemas. Nem Bob nem Alice sabem que isto ocorreu, pois o atacante, após abrir a mensagem pode re-encriptá-la com a chave pública de Bob.

A solução atual para este problema envolve Autoridades de Certificados Digitais, ou Certificadoras Digitais, como Verisign e DigiCert. Estas autoridades mantém banco de dados de chaves públicas de seus clientes. Por exemplo, a Amazon. Quando nos conectamos no site da Amazon, ao invés de solicitarmos a chave pública da Amazon diretamente para ela, o navegador solicita de uma certificadora. Quando esta autoridade envia uma chave pública, esta é assinada digitalmente com a assinatura da autoridade, de forma a sabermos que não houve um ataque man in the middle.

Claro, isto não resolve o problema: para verificarmos a assinatura da certificadora precisamos ter sua chave pública, mas como ter certeza que a chave pública é de fato da certificadora? Isso é resolvido com certificados raízes, ou chaves públicas pré-instaladas no navegador. Quando instalamos um navegador, ele já vem com chaves públicas das principais certificadoras, permitindo a verificação da assinatura digital destas.

Este é um bom motivo para não baixar navegadores de sites que não sejam confiáveis, ou utilizar navegadores de origem desconhecida. Estes podem trazer certificados falsos que permitem ataques man in the middle.

Assinaturas eletrônicas são a base de documentos eletrônicos como e-CPF e e-CNPJ. Quando criamos um destes documentos, estamos criando um par de chaves assimétricas e armazenando a chave pública em uma certificadora. Assim, quando assinamos eletronicamente um documento, estamos criptografando uma mensagem com nossa chave privada (tipicamente armazenada em um cartão ou token), que outros podem verificar solicitando a chave pública da certificadora.

Qual o tipo de criptografia que usa uma chave compartilhada entre emitente Alice e receptor Bob?

Como criar uma chave de criptografia?

Qual chave de criptografia utiliza a mesma chave tanto para codificar quanto para decodificar mensagens?

Qual o tipo de criptografia na qual a mesma chave usada para cifrar é usada para decifrar?