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) 


Teoria da Comunicação de Sistemas Secretos

C. E. Shannon

Parte 1 - Estrutura Matemática de Sistemas Secretos

7. Cifras puras e mistas

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 TiTj de quaisquer duas transformações no conjunto é igual a uma terceira transformação Tk no conjunto. Por outro lado, TiSj 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 Ti 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 Ti , Tj , Tk existir uma Ts 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.

Fechado
Fig. 2 - Diagrama de linhas para sistemas simples
TEOREMA 1
Numa cifra pura, as operações Ti-1Tj, as quais transformam o espaço de mensagem nele mesmo, formam um grupo cuja ordem é m, o número das diferentes chaves.

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 Ti-1Tj = Ts-1Tk para alguma s.

A operação Ti-1Tj 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 Ti 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 Ti são um grupo e igualmente prováveis, então T é pura, uma vez que

TiTj-1Tk = TiTr = Ts
TEOREMA 2
O produto de duas cifras puras que comutam é puro.

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

TiRj(TkRl)-1TmRn = TiRjRl-1Tk-1TmRn
= RuRv-1RwTrTs-1Tl
= RhTg

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 T1 ú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:

Puro
Fig. 4 - Sistema Puro

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