A computação quântica não matará a estrela criptográfica

Início » Cibersegurança » A computação quântica não matará a estrela criptográfica

Read Time:13 Minute, 48 Second

Foi no final de 2017 quando descobri que pessoas estranhas ao mundo criptográfico ou à física começaram a se interessar pela computação quântica . Parece o próximo grande hype, com pessoas fazendo diferentes tipos de expectativas fabulosas e grandes empresas de TI lutando uma batalha para liderar o progresso tanto na área científica quanto na de marketing.

A computação quântica é um avanço muito promissor na ciência da computação que foi inicialmente sugerido por Richard Feynman em sua palestra de 1959 “ Há muito espaço no fundo ”. Ele observou que “os átomos em pequena escala se comportam como nada em grande escala, pois satisfazem as leis da mecânica quântica. Então, conforme descemos e mexemos com os átomos lá embaixo, estamos trabalhando com leis diferentes e podemos esperar fazer coisas diferentes ”.

Feynman voltou à computação quântica em seu artigo de 1981, ” Simulando física com computadores “, onde considerou os computadores quânticos como simuladores quânticos universais .

Muitas outras pessoas colocaram seus cérebros e trabalharam na computação quântica. Para uma lista detalhada, você pode ver uma boa linha do tempo na Wikipedia .

Mas foi em 1994 quando o mundo conheceu uma aplicação de computação quântica que atrairia um interesse sem precedentes na tecnologia . Peter Shor encontrou um algoritmo que permitiria a um computador quântico resolver o log discreto e o problema de fatoração em tempo polinomial.

algoritmos para log discreto de computação quântica e fatoração

Em outras palavras, se um computador quântico prático existisse, nossa criptografia de chave pública atual seria facilmente quebrada .

Este artigo irá explicar alguns fundamentos da criptografia de chave pública e computação quântica para entender por que o trabalho de Shor é relevante. Também mostrará por que o algoritmo de Shor não elimina a criptografia de chave pública, a estrela de criptografia.

Conteúdo

Introdução à criptografia de chave pública 👨‍💻

Veja Alice e Bob. Eles costumavam enviar mensagens privadas um para o outro, mas de repente Eve apareceu escutando qualquer conversa ao redor. Agora, Bob deseja enviar uma nova mensagem para Alice. Como ele seria capaz de transmitir sua mensagem com segurança?

Com a criptografia simétrica tradicional, Alice e Bob precisam chegar a um acordo sobre uma chave que permita criptografar e descriptografar a mensagem. No entanto, Bob terá dificuldade em encontrar uma maneira de enviar a Alice a chave que ele usou para criptografar sua mensagem sem que Eva saiba a chave também. E se Eva souber a chave… ela poderá ler a carta!

Entre na criptografia pública. Ele foi inicialmente projetado para resolver a necessidade de acordo sobre uma chave secreta . Isso foi conseguido por Whitfield Diffie e Martin Hellman em 1976. Mais tarde, em 1978 , Rivest , Shamir e Adleman (RSA) encontraram uma maneira de criptografar e assinar mensagens.

Em um nível muito alto, você pode pensar na criptografia de chave pública da seguinte maneira: enquanto um criptosistema simétrico tem uma chave que permite a criptografia e descriptografia, um criptosistema de chave pública é baseado em um par de chaves matematicamente relacionadas:

O que uma chave criptografa só pode ser descriptografado pela outra e vice-versa.

Veja este exemplo:

Criação de chave

Alice cria um par de chaves: A1 e A2
Alice mantém A1 em segredo. Chamaremos isso de chave privada (Pv) .
Alice torna A2 público enviando para Bob ou postando em algum lugar. Não há problema em distribuí-lo abertamente, pois não revela nada sobre A1. Chamaremos isso de chave pública (Pb) .

Encriptação

Bob deseja enviar uma mensagem privada para Alice.
Bob criptografa a mensagem usando a chave pública de Alice, Pb .
Alice recebe a mensagem criptografada e a descriptografa com sua chave privada, Pv(lembre-se: o que uma chave criptografa só pode ser descriptografado pela outra e vice-versa ).
Eva não pode ler a mensagem de texto não criptografado, pois ela não tem acesso à chave privada de Alice, Pv .

A criptografia de chave pública também permite um aplicativo extremamente útil: assinaturas digitais. Funciona assim:

Alice deseja assinar uma mensagem para que qualquer pessoa possa verificar se ela foi preparada por ela e se não foi adulterada.
Alice criptografa a mensagem usando sua chave privada, Pv . Chamaremos isso de Assinatura .
Alice envia a Bob a mensagem de texto não criptografado e a assinatura .
Bob descriptografa a assinatura usando a chave pública de Alice, Pb .
Se a mensagem de texto não criptografado e a descriptografia da assinatura forem idênticas, Bob pode ter certeza de que só poderia ser preparada por Alice usando sua chave privada, Pv .

Os protocolos da vida real usam diferentes técnicas para melhorar a eficiência e a segurança, mas, em resumo, funcionam como este exemplo.

Fundamentos matemáticos 🧠

Até agora, as implementações práticas da criptografia de chave pública são baseadas em alguns problemas difíceis conhecidos: Logaritmos discretos e fatoração .

Esses problemas tornam-se exponencialmente mais difíceis à medida que o tamanho dos números envolvidos aumenta. Por exemplo, embora a fatoração de 35 seja trivial (5 × 7), a fatoração de um número de 1024 bits como usado no RSA (chamado módulo RSA) ainda não foi alcançada. É por isso que às vezes são chamadas de “funções de mão única”.

Logaritmo discreto

Logaritmo é a operação que dá como resultado o expoente que precisa ser aplicado a um determinado número, denominado base, para se obter algum número . Por exemplo, uma vez que 10 ^ 2 = 100, temos que o logaritmo na base 10 de 100 é 2.

Neste exemplo, 10 é chamado de base, 100 é chamado de anti-logaritmo e 2 é chamado de logaritmo.

A palavra “ discreto ” antes do logaritmo significa que a operação é definida em um campo numérico de tamanho finito, ao invés do campo de números reais , que é infinito . Existem diferentes campos numéricos para definir a operação de logaritmo discreto. Os mais comumente usados são “Inteiros módulo a primo” e “Curvas elípticas sobre inteiros módulo a primo”.

O cálculo de um logaritmo discreto em certos campos numéricos torna-se exponencialmente mais difícil à medida que o anti-logaritmo cresce.

Consulte o Anexo I, Diffie-Hellman para uma explicação detalhada do protocolo de troca de chaves de Diffie-Hellman , que é baseado em logs discretos.

Fatoração

Fatorar significa obter os fatores primos que formam qualquer número . Todos os números podem ser obtidos multiplicando um ou vários números primos. Portanto, fatorar 15 é saber que ele pode ser construído multiplicando 3 × 5.

Como dissemos antes, a fatoração torna-se exponencialmente mais difícil à medida que o número a ser fatorado aumenta.

Consulte o Anexo I , RSA para uma explicação detalhada do criptosistema de chave pública da RSA , que é baseado no problema de fatoração.

O que significa “exponencialmente mais difícil”?

A Figura 1 representa graficamente o tempo necessário em um teste de amostra para fatorar um número construído pela multiplicação de dois números primos aleatórios. Você pode ver facilmente que, à medida que o número a ser fatorado aumenta, o tempo necessário para fatorá-lo fica maior de forma acelerada . As duas séries mostram o esforço usando dois algoritmos de fatoração diferentes.

Usamos escalas logarítmicas (ou simplesmente escalas logarítmicas ) para representar gráficos exponenciais de uma forma que nos permite perceber detalhes ao longo de todo o conjunto de dados, como na Figura 2 , que mostra os mesmos dados em um formato (talvez) menos impactante visualmente, mas permitindo para fazer algumas estimativas .

Observe como o eixo vertical difere de um gráfico normal. Em um gráfico normal teríamos um crescimento proporcional de valores como na Figura 1 (0, 500, 1000, 1500, …), onde a cada 500 segundos são representados com o mesmo espaço vertical. Na Figura 2 , ao contrário, os valores aumentam de acordo com o incremento de um expoente (10 ^-2 , 10 ^-1 , 10 ⁰ , 10 ¹ , 10 ² , 10 ³ , …) e assim os valores de a na faixa de milissegundos são representado usando o mesmo espaço que os valores na faixa de milhares de segundos ou milhões de segundos.

Podemos adivinhar aproximadamente o quão difícil é fatorar um grande número usando uma escala logarítmica e alguns dados :

O maior módulo RSA fatorado publicamente (2009) na data desta redação (2020) tinha 768 bits de comprimento e exigia um esforço equivalente a 1500 anos em um processador AMD Opteron de 2,2 GHz de núcleo único.
Os autores desta conquista afirmam que fatorar um módulo RSA de 1024 bits exigiria 1000 vezes esse esforço.
Os FLOPS públicos do núcleo AMD Opteron 2427 de 2,2 GHz e diferentes supercomputadores
O esforço estimado para fatorar um módulo RSA de 2048 bits é 2 ^ 32 vezes mais difícil do que um módulo de 1024 bits.

Se agruparmos tudo isso em uma escala de log, teremos a Figura 3 .

Figura 3: Estimativa aproximada do tempo necessário para fatorar grandes módulos RSA

A potência combinada dos 500 supercomputadores mais poderosos do mundo precisaria da ordem de 10.000 anos para fatorar um módulo RSA de 2.048 bits . Portanto, seria necessário lançar seu programa de factoring durante o final da Idade do Gelo para obter o resultado hoje.

O tamanho da chave padrão atual usado pelo OpenSSH é 3072 bits, o que exigiria, aproximadamente, a idade do universo a ser fatorado pelo mesmo cluster de supercomputadores . Imagine-se com aquele cluster além do big bang.

Um módulo RSA de 4096 bits precisaria de aproximadamente um milhão de vezes a idade do universo para ser fatorado pelo mesmo cluster.

É assim que é difícil quebrar a criptografia de chave pública, quando usada corretamente . Existem formas alternativas de atacar a criptografia de chave pública e são baseadas principalmente em implementações deficientes. Mas isso está fora do escopo deste artigo.

Computação quântica 💻

A principal característica dos computadores quânticos é que eles são baseados em bits quânticos, qubits. Na computação clássica, operamos com bits e eles têm, a qualquer momento, um único valor, 0 ou 1. Ao contrário, os qubits são especiais porque fazem uso de certos fenômenos quânticos como a superposição e o emaranhamento .

Sobreposição

Talvez você tenha ouvido falar do gato de Schrödinger , um “gato quântico” imaginário que está morto e vivo simultaneamente até que alguém o observe. As partículas quânticas em superposição se comportam como se estivessem em diferentes estados simultaneamente e só obtêm um único estado final quando observadas ou medidas . Diz-se que eles “entram em colapso” para um estado específico.

Qubits são como o gato de Schrödinger: enquanto em superposição, eles se comportam como se estivessem no estado 0 E 1 SIMULTANEAMENTE. Somente quando o medimos, o qubit entra em colapso para um único estado. Antes disso, podemos calcular a probabilidade do resultado, mas não podemos ter certeza de qual será.

Emaranhamento

Graças ao emaranhamento, duas partículas quânticas sempre terão uma correlação entre seus estados . Considere, por exemplo, dois fótons emaranhados. Enquanto em superposição, não podemos saber qual spin (↑ ou ↓) eles mostrarão quando medidos. Mas uma vez que medimos um dos fótons, sabemos que o outro colapsou para o spin oposto. Se o fóton A for medido com spin ↑, sabemos que o fóton B colapsou para spin ↓.

Universos paralelos

Voltando ao gato de Schrödinger, uma das interpretações da estranheza da física quântica é o modelo de “ muitos mundos ” . Esta interpretação considera que, quando o gato em superposição é observado, o mundo “se divide” com cada estado possível do gato. Conseqüentemente, o mundo anterior gera dois ramos, um mundo onde o observador vê um gato vivo e outro mundo onde o observador vê um gato morto.

Há um bom curta-metragem que explora essa ideia de emaranhamento em múltiplos universos: One Minute Time Machine . Eu quero estragar tudo. Basta dar uma olhada e rir.https://www.youtube-nocookie.com/embed/1aTeGOeOsWs?controls=0&rel=0&showinfo=0&modestbranding=1&autoplay=1&autohide=1&loop=1

Por que os computadores quânticos são diferentes?

Uma maneira de pensar sobre os computadores quânticos é que, aproveitando a superposição e o emaranhamento, eles podem manipular vários estados ao mesmo tempo. Considere um computador clássico operando com bits. Ele só pode estar em um único estado em qualquer momento e seus n bits terão um único valor. Ao contrário, um computador quântico com n qubits estará em estados simultaneamente e será capaz de operar em todos esses estados DE UMA VEZ .

Isso às vezes é comparado à computação paralela. Isso não é muito preciso e há alguns argumentos contra essa comparação. De qualquer forma, a ideia básica é que um computador quântico pode fornecer uma aceleração exponencial ao atacar alguns problemas complexos .

O objetivo de um algoritmo quântico é transportar operações em estados quânticos de tal forma que a medição dos qubits provavelmente nos fornecerá uma resposta para nosso problema . E essa “probabilidade” é administrada brincando com superposição, emaranhamento, interferência e probabilidades.

Consulte o Anexo II para mais alguns detalhes sobre os fundamentos da computação quântica.

Algoritmo de Shor

Peter Shor encontrou uma maneira de calcular logaritmos discretos e números inteiros de fator de uma forma que não cresça exponencialmente com o tamanho da variável. O algoritmo que ele projetou é capaz de resolver esses problemas no que é chamado de “ tempo polinomial ”. Isto é, se o tamanho em bits do anti-logaritmo ou da chave RSA for n , a complexidade de calcular o logaritmo discreto ou fatorar a chave estaria na faixa de n elevado a 3 usando o algoritmo de Shor, em vez de x elevado a n usando algoritmos clássicos, que é uma função exponencial que cresce muito, muito mais rápido .

Isso significa, por exemplo, que quebrar uma chave RSA de 4096 bits pode levar minutos, horas ou dias, em vez de várias vezes a idade do universo.

Consulte o Anexo I , algoritmo de Shor, para uma explicação mais detalhada sobre como ele funciona.

Criptografia pós-quântica (ou por que quantum não mata a estrela criptográfica) ⭐️

Embora o algoritmo de Shor possa quebrar criptossistemas baseados em log discreto e fatoração, sua implementação requer um computador quântico com um grande número de qubits. Não há previsões precisas sobre quando existirá um computador quântico grande o suficiente para quebrar os criptosistemas de chave pública atuais, mas as expectativas mais próximas estimam a década de 2030 para esse evento .

Enquanto isso, pesquisadores e órgãos de padronização estão trabalhando na chamada “criptografia pós-quântica”. Ou seja, criptosistemas de chave pública que podem ser executados em computadores clássicos, mas não podem ser quebrados por computadores quânticos . Você pode encontrar mais informações sobre criptografia pós-quântica e os esforços de padronização nos seguintes links:

Padronização de criptografia pós-quântica por NIST
Grupo de Especificação da Indústria em Criptografia Quantum Safe (ISG QSC) por ETSI
Comunidade e conferência PQCrypto .
EU’s PQCrypto project

Espera-se que os esforços de PQ forneçam novos padrões no início da década de 2020, então esperamos que tenhamos alguns anos para nos adaptar e migrar dos criptossistemas de chave pública atuais para a nova criptografia de chave pública pós-quântica .

Enquanto isso, você deve se preocupar com quanto tempo seus dados e assinaturas criptografados devem permanecer protegidos. Isso dependerá muito do caso de uso.