Criptografia Numaboa

Detalhes

Categoria: Papers

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

Autor: Shannon

Acessos: 13274

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

TEOREMA 3

A importância do conceito de cifra pura (e a razão para o nome) reside no fato de que, na cifra pura, todas as chaves são essencialmente as mesmas. Seja qual for a chave usada para uma mensagem em particular, as probabilidades a posteriori de todas as mensagens são iguais. Para ver isto, note que duas chaves diferentes aplicadas à mesma mensagem levam a dois criptogramas na mesma classe residual, digamos C^'_i. Por isso, os dois criptogramas poderiam, cada um, serem decifrados por k/φ_i chaves em cada mensagem de C_i e em nenhuma outra mensagem. Sendo todas as chaves igualmente prováveis, as probabilidades a posteriori de várias mensagens são portanto

P_E(M) = P(M)P_M(E) / P(E) = P(M)P_M(E) / Σ_MP(M)P_M(E) = P(M) / P(C_i)

onde M está em C_i, E está em C^'_i e a soma é sobre todas as mensagens em C_i. Se E e M não estiverem em classes residuais correspondentes, P_E(M) = 0.

Pode ser mostrado de forma análoga que as probabilidades a posteriori das diferentes chaves são as mesmas em valor, porém estes valores estão associados a chaves diferentes quando uma chave diferente é usada. O mesmo conjunto de valores de P_E(K) foi submetido a uma permutação entre as chaves. Portanto temos como resultado o quarto teorema.

TEOREMA 4

A grosso modo podemos dizer que, numa cifra pura, qualquer escolha de chave leva ao mesmo problema criptanalítico. Uma vez que as diferentes chaves resultam em criptogramas da mesma classe residual, isto significa que todos os criptogramas da mesma classe residual são criptanaliticamente equivalentes - eles levam às mesmas probabilidades a posteriori de mensagens e, independentemente de uma permutação, às mesmas probabilidade de chaves.

Como um exemplo disso, a substituição simples com todas as chaves igualmente prováveis é uma cifra pura. A classe residual correpondente de um dado criptograma E é o conjunto de todos os criptogramas que podem ser obtidos de E por operações T_iT_k^-1E. Neste caso, T_iT_k^-1 é ela própria uma substituição e, consequentemente, qualquer substituição em E resulta num outro membro da mesma classe residual. Desta forma, se o criptograma for

E = X C P P G C F Q

então

E₁ = R D H H G D S N

E₂ = A B C C D B E F

etc estão na mesma classe residual. É óbvio neste caso que estes criptogramas são essencialmente equivalentes. Tudo que é de importância numa substituição simples com chave randômica é o padrão das repetições de letras, sendo as próprias letras variáveis sem importância (dummy variables). Na verdade podemos dispensá-las totalmente, indicando o padrão das repetições em E como a seguir:

Esta notação descreve a classe residual porém elimina toda informação do membro específico da classe. Desta forma, deixa precisamente apenas a informação que é criptanaliticamente pertinente. Isto está relacionado a um método de ataque a cifras de substituição simples - o método das palavras padrão.

Na cifra do tipo César, apenas as primeiras diferenças mod 26 do criptograma são significantes. Dois criptogramas com o mesmo Δe_i estão na mesma classe residual. Quebra-se esta cifra pelo processo simples de anotar os 26 membros da classe residual da mensagem e de escolher aquela que faz sentido.

A Vigenère de período d com chave randômica é um outro exemplo de cifra pura. Aqui a classe residual da mensagem consiste de todas as sequências com a mesmas primeiras diferenças como criptograma, para letras separadas pela distância d. Para d = 3 a classe residual é definida por:

m₁ -- m₄ = c₁ -- c₄

m₂ -- m₅ = c₂ -- c₅

m₃ -- m₆ = c₃ -- c₆

m₄ -- m₇ = c₄ -- c₇

onde E = e₁ , e₂ , ... é o criptograma e m₁ , m₂ , ... é qualquer M na classe residual correspondente.

Na cifra de transposição de período d com chave randômica, a classe residual consiste de todos os arranjos dos e_i nos quais nenhum e_i é retirado do seu bloco de comprimento d e quaisquer dois e_i numa distância d permanecem nesta distância. Isto é usado para quebrar estas cifras da seguinte maneira: O criptograma é escrito em blocos sucessivos de comprimento d, um abaixo do outro como mostrado abaixo (d = 5):

As colunas são então separadas e rearranjadas para fazer um texto com sentido. Quando as colunas são separadas, a única informação que sobra é a classe residual do criptograma.

TEOREMA 5

A primeira parte deste teorema é óbvia pela definição de um sistema puro. Para provar a segunda parte, notamos primeiramente que, se T_iT_j^-1T = T, então T_iT_j^-1T_s é uma transformação de T. Resta mostrar que todas as chaves são equiprováveis.

Nós temos T = Σ_sp_sT_s e

Σ_sp_sT_iT_j^-1T_s = Σ_sp_sT_s

O termo à esquerda somado a s = j produz p_jT_i. O único termo em T_i, à direita, é p_iT_i. Uma vez que todos os coeficientes são não-negativos, a consequência é

p_j < p_i

O mesmo argumento é válido com i e j trocados e consequentemente

p_j = p_i

e T é puro. Portanto, a condição que T_iT_j^-1T = T pode ser usada como uma definição alternativa de um sistema puro.

Tradução vovó Vicki