Detalhes

Categoria: Papers

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

Autor: Shannon

Acessos: 13922

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

Certos tipos de cifras, como a substituição simples, a transposição por um período dado, a Vigenère por um período dado, a Vigenère com alfabeto desordenado, etc, (todas com cada chave igualmente provável) possuem uma certa homogeneidade em relação à chave. Seja qual for a chave, os processos de cifragem, decifração e desencriptação são essencialmente os mesmos.

Isto pode ser contrastado com a cifra

pS + qT

onde S é uma substituição simples e T uma transposição de um dado período. Neste caso, todo o sistema muda quanto à cifragem, decifração e desencriptação, dependendo se é a substituição ou a transposição que está sendo usada.

A causa da homogeneidade destes sistemas deriva da propriedade do grupo - notamos que, nos exemplos acima de cifras homogêneas, o produto T_iT_j de quaisquer duas transformações no conjunto é igual a uma terceira transformação T_k no conjunto. Por outro lado, T_iS_j simplesmente não se iguala a qualquer transformação na cifra

pS + qT

a qual contém apenas substituições e transposições, e não produtos.

Podemos definir uma cifra "pura", então, como uma cujas T_i formam um grupo. Isto, entretanto, seria muito restritivo uma vez que requer que o espaço E seja o mesmo que o espaço M, ou seja, que o sistema seja endomórfico. A transposição fracionada é tão homogênea quanto a transposição ordinária, mesmo não sendo endomórfica. A definição mais apropriada é a seguinte: Uma cifra T é pura se, para cada T_i , T_j , T_k existir uma T_s de modo que

TiTj-1Tk = Ts

e se cada chave for igualmente provável. De outra forma, a cifra é mista. Os sistemas da Fig. 2 são mistos. A Fig. 4 é pura se todas as chaves forem igualmente prováveis.

Fig. 2 - Diagrama de linhas para sistemas simples

TEOREMA 1

Para

Tj-1TkTk-1Tj = I

de modo que cada elemento tenha um inverso. A lei associativa é verdadeira desde que estas sejam operações e que a propriedade de grupo derive de

Ti-1TjTk-1Tl = Ts-1TkTk-1Tl = Ts-1Tl

usando nossa suposição de que T_i^-1T_j = T_s^-1T_k para alguma s.

A operação T_i^-1T_j significa, evidentemente, cifrar a mensagem com a chave j e depois decifrar com a chave i, o que nos traz de volta ao espaço de mensagem. Se T for endomórfica, isto é, as próprias T_i transformam o espaço Ω_M nele mesmo (como no caso da maioria das cifras onde tanto o espaço de mensagem quanto o espaço de criptograma consistem de sequências de letras) e as T_i são um grupo e igualmente prováveis, então T é pura, uma vez que

TiTj-1Tk = TiTr = Ts

TEOREMA 2

Para, se T e R comutam, T_iR_j = R_lT_m para cada i,j com l,m apropriados e

Entretanto, a condição de comutação não é necessária para o produto ser uma cifra pura.

Um sistema com apenas uma chave, isto é, com uma operação T₁ única e definida, é puro desde que a única escolha de índices for

T1T1-1T1 = T1

Então a expansão de uma cifra genérica numa soma de tais transformações simples também a exibe como uma soma de cifras puras.

Um exame do exemplo de uma cifra pura mostrado na Fig. 4 revela certas propriedades. As mensagens caem em certos subconjuntos, os quais chamaremos de classes residuais, e os criptogramas possíveis estão divididos em classes residuais correspondentes. Existe pelo menos uma linha de cada mensagem duma classe para cada criptograma da classe correspondente, e não existem linhas entre classes que não tenham correspondência. O número de mensagens numa classe é um divisor do número total de chaves. O número de linhas "em paralelo" de uma mensagem M para um criptograma da classe correspondente é igual ao número de chaves dividido pelo número de mensagens da classe que contém a mensagem (ou criptograma). É mostrado no apêndice que isto, em geral, se mantém para cifras puras. Resumindo formalmente temos:

Fig. 4 - Sistema Puro