Motherboard

Estes brasileiros querem salvar nossos computadores do caos quântico

Com a água da computação quântica batendo na bunda, boa parte da criptografia que usamos hoje será inútil. Dois pesquisadores do Brasil explicam como buscam manter nossos segredos intocados.

por Brunno Marchetti
13 Outubro 2017, 10:00am

Interior de computador quântico. Crédito: IBM

Nos últimos meses, muitos cientistas reforçaram que a computação quântica baterà à nossa porta. Com ela, você deve saber, muita coisa será redefinida — inclusive a internet. Dentre as várias mudanças, a mais preocupante é a que se refere à criptografia. Do dia para noite, dizem, nossas comunicações seguras podem ficar escancaradas a quem tiver em mãos um computador quântico.

Com isso em vista, a agência de padronização dos Estados Unidos, o NIST (National Institute of Standards and Technology) — equivalente à brasileira ABNT —, abriu chamada pública para envio de novos padrões de criptografia. É a chamada busca pela criptografia pós-quântica. Um dos motivos para o evento foi o aumento da preocupação gerado pelo anúncio de que a NSA (Agência Segurança Nacional dos EUA) estaria trabalhando na criptografia resistente a ataques quânticos e que todos deveriam fazer o mesmo.

Segundo o documento divulgado pelo NIST, os algoritmos de chave privada mais comuns — em que a mesma senha é utilizada para cifrar e decifrar a mensagem — terão sua eficiência reduzida pela metade. Já os padrões de criptografia de chave pública — aquele em que a mensagem é cifrada utilizando uma chave pública e decifrada utilizando uma chave privada — não oferecerão mais segurança nenhuma.

Para o doutor em Ciências da Computação, Diego Aranha, a chamada feita pelo NIST é extremamente relevante, já que os padrões aprovados pela agência acabam sendo adotados em todo o mundo. "Isso é algo que acontece pelo menos desde a década de 1990, quando o padrão de Curvas Elípticas foi amplamente difundido", disse ao Motherboard Brasil.

Diego Aranha. Crédito: Helena Wolfenson

Aranha é um dos brasileiros que contribuirá com processo de seleção dos novos padrões de criptografia pós-quântica. Ele e outros professores de sua equipe, do Laboratório de Segurança da Informação e Criptografia da Unicamp — o Lasca —, vão trabalhar no teste da eficiência e dados de desempenho dos novos algoritmos. "Vamos analisar, por exemplo, quantos segundos e energia vou precisar para fazer uma operação", afirma. "Entender se é possível proteger essa implementação de alguém que consegue monitorar o consumo de energia para ver se ele varia com o tempo e se isso revela alguma informação secreta."

Paulo Barreto, pesquisador da Universidade de Washington Tacoma, nos EUA, também enviou algoritmos criptográficos para chamada do NIST. Ele afirma que desenvolvimento dos novos padrões foi bastante impulsionado pela declaração da NSA, mas não é de hoje que existe o ímpeto no campo de pesquisa. "Há pelo menos 10 anos atrás é conhecido o algoritmo de Schor para quebrar algoritmos clássicos."

Apesar do que o nome sugere, afirma Barreto, a criptografia quântica não utiliza poder computacional quântico. "Não têm nada de quântica, na verdade. É só o nome que pegou mesmo", diz. "É uma criptografia totalmente convencional, em princípio dá pra rodar no notebook, nos celulares, qualquer aparelho totalmente clássico."

O fator nada quântico não a torna menos importante ou sofisticada. Segundo Barreto, os algoritmos convencionais têm natureza algébrica — como o cálculo de elipses e a fatoração de números primos — enquanto as novas propostas de padrão se baseiam em outros problemas matemáticos. "Existem algumas propostas que se baseiam nesses modelos antigos, mas estas já foram quebradas logo de cara, então acho que não é bem por aí que a gente precisa procurar novas soluções criptográficas", comentou.

Ele está à frente do desenvolvimento de uma das propostas de algoritmos de chave pública, o Code-based Algorithm for Key Encapsulation(CAKE). Diferentemente do atual padrão, o problema computacional aqui é baseado em análise combinatória, ou seja quais são as formas possíveis de organizar uma informação. "Computadores quânticos são bons para fazer álgebra, mas não são bons para fazer análise combinatória. Estes problemas continuam difíceis mesmo para eles."

Esta proposta de algoritmo pertence aos chamados algoritmos code-based (baseados em código, tradução livre). "São corretores de erro", diz Barreto. "Uma informação corrompida têm alguns bits no meio do caminho que estão errados, então o problema é: corrija esses erros."

Paulo Barreto, o segundo da esquerda para a direita. Crédito: Universidade de Washington Tacoma

Segundo a explicação de Barreto, este é um problema considerado intratável desde 1962, embora existam vários artigos de pesquisa envolvidos sobre o assunto de códigos corretores de erro. "Pouco progrediu nesses 55 anos", afirma.

Chave simétrica, chave pública

Enquanto a situação é mais complicada com os algoritmos de chave pública, os de chave simétrica estão um pouco mais seguros. É que eles normalmente se baseiam em propriedades estatísticas. "Então existe um problema computacional associado à dificuldade de você quebrar esses algoritmos que um computador quântico não consegue tratar eficientemente", esclarece Barreto.

O problema a qual eles se refere é conhecido como o Problema da Satisfatibilidade de Circuitos Booleanos, ou CSAT. "Ele foi o primeiro problema que há 50 anos gerou a questão de 'P vs nP', ele é um problema chamado 'nP completo'", observou o Barreto. O problema de 'P vs nP' é considerado um dos maiores questões não resolvidas na Ciências da Computação.

De forma resumida, problemas de complexidade P podem ser resolvidos por um computador em um tempo razoável, enquanto problemas do tipo nP demoram um tempo absurdo para ser resolvidos, tornando a solução praticamente inviável. Apesar de uma urgência menor, ainda é um problema. "Trabalhos mais recentes que foram publicados depois da chamada do NIST e que mostram que alguns algoritmos simétricos são suscetíveis a computadores quânticos", diz Barreto

Problemas de prazo

Se a confiabilidade do concurso e a existência de possíveis soluções deixaram de ser quetões, o fator tempo é o que mais preocupa no momento. Em uma palestra realizada em 2016 o físico Michele Mosca, da Universidade de Waterloo, nos EUA, apresentou um dos principais problemas relacionados à adoção da criptografia pós-quântica. Em seu "teorema", descreve que, se o tempo de desenvolvimento somado ao tempo de implementação dos novos padrões forem maiores do que o tempo do surgimento de computadores quânticos potentes, isso significará um tempo totalmente desprotegido.

"Se a gente demorou quinze anos nessa mudança de padrão, então não é provável que consigamos mudar a criptografia do mundo em três anos pra resistir a computação quântica"

Apesar do alerta, ainda há muita especulação na jogada. "É um momento favorável para você conseguir financiamento para pesquisas nessa área, então há quem diga que este prazo é de 10 anos. Já os mais conservadores apostam em 20 ou 30 anos", observou Diego Aranha.

O cronograma divulgado pelo NIST prevê que serão aceitas submissões de algoritmos até o próximo mês de novembro deste ano. A partir desta data, começarão as fases de testes que devem durar entre 3 e 5 anos e, então, haverá a definição dos padrões para implementação, que deve tomar mais dois anos. Após esse intervalo de 5 a 7 anos, começará a adoção dos novos padrões de criptografia por parte de empresas e desenvolvedores. E isso não costuma ser rápido.

Segundo observou Aranha, foram cerca de quinze anos desde a padronização do algoritmo de curvas elípticas até a sua adoção completa no lugar do padrão de algoritmo de chave pública anterior, o RSA. Naquela época, porém, não havia ganho de segurança nessa migração. A justificativa se dava na eficiência do novo padrão. Logo, não era emergencial. "Se a gente demorou quinze anos nessa mudança de padrão, então não é provável que consigamos mudar a criptografia do mundo em três anos pra resistir a computação quântica", afirma Aranha

Já para Paulo Barreto, o tempo do desenvolvimento não chega a estar folgado. É, diz, adequado. Apesar disso, não é fácil ficar tranquilo. Como aponta Aranha: "Esses novos computadores não precisam nem estar disponíveis no mercado, basta estar no subsolo de uma agência de inteligência que a gente já tem um problemão."

Leia mais matérias de ciência e tecnologia no canal MOTHERBOARD.
Siga o Motherboard Brasil no Facebook e no Twitter.
Siga a VICE Brasil no Facebook , Twitter e Instagram .