Detalhes

Categoria: Papers

Atualização: Terça, 03 Junho 2008 13:48

Autor: Shannon

Acessos: 13054

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

Os problemas da criptografia e dos sistemas secretos proporcionam uma aplicação interessante da teoria da comunicação ¹. Neste ensaio é desenvolvida uma teoria dos sistemas secretos. A abordagem é em nível teórico e sua pretensão é a de complementar o tratamento encontrado em trabalhos padrão de criptografia ² nos quais é feito um estudo detalhado dos muitos tipos padrão de códigos e cifras e das formas de quebrá-los. Nós daremos uma atenção maior à estrutura matemática geral e às propriedades dos sistemas secretos.

O tratamento, de certo modo, é limitado. Primeiro, existem três tipos de sistemas secretos: (1) Sistemas de encobrimento, incluindo métodos como tinta invisível, ocultação de mensagens em textos inocentes ou num falso criptograma de cobertura, ou outros métodos nos quais a existência de uma mensagem é escondida do inimigo; (2) Sistemas de privacidade, por exemplo inversão de fala, nos quais são necessários equipamentos especiais para recuperar a mensagem; (3) Sistemas secretos "verdadeiros", onde o significado da mensagem é escondido por cifras, códigos, etc, apesar da sua existência não ser ocultada e se assume que o inimigo possua todos os equipamentos especiais necessários para interceptar e gravar o sinal transmitido. Consideramos apenas o terceiro tipo - sistemas de encobrimento são primariamente um problema psicológico e sistemas de privacidade são um problema tecnológico.

Em segundo lugar, o tratamento é limitado a casos de informação discreta, onde a mensagem que deve ser cifrada consiste numa sequência de símbolos discretos escolhidos de um conjunto finito. Estes símbolos podem ser letras de um idioma, palavras de uma língua, níveis de amplitude de uma fala ou sinais de vídeo "quantizados", etc, porém a ênfase e a preocupação maior foi com o caso das letras.

O ensaio é divido em três partes. Os principais resultados serão resumidos a seguir. A primeira parte lida com a estrutura matemática básica dos sistemas secretos. Assim como na teoria da comunicação, um idioma é considerado como sendo representado por um processo estocástico que produz uma sequência discreta de símbolos de acordo com algum sistema de probabilidades. Associado ao idioma, há um certo parâmetro D, o qual denominaremos redundância da linguagem. D mede, de alguma forma, quanto o comprimento de um texto, neste idioma, pode ser reduzido sem perder qualquer informação. Como um exemplo simples, uma vez que U sempre segue o Q em palavras em inglês, o U pode ser omitido sem perdas. Reduções consideráveis são possíveis em inglês devido à estrutura estatística da língua, a alta frequência de certas letras ou palavras, etc. A redundância tem uma importância central no estudo dos sistemas secretos.

Um sistema secreto é definido abstratamente como sendo um conjunto de transformações de um espaço (o conjunto das mensagens possíveis) em um segundo espaço (o conjunto dos criptogramas possíveis). Cada determinada transformação do conjunto corresponde a uma cifragem com uma determinada chave. Espera-se que as transformações sejam reversíveis (não-singulares), de modo que uma decifração única seja possível quando a chave é conhecida.

Considera-se que cada chave, e portanto cada transformação, tenha uma possibilidade a priori associada - a probabilidade de escolher esta chave. De forma semelhante, considera-se que cada mensagem possível tenha uma probabilidade a priori associada, determinada pelo processo estocástico subjacente. Na verdade, estas probabilidades para as várias chaves e mensagens são as probabilidades a priori do criptanalista inimigo para as escolhas em questão e representam seu conhecimento a priori da situação.

Para usar o sistema, primeiramente uma chave é escolhida e enviada para o ponto receptor. A escolha da chave determina uma transformação específica no conjunto que forma o sistema. Depois, uma mensagem é selecionada e a transformação específica correspondente à chave selecionada é aplicada a esta mensagem para produzir o criptograma. O criptograma é transmitido ao ponto receptor por um canal e pode ser interceptado pelo "inimigo" *. Ao final da recepção, o inverso da transformação específica é aplicada ao criptograma para recuperar a mensagem original.

Se o inimigo intercepta o criptograma, ele pode calcular a partir dele as probabilidades a posteriori das várias mensagens e chaves possíveis que possam ter produzido o criptograma. Este conjunto de probabilidades a posteriori constituem seu conhecimento sobre a chave e a mensagem após a interceptação. Portanto, o "conhecimento" é identificado pelo conjunto de proposições associadas às suas probabilidades. O cálculo das probabilidades a posteriori é o problema genérico da criptanálise.

Como exemplo destas noções, numa cifra de substituição simples com chave randômica, existem 26! transformações que correspondem a 26! maneiras como podem ser substituídas as 26 letras diferentes. Todas são igualmente prováveis, portanto, cada uma tem uma probabilidade a priori de 1/26!. Se isto for aplicado ao "inglês normal", assumindo que o criptanalista saiba apenas que a mensagem corresponda a um texto em inglês e nada mais, as probabilidades a priori de várias mensagens de N letras são meramente suas frequências relativas em textos normais em inglês.

Se o inimigo intercepta N letras de criptogramas neste sistema, suas probabilidades mudam. Se N for grande o suficiente (digamos 50 letras), geralmente existe a probabilidade a posteriori próxima de um de ser uma mensagem, enquanto que todas as outras têm a probabilidade total próximas de zero. Portanto, existe uma "solução" essencialmente única para o criptograma. Para um N menor (digamos N = 15), usualmente existirão muitas mensagens e chaves com probabilidade comparável, com nenhuma única próxima a um. Neste caso, existem "soluções" múltiplas para o criptograma.

Considerando que um sistema secreto seja representado desta forma, como um conjunto de transformações de um conjunto de elementos em outro, há duas operações naturais de combinação que produzem um terceiro sistema a partir de dois sistemas dados. A primeira operação de combinação é chamada de operação de produto e corresponde à cifragem da mensagem com o primeiro sistema secreto R e à cifragem do criptograma resultante com o segundo sistema S, sendo as chaves para R e S escolhidas independentemente. Esta operação total é um sistema secreto cujas transformações consistem de todos os produtos (no sentido usual de produtos de transformações) das trasnformações em S com transformações em R. As probabilidade são os produtos das probabilidades das duas transformações.

A segunda operação de combinação é a "adição ponderada".

T = pR + qS      p + q = 1

Ela corresponde a fazer uma escolha preliminar de qual sistema deve ser usado, R ou S, com as respectivas probabilidades p e q. Quando isto for feito, R ou S é usado como definido originalmente.

Já foi demonstrado que sistemas secretos com estas duas operações de combinação formam essencialmente uma "álgebra associativa linear" com um elemento unitário, uma variedade algébrica que foi extensivamente estudada por matemáticos.

Entre os muitos sistemas secretos possíveis existe um com muitas propriedades especiais. Este tipo denominamos de sistema "puro". Um sistema é puro quando todas as chaves são igualmente prováveis e quando, para quaisquer três transformações T_i, T_j, T_k no conjunto, o produto

TiTj-1Tk

também é uma transformação no conjunto. Isto é, cifragem, decifração e cifragem com quaisquer três chaves precisam ser equivalentes à cifragem com alguma chave.

Com uma cifra pura foi demonstrado que todas as chaves são essencialmente equivalentes - todas produzem o mesmo conjunto de probabilidades a posteriori. Além disso, quando um dado criptograma é interceptado, existe um conjunto de mensagens que podem ter produzido o criptograma (uma "classe residual") e as probabilidades a posteriori da mensagem desta classe são proporcionais às probabilidades a priori. Toda informação que o inimigo obteve interceptando o criptograma é uma especificação da classe residual. Muitas das cifras comuns são sistemas puros, inclusive a substituição simples com chave randômica. Neste caso, a classe residual consiste de todas as mensagens com o mesmo padrão de repetição de letras do criptograma interceptado.

Dois sistemas, R e S, são ditos "semelhantes" quando existir uma transformação fixa A com uma inversa, A^-1, de modo que

R = AS

Se R e S são semelhantes, pode-se obter uma correspondência um-para-um entre os criptogramas resultantes, levando às mesmas probabilidades a posteriori. Os dois sistemas são criptanaliticamente idênticos.

A segunda parte do ensaio lida com o problema do "secretismo teórico". Qual é a segurança de um sistema em relação à criptanálise quando o inimigo possui tempo e pessoal ilimitados, disponíveis para a análise do criptograma interceptado? O problema está estreitamente relacionado a questões de comunicação na presença de ruído e os conceitos de entropia e equivocação desenvolvidos para o problema da comunicação têm uma aplicação direta nesta parte da criptografia.

O "segredo perfeito" é definido como a exigência de que um sistema, após a interceptação de um criptograma representando várias mensagens, possua exatamente as mesmas probabilidades a priori das mesmas mensagens antes da interceptação. Foi demonstrado que o segredo perfeito é possível porém, se o número de mensagens for finito, requer o mesmo número de chaves possíveis. Se a mensagem for gerada constantemente numa determinada "taxa" (a ser definida posteriormente), a chave precisa ser gerada a uma taxa igual ou maior.

Se um sistema secreto com chaves finitas for usado e N letras do criptograma forem interceptadas, haverá, para o inimigo, um certo conjunto de mensagens com certas probabilidades que este criptograma poderia representar. À medida que N aumenta, o campo geralmente se estreita até que, eventualmente, haja uma solução "única" para o criptograma; uma mensagem com probabilidade essencialmente unitária enquanto todas as outras são praticamente zero. Uma quantidade H(N) é definida, denominada de equivocação, e mede de forma estatística o quanto o criptograma médio, de N letras, está próximo de uma solução única; isto é, o grau de incerteza que o inimigo tem em relação à mensagem original depois de interceptar um criptograma de N letras. Várias propriedades da equivocação são deduzidas - por exemplo, a equivocação da chave nunca aumenta com o aumento de N. Esta equivocação é um índice de secretismo teórico - teórico pelo fato de permitir que o inimigo use um tempo ilimitado para analisar o criptograma.

É determinada a função H(N) para um certo tipo idealizado de cifra, chamada de cifra randômica. Com certas modificações, esta função pode ser aplicada a vários casos de interesse prático. Isto proporciona um meio de calcular aproximadamente quanto material interceptado é necessário para se obter a solução de um sistema secreto. Através desta análise fica evidenciado que, em idiomas comuns e com os tipos usuais de cifras (não códigos), esta "distância da unicidade" é aproximadamente H(K)/D. Aqui, H(K) é um número que mede o "tamanho" do espaço da chave. Se todas as chaves forem a priori igualmente prováveis, H(K) é o logaritmo do número de chaves possíveis. D é a redundância da língua e mede a quantidade de "repressão estatística" imposta pelo idioma. Na substituição simples com chave randômica, H(K) é log₁₀26!, ou aproximadamente 20, e D (em dígitos decimais por letra) é cerca de 0.7 para o inglês. Portanto, a unicidade ocorre depois de cerca de 30 letras.

É possível contruir sistemas secretos com uma chave finita para certas "línguas" nas quais a equivocação não se aproxime de zero à medida que N->infinito (N tenda ao infinito). Neste caso, independentemente da quantidade de material interceptado, o inimigo não obtém uma solução única para a cifra. Restam-lhe muitas alternativas, todas de probabilidade razoável. Tais sistemas chamamos de sistemas ideais. É possível, em qualquer idioma, aproximar-se de tal comportamento - isto é, fazer com que a aproximação de zero de H(N) devolva um N arbitrariamente grande. Entretanto, estes sistemas possuem algumas limitações, como a complexidade e a susceptibilidade a erros na transmissão do criptograma.

A terceira parte deste ensaio é dedicada ao "secretismo prático". Dois sistemas com o mesmo tamanho de chave podem ser solucionados de forma única quando N letras tiverem sido interceptadas, porém diferem muito quanto ao volume de trabalho necessário para obter a solução. É feita uma análise da fraqueza básica dos sistemas secretos. Isto leva a métodos para a construção de sistemas que vão requerer uma grande quantidade de trabalho para serem solucionados. Finalmente, discute-se uma certa incompatibilidade entre as várias qualidades desejadas para sistemas secretos.