Aldeia Numaboa UM PORTAL DIFERENTE EM PORTUGUÊS DO BRASIL

6. A Álgebra de Sistemas Secretos

Detalhes

Categoria: Papers

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

Autor: Shannon

Acessos: 8789

Teoria da Comunicação de Sistemas Secretos
C. E. Shannon

Se tivermos dois sistemas secretos T e R, com frequência podemos combiná-los de vários modos para formar um novo sistema secreto S.

Se T e R possuírem o mesmo domínio (espaço de mensagem) podemos formar um tipo de "adição ponderada",

S = pT + qR

onde p + q = 1. Esta operação consiste em primeiramente fazer uma escolha preliminar com as probabilidades p e q, determinando qual dos T e R serão usados. Esta escolha faz parte da chave de S. Após esta determinação, T ou R serão usados como definido originalmente. A chave total de S precisa especificar qual de T e R será usado e qual chave de T (ou de R) será usada.

Se T consiste das transformações T₁ , ..., T_m com probabilidades p₁ , ..., p_m e R consiste de R₁ , ..., R_k com probabilidades q₁, ..., q_k, então S = pT + qR consiste respectivamente das transformações T₁ , ..., T_m , R₁ , ..., R_k com probabilidades pp₁ , pp₂ , ..., pp_m , qq₁ , qq₂ , ..., qq_k.

Generalizando, podemos formar a soma de inúmeros sistemas.

S = p1T + p2R + ... + pmU     onde pi = 1

Notamos que qualquer sistema T pode ser escrito como a soma de operações fixas

T = p1T1 + p2T2 + ... + pmTm

sendo T_i uma operação de cifragem definida de T, correspondendo à escolha da chave i cuja probabilidade é p_i.

Uma segunda forma de combinar dois sistemas secretos é tomando o "produto", mostrado esquematicamente na Fig. 3. Suponha que T e R sejam dois sistemas e que o domínio (espaço da linguagem) de R possa ser identificado com a série (espaço de criptograma) de T. Neste caso podemos aplicar primeiro T à nossa linguagem, e depois R ao resultado deste processo de cifragem.

Fig. 3 - Produto de dois sistemas S = RT

Isto dá uma operação resultante S que escrevemos como um produto

S = RT

A chave para S é composta pelas duas chaves de T e R, onde se assume que tenham sido escolhidas independentemente e de acordo com as suas probabilidades originais. Portanto, se m chaves de T, com probabilidades

p1 p2 ... pm

são escolhidas, e n chaves de R têm as probabilidades

p'1 p'2 ... p'n

então S tem no máximo mn chaves com probabilidades p_i p^'_j. Em muitos casos, algumas das transformações por produto R_iT_j serão as mesmas e podem ser agrupadas somando-se suas probabilidades.

A cifragem por produto é usada com frequência; por exemplo, segue-se uma substituição com uma transposição ou uma transposição com uma Vigenère, ou aplica-se um código ao texto e o resultado é cifrado com uma substituição, transposição, fracionamento, etc.

Deve-se notar que a multiplicação nem sempre é comutativa (não é sempre que temos RS = SR), apesar de o ser em casos especiais, como na substituição e na transposição. Uma vez que ela representa uma operação, por definição ela é associativa. Isto é, R(ST) = (RS)T = RST.

Além disso, temos as leis

p(p'T + q'R) + qS = pp'T + pq'R + qS

(a lei da associação ponderada para a adição)

T(pR + qS) = pTR + qTS
(pR + qS)T = pRT + qST

(leis da distribuição à direita e à esquerda) e

p1T + p2T + p3R = (p1 + p2)T + p3R

Deveria ser enfatizado que estas operações combinantes de adição e de multiplicação aplicam-se aos sistemas secretos como um todo. O produto de dois sistemas TR não deve ser confundido com o produto das transformações nos sistemas T_iR_j, que também aparecem com frequência neste trabalho. O primeiro, TR, é um sistema secreto, isto é, um conjunto de transformações com probabilidades associadas; o último é uma transformação em particular. Além disso, a soma de dois sistemas pR + qT é um sistema - a soma de duas transformações não está definida. Os sistemas T e R podem comutar sem a comutação individual de T_i e R_j, isto é, se R for um sistema Beaufort de período dado, com chaves igualmente prováveis, em geral

RiRj  RjRi

mas, é claro que RR não depende da ordem; na verdade

RR = V

uma Vigenère de mesmo período com chave randômica. Por outro lado, se os elementos T_i e R_j de dois sistemas T e R comutarem, então o sistema comuta.

Um sistema cujos espaços M e E possam ser identificados, um caso muito comum quando sequências de letras são transformadas em sequências de letras, pode ser denominado de endomórfico. Um sistema endomórfico T pode ser elevado a uma potência Tⁿ.

Um sistema secreto T, cujo produto com ele mesmo é igual a T, isto é, para o qual

TT = T

será denominado de idempotente. Por exemplo, substituição simples, transposição de período p, Vigenère de período p (todos com cada chave igualmente provável) são idempotentes.

O conjunto de todos os sistemas secretos endomórficos definidos num espaço de mensagem fixo constitui uma "variedade algébrica", isto é, um tipo de álgebra, usando as operações de adição e multiplicação. De fato, as propriedades da adição e da multiplicação que discutimos podem ser resumidas da seguinte maneira:

As operações de combinação nos fornecem um meio de construir muitos tipos novos de sistemas secretos à partir de outros, como nos exemplos dados. Também podemos usá-las para descrever a situação que um criptanalista enfrenta quando tenta solucionar um criptograma de tipo desconhecido. Na realidade, ele está solucionando um sistema secreto do tipo

T = p₁A + p₂B + ... + p_rS + p^'X      p = 1

onde A, B, ..., S são tipos conhecidos de cifras, com suas p_i probabilidades a priori nesta situação, e onde p^'X corresponde à possibilidade de um tipo completamente novo e desconhecido de cifra.

Tradução vovó Vicki