Detalhes

Categoria: Assuntos Gerais

Atualização: Quinta, 19 Abril 2012 19:11

Autor: vovó Vicki

Acessos: 22411

A teoria da informação moderna foi definida pela primeira vez por Claude Shannon (1916-2001) quando publicou A mathematical theory of communication no Bell System Technical Journal, vol. 27, pp. 379-423 e 623-656, Julho e Outubro, 1948. Nos downloads da Aldeia, seção de Criptologia, você pode fazer o download do texto original em Inglês.

Apenas os tópicos principais e seu tratamento matemático serão abordados no presente texto.

Entropia e Incerteza

A quantidade de informação de uma mensagem é definida na teoria da informação como sendo o menor número de bits necessários para conter todos os valores ou significados desta mensagem. Por exemplo, se quisermos transmitir ou armazenar os números dos meses do ano, serão necessários, no mínimo, 4 bits para representar esta informação:

     0000 = [não usado]               1000 =  8 [Agosto]
     0001 = 1 [Janeiro]               1001 =  9 [Setembro]
     0010 = 2 [Fevereiro]             1010 = 10 [Outubro]
     0011 = 3 [Março]                 1011 = 11 [Novembro]
     0100 = 4 [Abril]                 1100 = 12 [Dezembro]
     0101 = 5 [Maio]                  1101 = 13 [não usado]
     0110 = 6 [Junho]                 1110 = 14 [não usado]
     0111 = 7 [Julho]                 1111 = 15 [não usado]

Caso esta mesma informação fosse representada pelos caracteres ASCII, o número de bits necessários seria bem maior. A informação, no entanto, seria a mesma. Da mesma forma, para armazenar a informação "sexo", podemos usar apenas um bit ou 9 bytes (um para cada letra da palavra "masculino" ou 72 bits) para os caracteres ASCII "masculino" ou "feminino".

Entropia

A entropia é a quantidade mínima de bits necessários para transmitir ou armazenar um tipo de informação. A informação "sexo", por exemplo, possui entropia 1. Já a informação mês do ano possui um entropia um pouco menor do que 4 bits (alguns deles nãi são usados).

Portanto, a quantidade de informação de uma mensagem M é medida pela entropia da mensagem, designada por H(M). Na grande maioria dos casos, a entropia de uma mensagem é log₂n, onde n é o número de significados possíveis, se todos os significados forem igualmente prováveis.

Incerteza

A entropia de uma mensagem também mede a sua incerteza. Esta é o número de bits que precisam ser recuperados quando a mensagem está cifrada para obter novamente o texto claro. Por exemplo, se o bloco cifrado "GF#*3K~!B" representa "masculino" ou "feminino", a incerteza da mensagem é 1 porque é preciso conhecer apenas 1 bit bem escolhido para recuperar a mensagem.

Razão da Língua

A razão de uma língua é representada por r = H(M) / N, onde N é o comprimento ou o número de caracteres da mensagem. A razão do Inglês normal fica entre 1.0 e 1.5 bits/letra se a mensagem for grande. Shannon estimou este valor em 1.2. A razão absoluta de uma língua é o maior número de bits que podem ser codificados em cada caracter se todos os caracteres forem igualmente prováveis. Se hover L caracteres, a razão absoluta é R = log₂L. Esta é a entropia máxima de cada um dos caracteres.

No Português, com 26 letras se incluirmos K, W e Y, a razão absoluta é log₂26 = 4.7 bits/letra. Acontece que a frequência com que as letras são usadas é diferente: a letra A é muito mais utilizada do que a letra X, por exemplo. Diz-se que a letra A é muito mais redundante do que a letra X. Por este motivo, a razão do Português é muito menor do que a razão absoluta.

Redundância

A redundância de uma língua, chamada de D, é definida como D = R - r. Se considerarmos que a razão do Português também seja 1.2, então a sua redundância é 4.7 - 1.2 = 3.5 bits/letra. Isto significa que o Português carrega apenas 1.2 bits de informação e que todo o resto é redundante. Uma mensagem ASCII, que nada mais é do que a língua portuguesa impressa, continua tendo 1.2 bits de informação em cada 8 bits de mensagem. Isto significa que possui 3.5 bits de informação redundante, ou seja, 3.5 / 8 = 0.44 bits de redundância e 1 - 0.44 = 0.56 bits de informação em cada bit do texto ASCII. É preciso lembrar que os espaços entre as palavras, a pontuação, os acentos e os números modificam estes resultados.

A segurança de um criptossistema

Shannon definiu um modelo matemático preciso da segurança de um criptossistema. O objetivo de uma criptoanálise é determinar a chave k, o texto claro p, ou ambos. Entretanto, existem algumas informações prováveis sobre p: pode ser um audio digitalizado, um texto em Francês, uma planilha de dados, etc, e todo criptoanalista trabalha com isto: presume a língua e a associa com a sua redundância; se a mensagem for para o Sr. Silva, provavelmente começa com "Prezado Sr. Silva". O objetivo da criptoanálise é modificar as probabilidades associadas a cada um dos textos claros prováveis. Eventualmente, um destes textos claros é o correto ou, pelo menos, torna-se o mais que provável.

Um criptossistema pode atingir o grau do segredo perfeito - um sistema no qual o texto cifrado não guarda nenhuma informação sobre o texto claro. Shannon teorizou que isto só é possível quando o número de chaves possíveis é, no mínimo, o mesmo dos textos claros possíveis. Em outras palavras, a chave precisa ter o mesmo comprimento do texto claro e nenhuma chave pode ser usada mais de uma vez - o famoso One Time Pad.

Deixando a segurança perfeita de lado, todo texto cifrado incorpora alguma informação sobre o texto claro correspondente. Não tem como evitar. Um bom algoritmo criptográfico mantém esta informação num nível mínimo e um bom criptoanalista explora esta informação para obter o texto claro. Os criptoanalistas usam a redundância natural da língua para reduzir o número de textos claros possíveis. Quanto mais redundante for a língua, mais fácil se torna a análise do texto cifrado. Este é o motivo pelo qual muitos métodos criptográficos aplicam uma compressão (tipo zip) no texto claro antes de cifrá-lo porque a compressão reduz a redundância da mensagem.

Entropia de um criptossistema

A entropia de um criptossistema é a medida do tamanho do espaço das chaves. Corresponde a aproximadamente o logaritmo na base dois do número de chaves: H(K) = log₂(número de chaves). Um criptossistema com uma chave de 64 bits possui uma entropia de 64 e, um com uma chave de 56 bits, possui uma entropia de 56. Em geral, quanto maior for a entropia, mais difícil será quebrar o sistema.

Distância una

Para uma mensagem de comprimento n, o número de chaves diferentes que decifram o texto cifrado para um texto claro inteligível na mesma língua é dado por 2^{H(K) - nD}-1. Shannon definiu a distância una, também chamada de ponto único, como a aproximação da quantidade de texto cifrado cuja informação real (entropia) do texto claro correspondente, somada à entropia da chave, é igual ao número de bits do texto cifrado. Mostrou que textos cifrados maiores que esta distância, com toda probabilidade, possuem apenas uma decifração coerente. Textos cifrados menores provavelmente possuem decifrações múltiplas, igualmente válidas, o que lhes confere maior segurança.

Para a maior parte dos sistemas simétricos, a distância una é definida como a entropia do criptossistema dividida pela redundância da língua: U = H(K) / D.

A distância una, como toda medida estatística teórica, não faz predições determinísticas, mas dá resultados prováveis. A distância una indica a quantidade mínima de texto cifrado para o qual existe apenas um texto claro se for usado um ataque de força bruta. Normalmente, quanto maior for a distância una, melhor é o criptossistema. Para o DES, com uma chave de 56 bits usado numa mensagem em Inglês, a distância una é 56 / 6.8 = 8.2, ou seja, cerca de 8.2 caracteres ASCII ou 66 bits.

Confusão e Difusão

Segundo Shannon, as duas técnicas básicas para ocultar as redundâncias numa mensagem clara são a confusão e a difusão.

A confusão oculta a relação entre o texto claro e o texto cifrado. Isto dificulta a análise das redundâncias e dos padrões estatísticos do texto cifrado. A forma mais fácil de se obter uma difusão é através da substituição.

A difusão dissipa a redundância do texto claro pulverizando-a no texto cifrado. A maneira mais fácil de causar uma difusão é através da transposição, também chamada de permutação.

Texto base

• Schneier, Bruce - Applied Cryptography
• vovó Vicki - Tradução, pra variar muito livre.