Detalhes

Categoria: Papers

Atualização: Quarta, 17 Junho 2009 19:40

Autor: Shannon

Acessos: 8211

Teoria da Comunicação de Sistemas Secretos
C. E. Shannon

Vamos supor que as mensagens possíveis são em número finito M₁, ..., M_n, que possuam probabilidades a priori P(M₁), ..., P(M_n) e que estejam cifradas nos criptogramas possíveis E₁, ..., E_m através de

E = TiM

O criptoanalista intercepta um determinado E e pode calcular, pelo menos em princípio, as probabilidades a posteriori para as várias mensagens P_E(M). É natural definir o secretismo perfeito pela condição de que, para todos E, as probabilidades a posteriori são iguais às probabilidades a priori, independentemente dos seus valores. Neste caso a interceptação da mensagem não deu qualquer informação ao criptoanalista ⁹. Qualquer ação do criptoanalista que dependa da informação contida neste criptograma não pode ser alterada porque todas as probabilidades do que o criptograma contém permanecem inalteradas. Por outro lado, se a condição não é satisfeita, existirão situações em que o inimigo possui certas probabilidades a priori e poderão ocorrer certas escolhas de chave e de mensagem nas quais ocorrerão alterações nas probabilidades do inimigo. Isto, por sua vez, pode afetar suas ações e, consequentemente, o segredo perfeito não foi obtido. Por esta razão a definição dada é necessariamente requerida por nossas idéias intuitivas do que um secretismo perfeito deve significar.

Uma condição necessária e suficiente para um secretismo perfeito pode ser encontrada como a seguir: Temos o teorema de Bayes

PE(M) = P(M) PM(E) / P(E)

onde

P(M) = probabilidade a priori da mensagem M.

P_M(E) = probabilidade condicional do criptograma E se a mensagem M for escolhida, isto é, a soma de todas as probabilidades de todas as chaves que produzem o criptograma E da mensagem M.

P(E) = probabilidade de obter o criptograma E de qualquer origem.

P_E(M) = probabilidade a posteriori da mensagem M se o criptograma E for interceptado.

Para um secretismo perfeito, P_E(M) precisa ser igual a P(M) para todos E e todas M. Portanto, ou P(M) = 0, uma solução que precisa ser excluída porque demandamos a igualdade independentemente dos valores de P(M), ou

PM(E) = P(E)

para cada M e E. Reciprocamente, se P_M(E) = P(E), então

PE(M) = P(M)

e temos o segredo perfeito. Portanto, temos o resultado:

TEOREMA 6

Posto de outra forma, a probabilidade total de todas as chaves que transformam M_i num dado criptograma E é igual à de todas as chaves transformando M_j no mesmo E, para todas M_i, M_j e E.

Fig. 5 - Secretismo perfeito

Agora precisam existir tantos E quantas forem M porque, para um i fixo, T_i dá uma correspondência de um-para-um entre todas as M e alguns dos E. Para um secretismo perfeito P_M(E) = P(E) <> 0 para qualquer um destes E e para qualquer M. Portanto, existe pelo menos uma chave transformando qualquer M em qualquer um destes E. Mas todas as chaves de uma M fixa para E diferentes precisam ser diferentes e, desta forma, o número de chaves diferentes é pelo menos o mesmo que o número das M. Só é possível obter o secretismo perfeito com este número de chaves, como mostrado no seguinte exemplo: Deixe M_i ser numerada de 0 a n, da mesma forma E_i e, usando n chaves, deixe que

Ti Mj = Es

onde s = i + j (Mod n). Neste caso podemos ver que P_E(M) = 1/n = P(E) e que temos um secretismo perfeito. Um exemplo é mostrado na Fig. 5 com s = i+j - 1 (Mod 5).

Sistemas perfeitos, nos quais o número de criptogramas, o número de mensagens e o número de chaves são todos iguais, são caracterizados por propriedades que (1) cada M está conectada a cada E exatamente por uma linha e (2) todas as chaves são igualmente prováveis. Portanto, a representação matricial do sistema é um "Quadrado Latino".

Na MTC foi mostrado que a informação pode ser convenientemente medida através da entropia. Se temos um conjunto de possibilidades com probabilidades p₁, p₂, ..., p_n, a entropia H é dada por:

H = - Σ pi log pi

Num sistema secreto existem duas escolhas estatísticas envolvidas, a da mensagem e a da chave. Medimos a quantidade de informação produzida quano uma mensagem é escolhida por H(M):

H(M) = - Σ P(M) log P(M)

sendo a soma referente a todas as mensagens possíveis. Analogamente existe uma incerteza associada à escolha da chave dada por:

H(K) = - Σ P(K) log P(K)

Em sistemas perfeitos do tipo descrito acima, a quantidade de informação na mensagem é no máximo log n (ocorrendo quando todas as mensagens são equiprováveis). Esta informação pode ser completamente escondida somente se a incerteza da chave for no mínimo log n. Este é o primeiro exemplo de um princípio geral que vai aparecer com frequência: não existe um limite para o que pode ser obtido com uma certa incerteza na chave - a quantidade de incerteza que podemos introduzir na solução não pode ser maior do que a incerteza da chave.

A situação é um pouco mais complicada se o número de mensagens for infinito. Suponha, por exemplo, que elas são geradas como sequências infinitas de letras através de um processo Markoff adequado. Fica claro que nenhuma chave finita dará um secretismo perfeito. Supomos, então, que a fonte da chave gere uma chave do mesmo modo, ou seja, como uma sequência infinita de símbolos. Suponha, também, que apenas um certo comprimento de chave L_K seja necessário para cifrar e decifrar um comprimento L_M de mensagem. Deixe que o logaritmo do número de letras no alfabeto da mensagem seja R_M e que o alfabeto da chave seja R_K. Então, no caso finito, fica evidente que o segredo perfeito exige

RM LM < RK LK

Este tipo de secretismo perfeito é realizado pelo sistema Vernam.

Estes resultados foram deduzidos tomando por base probabilidades das mensagens a priori desconhecidas ou arbitrárias. A chave requerida para um secretismo perfeito depende do número total de mensagens possíveis. Seria de esperar que, se o espaço de mensagem possuir uma estatística fixa conhecida, de modo que tenha uma taxa média definida de R para gerar informação, de acordo com a MTC, então a quantidade de chave necessária poderia ser reduzida em R na média em apenas na proporção R/R_M, e isto é realmente verdade. De fato, a mensagem pode ser passada através de um transdutor que elimina a redundância e reduz o comprimento esperado nesta proporção e, depois, um sistema Vernam pode ser aplicado ao resultado. Evidentemente a quantidade de chave usada por cada letra da mensagem é estatisticamente reduzida por um fator R/R_M e, neste caso, as fontes de chave e informação estão apenas alinhadas - um bit de chave oculta completamente um bit de informação da mensagem. També, é facilmente demonstrável, através dos métodos usados na MTC, que isto é o melhor que pode ser feito.

Sistemas de secretismo perfeito possuem um lugar no cenário prático - eles podem ser usados tanto onde a maior importância está ligada ao segredo completo - por exemplo, na correspondência entre os mais altos níveis de comando ou em casos onde o número de mensagens possíveis é pequeno. Portanto, para dar um exemplo extremo, se apenas duas mensagens, "sim" ou "não", foram antecipadas, um sistema perfeito seria aplicável com, talvez, uma tabela de transformação:

M K | A  B
----|-----
sim | 0  1
não | 1  0

A desvantagem de sistemas perfeitos para grandes sistemas de correspondência é, naturalmente, o volume equivalente de chave que precisa ser enviado. Nas seções subsequentes vamos analisar o que pode ser obtido com tamanhos menores de chave, em particular com chaves finitas.

9 - Um purista poderia objetar que o inimigo obteve alguma informação quando sabe que uma mensagem foi enviada. Isto pode ser respondido tendo, entre as mensagens, uma "vazia" que corresponde a "nenhuma mensagem". Se nenhuma mensagem é originada, a vazia é cifrada e enviada como criptograma. Neste caso, até este modicum de informação restante é eliminado.

Tradução vovó Vicki