A promessa e a ameaça da computação quântica

A computação quântica promete segurança futura da informação, mas simultaneamente ameaça todas as informações atualmente protegidas pela criptografia RSA de 2048 bits.

É hora de avaliar a ameaça e examinar possíveis soluções.

Isso requer explorar o estado atual da computação quântica, examinar a ameaça ao RSA e considerar os desenvolvimentos na criptografia à prova de quantum, capazes de mitigar o risco futuro. Conversamos com o professor Frank Wailhelm-Mauch, um físico teórico que trabalha com computação quântica e chefe do grupo de pesquisa de estado sólido quântico da Universidade de Saarland. Ele é uma figura chave no projeto Quantum Flagship de 10 anos de € 1 bilhão da União Europeia. Ele está coordenando uma tarefa para construir um computador de 100 qubit (chamado OpenSuperQ) que pode então ser usado em pesquisas futuras.

O estado quântico

Em outubro de 2019, o Google anunciou que havia alcançado a ‘supremacia quântica’, o que significa que havia obtido sucesso em seu próprio projeto chamado ‘supremacia quântica’. Foi uma grande conquista – um processador de 54 qubit que resolveu um problema predefinido em 200 segundos. O Google calculou que o supercomputador clássico mais rápido do mundo levaria 10.000 anos para produzir a mesma saída.

O mundo percebeu. A computação quântica está mais próxima do que pensávamos? A criptografia atual está mais ameaçada do que imaginávamos?

Citando um artigo publicado em 2011 pela Computerworld, a Cyberspace Solarium Commission escreveu em março de 2020: “Hoje, computadores clássicos trabalhando juntos e testando 1 trilhão de chaves por segundo para quebrar a mesma chave de criptografia precisariam de até 10,79 quintilhões de anos, ou 785 milhões vezes a idade do universo conhecido. No entanto, um computador quântico poderia realizar a mesma tarefa em cerca de seis meses. ”

O objetivo desta declaração é estimular o governo a aumentar sua pesquisa quântica para “que a pesquisa dos EUA permaneça à frente da de outros países, particularmente a China”, e começar a usar criptografia à prova de quantum em comunicações confidenciais o mais rápido possível.

Mas é uma declaração sem sentido. Ele diz quanto tempo um computador ou computadores clássicos específicos levariam para realizar uma tarefa não especificada e, em seguida, o compara a um computador quântico não especificado de tamanho e potência não especificados em um futuro não especificado.

É hora de avaliar o status atual da computação quântica

O poder do quantum

O potencial da computação quântica pode ser visto comparando-o com a computação clássica. A computação clássica não depende mais da velocidade do clock do processador, como fazia 20 anos atrás, mas agora depende do número de núcleos próximos que podem ser aproveitados para processar dados em paralelo. 

Se você comparar os processadores usados ​​em um supercomputador clássico com os de um laptop, eles são um pouco melhores, mas basicamente semelhantes. A principal diferença é o número de núcleos que podem ser usados ​​em paralelo – por exemplo, foi afirmado na Conferência de Supercomputadores de 2016 em Frankfurt que o supercomputador Sunway TaihuLight da China tinha 10.649.600 núcleos de computação.

Simplificando, na computação clássica, o poder vem do processamento paralelo que vem da ligação de processadores separados. O processamento paralelo é externo ao processador individual.

Esse princípio é revertido na computação quântica, que usa o princípio da mecânica quântica de que um único objeto pode estar em vários lugares ao mesmo tempo. Essa multiplicidade pode ser traduzida em variáveis ​​que podem, em princípio, ser variáveis ​​diferentes em um único algoritmo que podem ser processadas simultaneamente. Em outras palavras, em termos muito simples, o processamento paralelo necessário para a potência do computador agora é movido para dentro de um único processador.

“Nesse sentido”, disse Wilhelm-Mauch à SecurityWeek , “o computador quântico é o computador paralelo definitivo. Porque o número de cálculos paralelos que são em princípio possíveis aumenta exponencialmente com o número de bits. Seria necessário um computador clássico um número exponencial de núcleos de processador paralelo para alcançá-lo. ”

Mas ainda existem enormes problemas para os engenheiros quânticos resolverem. Uma delas é que os computadores quânticos fornecem apenas resultados prováveis. “Quando uma variável quântica tem múltiplas variáveis ​​ao mesmo tempo e você deseja lê-la, você está obtendo todos esses resultados de cálculos paralelos com alguma probabilidade”, disse Wilhelm-Mauch. “O truque agora é encontrar um algoritmo quântico que, por um lado, use esse paralelismo maciço e, por outro lado, forneça a resposta certa com uma probabilidade aceitável. Idealmente, essa probabilidade deve ser certa, mas 50% também é bom – basta executá-lo algumas vezes. Esta é a arte de escrever algoritmos quânticos. ”

Acontece que o principal desafio para o hardware do computador quântico não é tanto o número de bits quânticos ou qubits, mas a probabilidade de erro de operação. No hardware de computador clássico, disse ele, “essa possibilidade é assustadoramente baixa. Se você estiver executando um computador clássico, apenas nas considerações de segurança mais extremas (como gerenciar uma usina nuclear) você pensaria em uma possível falha de hardware, porque a falha de software sempre ocorrerá primeiro. Para computadores quânticos é muito diferente, em primeiro lugar porque é um hardware muito experimental, mas também porque existem aspectos intrínsecos da fragilidade da mecânica quântica – isso abre muitas rotas de erro e é por isso que a taxa de erro das operações quânticas é muito alto.” 

(Deve-se observar, sem questionar a enormidade da conquista da supremacia quântica do Google, que o teste usado foi desenvolvido especificamente para o produto que ele tinha.)

Wilhelm-Mauch acredita que com o tempo a taxa de erro provavelmente cairá por um fator de cerca de 100, mas isso ainda não será bom o suficiente para executar algoritmos curtos com uma taxa de erro aceitável. “No entanto”, acrescentou ele, “há um campo de correção de erros quânticos, que está relacionado à correção de erros que fazemos na comunicação clássica. Usamos redundância para detectar erros usando coisas simples como somas de verificação – se a soma de verificação estiver errada, deve haver um erro em algum lugar. A correção de erros do Quantum requer que a taxa de erros do seu hardware seja sempre baixa o suficiente. Você pode então, por redundância, ao colocar muito mais açúcar em seu sistema, também executar algoritmos curtos. ”

O problema RSA

A segurança atual da criptografia de chave RSA é baseada no problema quase impossivelmente difícil de fatorar números muito grandes. Embora existam algoritmos que podem fazer isso, a quantidade de capacidade de computação necessária é imensa e facilmente aumentada – o esforço para quebrar a chave aumenta quase exponencialmente com o tamanho da chave. 

Para colocar isso em contexto, explicou Wilhelm-Mauch, “se você tivesse um supercomputador clássico capaz de quebrar o RSA 2048, você poderia, em princípio, apenas adicionar 2 dígitos ao tamanho da chave e torná-lo 4 milhões de vezes mais difícil de quebrar; ou seja, demoraria 4 milhões de vezes mais. Por esse motivo ”, acrescentou ele,“ qualquer corrida armamentista entre decifradores com supercomputadores e criptografadores clássicos sempre será vencida pelo criptografador ”.

Este princípio de que a criptografia sempre permanecerá à frente da capacidade de construir supercomputadores com mais e mais núcleos separados operando em paralelo e com capacidade de descriptografia não se aplica a computadores quânticos onde o paralelismo é efetivamente aumentado dentro do processador.

Em teoria, os computadores quânticos poderosos serão capazes de derrotar a criptografia RSA atual com relativa facilidade. Existe até um algoritmo quântico, que satisfaz os requisitos de precisão necessários, já disponível. Este é o algoritmo de Shor , inventado em 1994 pelo matemático americano Peter Shor. Shor mostrou que com computadores quânticos, a fatoração e logaritmos discretos podem ser resolvidos em tempo polinomial. Um computador quântico pode usar seu paralelismo embutido para reduzir drasticamente o tempo necessário para quebrar a chave. O algoritmo “usa paralelismo quântico massivo, mas no final obtém uma única resposta útil com quase certeza”, disse Wilhelm-Mauch. “Em princípio, o RSA será ameaçado por um algoritmo de 25 anos.”

Mas ainda não. Vamos voltar à supremacia quântica do Google, que foi uma conquista incrível para desenvolver um processador de 54 qubit. “Se extrapolarmos o progresso atual em hardware, número de qubits e taxa de erro”, diz Wilhelm-Mauch, “ainda há um longo caminho a percorrer. A taxa de erro qubit precisa cair por um fator de 10 ou mesmo 100; e mesmo se estivermos lá, para fazer um ataque significativo ao RSA que poderia ser feito em um dia, precisaríamos de um bilhão de qubits em um mundo onde agora temos cinquenta. Precisaríamos de um bilhão de qubits de uma ordem de magnitude melhor do que temos hoje. ”

Com base em nosso conhecimento atual de desenvolvimento quântico, a criptografia RSA é e permanecerá segura por muitos anos. Ele acabará sendo quebrado, mas a vida útil da maioria dos segredos comerciais pode ser medida em apenas alguns anos. Quando o RSA atual for perdido, a maioria dos segredos comerciais naturalmente não serão mais secretos.

Isso não se aplica a segredos de segurança nacional. Dados sensíveis sobre decisões políticas que permanecem sensíveis por décadas e são mantidos em segredo por muitos anos, de repente se tornam vulneráveis. Isso explica por que os governos estão se tornando cada vez mais vociferantes sobre a necessidade de mudar para métodos de criptografia à prova de quantum mais cedo ou mais tarde. “O trabalho que está sendo feito, como o do NIST, trabalhando em algoritmos de criptografia clássicos que não podem ser quebrados pela computação quântica, deve ser levado a sério”, adverte Wilhelm-Mauch; “Mas não precisamos mudar para o modo de pânico. No entanto, descobrir os fornecedores certos e concordar e implementá-los deve convergir para um prazo aceitável. ”

Computadores quânticos de agência

Tudo isso levanta uma questão importante: podemos ter certeza de que as grandes agências governamentais ainda não têm seu próprio computador quântico secreto? Edward Snowden demonstrou que as agências de inteligência ocidentais, como a NSA nos Estados Unidos e o GCHQ no Reino Unido, capturaram grandes trechos de tráfego da Internet (o GCHQ até tinha um projeto chamado ‘dominar a Internet’).

Nos anos mais recentes, a China foi suspeita de fazer o mesmo usando seus grupos APT patrocinados pelo estado para obter acesso a provedores de telecomunicações para roubar comunicações. Isso pode estar em parte por trás da preocupação dos EUA com a Huawei da China dominar as redes 5G do mundo. Às vezes, é descartado como uma preocupação, já que mesmo com equipamentos comprometidos da Huawei, apenas metadados e nenhum conteúdo criptografado seriam vulneráveis. 

Mas assim que qualquer serviço de inteligência de estado tiver acesso a um computador quântico capaz de quebrar o RSA, as comunicações atuais não estarão mais seguras. E a questão é: alguma dessas agências poderia ter um?

Wilhelm-Mauch acredita que isso é improvável. “A distância entre o que é conhecido publicamente apenas em termos de parâmetros de desempenho rígidos e frios e o que é necessário para a tarefa é tão grande que é extremamente improvável”, disse ele à SecurityWeek. O processo, ele acredita, teria sido visível – algo que ele detalhou em um artigo ( PDF ) de sua co-autoria para o BSI (o Escritório Federal Alemão de Segurança da Informação) em 2019:

“ Supondo que os desafios técnicos atuais sejam atendidos – operações um pouco melhores, uso esparso de periferia volumosa, áreas maiores de chip, conexões interchip e atualizações para tecnologia criogênica – parece ser possível ter um computador com um milhão de transmons planares [ Wikipedia] e uma taxa de erro físico de 1: 10000. Isso permitiria atacar 2048 bits RSA em algumas centenas de horas. Um ataque mais rápido (em uma hora) exigiria conectar até 1000 dessas unidades. Isso exigiria novas soluções tecnológicas para conectar essas unidades – o que foi demonstrado, mas atualmente seria muito lento. Além disso, o enchimento inicial dessas máquinas com Hélio 3 exigiria quase toda a demanda industrial anual de Hélio 3, provavelmente exigindo novas instalações nucleares para produzir este isótopo. O investimento financeiro e humano em tal esforço seria muito maior do que os esforços atuais em computação quântica. ”

A implicação é que a habilidade de crackear o RSA-2048 em menos de duas semanas é provável em um futuro próximo. A capacidade de fazer isso em uma hora ainda está muito distante. Tirar quinze dias para descobrir segredos de estado ou propriedade intelectual de alto valor é um bom retorno – tirar quinze dias para descobrir conversas comerciais é menos. No entanto, o uso de criptografia à prova de quantum deve ser implementado mais cedo ou mais tarde.

NIST e criptografia à prova de quantum

O NIST tem trabalhado em criptografia quântica à prova de computador (PQC) nos últimos cinco anos. Após um workshop de abril de 2015 que discutiu a criptografia pós-quântica e sua potencial padronização futura, o NIST anunciou uma ‘Solicitação de nomeações para algoritmos criptográficos pós-quânticos de chave pública’ em dezembro de 2016. O prazo final era novembro de 2017, e o NIST recebeu 82 inscrições de equipes com membros localizados em 25 países (recebeu apenas 21 inscrições para a competição AES anterior). Dos 82, o NIST aceitou 69, compreendendo 20 esquemas de assinatura digital e 49 criptografia de chave pública (PKE) ou mecanismos de encapsulamento de chave (KEMs).

Em janeiro de 2019, o NIST anunciou que 26 algoritmos (17 esquemas de criptografia de chave pública e estabelecimento de chave e nove esquemas de assinatura digital) foram selecionados para prosseguir para a segunda rodada do processo de padronização. Isso foi detalhado no relatório de status NISTIR 8240 ( PDF ). Cada submissão é descrita com um breve comentário do NIST.

Os candidatos foram dados até março de 2019 para fazer qualquer ajuste nos algoritmos, e o NIST anunciou: “Com o número de candidatos substancialmente reduzido desde o primeiro turno, esperamos que os esforços combinados da comunidade criptográfica avaliem os candidatos restantes e forneçam ao NIST feedback que apóia ou refuta as afirmações de segurança dos solicitantes. ” 

Em 22 de julho, o NIST anunciou que seu programa entrou na “Rodada de Seleção” que ajudaria a agência a decidir sobre o pequeno subconjunto de algoritmos que formarão o núcleo do primeiro padrão de criptografia pós-quântica. 

Ao encontrar um padrão de criptografia pós-quântica adequado, é útil considerar que a segurança da criptografia RSA é baseada em dois elementos: a dificuldade do problema matemático (fatoração de grandes números) que precisa ser resolvido, e a suposta falta de qualquer algoritmo ou método que pode resolver o problema com a tecnologia de computador clássica atual. A ameaça quântica vem do aumento do poder de computação junto com a existência de um algoritmo (algoritmo de Shor) que pode aproveitar esse poder para resolver o problema: ambas as partes são necessárias.

Conseqüentemente, o PQC requer um novo problema matemático que não é suscetível a quaisquer novos algoritmos que possam usar a potência quântica para resolver o problema. Na realidade, isso não é diferente do RSA hoje – ele assume que não há algoritmo capaz de quebrar a criptografia com a computação clássica em um momento significativo. (O algoritmo de Shor não é de propósito geral – ele não oferece nenhum caminho para quebrar nada além de fatoração ou problemas de logaritmo discreto e requer o paralelismo de computadores quânticos.)

A tarefa é incrivelmente complexa, mas a competição do NIST torna uma solução provável nos próximos anos. Com os atuais avanços conhecidos na computação quântica, é provável que chegue a tempo de proteger os segredos futuros – mas os segredos existentes protegidos pelo RSA-2048 ou mesmo pelo RSA-3072 podem se tornar vulneráveis ​​na próxima década. Tudo graças à computação quântica e ao algoritmo de 25 anos de Peter Shor.

Fonte: https://www.securityweek.com/promise-and-threat-quantum-computing