Uma rápida introdução à criptografia: Parte I

Ali pela quinta série do meu ensino fundamental, colegas costumavam trocar bilhetes com mensagens durante as aulas. Eram mensagens tipicamente falando sobre algum outro colega, na linha de “fulana gosta do beltrano” ou “beltrano é um bobalhão”. Saudades, quinta série. Como os bilhetes só percorriam a sala de mão em mão, era inevitável que em algum momento eles passariam por fulana ou beltrano. Para se precaver, o remetente trocava as letras por símbolos pré-combinados com o remetente, por telefone, no dia anterior. O resultado era algo como o abaixo.

O bilhete acima é uma mensagem cifrada e é o resultado da aplicação de um método de criptografia. Criptografia é um método para ocultar informação por meio do uso de códigos de forma que apenas pessoas que saibam como decodificar a mensagem cifrada conseguem ter acesso à mensagem original. Na quinta série, quando interceptávamos uma mensagem e sem conhecer a cifra utilizada, eu e meus colegas gastávamos algum tempo tentando reverter o processo de criptografia por meio de criptoanálise. Não me recordo se já conhecíamos o termo na época, porém. ¯\_(ツ)_/¯

A história da criptografia é bastante rica e inicia com métodos de esteganografia, que envolve ocultar a mensagem sem transformá-la. Também lá no ensino fundamental, brincávamos, sem muito sucesso, com uma técnica de escrever mensagem com suco de limão. Ao secar, a “tinta” praticamente desaparece mas pode ser revelada queimando levemente o suco em fogo. O suco queima mais rapidamente do que o papel, ou assim diz a teoria — com frequência iniciávamos um pequeno incêndio. Tente por conta e risco.

Um dos primeiros registros de esteganografia data de 440 AC, quando o grego Histiaeus enviou uma mensagem a um de seus aliados escrevendo-a na cabeça de um escravo e aguardando o cabelo crescer e ocultar a mensagem. Uma rede de transmissão de alta latência, certamente.

Na criptografia, a mensagem é transformada de forma que mesmo que alguém tenha acesso a mensagem cifrada, esta não saberá como recuperar a mensagem original; na esteganografia, porém, alguém que saiba onde olhar poderá ler a mensagem sem dificuldades.

Uma cifra é um par de algoritmos responsáveis pela encriptação e desencriptação de uma mensagem, podendo ou não ser o mesmo algoritmo para cada transação. O algoritmo de encriptação recebe uma mensagem em texto “limpo” e uma chave e retorna uma mensagem cifrada. O algoritmo de desencriptação recebe a mensagem cifrada e uma chave e retorna a mensagem original. Quando a chave de encriptação e desencriptação são a mesma, diz-se que é uma chave simétrica. A vasta maioria dos algoritmos de criptografia são de chave simétrica.

Um exemplo clássico de cifra é a chamada Cifra de César, nome advindo de Julio César que a utilizava no império Romano para comunicação com generais (ainda que haja registro de usos anteriores). Esta cifra é bastante simples: a chave é um número inteiro que é utilizada para deslocar o alfabeto. Assim, se a chave for 1, temos que a letra A se torna B, a letra B se torna C e assim por diante. Se a chave for 2, a letra A se torna C, a letra B se torna D. Ao chegar ao fim do alfabeto, retorna-se para a primeira letra.

H JPMYH KL JLZHY LO WVBJV ZLNBYH L ZVO KLCPH ZLY YLHSTLUAL BAPS XBHUKV H THPVY WHYAL KH WVWBSHJHV LYH HUHSMHILAH

Sabendo a chave, é trivial reverter o processo, rotacionando o alfabeto para o lado contrário. Mas a criptoanálise desta cifra também é trivial, sabendo que ela foi usada: basta testar todas possibilidades de chave — apenas 26 no nosso alfabeto, 24 no grego. Esta técnica de tentar todas chaves possíveis é denominada ataque por força bruta. Naturalmente, cada teste precisa verificar se o resultado faz sentido, o que implica que o criptoanalista precisa compreender pelo menos rudimentos da língua de origem.

A segurança é um pouco maior se o criptoanalista não souber que cifra foi utilizada. Qualquer semblante de segurança da Cifra de César advém dos atacantes (aqueles que procuram quebrar a cifra) não saberem qual foi a cifra utilizada. É, assim, importante que não só a chave se mantenha secreta, mas também a própria cifra.

A cifra utilizada por colegas na quinta série é uma generalização da Cifra de César. Trata-se de uma cifra de substituição monoalfabética, onde cada letra é substituída por um símbolo (que pode ser outra letra) qualquer. O termo monoalfabética diz respeito ao fato de que a substituição é um-para-um: cada letra é substituída por um símbolo e cada símbolo corresponde a uma letra. Neste caso, a chave é a tabela de substituição. No nosso alfabeto, temos um total de 26! possíveis chaves, um número considerável (cerca de 2⁸⁸), tornando ataques por força bruta bastante custosos. Note que a Cifra de César é um tipo especial de cifra de substituição monoalfabética, uma que impõe um forte padrão nas substituições possíveis.

A dificuldade considerável em quebrar uma cifra de substituição monoalfabética por força bruta permitiria, em princípio, que a cifra em si não precisasse ser oculta — todos podem usar a mesma cifra e apenas a chave precisa permanecer secreta. Isto é bastante desejável, pois trocar apenas chaves é muito mais prático do que negociar cifras a serem utilizadas.

No entanto, cifras de substituição monoalfabéticas podem ser quebradas facilmente por análise de frequência. Esta técnica de criptoanálise se baseia no fato de que, para uma dada língua e um texto suficientemente longo, a frequência com que letras individuais ocorrem segue um forte padrão e este padrão é mantido no texto cifrado. Por exemplo, a figura abaixo ilustra a frequência de ocorrências de letras para textos em português.

Frequência de ocorrência de letras do alfabeto em textos em português

O processo de criptoanálise calcula as frequências com que símbolos ocorrem no texto cifrado e substitui os símbolos pelas letras na mesma ordem de frequência. Assim, se no texto cifrado a letra que mais ocorre é "z", ela seria substituída por "a", pois esta é a que mais ocorre no alfabeto original.

A eficácia deste método será tão melhor quanto maior for o texto cifrado. De forma geral, a correspondência nunca será perfeita mas pode ser suficiente para revelar partes do texto original e as falhas podem ser inferidas a partir do contexto das palavras.

Os primeiros relatos de análise de frequência datam do ano 800, pelo árabe Al Kindi, e a análise é considerada um dos grandes marcos da criptoanálise. Esta técnica essencialmente torna insegura qualquer cifra de substituição monoalfabética. Edgar Alan Poe se utilizava deste fato para desafiar leitores de um jornal a enviarem textos cifrados para ele quebrar — a vasta maioria variações da cifra de substituição monoalfabética.

Uma maneira de tornar a cifra de substituição mais segura é permitir que cada letra original seja substituída por mais de um símbolo, um método chamado substituição homófona. Em particular, este método é efetivo se o número de símbolos ao qual corresponde uma letra é inversamente proporcional a sua frequência. Por exemplo, se a letra "y" ocorre 20 vezes menos que “a”, então “y” teria 20 símbolos a mais associados em comparação a “a”. Isto faz com que a análise de frequência apresente uma frequência bastante homogênea entre letras, impossibilitando seu uso. Neste caso, não é possível utilizar o alfabeto original como alfabeto cifrado, pois passa a ser necessário um número maior de símbolos e o uso de mapeamento para números é comumente utilizado.

Um caso famoso, e talvez apócrifo, de cifra homófona, é o caso dos irmãos Beale, dois irmãos que teriam enterrado uma quantia em metais preciosos no velho oeste norte-americano (por volta de 1821) e especificado o conteúdo, a localização e para quem o tesouro deveria ir se eles morressem, em três cartas cifradas. A segunda carta, única que foi decifrada, utilizava uma sequência de números que indicavam palavras na Declaração de Independência dos EUA. Tomando a primeira letra de cada palavra, a mensagem se revelava.

A segunda carta dos irmãos Beale. Cada número indica uma palavra na Declaração de Independência dos EUA.

Cifras homófonas bem balanceadas e que mapeiam para um grande número de símbolos são muito difíceis de serem quebradas. Porém, são também difíceis de serem utilizadas — a chave é consideravelmente grande e difícil de ser construída.

Outro avanço significativo veio no século XV com cifras de substituição polialfabéticas, do qual a Cifra de Vigenère é o exemplo mais popular. O ataque por análise de frequência é possível pois há uma relação um-para-um entre o alfabeto original e o alfabeto cifrado, fazendo com que propriedades estatísticas de um sejam transpostas para o outro. A cifra polialfabética faz com que tenhamos relações muitos-para-muitos: uma letra do alfabeto original pode aparecer no alfabeto cifrado como uma entre múltiplas letras e vice-versa.

A Cifra de Vigenère faz uso de uma tabela de substituições, que é fixa e parte do algoritmo:

Fonte: Wikipedia

O uso da tabela de substituições é feita por meio de uma sequência de letras que define a chave deste método. Por exemplo, considere a mensagem "OLA MUNDO" e a chave "AED". Iniciamos escrevendo a mensagem original e alinhando a chave sob cada letra e repetindo-a até que toda a mensagem seja coberta:

O|L|A|M|U|N|D|O
A|E|D|A|E|D|A|E

Cada par alinhado indica uma coluna e linha na tabela, que fornecerá a letra que deverá ser utilizada na substituição. No exemplo, a letra "O" do texto original está alinhada com a letra "A" da chave. Assim, devemos usar a linha A e coluna O. Consultando a tabela, a letra nesta posição é a letra "O". A segunda letra será substituída pela letra na linha L, coluna E: "P". Seguindo a lógica até o fim da mensagem, teremos:

O|L|A|M|U|N|D|O
A|E|D|A|E|D|A|E
---------------
O|P|D|M|Y|Q|D|S

Observe que o primeiro e último "O" da mensagem original são codificados com letras diferentes no texto cifrado (o primeiro como O, o segundo com o S). Também observe que o "D" no texto cifrado corresponde a letras diferentes no texto original: o primeiro corresponde a um "A" e o segundo a um "D".

A substituição polialfabética torna ineficaz a análise de frequência tradicional, pois não há mais a correspondência um-para-um. A Cifra de Vigenère foi considerara segura por bastante tempo e é um método razoavelmente prático de ser utilizado, pois a chave é algo que pode ser escrita (e talvez lembrada) com facilidade.

Apenas no século 19 temos relato de métodos sistemáticos para quebrar esta cifra, por ninguém menos que Charles Babbage, criador de um dos primeiros computadores mecânicos— dando início a uma forte intersecção de personalidades entre criptografia e computação.

O método de Babbage (que não publicou seu método, que acabou sendo re-descoberto por Friedrich Kasiski) envolve se dar conta que se o tamanho da chave for conhecido, então pode-se quebrar o problema em múltiplas Cifras de César. Observe que efetivamente cada linha da tabela é uma Cifra de César com um deslocamento diferente. Assim, no exemplo dado acima, o texto pode ser quebrado em três textos distintos (pois a chave tem 3 caracteres), cada um cifrado com uma substituição que pode ser quebrada por análise de frequência.

O problema passa a ser descobrir o tamanho da chave. Para tanto, faz-se uso de que, por sorte, uma mesma sequência no texto original será cifrado pela mesma sequência da chave, resultando em uma repetição no texto cifrado. A distância entre estas repetições é um indicativo do tamanho da chave — provavelmente ela terá um tamanho que é um fator desta distância. Por exemplo, se a distância for 8, então a provavelmente a chave pode ter tamanho 8, 4, 2 ou 1. Como chaves de tamanho 1 ou 2 seriam bastante óbvias, resta testar os tamanhos 8 e 4. Faz-se isso separando o texto em 8 ou 4 partes. Pode-se reduzir ainda mais o número de possibilidades procurando por diferentes repetições: o tamanho da chave provavelmente será um fator comum a ambas distâncias.

ORRUMKIJUILMVMJMVMRIDLDMMHRNZINGHAJTAMVMLMVMJMVMRIPIAKOQRMWKAWRXIZAQXQBISMQDMVCSHAVICVLXBWGVDNQIAGLNZIFSLXZWPSVBIINXHZQWRIPMVBETRZOQOZDVJITXLABIBIOTIAOELVLIAWVQUWNSPMDQGIQMZMFMFWCISWRKQIDSDKQNREHMTMDIIIBWPVRXWAUQDDIZIEFIWUAMVNWZTIGMABAGLNZIOUXMXZOZDDMTMIQBMTEZRCIITVLJCQCERQVKOVUMBI