O que é Criptografia?

Criptografia é o estudo dos métodos para codificar uma mensagem de modo que apenas o seu destinatário legítimo possa interpretar. Todos já brincamos de "falar em códigos" ou algo do tipo quando crianças, seja para combinar algo sem ser descoberto ou apenas por acharmos legal. A criptografia é basicamente isso mas elevado a um nível muito maior, de modo que seja possível ocultar dados como senhas, cartões, informações sensíveis e até mesmo dados vitais. Essa prática é importantíssima no mundo atual e entendê-la é ainda mais para aqueles que se propõem a desenvolver software.

Normalmente a criptografia se dá em duas etapas: Codificação e decodificação. Na codificação estamos ocultando os dados inciais, enquanto, na decodificação, estamos decifrando os dados. Todo código deve vir com duas receitas: uma para codificar e outra para decodificar. O códico mais famoso e antigo que temos conhecimento é a cifra de césar, que se baseia em transladar as letras do alfabeto por algum passo.

Definição: Cifra de César
Seja um alfabeto Ω e uma mensagem M na sua forma original. Para codificar a mensagem M tomamos um passo n, de modo que a letra ωₖ do alfabeto referente a posição i da mensagem seja substituida pela letra ωₖ₊ₙ. O processo de decodificação se faz de forma análoga, de modo que ωₖ seja substituída por ωₖ₋ₙ

Por exemplo, para a mensagem Hello World no nosso alfabeto usual, com passo 2, teríamos Jgnnq Yqtnf. Parece ser uma mensagem quase indecifrável se não soubéssemos qual era a mensagem original, mas esse método possui um grave problema: é vulnerável a uma análise léxica.

Se soubermos que a mensagem está em português temos as seguintes características:

• vogais são mais frequentes que consoantes
• a vogal mais frequente é o A
• se uma palavra tem apenas uma sílaba, então uma letra é uma vogal
• as consoantes S e M são as mais frequentes

Por exemplo:

T Ufqrjnwfx sat yjr rzsinfq

Inicialmente já podemos saber que, depois de decodifiar, T é uma vogal. Como T aparece sozinho, podemos supor que ele não é I, U e nem E, pela própria semântica da nossa língua, ou seja, T será A ou O. Dessa forma, temos apenas dois passos possíveis: 5 e 7. Utilizando um método de força bruta, temos as seguintes possíveis mensagens:

Passo 5: O Palmeiras nao tem mundial
Passo 7: A Bmxyqudme zãa fqy ygzpumx

Que claramente sabemos que a primeira opção é verdadeira XD.

Portanto, percebemos como uma cifra de César pode ser fácilmente decodificada mesmo se não soubermos a "receita" para decodificar.

Esse método de contagem de frequência também para decifrar inscrições antigas. O maior exemplo é a decifração dos hieróglifos egíicios por J.-F. Champollion em 1822, devido a descoberta da pedra de Roseta, um bloco de basalto negro que continha as mesmas incrições escritas em hieróglifos, demótico e grego. Atualmente a pedra se encontra no Museu Britânico. Na época dessas descobertas se discutia sobre qual tipo de escrita seriam os hieróglifos, se ideográfica, silábica ou alfabética.

• Escrita Ideográfica: Cada símbolo representa uma palavra ou frase completa
• Escrita Silábica: Cada símbolo representa uma sílaba
• Escrita Alfabética: Cada símbolo representa uma letra do alfabeto

Imagine que estamos decifrando um texto que sabemos que existe um equivalente grego (que é alfabético), como poderíamos descobrir qual a forma de escrita dele? Fica aqui meu desafio para você!

Esse tipo de decodificação é ainda mais rápido e simples se temos um computador, por isso esse tipo de criptografia é muito fraco e nunca deve ser utilizado se queremos realmente codificar uma informação importante. Como muitos sabem, os primeiros computadores foram criados exclusivamente para resolver esse tipo de problema, mas dessa vez para decifrar os códigos secretos dos alemães codificados pela máquina enigma, que foram brilhantemente quebrados por Allan Turing, no século passado.

Conhecendo a história da criptografia percebemos que os computadores foram inicialmente idealizados para esse fim, ou seja, codificar e decodificar mensagens. Portanto, é fácil perceber o porquê métodos fracos de encriptação são soluções porcas para a segurança da informação.

No ano de 1976, na universidade de Stanford, W. Diffie e M.E. Hellman desenvolveram ao mesmo tempo, de forma independente, com R.C.Merkle da Universidade da Califórnia uma ideia que resolveria o maior problema de algoritmos de criptografia baseados em cifras. A grande questão é: se você sabe encriptar, então você também sabe decriptar, isso é o que chamamos de criptografia simétrica. O que eles desenvolveram foi o que hoje chamamos de Criptografia Assimétrica, que consiste em gerarmos duas chaves: uma pública, que serve apenas para decodificar e, uma privada, que serve apenas para codificar. A chave pública apenas pode decodificar uma mensagem encriptada pela sua chave privada relacionada.

Tudo aqui depende de qual algoritmo será utilizado para gerar esse par de chaves, se for difícil descobrir qual é a chave pública correta o algoritmo é bom, caso contrário não. Esse daqui é talvez o conceito mais importante na segurança da informação: não existe criptografia inquebrável. Isso se deve a limitações da computação, para quem entende um pouco de cálculo numérico não deve ser difícil entender o porquê disso.

Recapitulando, criptografia é uma arte de códigos secretos, onde temos uma mensagem ou informação que queremos garantir que apenas alguém em específico leia, por isso não enviamos de forma "crua". Para isso precisamos de duas receitas, uma para codificar e outra para codificar. Assim temos duas opções:

• Criptografia Simétrica: a chave de encriptação é a mesma de decriptação
• Criptografia Assimétrica: a chave de encriptação é diferente da chave de encriptação

Geralmente chamamos a primeira opção de Cifra, contudo ela é fácilmente quebrável com uma análise léxica e de frequência, principalmente se colocarmos algum computador na jogada. Por isso utilizar algoritmos de criptografia Assimétrica nos dá uma segurança muito maior, pois dessa forma é possível dificultar o processo de encontrar a chave de decriptação.

Essa é a primeira postagem de uma sequência que irei fazer sobre o método RSA. A abordagem será puramente Matemática, de modo a dar o entendimento completo do funcionamento e também de toda a teoria por trás disso. Todas as postagens serão baseadas no Livro Números Inteiros e Criptografia RSA do professor Coutinho, publicado pelo IMPA em 2000. Alguns dados do livro estão desatualizados, contudo a teoria matemática por trás de tudo isso jamais estará ultrapassada, recomendo também a leitura desse livro.

Fonte: COUTINHO, S. C. Números Inteiros e Criptografia RSA. ISBN 85-244-0124-9. IMPA