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

Paulo Brito
26/01/2019

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

 

Compartilhar:

Últimas Notícias

Parabéns, você já está cadastrado para receber diariamente a Newsletter do CISO Advisor

Por favor, verifique a sua caixa de e-mail: haverá uma mensagem do nosso sistema dando as instruções para a validação de seu cadastro. Siga as instruções contidas na mensagem e boa leitura. Se você não receber a mensagem entre em contato conosco pelo “Fale Conosco” no final da homepage.

ATENÇÃO: INCLUA [email protected] NOS CONTATOS DE EMAIL

(para a newsletter não cair no SPAM)