Criptografia: o que muda com a computação quântica – Parte 1

Muitas notícias sobre a computação quântica têm vindo acompanhadas de comentários sobre os riscos que ela representa para a criptografia. Afinal, ela é tão poderosa que significa o fim para a criptografia convencional? Há mesmo esse risco? Já existem soluções? Para obter as respostas entrevistamos o cientista Roberto Gallo, CEO da empresa Kryptus e agora presidente da Associação Brasileira das Indústrias de Material de Defesa e Segurança. Nesta entrevista, dividida em duas partes, ele explica tudo o que é fundamental para o entendimento dessa questão. Se ao invés de ler preferir escutar, clique no link abaixo e ouça a entrevista em podcast.

 

A criptografia

O CEO da Kryptus começa a entrevista explicando a criptografia:

[quote]A criptografia como um todo é baseada num conceito matemático – do qual não há provas -, de que existem certas contas que são fáceis de fazer num sentido e difíceis de fazer em outro – dado o tipo de computador que está fazendo as operações. Se considerarmos que nós somos o computador, é fácil fazer três elevado ao quadrado. Qualquer um faz isso. Então, exponenciação é trivial. Por outro lado, qual é a operação inversa dessa exponenciação? É a raiz quadrada. Mas se eu lhe perguntar qual é a raiz quadrada de sete? Ninguém faz de cabeça. Ou só os ‘iluminados’ fazem de cabeça. Porque isso exige método e isso demora. No mínimo demora muito.[/quote]

Rapidez num sentido. Mas não no outro…

[quote]Então esse é o modelo de computação humana, numa operação que é rápida num sentido, enquanto a inversa é muito difícil, muito lenta e para a qual às vezes nem se conhece um método eficiente. Mas se a gente pegar essa mesma operação de elevar ao quadrado e extrair raiz quadrada, e levar para uma calculadora de mesa, de celular ou para um computador, tanto a operação direta quanto a inversa são rápidas. Por mais antiga que seja a calculadora, ela vai calcular a raiz quadrada de qualquer coisa. Porque por paradigma digital normal da Máquina de Turing, calcular raiz quadrada é um problema que a gente chama de ‘subexponencial’. É um problema polinomial: com um certo número de passos você chega num resultado com quantas casas de precisão você quiser.[/quote]

Problema polinomial

[quote]A ideia do polinomial e não-polinomial é a seguinte: por exemplo se vou calcular a raiz quadrada de um número de um dígito, é [necessário] um certo número de passos. Se eu vou calcular a raiz quadrada de um número de dois dígitos, o número de passos não vai crescer muito. Vai crescer, digamos, linearmente ou ao quadrado, ao cubo. Não vai crescer exponencialmente. É um problema em cuja solução o número de passos não explode exponencialmente. Ele pode ser o número passos ao quadrado, ou triplicado, quadruplicado. É isso que a gente chama de polinomial. O que é diferente de ter um total de passos que é um número elevado a sete por exemplo. Aí cresceu exponencialmente.[/quote]

[quote]Voltando ao problema da raiz quadrada e da exponenciação, para o humano ele é facil num sentido e dificil no outro. Mas se você colocar esse problema num PC ele é trivial nos dois sentidos. Porém, existem certos problemas – por exemplo fatoração de números ou multiplicar dois números – que são triviais num sentido e difíceis no outro tanto para nós quanto para o computador. Se eu pegar dois números grandes ou primos é fácil multiplicar. Fatorar não. Fatorar é difícil, toma muito tempo. Não é impóssível. Toma um tempo exponencial ou explosivo. Para o computador normal também é um problema dificil. Não é só para o humano.[/quote]

[box type=”info” style=”rounded” border=”full”]Fatorar significa decompor um número em fatores primos, isto é, representar um número por meio da multiplicação de números primos.[/box]

Velocidade quântica

[quote]O que diferencia o computador normal de um ser humano fazendo contas de cabeça? É o rastreio das coisas que ele faz, num número infindável de operações, e executar algoritmos também de forma infindável. Na prática, um humano muito bem treinado consegue rodar o famoso Método de Newton para extrair raiz quadrada. Mas um humano típico não faz isso. Agora, quando você vai para o computador quântico, andamos uma casinha para a frente. Multiplicar dois números continua sendo fácil para tanto quanto é para o humano ou para o computador convencional. Mas fatorar, para ele, é trivial. Do mesmo modo que para os outros computadores extrair raiz quadrada é trivial, para ele fatorar é trivial.[/quote]

[quote]Voltando: toda criptografia é baseada na ideia de que existem funções onde calcular a direta é fácil e a inversa difícil. Essa é a base da criptografia. Hoje, os problemas matemáticos nos quais baseamos a criptografia – que são principalmente a dificuldade de fatoração de números e o logaritmo discreto – têm a direta fácil, porque multiplicar dois números é fácil, mas fatorar é difícil. Tal como para o computador normal exponenciar dois números é fácil, mas é difícil tirar o log discreto disso. Só que para o computador quântico isso tudo é trivial.

Continuam existindo problemas que para o computador quântico são dificeis, ‘intratáveis’. Por um acaso, os problemas de log discreto e de fatoração aparentemente são solvíveis em tempo aceitável.[/quote]

Leia na continuação: como a criptografia responde a esse desafio

 

Criptografia: o que muda com a computação quântica – Parte 2

Esta é a parte 2 de “Criptografia: o que muda com a computação quântica“, uma entrevista com Roberto Gallo, CEO da empresa Kryptus e atual presidente da Associação Brasileira das Indústrias de Materiais de Defesa e Segurança (Abimde). Na primeira parte, ele explicou os fundamentos da criptografia, os problemas nos quais ela se baseia e aqueles que o computador quântico já consegue resolver – exigindo portanto atualização da criptografia. Nesta parte, o CEO da Kryptus explica as soluções que a criptografia já tem para resistir à computação quântica.

Se preferir, ouça a entrevista clicando no link do podcast abaixo.

 

Como os criptólogos respondem a esse desafio?

[quote]Dos algoritmos criptográficos em uso, nem todos são afetados (ou são pouco afetados) pelos algoritmos quânticos como o AES, por exemplo, que é o simétrico. Há vários casos em que se usa só simétricos. Por exemplo aquele password do seu WiFi é simétrico. Isso não vai ser afetado. Serão afetados por exemplo os certificados digitais, que utilizam RSA ou curvas elípticas. São algoritmos baseados em logaritmo discreto e fatoração. Esses serão afetados. Em geral – não é regra – os simétricos mais usados não são afetados pela computação quântica. Mas em geral os assimétricos são afetados.

Mas existem outras famílias de algoritmos já conhecidos, embora não-padronizados, que até onde se sabe não são afetados pelo computador quântico. Exemplos de algoritmos que não são afetados: são aqueles baseados em códigos, que é um tipo diferente de problema. Os algoritmos chamados de Lattice e os algoritmos chamados LWE (de learn with errors). São coisas mais abstratas, mas são algoritmos nos quais não se conhece uma vantagem importante do computador quântico.[/quote]

Por que novos algoritmos ainda não são adotados

[quote]O problema é que demora muito tempo para se fazer a rolagem de um algoritmo. Uma vez padronizado, ele pode ser implementado. Por que não se usa então os pós-quânticos de uma vez? Porque o tamanho de chavesque se precisa é grande demais. Para dispositivos pequenos, às vezes isso é um problema. Dá overhead. Quando falamos das chaves de curvas elípticas, elas têm 32 bytes, 64 bytes, coisa pequena. Mas a chave de um algoritmo de código são quilobytes. Pode não ser um problema para um celular ou para um computador. Mas dependendo do dispositvo, pode ser um problema. Você onera o dispositivo. [/quote]

[quote]Então, não é que o computador quântico começou a quebrar a criptografia. É que alguém teve a ideia de fazer um algoritmo que poderia resolver o problema de fatoração. Em tese, resolver um problema de fatoração. Então, o entendimento do poder do computador quântico também evolui. Há uma notícia dizendo que o computador quântico não quebra o RSA como se pensava. O fato é que tem muito algoritmo para fins em geral, a serem criados para o computador quântico. Entender o poder do computador quântico não é trivial. Ele tem um outro paradigma e isso está no começo. Pode ser que apareçam outros breakthroughs, que levem à vantagem e à quebra de um algoritmo de códigos. Pode ser. É que hoje na computação quântica ainda não existe esse algoritmo.[/quote]

A questão do comprimento da chave é uma questão relevante inclusive para o computador quântico?

[quote]Sim, também. Seria só trocar as chaves? Em tese sim. Mas determinadas coisas que a gente faz o sigilo caduca muito à frente no tempo. Nos caso de documentos de governo por exemplo são décadas. Se você cifra uma coisa hoje, você precisa prever se lá no futuro aquele algoritmo vai continuar seguro . Então não adianta pensar o algoritmo com as ferramentas que podem quebrar ele agora. Precisa é pensar em quanto tempo a informação protegida permanecerá relevante. [/quote]

[quote]O fato de termos o computador quântico não é propriamente relevante. A pergunta é: haverá um viável daqui a dez, daqui vinte anos? Tudo indica que sim, haverá. E aí voltamos à questão do tamanho de chave: existe mais de um tipo de computador quântico. Existe o computador quântico de uso geral, que pode fazer qualquer tipo de coisa. A dificuldade dele é o número de bits que processa simultaneamente.  Nos computadores normais falamos de 32 bits, 64 bits e nos quânticos falamos de Qbits. Os computadores são de poucas dezenas de Qbits – 15, 16 Qbits. O que se sabe é que para quebrar criptografia é preciso um número de Qbits do tamanho da chave.[/quote]

[quote]Então, ao se falar de curvas elípticas de 256 bits, precisariamos de um computador de 256 Qbits. Aparentemente é uma coisa que ainda não existe. E o problema de se manter vários Qbits funcionando simultaneamente parece que é muito difícil. Ao mesmo tempo que isso nos dá uma certa tranquilidade, é um problema na física.[/quote]

Há diferentes computadores quânticos

[quote]Existe também um outro tipo de computador, que alguns chamam de quântico e outros não,  que é o Computador de Aleação. Ele não consegue fazer qualquer conta. Serve para alguns problemas de otimização. Por exemplo, otimizar processos químicos. Porque para que seja utilizado é preciso haver uma função matemática que ele calcula e vê, por exemplo, o melhor rendimento. Esses computadores chegam a ter 2 mil Qbits. O problema é que não se conhece um algoritmo para computadores de aleação que gerem vantagem na parte de criptografia.

Se alguém descobrir um algoritmo que sirva para cripto, aí já se tem um computador de 2 mil Qbits e aí será um problema. Resumindo: a criptografia se baseia em certas funções que são fáceis num sentido e dificeis no outro. O fácil ou difícil depende do paradigma computacional. Fazer de cabeça é uma coisa. Em computador convencional, outra. Em computador quântico de uso geral, outra. E no computador de aleação, outra ainda. ‘Difícil’ sempre depende do algoritmo que criou. Pode ser até que a criptografia convencional seja quebrada por um avanço em algoritmos, como os problemas convencionais. Só que não se tem a prova matemática ainda. Por outro lado, se vê que os computadores quânticos estão evoluindo em número de Qbits de forma progressiva e portanto deve-se ser precavido e ter uma infraestrutura de troca de algoritmos. Para os algoritmos que a gente chama de pós-quânticos.

Porque eles são pensados para um mundo que já tem computação quântica. Mesmo assim, existem algoritmos perfeitamente viáveis [para suportá-la].[/quote]