A Aldeia Numaboa ancestral ainda está disponível para visitação. É a versão mais antiga da Aldeia que eu não quis simplesmente descartar depois de mais de 10 milhões de pageviews. Como diz a Sirley, nossa cozinheira e filósofa de plantão: "Misericórdia, ai que dó!"

Se você tiver curiosidade, o endereço é numaboa.net.br.

Leia mais...

Criptografia Numaboa

7. Cifras puras e mistas

Qua

28

Nov

2007


09:06

(2 votos, média 5.00 de 5) 


TEOREMA 3
Num sistema puro as mensagens podem ser divididas num conjunto de "classes residuais" C1, C2, ..., Cs e os criptogramas num conjunto de classes residuais correspondente C'1, C'2, ..., C's com as seguintes propriedades:
(1) As classes residuais das mensagens são mutuamente exclusivas e contém, coletivamente, todas as mensagens possíveis. De forma similar para as classes residuais dos criptogramas.
(2) A cifragem de qualquer mensagem em Ci, com qualquer chave, produz um criptograma em C'i. A decifração de qualquer criptograma em C'i, com qualquer chave, leva a uma mensagem em Ci.
(3) O número de mensagens em Ci, digamos φi, é igual ao número de criptogramas em C'i e é um divisor de k o número de chaves.
(4) Cada mensagem em Ci pode ser cifrada em cada um dos criptogramas em C'i por exatamente k/φi chaves diferentes. De forma similar para a decifração.

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 Ci e em nenhuma outra mensagem. Sendo todas as chaves igualmente prováveis, as probabilidades a posteriori de várias mensagens são portanto

PE(M) = P(M)PM(E) / P(E) = P(M)PM(E) / ΣMP(M)PM(E) = P(M) / P(Ci)

onde M está em Ci, E está em C'i e a soma é sobre todas as mensagens em Ci. Se E e M não estiverem em classes residuais correspondentes, PE(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 PE(K) foi submetido a uma permutação entre as chaves. Portanto temos como resultado o quarto teorema.

TEOREMA 4
Num sistema puro, as probabilidades a posteriori de várias mensagens PE(M) são independentes da chave escolhidas. As probabilidades a posteriori das chaves PE(K) são as mesmas em valor porém são submetidas a uma permutação com uma escolha de chave diferente.

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 TiTk-1E. Neste caso, TiTk-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

E1 = R D H H G D S N

E2 = 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:

repete

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 Δei 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:

m1 -- m4 = c1 -- c4

m2 -- m5 = c2 -- c5

m3 -- m6 = c3 -- c6

m4 -- m7 = c4 -- c7

onde E = e1 , e2 , ... é o criptograma e m1 , m2 , ... é 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 ei nos quais nenhum ei é retirado do seu bloco de comprimento d e quaisquer dois ei 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):

e1 e2 e3 e4 e5
e6 e7 e8 e9 e10
e11 e12 . . .

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
Se T é pura então TiTj-1T = T, onde TiTj são quaisquer duas transformações de T. Inversamente, se isto for verdadeiro para qualquer TiTj num sistema T, então T é pura.

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

Nós temos T = ΣspsTs e

ΣspsTiTj-1Ts = ΣspsTs

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

pj < pi

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

pj = pi

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




Tradução vovó Vicki vovo

компромат Вадим Логофет чугунные казанылобановский александрвидеокамера купитьoltatravel лобановский александрхарьков никас

Informações adicionais