Criptografia Numaboa
4. Alguns exemplos de sistemas secretos
Ter 27 Nov 2007 10:22 |
- Detalhes
- Categoria: Papers
- Atualização: Terça, 03 Junho 2008 15:58
- Autor: Shannon
- Acessos: 15567
Teoria da Comunicação de Sistemas Secretos
C. E. Shannon
Parte 1 - Estrutura Matemática de Sistemas Secretos
4. Alguns exemplos de sistemas secretos
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 m1, m2, ... 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 d1, d2, ..., dn, fica claro que o resultado é uma transposição de período d, onde d é o mínimo múltiplo comum de d1, d2, ..., dn.
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 ki tem o período d no índice i. Por exemplo, com a chave G A H obtemos
mensagem | N O W I S T H E ... |
chave repetida | G A H G A H G A ... |
criptograma | T O D O S A N E ... |
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, ki , li , ..., si 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 6 com
ei = mi + ki (mod 26)
sendo o ki 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 262 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 7
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 m1 m2 ... mn de mensagem, a matriz aij dá um n-grama de criptograma
ei = aij mj i = 1, ..., n
A matriz aij é a chave e a decifração é feita com a matriz inversa. A matriz inversa existirá se, e somente se, a determinante |aij| 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:
L | Z | Q | C | P |
A | G | N | O | U |
R | D | M | I | F |
K | Y | H | V | S |
X | B | T | E | W |
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 m1 m2 m3 m4 m5 m6 ... 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"
Mensagem | S | E | N | D | S | U | P | P | L | I | E | S | ... |
Chave | C | O | M | E | T | S | E | N | D | S | U | P | ... |
Criptograma | U | S | Z | H | L | M | T | C | O | A | Y | H | ... |
O criptograma usado como "chave" 8:
Mensagem | S | E | N | D | S | U | P | P | L | I | E | S | ... |
Chave | C | O | M | E | T | U | S | Z | H | L | O | H | ... |
Criptograma | U | S | Z | H | L | O | H | O | S | T | S | Z | ... |
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:
0 | 1 | 2 | 3 | 4 | |
0 | L | Z | Q | C | P |
1 | A | G | N | O | U |
2 | R | D | M | I | F |
3 | K | Y | H | V | S |
4 | X | B | T | E | W |
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