Entropia

A seguir será discutido o que é a entropia de um código, tópico de necessário entendimento para realizar uma criptoanálise. Caso você já saiba o que é entropia, talvez queira ir direto para o tópico "decifrando textos em português".

Na teoria, uma chave de N bits pode gerar até 2^N chaves diferentes. Porém, uma chave longa não significa necessariamente uma chave difícil de ser quebrada. Isso é devido à entropia, que pode ser considerada a medida de incerteza de uma chave. Uma chave com alta entropia significa uma chave difícil de ser quebrada.

Por exemplo: deseja-se codificar uma chave-senha para cada aluno de computação na UFRJ. Para isso, utilizaremos informações sobre o sexo, número do CPF e sua cor preferida.

Codificação:
Sexo: 1 bit. Valor 0 = sexo masculino, valor 1 = sexo feminino.
Número do CPF: 44 bits. Contém 11 algarismos e 4 bits para cada algarismo.
Cor: 4 bits.

Com isso, nossa chave-senha tem um total de 49 bits. Agora iremos analisar a entropia da chave:

Como sabemos, quase a totalidade dos alunos de computação na UFRJ são do sexo masculino. Com isso, esse bit tem baixa entropia. Partindo para a seqüência de bits do número do CPF, sabemos que os 9 primeiros algarismos têm algum valor significativo, e que os outros dois são gerados a partir dos nove primeiros. Assim, da seqüência de 44 bits, podemos considerar que apenas 36 têm entropia. Assim, já sabemos que somente 40 dos 49 bits têm entropia. Discutiremos a entropia dos bits relacionados às cores a seguir.

O problema maior da criptografia consiste em montar um processo que gere chaves de alta entropia. Com isso, um algoritmo gerador deve garantir um certo número de bits de entropia. Um processo que gera chaves aleatoriamente não necessariamente tem a mesma quantidade de bits de entropia quanto a quantidade de bits da chave.

Por exemplo: para criptografar um texto, deve-se modificar a codificação dos bits de cada caractere para maximizar a entropia do código. Utilizando 8 bits para codificá-las, temos um total de 256 possibilidades para escrever 26 símbolos. Para definir quais seqüências de bits vão representar quais símbolos, descobrimos qual a freqüência do símbolo no texto, por exemplo: letra X possui N% de ocorrências, e representamos N% do total de combinações possíveis da chave para essa determinada letra.

Agora falaremos sobre a codificação da representação das cores na chave-senha descrita acima. Supomos que 50% dos alunos preferem branco, 25% dos alunos preferem azul, 10% preferem laranja, 10% vermelho e 5% rosa. Na tabela a seguir, consta a quantidade de representações diferentes, dentro das 16 possíveis, atribuídas a cada cor.

Cor	Quantidade de códigos diferentes
Branco	8
Azul	4
Laranja	2
Vermelho	1
Rosa	1

O resultado desse algoritmo é fazer com que a probabilidade a priori de cada seqüência de código seja igual, não criando vícios no código.

O principal problema redutor de entropia acontece quando o que é codificado pelo algoritmo possui algum significado. No caso de um texto, devido à alta densidade de probabilidade da ocorrência de algumas letras (como as vogais A, E e O no português), as primeiras tentativas a serem feitas para descobrir por força bruta qual é a chave-senha são as seqüências de bits correspondentes a estas letras. Para evitar que a chave-senha seja mais facilmente descoberta, deve-se utilizar caracteres randômicos e sem nenhum vício de língua para a construção da chave.

No caso das cores do exemplo anterior, as primeiras tentativas serão sempre as que estão relacionadas à cor branca. Ainda há uma correlação dos bits das cores com o bit do sexo, pois quando estamos codificando uma mulher, a chance da sua cor preferida ser rosa é mais alta do que se estivéssemos tratando de um homem.