Criptografia Numaboa

Detalhes

Categoria: Papers

Atualização: Terça, 03 Junho 2008 16:07

Autor: Shannon

Acessos: 6660

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

Suponhamos que uma cifra de substituição simples tenha sido usada num texto em inglês e que interceptamos uma certa quantidade, N letras, de texto cifrado. Para um N razoavelmente grande, digamos de mais de 50 letras, com grande probabilidade haverá sempre uma solução única para a cifra, isto é, só uma boa sequência em inglês que se transforma no material interceptado através de uma substituição simples.

Entretanto, com um N menor, a chance de existir mais de uma solução é maior: com N = 15 geralmente haverá vários fragmentos de texto que se encaixam, enquanto que com N = 8 uma boa parte (da ordem de 1/8) de todas as sequências razoáveis em inglês e deste comprimento serão possíveis porque é raro haver mais de uma letra repetida nas 8. Com N = 1, qualquer letra é claramente possível e possui a mesma probabilidade a posteriori que sua probabilidade a priori. Para uma letra o sistema é perfeito.

Isto geralmente acontece com cifras que têm solução. Antes de qualquer material ser interceptado, podemos imaginar as probabilidades a priori anexadas às várias mensagens possíveis, como também às várias chaves. Assim que algum material é interceptado, o criptoanalista calcula as probabilidades a posteriori; à medida que N aumenta, as probabilidades de certas mensagens aumenta e, da maioria, diminui, até finalmente restar apenas uma que tem a probabilidade próxima de um, enquanto a probabilidade total de todas as outras se aproxima de zero.

Estes cálculos podem ser efetuados para sistemas muito simples. A tabela 1 mostra as probabilidades a posteriori para uma cifra do tipo César aplicada a um texto em inglês com a chave escolhida randomicamente dentre 26 possibilidades. Para habilitar o uso de tabelas de frequência padrão para letras, digramas e trigramas, o texto foi iniciado num ponto randômico (abrindo-se um livro e colocando-se um lápis numa página randômica). A mensagem selecionada deste modo começa com "creases to ...", começando dentro da palavra "increases". Se se sabe que a mensagem é o início de uma sentença, um conjunto de probabilidades diferente precisa ser usado para as frequências de letras, digramas, etc, que aparecem no início das sentenças.

Decifrações          N = 1    N = 2    N = 3    N = 4    N = 5
C R E A S            .028     .0377    .1111    .3673     1
D S F B T            .038     .0314
E T G C U            .131     .0881
F U H D V            .029     .0189
G V I E W            .020
H W J F X            .053     .0063
I X K G Y            .063     .0126
J Y L H Z            .001
K Z M I A            .004
L A N J B            .034     .1321    .2500
M B O K C            .025     .0222
N C P L D            .071     .1195
O D Q M E            .080     .0377
P E R N F            .020     .0818    .4389    .6327
Q F S O G            .001
R G T P H            .068     .0126
S H U Q I            .061     .0881    .0056
T I V R J            .105     .2830    .1667
U J W S K            .025
V K X T L            .009
W L Y U M            .015     .0056
X M Z V N            .002
Y N A W O            .020
Z O B X P            .001
A P C Y Q            .082     .0503
B Q D Z R            .014
H(dígitos decimais) 1.2425    .9686    .6034    .285      0

Tabela 1 - Probabilidades a posteriori para criptogramas do tipo César

A César com chave randômica é uma cifra pura e a chave escolhida não afeta as probabilidades a posteriori. Para determinar as que precisamos precisamos apenas listar todas as decifrações possíveis para todas as chaves e calcular usas probabilidades a priori. As probabilidades a posteriori são estas divididas pela sua soma. As decifrações possíveis são encontradas através do processo padrão de "correr o alfabeto" e podem ser vistas na coluna da esquerda. Estas formam a classe residual da mensagem. Para apenas uma letra interceptada, as probabilidades a posteriori são iguais às probabilidades a priori para letras ¹⁰ e são mostradas na coluna encabeçada por N = 1. Para duas letras interceptadas, as probabilidades são as dos digramas ajustados para somar a unidade e são mostradas na coluna N = 2.

Frequências de trigramas também foram tabuladas e são mostradas na coluna N = 3. As probabilidades de quatro e cinco letras sequenciais foram obtidas pela multiplicação das frequências de trigramas porque, a grosso modo,

p(ijkl) = p(ijk)pjk(l)

Observe que com três letras o campo foi reduzido para quatro mensagens de probabilidade bastante alta, sendo as outras muito pequenas se comparadas. Com quatro há apenas duas possibilidades e, com cinco, apenas uma - a decifração correta.

Em princípio, isto poderia ser aplicado a qualquer sistemas, mas, a não ser que a chave seja muito pequena, o número de possibilidades é tão grande que o trabalho envolvido torna o cálculo proibitivo.

O conjunto de probabilidades a posteriori descreve como o conhecimento do criptoanalista sobre a mensagem e sobre a chave gradualmente se torna mais preciso à medida que mais material cifrado é obtido. Esta descrição, no entanto, é muito elaborada e difícil de obter para nossos propósitos. O desejado é uma descrição simplificada desta aproximação de uma solução possível única.

Uma situação parecida ocorre na teoria da comunicação quando um sinal transmitido é perturbado por ruído. É necessário criar uma medida adequada de incerteza do que realmente foi transmitido conhecendo apenas a versão perturbada dada pelo sinal recebido. Na MTCa foi mostrado que uma medida matemática natural desta incerteza é a entropia condicional do sinal transmitido quando o sinal recebido é conhecido. Esta entropia condicional foi chamada, por conveniência, de equivocação.

Do ponto de vista do criptoanalista, um sistema secreto é praticamente idêntico a um sistema de comunicação com ruído. A mensagem (sinal transmitido) é tratada por um elemento estatístico, o sistema cifrante, com sua chave escolhida estatisticamente. O resultado desta operação é o criptograma (análogo a um sinal perturbado) que fica disponível para ser analisado. As maiores diferenças nestes dois casos são: primeiro, que a operação da transformação cifrante geralmente tem uma natureza mais complexa do que um ruído perturbador num canal; e, em segundo lugar, a chave do sistema secreto usualmente é escolhida de um conjunto finito de possibilidades enquanto que o ruído num canal geralmente é introduzido continuamente e, na verdade, escolhido de um conjunto infinito.

Com estas considerações em mente, é natural usar a equivocação como um índice de secretismo teórico. Deve ser observado que existem duas equivocações importantes, a da chave e a da mensagem. Estas serão expressas por H_E(K) e H_E(M) respectivamente. Elas são dadas por:

HE(K) = ΣE,K P(E,K) log PE(K)
HE(M) = ΣE,K P(E,M) log PE(K)

onde E, M e K são o criptograma, a mensagem e a chave e

P(E,K) é a probabilidade da chave K e do criptograma E.

P_E(K) é a probabilidade a posteriori da chave K se o criptograma E for interceptado.

P(E,M) e P_E(M) são as probabilidades similares para a mensagem ao invés da chave.

A soma em H_E(K) refere-se a todos os criptogramas possíveis de determinado comprimento (digamos N letras) e a todas as chaves. Para H_E(M), a soma é de todas as mensagens e criptogramas de comprimento N. Portanto, H_E(K) e H_E(M) são funções de N, o número de letras interceptadas. Algumas vezes, isto será indicado explicitamente escrevendo-se H_E(K,N) e H_E(M,N). Note que estas são equivocações "totais", isto é, não as dividimos por N para obter a taxa de equivocação que foi usada na MTC.

Os mesmos argumentos gerais usados para justificar a equivocação como medida de incerteza na teoria da comunicação também podem ser aplicados aqui. Notamos que uma equivocação zero requer que uma mensagem (ou chave) tenha uma probabilidade unitária, diferente de zero, que corresponde a um conhecimento completo. Considerada como uma função de N, a diminuição gradual da equivocação corresponde a um aumento do conhecimento da mensagem ou da chave original. As duas curvas de equivocação plotadas como funções de N serão denominadas de características de equivocação do sistema secreto em questão.

Os valores de H_E(K,N) e H_E(M,N) para o criptograma do tipo César considerado acima foram calculados e são dados na última linha da Tabela 1. H_E(K,N) e H_E(M,N) são iguais neste caso e são dados em dígitos decimais (isto é, a base logarítmica 10 é usada nos cálculos). Deve-se notar que aqui a equivocação é para um criptograma em particular e que a soma foi feita apenas para M (ou K), e não para E. Geralmente a soma seria para todos os criptogramas interceptados de comprimento N e daria a média da incerteza. As dificuldades computacionais são proibitivas para este tipo de cálculo geral.

10. As probabilidades para esta tabela foram obtidas nas tabelas de frequência dadas por Fletcher Pratt num livro "Secret and Urgent" publicado por Blue Ribbon Books, Nova Iorque, 1939. Apesar de não estarem completas, são suficientes para nossos propósitos.

Tradução vovó Vicki