Criptografia Numaboa
7. Cifras puras e mistas
Qua 28 Nov 2007 09:06 |
- Detalhes
- Categoria: Papers
- Atualização: Quarta, 17 Junho 2009 19:39
- Autor: Shannon
- Acessos: 13739
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.
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:
- Anterior
- Próximo >>