QUEBRANDO UMA TRANSPOSIÇÃO COLUNAR COM CHAVE

Transposições com chaves numéricas são muito mais seguras 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 é importante ter um método de trabalho e seguir um roteiro planejado. Usaremos como exemplo o texto abaixo:

EXEMPLO

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

Informações sobre o contexto

Fig.1 - Histograma

Inicialmente vamos tentar estabelecer o idioma utilizado. 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 de 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, chama a atenção a porcentagem de vogais (A E I O U): 50.9% ou 58 em 114. Além disso, 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 no Departamento de Estatística da Aldeia no texto Frequência da Ocorrência de Letras no Português.

Determinando o tipo de cifra

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. É hora de testar uma transposição solunar com chave.

As chaves numéricas geralmente são baseadas numa frase ou palavra chave. Estas podem conter letras repetidas e, nestes casos, as letras repetidas geralmente são numeradas 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, 50% dos caracteres são vogais. A tentativa é obter uma matriz onde cada linha possua uma porcentagem de vogais próxima deste 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, uma palavra chave de 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 disso, a 18a. linha 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 18a. linha para a sexta coluna e o U da 19a. linha para a primeira coluna. Façamos um rearranjo das colunas 3 e 5, as que contém Q e U na 18a. linha e 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, por exemplo), 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.

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 de neurônios 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