Hackers iranianos alegam ter derrubado energia em Israel
Ransomware atinge empresa de logística no Brasil
USP, UFRJ e UFMG sob ataque de negação de serviço
Pane de rede retardou produção na Volkswagen
Site da Prefeitura de Suzano (SP) está fora do ar
DDoS atinge subdomínio da NASA

Assine nossa newsletter Premium e ganhe acesso ao grupo de WhatsApp In_Cyber.
Conheça também a versão Básica

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

Share on linkedin
Share on twitter
Share on facebook

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