Detalhes

Categoria: Papers

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

Autor: Shannon

Acessos: 10878

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

Parte 1 - Estrutura Matemática de Sistemas Secretos
2. Sistemas Secretos

Como primeiro passo na análise matemática da criptogafia é necessário idealizar a situação adequadamente e definir, de maneira matematicamente aceitável, o que queremos dizer com sistema secreto.
 

Um diagrama "esquemático" de um sistema secreto genérico é mostrado na Fig. 1. Na extremidade transmissora existem duas fontes de informação - uma fonte da mensagem e uma fonte da chave. A fonte da chave produz uma chave em particular dentre as chaves possíveis do sistema. Esta chave é transmitida de alguma forma, supostamente não interceptável, por exemplo por um mensageiro, para a extremidade receptora. A fonte da mensagem produz uma mensagem (a "clara"), a qual é cifrada, e o criptograma resultante é enviado à extremidade receptora através de um meio possivelmente interceptável, por exemplo rádio. Na extremidade receptora, o criptograma e a chave são combinados no decifrador para recuperar a mensagem.


É evidente que o cifrador tem uma função operacional. Se M é a mensagem, K a chave e E a mensagem cifrada ou criptograma, então temos
E = f(M,K)

ou seja, E é uma função de M e de K. Entretanto, é preferível pensar nisto não como uma função de duas variáveis, mas como uma família de operações ou transformações (de um parâmetro) e escrevê-la como
E = TiM

onde a transformação Ti, aplicada à mensagem M, produz o criptograma E. O índice i corresponde à chave particular que está sendo usada.
Genericamente, iremos assumir que há apenas um número finito de chaves possíveis e que cada uma possua uma probabilidade pi associada. Portanto, a fonte da chave é representada por um processo estatístico ou dispositivo que escolhe uma das transformações do conjunto de transformações T1, T2, ..., Tm com as respectivas probabilidades p1, p2, ..., pm. De forma análoga, iremos assumir genericamente um número finito de mensagens possíveis M1, M2, ..., Mn associadas às probabilidades a priori q1, q2, ..., qn. As mensagens possíveis, por exemplo, podem ser as sequências de letras possíveis no inglês, todas de comprimento N, e as probabilidades associadas são então relativas às frequências de ocorrência destas sequências num texto normal em inglês.
Na extremidade receptora é preciso poder recuperar M conhecendo-se E e K. Portanto, as transformações Ti da família precisam possuir inversos únicos Ti-1 de modo que TiTi-1 = I, a transformação de identidade. Portanto
M = Ti-1E

Em todos os casos, este inverso precisa existir e ser único para cada E, o qual pode ser obtido de uma M com chave i. Portanto, chegamos à definição:

  

    

Um sistema secreto é uma família de transformações Ti, reversíveis e únicas, de um conjunto de mensagens possíveis em um conjunto de criptogramas, tendo a transformação Ti uma probabilidade pi associada.
    
  

Reciprocamente, qualquer conjunto de entidades deste tipo será chamado de "sistema secreto". Por conveniência, o conjunto das mensagens possíveis será chamado de "espaço de mensagens" e o conjunto de criptogramas possíveis de "espaço de criptogramas".
Dois sistemas secretos serão iguais se forem constituídos pelo mesmo conjunto de transformações Ti, com o mesmo espaço de mensagens e criptogramas (extensão e domínio) e a mesma probabilidade para as chaves.
Um sistema secreto pode ser visualizado mecanicamente como uma máquina que possua um ou mais controles. Uma sequência de letras, a mensagem, alimenta a entrada da máquina e uma segunda série emerge na saída. A uma determinada configuração dos controles corresponde uma determinada chave que está sendo usada. Alguns métodos estatísticos precisam ser estabelecidos para a escolha de uma chave dentre todas as possíveis.
Para tornar o problema matematicamente tratável, devemos assumir que o inimigo conhece o sistema que está sendo usado, isto é, ele conhece a família de transformações Ti e as probabilidades de escolha das várias chaves. Pode ser que esta premissa seja refutada com o argumento de que esteja fora da realidade porque, com frequência, o criptanalista não conhece o sistema usado ou desconhece as probabilidades em questão. Existem duas respostas para esta objeção:

  
A restrição é muito mais fraca do que parece inicialmente devido à nossa definição ampla do que é um sistema secreto. Imagine que um criptógrafo intercepte uma mensagem e que não saiba se foi usada uma substituição por transposição ou uma cifra de Vigenère. Ele pode considerar a mensagem como tendo sido cifrada por um sistema no qual parte da chave seja a especificação de qual dos dois tipos foi usado e a parte seguinte como sendo a chave específica para este tipo. Estas três possibilidades diferentes possuem probabilidades associadas de acordo com as melhores estimativas das probabilidades a priori do cifrador, usando os respectivos tipos de cifras.
  
A premissa é a que atualmente é comumente usada em estudos criptográficos. É pessimista e portanto segura, mas, a longo prazo, realista, uma vez que a expectativa é de que nosso sistema pode ser eventualmente descoberto. Portanto, mesmo quando um sistema inteiramente novo é inventado, de modo que o inimigo não possa atribuir-lhe nenhuma probabilidade a priori antes de desvendá-lo, ainda assim é preciso conviver com a expectativa do seu eventual conhecimento.


A situação é parecida com a que ocorre na teoria dos jogos 3, onde se assume que o oponente "descobre" a estratégia de jogo que está sendo usada. Em ambos os casos, a premissa serve para delinear nitidamente o conhecimento do oponente.
Uma segunda objeção possível à nossa definição de sistemas secretos é que ela não leva em conta a prática comum da inserção de nulos em uma mensagem e o uso de substitutos múltiplos. Nestes casos não existe um criptograma único para uma dada mensagem e chave - o cifrador pode escolher à vontade dentre vários criptogramas diferentes. A situação poderia ser tratada, porém iria apenas adicionar complexidade ao presente estágio sem alterar substancialmente qualquer dos resultados básicos.
Se as mensagens forem produzidas por um processo de Markoff do tipo descrito em (1) para representar uma fonte de informação, as probabilidades das várias mensagens são determinadas pela estrutura do processo de Markoff. No momento, entretanto, queremos ter uma visão mais geral da situação e considerar as mensagens meramente como um conjunto abstrato de entidades com probabilidades associadas, não necessariamente compostas por uma sequência de letras e não necessariamente produzidas por um processo de Markoff.
Deve ser destacado que, em todo este trabalho, um sistema secreto não significa uma, mas sim um conjunto de muitas transformações. Após a escolha da chave, apenas uma destas transformações é usada e, devido a isto, pode-se ser induzido a definir um sistema secreto como uma simples transformação num idioma. O inimigo, entretanto, não sabe qual foi a chave escolhida e as chaves que "podem ter sido" são tão importantes para ele quanto a efetivamente usada. Na verdade, é apenas a existência destas outras possibilidades que confere algum segredo ao sistema. Uma vez que o segredo é nosso interesse primário, somos forçados a ficar com o conceito bastante elaborado para um sistema secreto definido acima. Este tipo de situação, onde as possibilidades são tão importantes quanto as atualidades, ocorre frequentemente em jogos de estratégia. O desenrolar de um jogo de xadrez é amplamente controlado por linhas que não são completadas. A "existência virtual" de imputações não realizadas, da teoria dos jogos, também guarda alguma semelhança.
Deve ser notado que, de acordo com a nossa definição, uma única operação numa língua produz um tipo degenerado de sistema secreto - um sistema com apenas uma chave de probabilidade unitária. Tal sistema não possui segredo - o criptanalista acha a mensagem aplicando o inverso desta transformação, a única do sistema, no criptograma interceptado. O decifrador e o criptanalista, neste caso, possuem a mesma informação. Em geral, a única diferença entre o conhecimento do decifrador e o conhecimento do criptanalista inimigo é que o decifrador conhece a chave específica que está sendo usada enquanto o criptanalista conhece apenas as probabilidades a priori das várias chaves do conjunto. O processo de decifração é o de aplicar o inverso da transformação específica usada para a cifragem do criptograma. O processo de criptanálise é o de tentar determinar a mensagem (ou a chave específica) tendo o criptograma e as probabilidades a priori das várias chaves e mensagens.
Existe uma série de difíceis questões epistemológicas associadas à teoria do secretismo ou, na realidade, com qualquer teoria que envolva questões de probabilidade (particularmente probabilidades a priori, teorema de Baye, etc.) quando aplicadas a situações físicas. Tratada abstratamente, a teoria da probabilidade pode ser enquadrada numa base lógica rigorosa através do enfoque da moderna teoria das medidas 4 5. Entretanto, aplicadas a uma situação física, especialmente quando estão envolvidas probabilidades "subjetivas" e experimentos que não podem ser repetidos, aparecem muitas questões de validade lógica. Por exemplo, no enfoque de segredo aqui utilizado, as probabilidades a priori de várias chaves e mensagens são consideradas como conhecidas pelo criptógrafo inimigo - como podemos determinar operacionalmente se suas estimativas estão corretas, baseadas no seu conhecimento da situação?
Podemos construir situações criptográficas artificiais do tipo "urn and die", nas quais as probabilidades a priori possuem um significado definido não ambíguo, e a idealização aqui usada certamente é apropriada. Em outras situações que pudermos imaginar, por exemplo uma comunicação interceptada entre marcianos invasores, as probabilidades a priori seriam provavelmente tão incertas que seriam desprovidas de significado. A maioria das situações criptográficas práticas ficam em algum ponto entre estes limites. Um criptanalista poderia ficar tentado em classificar as mensagens possíveis em categorias como "razoável", "possível porém pouco provável" e "absurdo", mas sente logo que esta subdivisão mais detalhada não faz sentido.
Felizmente, em situações práticas, apenas erros extremos nas probabilidades a priori de chaves e mensagens causam erros significantes nos parâmetros importantes. Isto se deve ao comportamento exponencial do número de mensagens e criptogramas e às medidas logarítmicas utilizadas.



1 - Shannon, C. E., "A Mathematical Theory of Communication", Bell System Technical Journal, Julho de 1948, p.379; Outubro de 1948, p.623.
3. Veja von Neumann e Morgenstern "The Theory of Games", Princeton 1947.
4. Veja J. L. Doob, "Probability as Measure", Annals of Math. Stat., v. 12, 1941, pp. 206-214.
5. A. Kolmogoroff, "Grundbegriffe der Wahrscheinlichkeitsrechnung", Ergebnisse der Mathematic, v. 2, No. 3 (Berlim 1933).

Tradução vovó Vicki  
Вадим Логофет семьясковорода для костра на природе купитьадреса никас  блендер рецептысковорода вок thomashuawei телефоныполигон ооо