Os cinco universos escondidos por trás de cada senha que você digita

Toda vez que você faz login no banco, compra algo pela internet ou simplesmente vê aquele cadeado ao lado do endereço do site, está confiando em uma promessa matemática que ninguém jamais conseguiu provar. Não é uma falha de engenharia nem um segredo mal guardado — é uma lacuna na própria matemática que sustenta a criptografia moderna. Cientistas da computação sabem, com desconforto, que toda a segurança digital repousa sobre uma suposição que pode ser verdadeira, mas que também pode, em princípio, ser falsa.

Essa suposição tem nome: a existência de “funções de mão única” (ou “funções unidirecionais”), operações fáceis de fazer em um sentido e — supostamente — quase impossíveis de desfazer no sentido contrário. Toda vez que você usa uma senha, faz uma transferência bancária ou acessa um site com HTTPS, está apostando que esse tipo de função realmente existe. O problema é que essa aposta nunca foi comprovada. Em 1995, o cientista da computação Russell Impagliazzo, da Universidade da Califórnia em San Diego, decidiu levar essa incerteza a sério e organizou as possibilidades em uma espécie de mapa de universos paralelos — cinco cenários hipotéticos e mutuamente excludentes sobre como a computação realmente funciona por baixo do capô. Um deles é o mundo em que, supostamente, vivemos. Só não sabemos provar qual.

Este artigo explica o que são essas funções, por que ninguém consegue confirmar sua existência e o que os “cinco mundos” de Impagliazzo revelam sobre os alicerces — surpreendentemente frágeis — de tudo o que chamamos de segurança digital.

O truque que sustenta a internet

Uma função de mão única funciona como uma porta giratória: fácil de atravessar em uma direção, praticamente impossível de atravessar de volta. O exemplo clássico é a multiplicação de números primos grandes. Pegue dois números primos enormes — cada um com centenas de dígitos — e multiplique-os. Qualquer computador faz essa conta em uma fração de segundo. Agora inverta o problema: dado apenas o resultado dessa multiplicação, tente descobrir quais eram os dois primos originais. Não existe, até hoje, nenhum método conhecido que faça isso rapidamente para números grandes o suficiente. É exatamente esse desequilíbrio — fácil multiplicar, “difícil” fatorar de volta — que sustenta boa parte da criptografia de chave pública usada para proteger e-mails, senhas e transações bancárias.

A palavra-chave da frase anterior é “supostamente”. Ninguém provou matematicamente que fatorar números grandes é, de fato, um problema difícil para qualquer computador, em qualquer método possível, para sempre. O que existe é um histórico de décadas de tentativas fracassadas de encontrar um atalho rápido — o que é uma evidência prática forte, mas não uma demonstração matemática. Como resumiu o cientista da computação Rafael Pass, da Cornell Tech, à revista Quanta Magazine, “se as funções de mão única existem, sem sombra de dúvida, é o problema mais importante da criptografia” — e essa existência continua sendo uma conjectura, não um teorema.

Cinco universos, uma pergunta sem resposta

Foi para organizar essa incerteza que Impagliazzo escreveu, em 1995, o artigo “A Personal View of Average-Case Complexity” (“Uma visão pessoal da complexidade em caso médio”). Nele, propôs cinco cenários hipotéticos — batizados com humor de Algorithmica, Heuristica, Pessiland, Minicrypt e Cryptomania — que descrevem, cada um, uma resposta diferente para uma pergunta central: o quão difíceis são, em média (e não apenas no pior caso possível), os chamados problemas NP, uma classe de problemas computacionais que inclui desde quebra-cabeças de otimização até a própria fatoração de números.

A distinção entre “pior caso” e “caso médio” é o ponto central da tese de Impagliazzo. Provar que um problema é difícil de resolver no pior cenário imaginável não garante que ele seja difícil na prática, na maioria das vezes — e é justamente essa dificuldade “típica”, não a excepcional, que a criptografia precisa para funcionar. Um cofre cuja combinação só é difícil de adivinhar em casos raríssimos não serve para proteger nada.

Impagliazzo também chamou atenção, décadas depois, em entrevista à Quanta Magazine publicada em 2024, para uma distinção adicional que ajuda a entender os mundos mais avançados de sua taxonomia: a diferença entre um “problema” comum, cuja solução ninguém necessariamente conhece de antemão, e um “quebra-cabeça” (puzzle), criado por alguém que já sabe a resposta e quer testar se outra pessoa consegue chegar a ela sem ajuda. “Em criptografia, usamos quebra-cabeças para testar o conhecimento de alguém”, explicou. É essa ideia — conseguir fabricar problemas difíceis sob encomenda — que separa os mundos onde a criptografia é possível dos mundos onde não é.

Algorithmica e Heuristica: mundos sem segredos

No primeiro e mais otimista dos cinco cenários, batizado de Algorithmica, a fronteira entre problemas fáceis e difíceis praticamente desaparece: nele, valeria a igualdade P = NP (ou algo matematicamente equivalente a ela), o que significaria que todo problema cuja solução pode ser conferida rapidamente também poderia ser resolvido rapidamente. Seria uma notícia extraordinária para quase qualquer área da ciência e da logística — e uma catástrofe para a criptografia, porque toda cifra seria, em princípio, quebrável com a mesma facilidade com que foi criada.

Em Heuristica, o segundo mundo, os problemas mais difíceis continuam existindo no pior caso teórico, mas se tornam solucionáveis na prática para praticamente qualquer distribuição razoável de exemplos — ou seja, seriam difíceis apenas em casos artificiais e raros, quase impossíveis de gerar de propósito. O resultado prático é semelhante ao de Algorithmica: também não haveria como fabricar problemas realmente difíceis para proteger informações, porque um invasor motivado enfrentaria, em média, o mesmo nível de dificuldade que um usuário legítimo. Nenhum dos dois mundos permite qualquer forma de criptografia segura.

Pessiland: o pior de todos os cenários possíveis

O terceiro mundo é o mais desconfortável de todos, e por isso mesmo ganhou o apelido irônico de Pessiland — de “péssimo”. Nele, existem sim problemas genuinamente difíceis mesmo em caso médio: não há atalho eficiente para resolvê-los na maioria das vezes. O problema é que essa dificuldade não ajuda em nada. Em Pessiland, não existem funções de mão única — todo processo fácil de executar também seria, de alguma forma, fácil de reverter quando alguém quisesse fabricar deliberadamente um quebra-cabeça difícil já conhecendo a resposta.

Isso significa que Pessiland concentraria as piores características de todos os cenários ao mesmo tempo: computação cara e imprevisível para tarefas legítimas, sem nenhuma das vantagens que a dificuldade computacional poderia oferecer em troca. Seria possível encontrar problemas difíceis “na natureza”, mas ninguém conseguiria criá-los sob encomenda para proteger uma senha ou uma mensagem — e é exatamente essa capacidade de fabricar dificuldade sob controle que a criptografia exige.

Minicrypt e Cryptomania: a aposta em que vivemos

Os dois últimos mundos são os únicos em que a criptografia, tal como a conhecemos, se torna possível — e é neles que os especialistas acreditam, de fato, que vivemos. Em Minicrypt, funções de mão única realmente existem: é possível fabricar quebra-cabeças difíceis mesmo já sabendo a resposta. Isso já é suficiente para viabilizar ferramentas importantes, como cifragem de chave secreta, geradores de números pseudoaleatórios e certas formas de assinatura digital. O que falta em Minicrypt é a criptografia de chave pública — o mecanismo que permite a duas pessoas que nunca se encontraram, e que só se comunicam por um canal aberto e vigiado, combinarem um segredo que ninguém mais consiga descobrir.

É exatamente essa capacidade adicional que define Cryptomania, o quinto e mais rico dos mundos, considerado por Impagliazzo o mais próximo da realidade que observamos. Nele, além das funções de mão única, existem as chamadas funções de mão única com “porta dos fundos” (trapdoor functions), que tornam viável a criptografia de chave pública usada em praticamente toda a internet — desde o HTTPS até assinaturas digitais e votação eletrônica segura. Toda a nossa infraestrutura digital de segurança pressupõe que vivemos em Cryptomania. O problema é que essa suposição continua sendo exatamente isso: uma suposição bem fundamentada, sustentada por décadas de tentativas fracassadas de quebrar sistemas como o RSA, mas nunca demonstrada como verdade matemática permanente.

O elo com o maior enigma da matemática

A pergunta de fundo por trás dos cinco mundos de Impagliazzo é uma prima próxima de um dos problemas mais famosos de toda a matemática: P versus NP. Formulado formalmente na década de 1970, o problema pergunta, essencialmente, se todo problema cuja resposta pode ser verificada rapidamente também pode ser resolvido rapidamente do zero. É uma questão tão central e tão resistente à solução que o Clay Mathematics Institute a incluiu entre os sete “Problemas do Milênio”, com um prêmio de um milhão de dólares para quem apresentar uma prova rigorosa.

Se algum dia se provar que P = NP, isso eliminaria de uma vez os mundos mais favoráveis à criptografia — Minicrypt e Cryptomania simplesmente deixariam de ser possíveis, e estaríamos em Algorithmica, goste-se ou não. Mas o inverso não é automático: provar que P ≠ NP, sozinho, não bastaria para garantir que vivemos em Cryptomania — ainda seria preciso descartar Heuristica e Pessiland, cenários também compatíveis com P ≠ NP e igualmente hostis à criptografia. É por isso que pesquisadores da área descrevem excluir formalmente esses mundos intermediários como uma espécie de “santo graal” da complexidade computacional: mais difícil, em certo sentido, do que a própria pergunta P versus NP.

O importante para quem não é especialista é entender a natureza dessa incerteza. Ela não indica que a criptografia atual esteja prestes a falhar, nem que exista alguma ameaça iminente às senhas ou aos bancos. O que ela revela é algo mais sutil e, de certa forma, mais intrigante: uma das infraestruturas mais críticas da vida digital contemporânea — capaz de proteger desde uma conversa privada até uma eleição — se apoia, até hoje, sobre uma conjectura matemática elegante, historicamente bem-sucedida, mas oficialmente indemonstrada. Continuamos operando o mundo digital como se morássemos em Cryptomania. A matemática, por enquanto, apenas nos deixa apostar nisso.

Fontes citadas neste artigo: