Introdução
Em 1994, o cientista da computação Peter Shor descoberto que se os computadores quânticos fossem inventados, eles dizimariam grande parte da infraestrutura usada para proteger as informações compartilhadas online. Essa possibilidade assustadora fez com que os pesquisadores lutassem para produzir novos esquemas de criptografia “pós-quânticos”, para salvar o máximo de informações que pudessem de cair nas mãos de hackers quânticos.
No início deste ano, o Instituto Nacional de Padrões e Tecnologia revelou quatro finalistas em sua busca por um padrão de criptografia pós-quântica. Três deles usam “criptografia de treliça” – um esquema inspirado em treliças, arranjos regulares de pontos no espaço.
A criptografia de rede e outras possibilidades pós-quânticas diferem dos padrões atuais de maneiras cruciais. Mas todos eles dependem da assimetria matemática. A segurança de muitos sistemas de criptografia atuais é baseada na multiplicação e fatoração: qualquer computador pode multiplicar rapidamente dois números, mas pode levar séculos para fatorar um número criptograficamente grande em seus constituintes primos. Essa assimetria torna os segredos fáceis de codificar, mas difíceis de decodificar.
O que Shor revelou em seu algoritmo de 1994 foi que uma peculiaridade de fatoração o torna vulnerável a ataques de computadores quânticos. “É uma coisa muito específica e especial que o computador quântico pode fazer”, disse Katherine Stange, um matemático da Universidade do Colorado, Boulder. Então, depois de Shor, os criptógrafos tiveram um novo trabalho: encontrar um novo conjunto de operações matemáticas fáceis de fazer, mas quase impossíveis de desfazer.
A criptografia de rede é uma das tentativas mais bem-sucedidas até agora. Originalmente desenvolvido na década de 1990, ele se baseia na dificuldade de somas de pontos de engenharia reversa.
Aqui está uma maneira de descrever a criptografia de treliça: imagine que seu amigo tem uma treliça, que é apenas um monte de pontos em um padrão regular e repetitivo por todo o plano. Seu amigo quer que você nomeie 10 desses pontos. Mas ele está sendo difícil e não vai desenhar toda a treliça. Em vez disso, ele lista apenas dois pontos - o primeiro com um x-valor de 101 e um y-valor de 19, o outro com coordenadas [235, 44].
Felizmente, é fácil encontrar novos pontos em uma rede, porque quando você adiciona e subtrai dois pontos quaisquer em uma rede, obtém um terceiro ponto na mesma rede. Então, tudo o que você precisa fazer é somar os pontos que seu amigo lhe deu, ou multiplicá-los por números inteiros e depois somá-los, ou alguma combinação dos dois. Faça isso de oito maneiras diferentes e você poderá responder à pergunta do seu amigo.
Mas seu amigo ainda não está satisfeito. Ele fornece os mesmos dois pontos iniciais e depois pergunta se o ponto [2, 1] está na mesma rede. Para responder a esta pergunta corretamente, você deve encontrar a combinação de [101, 19] e [235, 44] que produz [2, 1]. Este problema é muito mais difícil do que o primeiro, e você provavelmente acabará apenas adivinhando e verificando para obter a resposta.* Essa assimetria é o que fundamenta a criptografia em rede.
Se você realmente deseja usar criptografia de rede para compartilhar informações, faça o seguinte. Imagine que um amigo (mais simpático!) queira lhe enviar uma mensagem segura. Você começa com uma grade quadrada de números. Digamos que ele tenha duas linhas e duas colunas e fique assim:
Agora você cria uma “chave” privada que só você conhece. Neste exemplo, digamos que sua chave privada seja apenas dois números secretos: 3 e −2. Você multiplica os números da primeira coluna por 3 e os da segunda coluna por -2. Some os resultados em cada linha para obter uma terceira coluna com duas entradas.
Cole a nova coluna no final da sua grade. Essa nova grade de três colunas é sua chave pública. Compartilhe-o livremente!
(Um cenário do mundo real será um pouco mais complicado. Para evitar que hackers decodifiquem sua chave privada, você precisa adicionar um pouco de ruído aleatório em sua coluna final. Mas aqui vamos ignorar esse passo para simplificar. )
Agora seu amigo usará a chave pública para lhe enviar uma mensagem. Ela pensa em dois números secretos próprios: 2 e 0. Ela multiplica os números da primeira linha por 2 e os da segunda linha por 0. Ela então soma os resultados em cada coluna para obter uma terceira linha.
Ela agora anexa a nova linha à parte inferior da grade e a envia de volta para você. (Novamente, em um sistema real, ela precisaria adicionar algum ruído à sua linha.)
Agora você vai ler a mensagem. Para fazer isso, você verifica se a última linha do seu amigo está correta. Aplique sua própria chave privada às duas primeiras entradas de sua linha. O resultado deve corresponder à última entrada.
Seu amigo também pode optar por enviar uma linha com um número errado na última coluna. Ela sabe que esse número não corresponderá aos seus cálculos.
Se sua amiga enviar uma linha onde o último número está correto, você interpretará isso como 0. Se ela enviar uma linha onde o número estiver incorreto, você a interpretará como 1. A linha, portanto, codifica um único bit: 0 ou 1.
Observe que um invasor externo não terá acesso nem à sua chave privada nem à do seu amigo. Sem isso, o invasor não terá ideia se o número final está correto ou não.
Na prática, você gostaria de enviar mensagens com mais de um bit. Assim, as pessoas que desejam receber, digamos, uma mensagem de 100 bits gerarão 100 novas colunas em vez de apenas uma. Em seguida, o remetente da mensagem criará uma única nova linha, modificando as últimas 100 entradas para codificar 0 ou 1 para cada entrada.
Se a criptografia de rede for realmente implementada, ela terá inúmeras nuances não cobertas neste cenário. Por exemplo, se você quer que a mensagem esteja realmente a salvo de olhares indiscretos, a matriz precisa ter um número impensável de entradas, tornando a coisa toda tão pesada que não vale a pena usá-la. Para contornar isso, os pesquisadores usam matrizes com simetrias úteis que podem reduzir o número de parâmetros. Além disso, há todo um conjunto de ajustes que podem ser aplicados ao problema em si, à forma como os erros são incorporados e muito mais.
Claro, é sempre possível que alguém encontre uma falha fatal na criptografia de rede, assim como Shor fez para fatoração. Não há garantia de que um esquema criptográfico específico funcionará diante de qualquer possível ataque. A criptografia funciona até ser quebrada. De fato, no início deste verão um esquema de criptografia pós-quântica promissor foi quebrado usando não um computador quântico, mas um laptop comum. Para Stange, todo o projeto cria um paradoxo desconfortável: “O que eu acho tão incrível na criptografia é que construímos essa infraestrutura para a raça humana com a firme convicção de que nossa capacidade como humanos é limitada”, disse ela. “É tão atrasado.”
*: A resposta, se você estiver curioso, é 7 × [101, 19] – 3 × [235, 44] = [2, 1]. [voltar ao artigo]
