Criptografia Numaboa
12. Propriedades da Equivocação
|
Sex 30 Nov 2007 08:22 |
- Detalhes
- Categoria: Papers
- Atualização: Terça, 03 Junho 2008 16:08
- Autor: Shannon
- Acessos: 6719
Teoria da Comunicação de Sistemas Secretos
C. E. Shannon
Parte II - Secretismo Teórico
12. Propriedades da Equivocação
A equivocação possui várias propriedades interessantes, a maioria das quais se encaixa na nossa figura intuitiva de como um valor deste tipo deveria se comportar. Primeiro vamos mostrar que a equivocação da chave ou de uma parte fixa da mensagem diminui quando mais material cifrado é interceptado.
TEOREMA 7
| A equivocação da chave HE(K,N) é uma função não-incrementativa de N. A equivocação das primeiras A letras da mensagem é uma função não-incrementativa do número N que foi interceptado. Se N letras foram interceptadas, a equivocação das primeiras N letras da mensagem é menor ou igual à da chave. Isto pode ser escrito: HE(K, S) < HE(K,N) S>N HE(M, S) < HE(M,N) S>N (H para A primeiras letras de texto) HE(M,N) < H E(K,N) |
A qualificação relativa a A letras no segundo resultado do teorema é tal de modo que a equivocação será calculada de acordo com a quantidade de mensagem que foi interceptada. Se for, a equivocação da mensagem (isto usualmente ocorre) aumenta por um tempo devido meramente ao fato de que mais letras fornecem um espaço possível maior de mensagens. Os resultados do teorema são o que se poderia esperar de um bom índice de segredo porque dificilmente esperamos estar numa situação pior depois de interceptar material adicional. O fato de poderem ser provados é uma justificativa adicional para se usar a medida da equivocação.
Os resultados deste teorema são uma consequência de certas propriedades da entropia condicional provada na MTC. Portanto, para demonstrar a primeira ou a segunda declaração do Teorema 7, temos para qualquer chance os eventos A e B
H(B)> HA(B)
Se identificarmos B com a chave (conhecendo as primeiras S letras do criptograma) e A com as N - S letras restantes, obtemos o primeiro resultado. De forma semelhante, identificando B com a mensagem dá o segundo resultado. O último resultado deriva de
HE(M)<HE(K,M) = HE(K)+HE,K(M)
e do fato de que HE,K(M) = 0 uma vez que K e E determinam uma M única.
Como a mensagem e a chave são escolhidas de forma independente, temos:
H(M,K) = H(M) + H(K)
Além disto
H(M,K) = H(E,K) = H(E) + HE(K)
sendo a primeira igualdade resultante do fato de que o conhecimento de M e K ou de E e K é equivalente ao conhecimento de todos os três. Combinando os dois obtemos a fórmula para a equivocação da chave:
HE(K) = H(M) + H(K) - H(E)
Em particular, se H(M) = H(E) então a equivocação da chave, HE(K), é igual à incerteza a priori da chave, H(K). Isto ocorre em sistemas perfeitos descritos acima.
A fórmula para a equivocação da mensagem pode ser encontrada de forma parecida. Temos
H(M,E) = H(E) + HE(M) = H(M) + HM(E) HE(M) = H(M) + HM(E) - H(E)
Se temos um sistema de produto S = TR, é de se esperar que o segundo processo de cifragem diminuirá a equivocação da mensagem. Que isto é realmente verdade pode ser demonstrado como a seguir: Deixe M, E1, E2 serem a mensagem e a primeira e segunda cifragens respectivamente. Então
PE1E2(M) = PE1(M)
Consequentemente
HE1E2(M) = HE1(M)
Como, para quaisquer variáveis de chance x, y, z, Hxy(z)<Hy(z), temos o resultado desejado, HE2(M) > HE1(M).
TEOREMA 8
| A equivocação de uma mensagem em um sistema de produto S = TR não é menor do que quando R é usado. |
Suponha agora que temos um sistema T que pode ser expresso como uma soma ponderada de vários sistemas R, S, ..., U
T = p1R + p2S + ... + pmU Σpi = 1
e que os sistemas R, S, ..., U têm equivocações H1, H2, H3, ..., Hm.
TEOREMA 9
| A equivocação H de uma soma ponderada de sistemas está ligada pelas desigualdades ΣpiHi < H < ΣpiHi - Σpi log pi Estes são os melhores limites possíveis. Os H podem ser equivocações tanto da chave, quanto da mensagem. |
O limite superior é obtido, por exemplo, em sistemas fortemente ideais (que serão descritos mais tarde) onde a decomposição é feita em transformações simples do sistema. O limite inferior é obtido se todos os sistemas R, S, ..., U vão para espaços de criptogramas completamente diferentes. Este teorema também é provado pelas desigualdades gerais que governam a equivocação,
HA(B) < H(B) < H(A) + HA(B)
Identificamos A com um determinado sistema que esteja sendo usado e B com a chave ou a mensagem.
Existe um teorema semelhante para as somas ponderadas de linguagens. Neste, identificamos A com um determinado idioma.
TEOREMA 10
| Suponha que um sistema possa ser aplicado às linguagens L1, L2, ..., Lm e tenha características de equivocação H1, H2, ..., Hm. Quando aplicada à soma ponderada ΣpiLi, a equivocação H é ligada por ΣpiHi < H < ΣpiHi - Σpi log pi Estes limites são os melhores possíveis e as equivocações em questão podem ser tanto da chave quanto da mensagem. |
A redundância total DN para N letras da mensagem é definida por
DN = log G - H(M)
onde G é o número total de mensagens de comprimento N e H(M) é a incerteza de escolher uma delas. Em sistemas de secretismo onde o número total de criptogramas possíveis é igual ao número de mensagens possíveis de comprimento N, H(E) < log G. Consequentemente,
HE(K) < H(K) + H(M) - H(E)
> H(K) - [ log G - H(M)]
portanto
H(K) - HE(K) < DN
Isto mostra que, em sistemas fechados, por exemplo, a diminuição da equivocação da chave depois de N letras foi interceptada e não é maior do que a redundância de N letras do idioma. Nestes sistemas, que compreendem a maior parte das cifras, é apenas a existência da redundância nas mensagens originais que possibilita uma solução.
Suponha agora que temos um sistema puro. Deixe que classes diferentes de resíduos de mensagens sejam C1, C2, C3, ..., Cr e que o conjunto correspondente de classes de resíduos de criptogramas seja C'1, C'2, C'3, ..., C'r. A probablidade de cada E em C1 é a mesma:
P(E) = P(Ci) / φi onde E é um membro de Ci
onde φi é o número de diferentes mensagens em Ci. Portanto, temos
H(E) = - Σi φi ( P(Ci) / φi ) log ( P(Ci) / φi ) H(E) = - Σi P(Ci) log ( P(Ci) / φi )
Substituindo na nossa equação HE(K) obtemos:
TEOREMA 11
| Para uma cifra pura HE(K) = H(K) + H(M) + Σi P(Ci) log ( P(Ci) / φi ) |
Este resultado pode ser usado para calcular HE(K) em certos casos de interesse.
Tradução vovó Vicki 