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

Informações adicionais