Computadores quânticos: o fim da criptografia?

Propaganda

A computação quântica é uma daquelas tecnologias que são tão misteriosas que o nome dos personagens de TV a deixa cair quando querem soar inteligentes.

A computação quântica como uma idéia existe há algum tempo - a possibilidade teórica foi originalmente introduzida por Yuri Manin e Richard Feynman em 1982. Nos últimos anos, no entanto, o campo tem se aproximado de forma preocupante da praticidade.

Empresas como Google e Microsoft, bem como agências governamentais como a NSA, vêm perseguindo febrilmente computadores quânticos há anos. Uma empresa chamada D-Wave produziu e vende dispositivos que (embora não sejam computadores adequados e possam apenas executam alguns algoritmos) exploram propriedades quânticas e são outra etapa incremental no caminho em direção a um totalmente Turing-complete O que é o teste de Turing e será vencido?O Teste de Turing visa determinar se as máquinas pensam. O programa Eugene Goostman realmente passou no teste de Turing ou os criadores simplesmente trapacearam? consulte Mais informação máquina quântica.

Não parece irracional dizer que podem ocorrer avanços que permitirão a construção do primeiro computador quântico em larga escala dentro de uma década.

Então, por que todo o interesse? Por que você deveria se importar? Os computadores ficam mais rápidos o tempo todo O que é a lei de Moore e o que isso tem a ver com você? [MakeUseOf explica]A má sorte não tem nada a ver com a Lei de Moore. Se essa é a associação que você teve, está confundindo-a com a Lei de Murphy. No entanto, você não estava muito longe porque a Lei de Moore e a Lei de Murphy ... consulte Mais informação - o que há de tão especial nos computadores quânticos?

Para explicar por que essas máquinas são tão importantes, teremos que dar um passo atrás e explorar exatamente o que são computadores quânticos e por que eles funcionam. Para começar, vamos falar sobre um conceito chamado "complexidade de tempo de execução".

O que é complexidade de tempo de execução?

Uma das grandes surpresas nos primeiros dias da ciência da computação foi a descoberta de que, se você tem um computador que resolve um problema de um certo tamanho em um certo período de tempo, dobrar a velocidade do computador não o deixa necessariamente resolver os problemas duas vezes mais grande.

Alguns algoritmos aumentam no tempo total de execução muito, muito rapidamente, à medida que o tamanho do problema aumenta - alguns algoritmos podem ser concluídos rapidamente dado 100 pontos de dados, mas concluir o algoritmo dado 1000 pontos de dados exigiria um computador do tamanho da Terra funcionando por um bilhão anos. A complexidade do tempo de execução é uma formalização dessa idéia: ela analisa a curva de velocidade com que a complexidade de um problema aumenta e usa o formato dessa curva para classificar o algoritmo.

Geralmente, essas classes de dificuldade são expressas como funções. Um algoritmo que fica proporcionalmente mais difícil quando o conjunto de dados está trabalhando aumenta (como uma função simples de contagem) é considerado uma função com uma complexidade de tempo de execução de "n " (como em, leva n unidades de tempo para processar n Os pontos de dados).

Como alternativa, pode ser chamado de "linear", porque quando você faz o gráfico, obtém uma linha reta. Outras funções podem ser n ^ 2 ou 2 ^ n ou n! (n fatorial). Estes são polinomiais e exponenciais. Nos dois últimos casos, os exponenciais crescem tão rapidamente que, em quase todos os casos, não podem ser resolvidos por nada, exceto exemplos muito triviais.

Complexidade de tempo de execução e criptografia

Se você está ouvindo essas coisas pela primeira vez e parece sem sentido e misterioso, vamos tentar fundamentar essa discussão. A complexidade do tempo de execução é fundamental para a criptografia, que se baseia em tornar a descriptografia muito mais fácil para pessoas que conhecem uma chave secreta do que para quem não conhece. Em um esquema criptográfico ideal, a descriptografia deve ser linear se você tiver a chave e 2 ^ k (onde k é o número de bits na chave), se você não

Em outras palavras, o melhor algoritmo para descriptografar a mensagem sem a chave deveria ser simplesmente adivinhar possíveis chaves, o que é intratável para chaves com apenas algumas centenas de bits.

Para criptografia de chave simétrica (na qual as duas partes têm a chance de trocar um segredo com segurança antes de iniciar a comunicação), isso é bastante fácil. Para criptografia assimétrica, é mais difícil.

A criptografia assimétrica, na qual as chaves de criptografia e descriptografia são diferentes e não podem ser facilmente calculadas uma da outra, é uma matemática muito mais difícil estrutura a ser implementada do que a criptografia simétrica, mas também é muito mais poderosa: a criptografia assimétrica permite que você tenha conversas privadas, mesmo com toques excessivos linhas! Ele também permite que você crie "assinaturas digitais" para verificar de quem veio uma mensagem e se ela não foi adulterada.

Essas são ferramentas poderosas e compõem a base da privacidade moderna: sem criptografia assimétrica, os usuários de dispositivos eletrônicos não teriam proteção confiável contra olhares indiscretos.

Como a criptografia assimétrica é mais difícil de construir do que simétrica, os esquemas de criptografia padrão em uso atualmente não são tão fortes como poderiam ser: o padrão de criptografia mais comum, o RSA, pode ser quebrado se você conseguir encontrar com eficiência os principais fatores de uma grande número. A boa notícia é que esse é um problema muito difícil.

O algoritmo mais conhecido para fatorar grandes números em seus primos componentes é chamado de peneira de campo numérico geral e possui uma complexidade de tempo de execução que cresce um pouco mais devagar que 2 ^ n. Como conseqüência, as chaves precisam ser cerca de dez vezes mais longas para fornecer segurança semelhante, algo que as pessoas normalmente toleram como custo para fazer negócios. A má notícia é que todo o campo de jogo muda quando os computadores quânticos são jogados na mistura.

Computadores quânticos: mudando o jogo de criptografia

Os computadores quânticos funcionam porque podem ter vários estados internos ao mesmo tempo, através de um fenômeno quântico chamado “superposição”. Isso significa que eles podem atacar diferentes partes de um problema simultaneamente, divididas em possíveis versões do universo. Eles também podem ser configurados de forma que os ramos que resolvem o problema acabem com a maior amplitude, de modo que, quando você abrir a caixa no O gato de Schrodinger, a versão do estado interno com o qual você provavelmente será apresentado é um gato de aparência presunçosa, segurando uma descriptografada mensagem.

Para mais informações sobre computadores quânticos, confira nosso artigo recente sobre o assunto Como funcionam os computadores ópticos e quânticos?A Era Exascale está chegando. Você sabe como os computadores ópticos e quânticos funcionam e essas novas tecnologias se tornarão o nosso futuro? consulte Mais informação !

O resultado disso é que os computadores quânticos não são linearmente mais rápidos, como são os computadores normais: obter duas, dez ou cem vezes mais rápido não ajuda muito quando se trata de criptografia convencional que você tem centenas de bilhões de vezes muito lento para processar. Os computadores quânticos suportam algoritmos com complexidades de tempo de execução de crescimento menor do que as possíveis de outra forma. É isso que torna os computadores quânticos fundamentalmente diferentes de outras futuras tecnologias computacionais, como computação de grafeno e memrister A mais recente tecnologia de computador que você precisa ver para acreditarConfira algumas das mais recentes tecnologias de computador que devem transformar o mundo da eletrônica e dos PCs nos próximos anos. consulte Mais informação .

Para um exemplo concreto, o algoritmo de Shor, que só pode ser executado em um computador quântico, pode levar em consideração grandes números em log (n) ^ 3 tempo, que é drasticamente melhor que o melhor ataque clássico. O uso da peneira de campo numérico geral para fatorar um número com 2048 bits leva cerca de 10 ^ 41 unidades de tempo, o que resulta em mais de um trilhão de trilhões de trilhões de trilhões. Usando o algoritmo de Shor, o mesmo problema leva apenas cerca de 1000 unidades de tempo.

O efeito fica mais pronunciado quanto mais longas as teclas. Esse é o poder dos computadores quânticos.

Não me entenda mal - os computadores quânticos têm muitos usos não-maus em potencial. Os computadores quânticos podem resolver com eficiência o problema do vendedor ambulante, permitindo que os pesquisadores construam redes de remessas mais eficientes e projetem melhores circuitos. Os computadores quânticos já têm usos poderosos em inteligência artificial.

Dito isso, o papel deles na criptografia será catastrófico. As tecnologias de criptografia que permitem que nosso mundo continue funcionando dependem da dificuldade do problema de fatoração de número inteiro. O RSA e os esquemas de criptografia relacionados são os que permitem confiar que você está no site certo, nos arquivos que o download não está repleto de malware e as pessoas não estão espionando sua navegação na Internet (se você estiver usando Tor).

A criptografia mantém sua conta bancária segura e protege a infraestrutura nuclear do mundo. Quando os computadores quânticos se tornam práticos, toda essa tecnologia para de funcionar. A primeira organização a desenvolver um computador quântico, se o mundo ainda trabalhar com as tecnologias que usamos hoje, estará em uma posição assustadoramente poderosa.

Então, o apocalipse quântico é inevitável? Existe algo que possamos fazer sobre isso? Como se vê... sim.

Criptografia Pós-Quantum

Existem várias classes de algoritmos de criptografia que, até onde sabemos, não são significativamente mais rápidos para resolver em um computador quântico. Elas são conhecidas coletivamente como criptografia pós-quântica e fornecem alguma esperança de que o mundo possa fazer a transição para sistemas de criptografia que permanecerão seguros em um mundo de criptografia quântica.

Os candidatos promissores incluem criptografia baseada em treliça, como Ring-Learning With Error, que deriva sua segurança de um sistema comprovadamente complexo problema de aprendizado de máquina e criptografia multivariada, que deriva sua segurança da dificuldade de resolver sistemas muito grandes de equações Você pode ler mais sobre este tópico no site Artigo da Wikipedia. Cuidado: muitas dessas coisas são complexas e você pode achar que seu conhecimento em matemática precisa ser aprimorado consideravelmente antes que você possa realmente descobrir os detalhes.

A conclusão de tudo isso é que os criptoquimicos pós-quantum são muito legais, mas também muito jovens. Eles precisam de mais trabalho para serem eficientes e práticos, e também para demonstrar que são seguros. A razão pela qual podemos confiar nos sistemas de criptografia é porque jogamos neles gênios clinicamente paranóicos suficientes por tempo suficiente que quaisquer deficiências óbvias já teriam sido descobertas até agora, e os pesquisadores provaram várias características que as tornam Forte.

A criptografia moderna depende da luz como desinfetante, e a maioria dos esquemas criptográficos pós-quânticos são simplesmente novos demais para confiar na segurança mundial. Eles estão chegando lá, porém, e com um pouco de sorte e alguma preparação, os especialistas em segurança podem concluir a troca antes que o primeiro computador quântico já entre em operação.

Se eles falharem, no entanto, as consequências podem ser terríveis. O pensamento de alguém com esse tipo de poder é perturbador, mesmo se você estiver otimista sobre as intenções deles. A questão de quem primeiro desenvolve um computador quântico funcional é uma questão que todos deveriam observar com muito cuidado à medida que avançamos na próxima década.

Você está preocupado com a insegurança da criptografia para computadores quânticos? Qual é a sua opinião? Compartilhe seus pensamentos nos comentários abaixo!

Créditos da imagem: Orbe binário Via Shutterstock