Ninguém sabe quando, mas as máquinas quânticas que irão ameaçar a criptografia estão prestes a chegar. É assim que os investigadores utilizam a mecânica quântica para decifrar grandes números inteiros na criptografia assimétrica.
Por Matthew Tyson
A computação quântica ainda habita o espaço nebuloso entre a aplicação prática e a especulação teórica, mas está cada vez mais próxima da utilização no mundo real. Um dos casos de utilização mais interessante para os computadores quânticos é a criptografia moderna da Internet.
Computação quântica e cúbitos
O nome computação quântica vem do facto de se basear nas propriedades das partículas subatómicas, governadas por leis que parecem estranhas. Em particular, os computadores quânticos utilizam cúbitos (bits quânticos) em vez dos dígitos binários (bits) que conhecemos dos sistemas informáticos tradicionais.
Os cúbitos são probabilísticos por natureza, enquanto que os bits são determinísticos. Um bit acaba por se resumir a um interruptor físico, embora muito pequeno, medido num punhado de nanómetros. Os bits são binários: ligado ou desligado, verdadeiro ou falso, 0 ou 1.
Este não é o caso dos cúbitos.
A base física de um cúbito pode consistir em muitos fenómenos, tais como o spin de um eletrão ou a polarização de fotões. Este é um assunto fascinante: o reino das equações lineares que fazem a ponte entre a imaginação e a realidade. A mecânica quântica é considerada uma interpretação de uma realidade subjacente, em vez de uma descrição, e abriga a uma intensa complexidade computacional.
O estado de um cúbito é descrito como uma sobreposição linear dos dois estados possíveis. Uma vez observado, o estado é resolvido para verdadeiro ou falso. Contudo, o mesmo input não se resolverá necessariamente para o mesmo output, e quando não observado o estado só pode ser descrito em termos probabilísticos.
Do ponto de vista da física clássica, o que é ainda mais surpreendente é que os cubitos de um computador quântico podem conter vários estados simultaneamente. Quando um computador recolhe amostras de um cubito para determinar o seu estado, resolve-se num único ou/ou (conhecido como colapso por função de onda).
Computação quântica em criptografia
Tudo isto é bastante interessante de um ponto de vista científico e filosófico. Por exemplo, a funcionalidade dos computadores quânticos verifica o efeito da observação sobre as partículas e sugere que Deus joga de facto dados com o universo. Mas estamos aqui preocupados com os aspetos práticos do poder crescente da computação quântica na nossa vida quotidiana. Nos próximos anos, é provável que o impacto mais profundo seja na criptografia.
A via mais conhecida da computação quântica para a criptografia é um avanço teórico que ocorreu em 1994: o algoritmo de Shorts. Em teoria, este algoritmo demonstrou a capacidade de uma máquina de Turing quântica para resolver eficazmente uma classe de problemas que eram intratáveis com os computadores tradicionais: factoring de grandes inteiros.
Se estiver familiarizado com algoritmos de criptosistemas assimétricos como Diffie-Hellman e RSA, sabe que estes se baseiam na dificuldade de resolver fatores de grande número. Mas e se a computação quântica resolver isso?
Decifração de inteiros grandes com mecânica quântica
O algoritmo de Shor e um punhado de outros algoritmos aproveitam a mecânica quântica para quebrar as funções unidirecionais no coração da criptografia assimétrica. O cálculo quântico adiabático também tem sido utilizado para atacar a factorização.
O Shor’s e outros algoritmos dependem da capacidade de o computador quântico habitar uma multiplicidade de estados em virtude dos cúbitos. Em seguida, recolhem amostras desses cúbitos (que colapsam o seu estado) de uma forma que permite um elevado grau de probabilidade de amostragem. Essencialmente, traduzimos a questão “Quais são os fatores para um dado número?” para o mundo misterioso do invisível, onde as propriedades das partículas podem existir em múltiplos estados. Por fim, questionamos essas propriedades para obter a resposta mais provável (sim, isto funciona realmente).
O maior número de fatores pelo algoritmo de Shor’s é 21. O cálculo quântico adiabático teve um sucesso de 143 fatores.
Estes algoritmos são sofisticados e impressionantes, mas até agora os seus números são insignificantes. A norma RSA atual é 2048 bits, que é de 617 dígitos. No entanto, ao atacar o número 143, os investigadores revelaram involuntariamente uma abordagem que permite números maiores, pelo menos em teoria. Um exemplo é 56.153, que é ainda um número relativamente pequeno em comparação com o que seria necessário para comprometer os sistemas de criptos do mundo real. Também depende de um truque redutor que não pode ser usado para todos os números.
A ameaça à infraestrutura de segurança da web
O que sabemos por agora é que os aspetos fundamentais do ataque quântico aos algoritmos assimétricos estão a ser eliminados. A que velocidade avançará a tecnologia ao ponto de se poder aproximar de números significativamente mais elevados?
Curiosamente, os algoritmos simétricos que usamos todos os dias não são terrivelmente vulneráveis aos algoritmos quânticos. O algoritmo de Grover é o que se aplica. É incapaz, mesmo em teoria, de reduzir o tempo necessário para atacar estes algoritmos muito mais do que os algoritmos clássicos, desde que sejam utilizadas chaves de 256 bits.
No entanto, a maioria das comunicações seguras simétricas estabelecem as suas chaves através de trocas assimétricas. Por conseguinte, a maior parte do tráfego da Web atual é vulnerável a ataques avançados de computação quântica. Se um atacante pode descobrir a chave estabelecida no início de uma interação, a encriptação simétrica é inútil.
Assim, a ameaça à infraestrutura de segurança da web é real. Pensemos por um momento sobre a dinâmica em jogo. A primeira coisa a considerar é a economia e o acesso. Neste momento, apenas organizações com muito dinheiro se podem dar ao luxo de mexer nestas coisas. A IBM, a Google e os cientistas de investigação da China estão a lutar pela liderança na produção de sistemas viáveis, juntamente com uma série de esforços universitários. Nos bastidores, agências governamentais tais como a Agência de Segurança Nacional dos EUA não estão sentadas de braços cruzados. Na realidade, a NSA tem a sua própria opinião sobre a questão da criptografia pública e da computação quântica.
A evolução da segurança com vista à computação quântica
É pouco provável que os atores de pequena escala alcancem capacidades de computação quântica suficientes para atacar chaves assimétricas modernas até muito depois de as grandes instituições o terem feito. Isto significa que estamos perante um longo período de tempo em que a infraestrutura de segurança pode evoluir em resposta à dinâmica da computação quântica.
Ninguém sabe quando aparecerão máquinas quânticas verdadeiramente criptográficas, mas parece provável que apareçam. Dois parâmetros para compreender a questão são o número de cubitos num sistema e a longevidade desses côvados.
Os cúbitos estão sujeitos ao que se chama decorrência. A entropia retira sempre os delicados conjuntos de eletrões e fotões. O problema é que tanto o número como a longevidade dos cúbitos são difíceis de quantificar. Quantos cúbitos são necessários para um ataque prático a uma chave RSA 2048? Uns dizem dezenas, outros dizem milhões. Quanta coerência é necessária? Alguns dizem centenas de nanossegundos, outros dizem minutos.
E tudo isto pode ser invertido por técnicas como o uso enganoso de algoritmos de pré-processamento acima mencionados. Quem sabe que engenhoso académico está agora mesmo a conceber uma nova abordagem. Aqueles que racharam 143 numa máquina quântica só dois anos mais tarde se aperceberam que também tinham rachado 56.153.
Criptografia pós-quantum
Todas as estradas levam a um mundo pós-quântico, e muitas pessoas já estão a trabalhar nele. O Instituto Nacional de Normas e Tecnologia dos EUA está a realizar concursos para desenvolver algoritmos quantum-resistentes. Alguns destes esforços estão a dar resultados.
Em suma, podemos dizer que a ameaça quântica à criptografia é real, com base em resultados cada vez mais reais. Mas por agora, é mais do que compensado por forças compensatórias. Podemos eventualmente ter de nos despedir de alguns dos nossos antigos e queridos algoritmos, mas os novos tomarão o seu lugar. Será uma dança interessante de observar durante a próxima década.