Criptografia Numaboa
Quebrando uma transposição colunar com chave
Qua 28 Jan 2009 20:08 |
- Detalhes
- Categoria: Criptoanálise
- Atualização: Quarta, 28 Janeiro 2009 20:44
- Autor: vovó Vicki
- Acessos: 7209
Transposições com chaves numéricas são muito mais seguras do que as transposições colunares simples. A técnica de explorar todas as matrizes possíveis, explicada no texto Quebrando uma Transposição Geométrica Simples, não é eficaz nas transposições com chave numérica porque, mesmo encontrando a matriz correta, as letras ainda continuam embaralhadas.
Vamos analisar um texto cifrado e nunca é demais repetir: em todo procedimento de criptoanálise o importante é ter um método de trabalho e seguir um roteiro planejado. Usaremos como exemplo o texto abaixo:
UEOJE MOHSE QLREO DPUOF EUOIR IIETD APERC OIDPS OEOTS AESIU LRHGE OEXME OLIAN PCANO SDOGN ADIMR SACAA MLEEO NAICA GUEPM ADCOQ AUTIT OCXE
Roteiro de Criptoanálise
- Obter informações sobre o contexto
- Determinar se a cifra realmente é de transposição
- Determinar o formato da matriz e o método
Inicialmente vamos tentar estabelecer o idioma utilizado, pois este é um dos aspectos mais importantes do contexto. Identificar corretamente o idioma de um texto cifrado nem sempre é uma tarefa fácil, principalmente quando se trata de um texto curto. Em todo caso, a primeira providência é estabelecer a frequência de ocorrência das letras:
12 | 0 | 6 | 6 | 16 | 1 | 3 | 2 | 9 | 1 | 0 | 4 | 5 | 4 | 15 | 5 | 2 | 5 | 6 | 4 | 6 | 0 | 0 | 2 | 0 | 0 |
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
Num total de 114 caracteres, o que chama a atenção é a porcentagem de vogais (A E I O U): 50.9% ou 58 em 114. Além disto, a letra mais frequente é o E (16), seguida pelo O (15). As consoantes de alta frequência (29%) são S D C R P M, as de média frequência (18%) são T N L G X Q H e as de baixa frequência (2%) são J F.
Pelos primeiros resultados, o idioma tem uma grande probabilidade de ser o Português. Confira o texto Frequência da Ocorrência de Letras no Português.
O Índice de Coincidência pode nos revelar se se trata de uma cifra de transposição/substituição monoalfabética ou de uma substituição polialfabética. Calculando o Índice de Coincidência obtemos o valor Kappa = 0.068468, que corresponde a um IC = 1.78 (0.068468/0.0385), muito distante do IC de um texto randômico que seria 1.0 (0.0385/0.0385). Portanto, temos um forte indício de que se trata de uma transposição ou de uma substituição monoalfabética.
Se tiver dúvidas, leia o texto Identificação de Classes, analisando principalmente as Tabelas de Kullback e o Teste Kappa de Friedman.
Determinando o formato da matriz e o método
Digamos que se trata de uma transposição e que já tenham sido testadas matrizes de diversos tamanhos sem resultado. Então agora está na hora de testar uma transposição colunar com chave.
As chaves numéricas geralmente são baseadas numa frase ou numa palavra-chave. Estas podem conter letras repetidas e, nestes casos, as letras repetidas geralmente são numeradas sequencialmente da esquerda para a direita. Por exemplo:
B | A | N | A | N | A |
4 | 1 | 5 | 2 | 6 | 3 |
Nas transposições com chave, a incidência das vogais assume importância ainda maior. Sabemos que no Português cerca de 50% dos caracteres são vogais. A tentativa é obter uma matriz onde cada linha possua uma porcentagem de vogais próxima a este valor. Na hipótese de se tratar de uma matriz totalmente preenchida, os 114 caracteres podem ser arranjados em matrizes de 2x57, 3x38, 6x19, 19x6, 38x3 e 57x2. Dentre estas possibilidades, a mais provável parece ser 6x19, ou seja, a palavra-chave teria 6 letras.
123456 | Vogais | |
1 | UEOJEM | 4 |
2 | OHSEQL | 2 |
3 | REODPU | 3 (50%) |
4 | OFEUOI | 5 |
5 | RIIETD | 3 (50%) |
6 | APERCO | 3 (50%) |
7 | IDPSOE | 3 (50%) |
8 | OTSAES | 3 (50%) |
9 | IULRHG | 2 |
10 | EOEXME | 4 |
11 | OLIANP | 3 (50%) |
12 | CANOSD | 2 |
13 | OGNADI | 3 (50%) |
14 | MRSACA | 2 |
15 | AMLEEO | 4 |
16 | NAICAG | 3 (50%) |
17 | UEPMAD | 3 (50%) |
18 | COQAUT | 3 (50%) |
19 | ITOCXE | 3 (50%) |
6...35 | |
M...OE | 1 |
L...SQ | 2 |
U...OP | 3 |
I...EO | 4 |
D...IT | 5 |
O...EC | 6 |
E...PO | 7 |
S...SE | 8 |
G...LH | 9 |
E...EM | 10 |
P...IN | 11 |
D...NS | 12 |
I...ND | 13 |
A...SC | 14 |
O...LE | 15 |
G...IA | 16 |
D...PA | 17 |
T...QU | 18 |
E...OX | 19 |
Como primeira tentativa, até que não está mau - a maioria das linhas possui 3 vogais e as outras distanciam-se apenas ligeiramente do esperado. Agora é tentar encontrar a sequência correta de colunas. O processo mais utilizado é o de anagramas, ou seja, tentar encontrar sequências de caracteres plausíveis ou até mesmo palavras completas.
Uma das melhores dicas de anagramas é a letra Q que, em várias línguas, é seguida de U. O trigrama mais frequente em Português é QUE, mas não podemos nos esquecer que QUA, QUO e, mais raramente, QUI também são possibilidades que devem ser consideradas.
A 2a. e a 18a. linhas possuem a letra Q. Além disto, a linha 18 possui também a letra U. A 2a. linha não possui a letra U, porém ela aparece na linha seguinte. A única maneira de torná-las contíguas seria deslocar o Q da linha 18 para a coluna 6 e o U da linha 19 para a primeira coluna. Façamos um rearranjo das colunas 3 e 5, as que contêm Q e U na linha 18, e da coluna 6, que contém o U na terceira linha.
Observe o resultado da permutação das coluna à direita. Agora começa um verdadeiro "jogo de caça-palavras". Usando o mesmo raciocínio de Q seguido de U, podemos analisar a letra H: ou inicia uma palavra (homem, hoje, há, etc), ou faz parte de trígafos como CH..., LH..., etc. Logo na segunda linha encontramos um H e a primeira letra é o L: LH... é uma boa possibilidade, que pode ser ampliada para LHE ou LHO (porque E e O são as únicas vogais desta linha).
Logo na primeira linha ocorre o J, uma consoante de baixa frequência no Português. Vamos analisar as primeiras linhas concatenadas: M...OEL...SQU...OPI... A letra antes de duas vogais, como OE, tem grande probabilidade de ser uma consoante. Na primeira linha só resta o J. Então é válida a seguinte tentativa: M..JOEL...SQU...OPI. Agora só restam as letras U e E na primeira linha, ou seja, podemos formar MUE ou MEU. A segunda opção, sem dúvida alguma, é a melhor: MEUJOEL...SQU...OPI.
Se o rearranjo de colunas estiver correto para a primeira linha, então também estará correto para as restantes. Não custa tentar com as colunas posicionadas em 6-2-1-4-3-5:
621435 | |
1 | MEUJOE |
2 | LHOESQ |
3 | UERDOP |
4 | IFOUEO |
5 | DIREIT |
6 | OPAREC |
7 | EDISPO |
8 | STOASE |
9 | GUIRLH |
10 | EOEXEM |
11 | PLOAIN |
12 | DACONS |
13 | IGOAND |
14 | ARMASC |
15 | OMAELE |
16 | GANCIA |
17 | DEUMPA |
18 | TOCAQU |
19 | ETICOX |
O resultado obtido é MEUJOE LHOESQ UERDOP IFOUEO DIREIT OPAREC EDISPO STOASE GUIRLH EOEXEM PLOAIN DACONS IGOAND ARMASC OMAELE GANCIA DEUMPA TOCAQU ETICOX, ou seja,
MEU JOELHO ESQUERDO PIFOU E O DIREITO PARECE DISPOSTO A SEGUIR-LHE O EXEMPLO. AINDA CONSIGO ANDAR, MAS COM A ELEGÂNCIA DE UM PATO CAQUÉTICO.
Observações
O texto foi extraído de uma crônica do João Ubaldo e a palavra chave utilizada foi UBALDO. Pelo que me foi informado, este texto cifrado foi enviado para o ortopedista pelo João que, obviamente, pretendia se vingar do médico - conseguiu provocar várias fraturas neuronais no homem de branco
Brincadeiras à parte, o exemplo acima nos mostra que decifrar uma transposição é sempre uma sequência de tentativas e um enorme exercício de paciência. Uma vez identificada a língua da mensagem, as vogais e as consoantes raras constituem o mapa da mina.
Neste exemplo, a matriz é simétrica e totalmente preenchida, o que acaba facilitando o trabalho. Para matrizes com células em branco ou nas transposições triangulares ou em círculo, algumas técnicas adicionais precisam ser aplicadas.
Grande parte do presente texto foi extraído do manual de criptoanálise do exército dos EUA, especialmente do capítulo 12. O manual completo, em Inglês, está disponível para download no site da Universidade de Michigan. A identificação do manual é:
Basic Cryptanalysis *FM 34-40-2 FIELD MANUAL NO 34-40-2 HEADQUARTERS DEPARTMENT OF THE ARMY Washington, DC, 13 September 1990 |