Um Pilar Inseguro na Segurança Cibernética

A história diz que César, para trocar mensagens secretas com seus generais no campo, costumava raspar a cabeça de seus mensageiros e escrever a mensagem em seus escalpos. Ele então esperaria alguns meses para que seus cabelos crescessem novamente e os enviaria para seus destinos. Apenas seus generais de confiança saberiam desse método de troca de mensagens, entregando assim suas ordens com segurança (embora com alguns meses de atraso).

Este exemplo impraticável e bastante tolo descreve o que é a criptologia. Criptologia é a ciência de proteger a comunicação. O termo é retirado do grego kryptós ("oculto, secreto") e lógos ("palavra"). Em essência, trata-se de "ocultar palavras". É apenas um pilar na ciência da segurança cibernética, mas é significativo. Na base deste pilar estão as subdivisões da criptologia: Criptografia e Criptanálise. Os dois quase podem ser vistos como complementares. Onde a criptografia é a prática de transformar as comunicações em uma forma ilegível para os bisbilhoteiros, a criptoanálise é a prática de tentar desvendar essas mensagens transformadas por um destinatário não intencional.

E é aqui, na base deste pilar, que uma prova de um problema pode causar o colapso da Cibersegurança.

Então, entre no Panteão, este templo de segurança cibernética, se quiser, e deixe-me guiá-lo até onde as rachaduras nas colunas coríntias começam a aparecer.

Existem muitos algoritmos diferentes projetados para manter as mensagens seguras. Vou falar um pouco sobre alguns desses sistemas para que fique claro o fundamento desses algoritmos.

Se você leu alguma coisa sobre criptografia, é provável que tenha encontrado um conceito chamado "cifra de César". Este é outro exemplo de método usado para proteger mensagens. Também é atribuído a César, embora este não envolva os bloqueios de um mensageiro (trocadilhos) para manter a mensagem segura. Em vez disso, essa cifra introduz um conceito importante no qual uma parte significativa dos algoritmos criptográficos se baseia: Aritmética Modular.

Eu sei eu sei. Parece assustador, certo? E se eu te dissesse que é tão simples que você usa todos os dias? Veja, seu relógio também é baseado em aritmética modular. Quando você está tentando descobrir quanto sono vai conseguir se tiver que acordar às 06:00, já que está terminando esse prazo às 23:00, você sabe que não deve contar depois das 24:00. . O resultado sempre será menor que 24:00. Você está basicamente calculando o módulo 24. Isso é aritmética modular e é amplamente usado em criptografia. Mesmo em sua simplicidade, porém, a aritmética modular guarda muitos segredos que não são imediatamente evidentes. Muitos algoritmos criptográficos dependem desses segredos.

A cifra de César é uma cifra simétrica. Isso significa que ambas as partes usam a mesma chave. Digamos que a chave seja 3. O remetente mudaria cada letra de sua mensagem em 3. Isso é chamado de criptografia. O receptor precisa saber a chave e, então, retroceder cada letra em 3, obtendo a mensagem original. Isso é chamado de descriptografia. Compare isso com o método do mensageiro careca. Criptografia é deixar o cabelo do mensageiro crescer sobre a mensagem, descriptografia é deixar o mensageiro careca.

Agora, a cifra de César é muito segura? Bem, na verdade não. Qualquer pessoa pode facilmente experimentar todas as diferentes chaves, das quais são 26 no total, e encontrar a correta para desvendar a mensagem. Isso é chamado de Ataque de Força Bruta. Embora a cifra não seja muito segura, ela adere a um princípio importante ao qual os mensageiros carecas de César não aderem. O princípio de Kerckhoff afirma:

"Uma cifra não deve exigir sigilo e não deve ser um problema se cair nas mãos do inimigo."

Em outras palavras, o princípio afirma que apenas a chave deve permanecer secreta. O método pode ser tornado público, mas sem a chave, a mensagem deve permanecer segura.

Se o mensageiro anteriormente careca de César for interceptado pelo inimigo e o interceptador estiver ciente do método usado por César, o pobre mensageiro ficará careca novamente em pouco tempo, revelando a mensagem em seu couro cabeludo. Com a cifra de César, no entanto, mesmo que o interceptador conheça o método de criptografia, ele ainda terá que tentar 26 chaves diferentes para descobrir a mensagem.

A cifra de César é uma das cifras mais simples existentes, mas sua simplicidade demonstra bem os aspectos da aritmética modular. Outros sistemas criptográficos simétricos comuns são DES, 3DES e AES. Eles essencialmente fazem a mesma coisa que a cifra de César, embora muito mais complexa e mais difícil de força bruta. Se você quiser ler mais sobre esses sistemas, recomendo fortemente a leitura do AES Comic .

Vamos introduzir outro conceito importante. Criptografia assimétrica (ou criptografia de chave pública). A diferença é que ao invés de as duas partes terem a mesma chave, elas possuem suas próprias chaves públicas e secretas.

Antes de mergulharmos no RSA, aqui está um boato sobre ele para você. Quando o RSA foi inventado por Ron Rivest, Adi Shamir e Leonard Adleman, era ilegal para eles exportar o algoritmo ou mesmo sua descrição, como parte do controle de munições nos EUA. A RSA era considerada tão poderosa que deveria ser mantida em segredo militar. Como protesto pela liberdade de expressão, eles usaram camisetas com o algoritmo impresso para convenções e palestras.

O RSA é o criptosistema de chave pública mais popular. É um sistema super legal que ilustra perfeitamente no que se baseia grande parte da criptografia moderna. Nós vamos ficar um pouco técnicos aqui, mas tenha paciência comigo.

O teorema fundamental da aritmética afirma que qualquer número positivo pode ser representado exatamente de uma maneira como um produto de um ou mais primos. Por exemplo, o número 77 pode ser representado pela multiplicação de 7 (um primo) e 11 (um primo). Não há outra maneira de representar 77 em primos além de alterar a ordem dos primos. Lembre-se disso enquanto explico o RSA.

Antes que uma mensagem possa ser enviada, precisamos fazer algumas configurações. Digamos que Bob queira enviar uma mensagem para Alice e haja uma bisbilhoteira chamada Eva. Alice, como receptora, escolhe dois grandes números primos. Ela multiplica esses dois números para obter o resultado m, o módulo. Vamos mantê-lo simples e pequeno em nosso exemplo. Alice escolhe 7 e 11 como números primos, resultando no módulo 77. Ela publica o módulo 77 e algum expoente de criptografia escolhido e. A combinação do módulo 77 e o expoente de criptografia e é chamada de chave pública.

Com a chave pública de Alice, Bob pode criptografar a mensagem que deseja enviar. Nesse caso, a mensagem é um número x. A criptografia no RSA é feita usando x^e mod m. Isso resulta no texto cifrado y e o envia para Alice.

Agora, Alice pode fazer alguma mágica com os fatores primos 7 e 11, o que resulta em uma informação chamada d (para descriptografia). Esta é a chave secreta de Alice. Tudo o que Alice precisa fazer agora é pegar y^d, o que resultará na mensagem original de Bob x.

Ufa, foi muito, mas o difícil já passou! Agora, observe que apenas Alice conhece os fatores primos 7 e 11. Isso significa que apenas Alice pode fazer aquele truque de mágica para obter a informação d. Mas se você for perspicaz, discordaria de mim aqui. Você diria: "Como 77 está publicado e todos têm acesso a ele, Eva pode facilmente descobrir que 77 = 7*11 e também fazer o truque de mágica para obter d, com o qual ela pode obter a mensagem original x". Eu concordaria com você aqui. Aí eu te diria: "Quais são os primos do número 30142741". Provavelmente, você não será capaz de me dizer a resposta. Posso lhe dizer a resposta com muita facilidade, já que tudo o que fiz foi pegar dois números primos e multiplicá-los para obter 30142741. E se eu lhe dissesse esses dois números, você poderia facilmente verificar que o produto é 30142741. Então, de fato, RSA depende de Eve (ou você) não ser capaz de encontrar esses dois primos. Nesse caso, os primos são 6037 e 4993. Veja como é difícil a fatoração de primos, mas como é fácil verificar os primos corretos?

É isso! Finalmente chegamos à base do pilar. Você vê as rachaduras? Provavelmente não. Deixe-me esclarecer.

Assim, as transformações que aplicamos na mensagem (criptografia) precisam ser invertíveis para que o receptor consiga descriptografá-la. O receptor pode inverter a mensagem porque está de posse de alguma informação extra. Enquanto isso, qualquer interceptador, não de posse dessa informação, não conseguirá descriptografar a mensagem. No RSA, por exemplo, o interceptador precisaria encontrar os dois fatores primos do módulo. Encontrar os dois fatores primos de um número pequeno como 77 é, obviamente, fácil, mas a fatoração prima torna-se muito mais difícil quando um número grande é escolhido. Verificar se os dois primos são fatores do módulo é sempre relativamente fácil, pois você apenas faz multiplicações.

Se a fatoração primária fosse fácil ou se houvesse um algoritmo que pudesse resolver o problema relativamente rápido, o RSA se tornaria obsoleto. Ele depende da fatoração primária ser difícil de resolver, mas fácil de verificar. Podemos fazer uma distinção entre dois conjuntos de problemas. Existem problemas para os quais conhecemos uma maneira de encontrar a resposta rapidamente, por exemplo, multiplicação ou elevação ao quadrado. Este conjunto é chamado de "classe P". A outra classe, "NP" é um conjunto de problemas para os quais não existem maneiras conhecidas de encontrar uma resposta rapidamente, mas quando você tem alguma informação, a resposta é facilmente verificável. A fatoração primária pertence a esta classe.

Mas e se houver uma maneira de resolver facilmente um problema de fatoração de números primos? Isso implicaria que a fatoração prima pertence à classe P. De fato, talvez possamos provar que todos os problemas NP são na verdade problemas P. A conclusão seria que P = NP.

Essa conclusão teria consequências desastrosas para a criptografia. Como vimos, o RSA depende da fatoração prima ser difícil de resolver. Mas o RSA é apenas um dos muitos algoritmos que dependem de problemas NP e a fatoração primária é apenas um exemplo de um problema NP. Outras cifras simétricas e assimétricas usadas para suas transações financeiras, sua comunicação por e-mail etc. se tornariam obsoletas.

Bitcoin e outras criptomoedas também sofreriam consequências graves, já que o Bitcoin depende de hashing criptográfico, especificamente, o algoritmo de hash SHA-256. Para que um novo bloco seja aceito na blockchain, esse novo bloco precisa conter um proof-of-work. Resumindo, a prova é fácil para qualquer nó da rede verificar, mas gerar o número correto é extremamente difícil.

A prova de P = NP poderia, por outro lado, ter consequências positivas para outros campos. Muitos problemas matemáticos permanecem difíceis de resolver. Imagine os efeitos que isso poderia ter na matemática!

A prova de P ≠ NP significaria que nossos algoritmos criptográficos são seguros e que o título deste artigo é apenas clickbait. Mas pelo menos ofereci a você a chance de ganhar um milhão de dólares! Essa é a recompensa que o Clay Mathematics Institute concederá à primeira pessoa que resolver o problema "P vs NP".

Então, experimente! Talvez você possa quebrar a criptografia moderna e nos enviar de volta ao uso de mensageiros carecas para nossa comunicação diária.

Também publicado aqui