Detalhes

Categoria: Papers

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

Autor: Shannon

Acessos: 13928

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