A revolução do computador quântico pode quebrar a criptografia – mas algoritmos mais seguros podem proteger a privacidade
Nos círculos de segurança cibernética, eles chamam de Q-day: o dia em que os computadores quânticos quebrarão a Internet.
Quase tudo o que fazemos online é possível pelo zumbido silencioso e implacável dos algoritmos criptográficos. Esses são os sistemas que embaralham os dados para proteger nossa privacidade, estabelecer nossa identidade e proteger nossos pagamentos. E eles funcionam bem: mesmo com os melhores supercomputadores disponíveis hoje, quebrar os códigos que o mundo online atualmente roda seria uma tarefa quase sem esperança.
Mas as máquinas que explorarão as peculiaridades da física quântica ameaçam todo esse negócio. Se eles atingirem sua escala total, os computadores quânticos quebrariam os algoritmos de criptografia atuais exponencialmente mais rápido do que as melhores máquinas não quânticas. “Um computador quântico real seria extremamente perigoso”, diz Eric Rescorla, diretor de tecnologia da equipe do navegador Firefox na Mozilla em San Francisco, Califórnia.
Como em uma inacreditável viagem no tempo, as máquinas que ainda não existem colocam em risco não apenas nossas comunicações futuras, mas também nossas atuais e passadas. Os ladrões de dados que espionam o tráfego da Internet já podem estar acumulando dados criptografados, que podem desbloquear assim que os computadores quânticos estiverem disponíveis, potencialmente visualizando tudo, desde nossos históricos médicos até nossos antigos registros bancários. “Digamos que um computador quântico seja implantado em 2024”, diz Rescorla. “Tudo o que você fez na Internet antes de 2024 estará aberto para discussão.”
Mesmo os defensores mais otimistas da computação quântica dizem que teremos que esperar um pouco até que as máquinas sejam poderosas o suficiente para quebrar as chaves de criptografia, e muitos duvidam que isso aconteça nesta década – se é que acontecerá.
Mas o risco é real o suficiente para que a Internet esteja sendo preparada para uma reforma, para limitar os danos se o Q-day acontecer.
Isso significa mudar para sistemas criptográficos mais fortes, ou sistemas criptográficos. Felizmente, décadas de pesquisa em ciência da computação teórica trouxeram muitos candidatos. Esses algoritmos pós-quânticos parecem imunes a ataques: mesmo usando abordagens matemáticas que levam em conta a computação quântica, os programadores ainda não encontraram maneiras de derrotá-los em um tempo razoável.
Qual desses algoritmos se tornará padrão pode depender em grande parte de uma decisão a ser anunciada em breve pelo Instituto Nacional de Padrões e Tecnologia dos EUA (NIST) em Gaithersburg, Maryland.
Em 2015, a Agência de Segurança Nacional dos EUA (NSA) anunciou que considerava os atuais criptossistemas vulneráveis e aconselhou as empresas americanas e o governo a substituí-los. No ano seguinte, o NIST convidou cientistas da computação de todo o mundo a enviar algoritmos pós-quânticos candidatos a um processo no qual a agência testaria sua qualidade, com a ajuda de toda a comunidade criptográfica. Desde então, reduziu sua lista de 65 para 15. Nos próximos meses, selecionará alguns vencedores e publicará versões oficiais desses algoritmos. Organizações semelhantes em outros países, da França à China, farão seus próprios anúncios.
Mas isso será apenas o começo de um longo processo de atualização dos sistemas criptográficos do mundo – uma mudança que afetará todos os aspectos de nossas vidas online, embora a esperança seja que seja invisível para o usuário médio da Internet. A experiência mostra que pode ser um caminho esburacado: os primeiros testes de empresas como o Google nem todos correram bem.
“Acho que é algo que sabemos fazer; não está claro que faremos isso a tempo”, disse Peter Shor, matemático do Instituto de Tecnologia de Massachusetts em Cambridge, cujo trabalho mostrou as vulnerabilidades da criptografia atual, à Nature em 2020.
Mesmo que o Q-day nunca aconteça, a possibilidade de máquinas quânticas decifrar códigos já mudou a ciência da computação – e, em particular, a antiga arte da criptografia. “A maioria das pessoas que conheço pensa em termos de criptografia resistente ao quantum”, diz o cientista da computação Shafi Goldwasser, diretor do Simons Institute for the Theory of Computing da Universidade da Califórnia, Berkeley.
Nascimento da criptografia de chave pública
Exércitos e espiões sempre foram capazes de enviar mensagens com segurança, mesmo quando um canal – seja um pombo mensageiro ou um link de rádio – é suscetível a espionagem, desde que suas mensagens sejam criptografadas. No entanto, até a década de 1970, isso exigia que as duas partes concordassem com uma cifra secreta compartilhada com antecedência.
Então, em 1976, três cientistas da computação dos EUA, Whitfield Diffie, Martin Hellman e Ralph Merkle, criaram o conceito revolucionário de criptografia de chave pública, que permite que duas pessoas troquem informações com segurança, mesmo que não tenham um acordo prévio.
A ideia se baseia em um truque matemático que usa dois números: um, a chave pública, é usado para criptografar uma mensagem, e é diferente do segundo, a chave privada, usada para descriptografá-la. Alguém que queira receber mensagens confidenciais pode anunciar sua chave pública para o mundo, digamos, imprimindo-a em um jornal. Qualquer pessoa pode usar a chave pública para embaralhar sua mensagem e compartilhá-la abertamente. Apenas o receptor conhece a chave privada, permitindo-lhe decifrar as informações e lê-las.
Na prática, as chaves públicas normalmente não são usadas para criptografar os dados, mas para compartilhar com segurança uma chave simétrica convencional — uma que ambas as partes podem usar para enviar dados confidenciais em qualquer direção. (Sistemas de chave simétrica também podem ser enfraquecidos por algoritmos quânticos existentes, mas não de maneira catastrófica.)
Nas primeiras duas décadas da era da Internet, a partir de meados da década de 1990, o algoritmo de troca de chave pública mais usado era o RSA, em homenagem a seus inventores, Ron Rivest, Adi Shamir e Leonard Adleman.
O RSA é baseado em números primos — números inteiros, como 17 ou 53, que não são divisíveis por nenhum número, exceto eles mesmos e 1. A chave pública é o produto de pelo menos dois números primos. Apenas uma parte conhece os fatores que constituem a chave privada. A privacidade é protegida pelo fato de que, embora a multiplicação de dois números grandes seja simples, encontrar os fatores primos desconhecidos de um número muito grande é extremamente difícil.
Mais recentemente, a Internet está se afastando do RSA, que é vulnerável até mesmo aos ataques clássicos – em oposição aos quânticos. Em 2018, a Internet Engineering Task Force (IETF), uma organização virtual baseada em consenso que orienta a adoção de padrões de segurança em escala global, endossou outro sistema de chave pública para substituí-lo. Esse sistema é chamado de criptografia de curva elíptica, porque sua matemática surgiu de um ramo da geometria do século XIX que estuda objetos chamados curvas elípticas.
A criptografia de curva elíptica é baseada no cálculo da n – ésima potência de um inteiro (que está associado a um ponto na curva). Apenas uma parte conhece o número n , que é a chave privada. Calcular a exponencial de um número é fácil, mas dado o resultado, é extremamente difícil encontrar o que n era. Essa técnica é mais rápida e segura do que RSA.
Todos os tipos de dispositivos, de telefones celulares a carros, usam criptografia de chave pública para se conectar à Internet. A tecnologia também se espalhou para além do ciberespaço: por exemplo, os chips de radiofrequência em tudo, de cartões de crédito a passes de segurança, normalmente usam algoritmos de curva elíptica.
Quebrando RSA
Assim como o número de usuários da Internet em todo o mundo – e o uso de criptossistemas de chave pública, como RSA – estava começando a crescer exponencialmente, Shor, então no AT&T Bell Laboratories em Murray Hill, Nova Jersey, lançou as bases para o fim desses algoritmos. Ele mostrou em 1994 como um computador quântico deve ser capaz de fatorar grandes números em primos exponencialmente mais rápido do que um computador clássico pode ( PW Shor Proc. 35th Annu. Symp. Found. Comput. Sci . 124-134; 1994 ). Uma das etapas do algoritmo quântico de Shor também pode quebrar com eficiência uma chave de curva elíptica.
O de Shor não foi o primeiro algoritmo quântico, mas foi o primeiro a mostrar que os computadores quânticos podem resolver problemas práticos. Na época, era em grande parte um exercício teórico, porque os computadores quânticos ainda eram sonhos para os físicos. Mas mais tarde naquela década, pesquisadores da IBM realizaram as primeiras provas do princípio dos cálculos quânticos, manipulando moléculas em uma máquina de ressonância magnética nuclear.
Em 2001, eles demonstraram que podiam executar o algoritmo de Shor – mas apenas para calcular que os fatores primos de 15 são 3 e 5. A tecnologia de computação quântica fez um enorme progresso desde então, mas executar o algoritmo de Shor em um grande número inteiro ainda é um muito longe.
Ainda assim, após a descoberta de Shor, o mundo da pesquisa de criptomoedas começou a prestar atenção à possibilidade de um Q-day. Os pesquisadores já estudavam algoritmos alternativos de chave pública, e as notícias atraíram muitos talentos para o campo, diz Goldwasser.
Sistemas baseados em rede
A maioria dos algoritmos que chegaram à lista final do NIST dependem, direta ou indiretamente, de um ramo da criptografia que foi desenvolvido na década de 1990 a partir da matemática das redes.
Utiliza conjuntos de pontos localizados nos cruzamentos de uma rede de linhas retas que se estendem pelo espaço. Esses pontos podem ser somados usando a álgebra de vetores; alguns podem ser divididos em somas de vetores menores. Se a rede tem muitas dimensões – digamos, 500 – é muito demorado calcular o menor desses vetores. Isso é semelhante à situação com números primos: a pessoa que conhece os vetores curtos pode usá-los como chave privada, mas resolver o problema é extremamente difícil para todos os outros.
Desde a década de 1990, os pesquisadores desenvolveram uma infinidade de algoritmos de criptografia de chave pública que usam reticulados diretamente ou estão de alguma forma relacionados a eles. Um dos primeiros tipos, desenvolvido em 1996, é chamado de NTRU. Suas chaves consistem em polinômios com coeficientes inteiros, mas é considerado seguro devido à sua semelhança teórica com problemas de rede. Para mostrar que um sistema criptográfico é confiável, os pesquisadores geralmente provam que é pelo menos tão difícil de quebrar quanto um problema de treliça.
Uma abordagem popular para criptografia baseada em rede é chamada de aprendizado com erros (LWE), que forma a base para vários finalistas do NIST. Foi introduzido em 2005 pelo cientista da computação Oded Regev na Universidade de Nova York. Na sua forma mais simples, baseia-se na aritmética. Para criar uma chave pública, a pessoa que deseja receber uma mensagem escolhe um número grande e secreto — a chave privada. Eles então calculam vários múltiplos desse número e adicionam ‘erros’ aleatórios a cada um: a lista de números resultante é a chave pública. O remetente soma esses números inteiros e outro número que representa a mensagem e envia o resultado.
Para receber a mensagem de volta, tudo o que o receptor precisa fazer é dividi-la pela chave secreta e calcular o restante. “É realmente o nível do ensino médio de matemática”, diz Regev.
O passo mais importante foi a prova de Regev em 2009 de que qualquer pessoa que quebrasse esse algoritmo também seria capaz de quebrar o problema da rede aparentemente mais complexo. Isso significa que o LWE tem a mesma segurança que as treliças, mas sem ter que lidar com vetores multidimensionais, diz Goldwasser. “É uma ótima formulação, porque facilita o trabalho.” Ironicamente, Regev descobriu o LWE durante uma tentativa malsucedida de encontrar um algoritmo quântico que quebraria o problema da rede. “Às vezes, o fracasso é o sucesso”, diz ele.
Desde então, os pesquisadores trabalharam para combater uma desvantagem dos sistemas baseados em treliça. “A criptografia baseada em treliça sofre com enormes chaves públicas”, diz Yu Yu, criptógrafo da Shanghai Jiao Tong University, na China.
Enquanto a chave pública de um aplicativo de Internet atual é do tamanho de um tweet, a criptografia baseada em treliça normalmente requer chaves de até um megabyte ou mais. Os sistemas de ‘rede estruturada’ usam o que são essencialmente ajustes algébricos para reduzir drasticamente o tamanho da chave pública, mas isso pode deixá-los mais abertos a ataques. Os melhores algoritmos de hoje precisam encontrar um equilíbrio delicado entre tamanho e eficiência.
Candidatos quânticos
Em 2015, a admissão incomumente sincera da NSA de que os computadores quânticos eram um sério risco à privacidade fez com que as pessoas nos círculos políticos prestassem atenção à ameaça do Q-day.
“A NSA não costuma falar sobre criptomoedas publicamente, então as pessoas notaram”, disse o matemático do NIST Dustin Moody em uma palestra em uma conferência de criptografia no ano passado.
Sob a liderança da Moody’s, o NIST já estava trabalhando no concurso que anunciou em 2016, no qual convidou cientistas da computação a apresentar algoritmos pós-quânticos candidatos para criptografia de chave pública, liberando-os para escrutínio da comunidade de pesquisa. Ao mesmo tempo, o NIST pediu o envio de algoritmos de assinatura digital – técnicas que permitem que um servidor da Web estabeleça sua identidade, por exemplo, para impedir que golpistas roubem senhas. As mesmas técnicas matemáticas que permitem trocas de chave pública geralmente também se aplicam a esse problema, e os atuais sistemas de assinatura digital são igualmente vulneráveis a ataques quânticos. Além da supremacia quântica: a busca por computadores quânticos úteis
Equipes de laboratórios acadêmicos e empresas, com membros de quatro dezenas de países em seis continentes, submeteram 82 algoritmos, dos quais 65 foram aceitos.
Fiel às credenciais nerd de seus criadores, muitos dos nomes dos algoritmos tinham temas de Guerra nas Estrelas, Jornada nas Estrelas ou Senhor dos Anéis, como FrodoKEM, CRYSTALS-DILITHIUM ou New Hope.
Os algoritmos estão sendo julgados tanto por sua segurança quanto por sua eficiência, o que inclui a velocidade de execução e a compactação das chaves públicas. Quaisquer algoritmos que o NIST escolher padronizar terão que ser isentos de royalties.
Assim que os algoritmos foram apresentados, era época de caça. Os pesquisadores de criptografia adoram quebrar os algoritmos uns dos outros e, depois que os envios do NIST foram tornados públicos, vários dos sistemas foram rapidamente quebrados. “Acho que as pessoas se divertiram muito olhando para esses algoritmos”, diz Moody.
Embora o NIST seja uma agência do governo dos EUA, a comunidade cripto mais ampla tem contribuído. “É um esforço mundial”, diz Philip Lafrance, matemático da empresa de segurança informática ISARA Corporation em Waterloo, Canadá. Isso significa que, ao final do processo, os algoritmos sobreviventes terão ampla aceitação. “O mundo vai basicamente aceitar os padrões do NIST”, diz ele. Ele faz parte de um grupo de trabalho que está monitorando a seleção do NIST em nome do Instituto Europeu de Padrões de Telecomunicações, uma organização abrangente para grupos em todo o mundo. “Esperamos ver muita adoção internacional do padrão que criaremos”, diz Moody.
Ainda assim, como a criptografia afeta interesses nacionais sensíveis, outros países estão de olho – e alguns são cautelosos. “A maturidade dos algoritmos pós-quânticos não deve ser superestimada: muitos aspectos ainda estão em fase de pesquisa”, diz a especialista em criptografia Mélissa Rossi da Agência Nacional de Segurança Cibernética da França em Paris. No entanto, ela acrescenta, isso não deve atrasar a adoção de sistemas pós-quânticos para fortalecer a criptografia atual.
Diz-se que a China está planejando seu próprio processo de seleção, a ser gerenciado pelo Escritório da Administração Estatal de Criptografia Comercial (a agência não respondeu ao pedido de comentário da Nature ). “O consenso entre os pesquisadores na China parece ser que esta competição será uma competição internacional aberta, de modo que os padrões chineses [de criptografia pós-quântica] sejam dos mais altos padrões internacionais”, diz Jintai Ding, matemático da Universidade de Tsinghua em Pequim.
Enquanto isso, uma organização chamada Associação Chinesa de Pesquisa Criptológica já realizou sua própria competição por algoritmos pós-quânticos. Seus resultados foram anunciados em 2020, levando alguns pesquisadores de outros países a concluir erroneamente que o governo chinês já havia feito uma escolha oficial.
Atualizando sistemas
Dos 15 candidatos do NIST, 9 são sistemas de chave pública e 6 são para assinaturas digitais. Os finalistas incluem implementações de NTRU e LWE, bem como outro sistema testado e comprovado que usa a álgebra de técnicas de correção de erros. Conhecidos como ‘algoritmos baseados em código’, esses sistemas armazenam dados com redundância que possibilita a reconstrução de um arquivo original após ter sido levemente danificado por ruído. Em criptografia, o algoritmo de armazenamento de dados é a chave pública e uma chave secreta é necessária para reconstruir uma mensagem original.
Nos próximos meses, o instituto selecionará dois algoritmos para cada aplicação. Ele então começará a elaborar padrões para um, mantendo o outro como reserva caso a primeira escolha acabe sendo quebrada por um ataque inesperado, quântico ou outro.
Selecionar e padronizar algoritmos não será o fim da história. “Certamente é um passo sólido para abençoar um candidato, mas como acompanhamento, a Internet precisa concordar em como integrar um algoritmo em protocolos existentes”, diz Nick Sullivan, criptógrafo aplicado da empresa de serviços de Internet Cloudflare, que é com sede na cidade de Nova York.
Tanto a Cloudflare quanto o Google – muitas vezes em cooperação – começaram a executar testes na vida real de alguns algoritmos pós-quânticos, incluindo-os em algumas versões beta do navegador Chrome e no software do servidor.
O teste é crucial porque, para que as comunicações na Internet ocorram sem problemas, não basta ter servidores e navegadores perfeitamente compatíveis.
Para conectá-los, os dados também devem ser executados por meio de dispositivos de rede que podem bloquear o tráfego que eles sinalizam como incomum por causa de seus protocolos de criptografia desconhecidos. (Esses sistemas podem ser usados para impedir hackers ou impedir que usuários acessem conteúdo proibido.) O software antivírus pode causar problemas semelhantes.
Os problemas também existem “em uma escala mais ampla, em toda a Internet, em alguns países que acompanham o que os usuários estão fazendo”, diz Sullivan. Os profissionais de segurança de rede referem-se a esses problemas como ‘ossificação de protocolo’, ele diz; já complicou a transição do RSA e também pode atrapalhar a implantação de algoritmos de segurança quântica.
Um teste inicial em 2016 implementou New Hope – uma versão estruturada do LWE com o nome do filme original de Star Wars – em uma versão beta do Chrome e funcionou sem problemas. “Este teste mostrou que é utilizável”, diz Erdem Alkım, cientista da computação agora na Universidade Dokuz Eylül em İzmir, Turquia, que escreveu parte do código como parte de sua tese. “Achei que foi um bom resultado para o meu doutorado.”
Mas um experimento em maior escala realizado em 2021 pelo Google em um algoritmo diferente encontrou alguns problemas. Alguns dispositivos da Internet aparentemente ‘quebraram’ – linguagem de segurança de rede para um gadget que bloqueia uma conexão quando o navegador de um cliente tenta se comunicar com um protocolo incomum. O problema pode ter sido que a mensagem de abertura do navegador foi mais longa do que o esperado, porque carregava uma grande chave pública. Algoritmos que quebram a Internet dessa maneira podem ser arquivados até que esses problemas sejam resolvidos.
“Às vezes você se depara com situações em que algum elemento da rede se comporta mal ao adicionar algo novo”, comenta Rescorla. Persuadir os fornecedores a adaptar seus produtos – algo que muitas vezes pode ser feito com uma simples atualização de software – pode levar alguns empurrões, diz ele. “Isso vai demorar um pouco.”
Ainda assim, Rescorla está otimista, pelo menos quando se trata de navegadores de internet. Como apenas um pequeno número de empresas controla a maioria dos navegadores e muitos servidores, tudo o que precisa acontecer é que eles alterem os sistemas de criptografia. “Todo mundo está bastante confiante de que, assim que o NIST e o IETF especificarem novos padrões, poderemos implementá-los rapidamente.”
Onde a transição pode ser mais complicada é a multiplicidade de dispositivos conectados modernos, como carros, câmeras de segurança e todos os tipos de máquinas de ‘casas inteligentes’, que sofrem de ossificação de protocolo – especialmente aqueles que podem ter recursos de segurança conectados em seus chips e que são não é substituído com frequência. “Leva de cinco a sete anos para projetar um veículo, e ele estará na estrada por uma década”, diz Lafrance. “Ainda será seguro daqui a dez anos?”
De qualquer forma, as implementações iniciais serão híbridas, usando tecnologia pós-quântica para aumentar a segurança dos sistemas existentes. Vadim Lyubashevsky, cientista da computação da IBM em Zurique, na Suíça, cuja equipe tem dois algoritmos baseados em rede entre os finalistas do NIST, diz que acha que os métodos de criptografia pós-quânticos e atuais devem funcionar juntos por uma década antes que os novos algoritmos sejam usados exclusivamente.
Se tudo correr como planejado, a Internet estará em sua era pós-quântica quando a computação entrar em sua era quântica. Essa Internet pós-quântica poderá algum dia ser seguida, de forma confusa, por uma Internet quântica – ou seja, uma rede que usa os princípios da física quântica para tornar a troca de informações à prova de hackers.
Os pesquisadores estimam que, para quebrar os sistemas criptográficos, os computadores quânticos precisarão ter cerca de 1.000 vezes mais componentes de computação (qubits) do que atualmente. “Há uma boa chance de termos um computador quântico que possa fazer coisas positivas muito antes de quebrar a criptografia”, diz Lyubashevsky.
Mas isso não é motivo para ser complacente. A transição completa de toda a tecnologia para ser resistente ao quantum levará no mínimo cinco anos, diz Rescorla, e sempre que o Q-day acontecer, é provável que haja dispositivos escondidos em algum lugar que ainda serão vulneráveis, diz ele. “Mesmo que façamos o melhor que pudermos, um computador quântico real será incrivelmente perturbador.”
Natureza 602 , 198-201 (2022)
doi: https://doi.org/10.1038/d41586-022-00339-5
NIST’s Post-Quantum Cryptography Program Enters ‘Selection Round’
Cibersegurança na Era Quântica: Implicações na criptografia
Viveremos no mundo da computação quântica. Por Eduardo Lacerda
Philip R. Zimmermann apresenta o 3º episódio AET Security Topics: Quantum Key Distribution
NSA publica atualização sobre criptografia resistente a quantum
Empresa Inglesa utiliza satélites para distribuir chaves quânticas para centros de dados
O Crypto ID é a maior fonte de consulta sobre criptografia no Brasil e na América Latina
Criptografia forte é o padrão que mantém bilhões de pessoas, empresas e nações seguras todos os dias
O Crypto ID é a sua porta de entrada para o mundo fascinante da criptografia, com conteúdos que exploram desde os fundamentos da cripto-agil até as mais recentes inovações em criptografia pós-quântica a geração de chaves baseada em fenômenos quânticos com o comportamento de partículas subatômicas.
Acesse agora a Coluna Criptografia e mantenha-se atualizado sobre as últimas tendências em segurança da informação.
Gostou? Compartilhe com seus amigos e colegas!
