Detalhes

Categoria: Papers

Atualização: Terça, 03 Junho 2008 15:58

Autor: Shannon

Acessos: 15602

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

Nesta seção serão dados alguns exemplos de cifras. Estas cifras serão citadas com frequência no restante deste texto com propósitos ilustrativos.

4.1 CIFRA DE SUBSTITUIÇÃO SIMPLES

Nesta cifra, cada letra da mensagem é trocada por um substituto fixo, geralmente também uma letra. Portanto, a mensagem

M = m1m2m3m4 ...

onde m₁, m₂, ... são letras sucessivas transforma-se em

E = e1e2e3e4 ...
  = f(m1)f(m2)f(m3)f(m4) ...

onde a função f(m) é uma função com uma inversa. A chave é uma permutação do alfabeto (quando os substitutos forem letras), por exemplo, X G U A C D T B F H R S L M Q V Y Z W I E J O K N P. A primeira letra X é o substituto para o A, G é o substituto para o B, etc.

4.2 TRANSPOSIÇÃO (Período fixo d)

A mensagem é dividida em grupos de comprimento d e a permutação é aplicada ao primeiro grupo, a mesma permutação ao segundo grupo, etc. A permutação é a chave e pode ser representada por uma permutação dos primeiros d inteiros. Portanto, para d = 5, poderemos ter 2 3 1 5 4 como permutação. Isto significa que

m1 m2 m3 m4 m5 m6 m7 m8 m9 m10 ...

se transforma em

m2 m3 m1 m5 m4 m7 m8 m6 m10 m9 ...

Aplicações sequenciais de duas ou mais transposições serão chamadas de transposições compostas. Se os períodos são d₁, d₂, ..., d_n, fica claro que o resultado é uma transposição de período d, onde d é o mínimo múltiplo comum de d₁, d₂, ..., d_n.

4.3 VIGENÈRE E VARIAÇÕES

Na cifra de Vigenère a chave é constituída por uma série de d letras. Estas são escritas repetidamente abaixo da mensagem e as duas são adicionadas módulo 26 (considerando o alfabeto numerado de A=0 a Z=25). Portanto,

ei = mi + ki (mod 26)

onde k_i tem o período d no índice i. Por exemplo, com a chave G A H obtemos

A Vigenère de período 1 é chamada de cifra de César. É uma substituição simples onde cada letra de M é avançada uma quantidade fixa no alfabeto. Esta quantidade é a chave, que pode ser qualquer número de 0 a 25. As assim chamadas Beaufort e Variante Beaufort são semelhantes à Vigenère e cifram-se respectivamente pelas equações

ei = ki - mi (mod 26)
ei = mi - ki (mod 26)

A Beaufort de período um é chamada de cifra de César reversa.

A aplicação de duas ou mais Vigenère em sequência será chamada de Vigenère composta. Tem a equação

ei = mi + ki + li + ... + si (mod 26)

onde, em geral, k_i , l_i , ..., s_i têm períodos diferentes. O período das suas somas,

ki + li + ... + si

assim como na transposição composta, é o mínimo múltiplo comum dos períodos individuais.

Quando a Vigenère é usada com uma chave ilimitada, que nunca se repete, temos o sistema Vernam ⁶ com

ei = mi + ki (mod 26)

sendo o k_i escolhido ao acaso e independentemente entre 0, 1, ..., 25. Se a chave for um texto com sentido, temos a cifra de "chave corrida" ("running key").

4.4 SUBSTITUIÇÃO DIGRÂMICA, TRIGRÂMICA e N-GRÂMICA

Ao invés de substituir letras, pode-se substituir digramas, trigramas, etc. A substituição digrâmica genérica requer uma chave constituída pela permutação dos 26² digramas. Pode ser representada por uma tabela na qual a linha corresponde à primeira letra do digrama e a coluna à segunda letra, com as inscrições na tabela sendo as substituições (usualmente também digramas).

4.5 VIGENÈRE DE ALFABETO ÚNICO DESORDENADO

É uma substituição simples seguida de uma Vigenère.

ei = f(mi) + ki
mi = f -1(ei - ki)

O "inverso" deste sistema é uma Vigenère seguida de uma substituição simples.

ei = g(mi + ki)
mi = g -1(ei) - ki

4.6 SISTEMA MATRICIAL ⁷

Um dos métodos de substituição n-grâmica é operar em sucessivos n-gramas com uma matriz que possua um inverso. Assume-se que as letras estejam numeradas de 0 a 25, transformando-as em elementos de um anel algébrico. Do n-grama m₁ m₂ ... m_n de mensagem, a matriz a_ij dá um n-grama de criptograma

ei =  aij mj      i = 1, ..., n

A matriz a_ij é a chave e a decifração é feita com a matriz inversa. A matriz inversa existirá se, e somente se, a determinante |a_ij| possuir um elemento inverso no anel.

4.7 A CIFRA PLAYFAIR

Este é um tipo particular de substituição digrâmica dirigida por um alfabeto desordenado de 25 letras escrito num quadrado 5x5. (A letra J geralmente é eliminada do trabalho criptográfico - é pouco frequente e, quando ocorre, pode ser substituída pelo I.) Imagine que o quadrado chave seja como o mostrado abaixo:

O substituto para o digrama AC, por exemplo, é o par de letras nos outros cantos do retângulo definido por A e C, isto é, LO, o L ocorrendo primeiro porque está acima do A. Se as letras do digrama estiverem numa linha horizontal, como em RI, usa-se as letras que estejam à direita, DF; RF se torna DR. Se as letras estiverem numa linha vertical, são usadas as letras abaixo delas. Deste modo, PS se torna UW. Se as letras do digrama forem repetidas, pode-se usar nulos para separá-las ou elas podem ser omitidas, etc.

4.8 SUBSTITUIÇÃO COM MÚLTIPLOS ALFABETOS DESORDENADOS

Nesta cifra existe um conjunto de l substituições simples que são usadas em sequência. Se o período d for quatro então m₁ m₂ m₃ m₄ m₅ m₆ ... se torna

f1(m1)f2(m2)f3(m3)f4(m4)f1(m5)f2(m6)...

4.9 A CIFRA DE AUTOCHAVE

Um sistema do tipo Vigenère, no qual a própria mensagem ou o criptograma resultante é usado como "chave", é chamado de cifra de autochave. A cifragem é iniciada com uma "chave preparatória" (a qual, a nosso ver, é a chave inteira) e continuada com a mensagem ou criptograma deslocado de acordo com o comprimento da chave preparatória como indicado abaixo, onde a chave preparatória é COMET.

A mensagem usada como "chave"

O criptograma usado como "chave" ⁸:

4.10 CIFRAS FRACIONADAS

Nestas, cada letra é inicialmente cifrada em duas ou mais letras ou números e estes símbolos são misturados de alguma forma (por exemplo, por transposição). O resultado pode então ser retraduzido para o alfabeto original. Então, usando um alfabeto desordenado de 25 letras como chave, podemos traduzir as letras em números quinários de dois dígitos usando a tabela:

Desta forma, B se torna 41. Depois que a série resultante de números é transposta de alguma forma, eles são tomados em pares e traduzidos de volta para letras.

4.11 CÓDIGOS

Nos códigos, as palavras (ou, algumas vezes, as sílabas) são trocadas por grupos de letras substitutas. Algumas vezes uma cifra de um tipo ou de outro é aplicada ao resultado.

6. G. S. Vernam, "Cipher Printing Telegraph Systems for Secret Wire and Radio Telegraphic Communications", Journal American Institute of Electrical Engineers, v. XLV, pp. 109-115, 1926.

7. Veja L. S. Hill, "Cryptography in an Algebraic Alphabet", American Math. Monthly, v. 36, No. 6, 1, 1929, pp. 306-312; também "Concerning Certain Linear Transformation Apparatus of Cryptography", v. 38, No. 3, 1931, pp. 135-154.

8. Este sistema é trivial do ponto de vista do segredo uma vez que, com exceção das primeiras d letras, o inimigo estará de posse da "chave" inteira.

Tradução vovó Vicki