Análise de frequência

Análise de frequência é um método empregado para decifrar mensagens criptografadas por meio da análise, no texto criptografado, de padrões que se repetem constantemente, que podem indicar a ocorrência de letras ou de palavras de uso corriqueiro, tais como preposições ("de", "da"), pronomes, ("não", "sim"), etc.

Frequência de uso das letras na língua portuguesa

Análise de frequência para algoritmos de substituição simples

Num algoritmo de substituição simples, cada letra do texto plano substitui-se por outra e uma dada letra do texto plano será sempre transformada na mesma letra na mensagem cifrada. Por exemplo, todas as a se converterão em X. Um texto cifrado com uma alta frequência de letras X poderia sugerir ao criptoanalista que os X representam a letra a.

O uso básico de análise de frequências consiste em primeiro em calcular a frequência das letras que aparecem no texto cifrado e de seguida associar letras de texto plano a elas. Uma grande frequência de X poderá sugerir que as X serão correspondentes ao a, mas este nem sempre será assim , já que as letras e e o têm una frequência alta também em português. No entanto, não será nada provável que as X representem, neste caso, a letra k ou a w. Por isso, o criptoanalista poderá ter que tentar várias combinações até decifrar o texto.

Estatísticas mais complexas poderiam ser usadas, como considerar os pares de letras ou mesmo trios. Isto faz-se para proporcionar mais informação ao criptoanalista. Por exemplo, as letras q e u vão quase sempre juntas em português, enquanto que a q isolada é muito rara.

Uso na História

Primeira página de um Manuscrito para decifrar mensagens criptográficas, de Al-Kindi

A primeira explicação bem documentada da análise de frequências (de facto, de qualquer tipo de criptoanálise) foi dada no século IX pelo filósofo árabe Al-Kindi num Manuscrito para decifrar mensagens criptográficas (Ibraham, 1992). Sugeriu-se que o estudo intensivo do Corão lhe revelou que a língua árabe tinha uma característica frequência de letras. O seu uso estendeu-se e foi tão usado na Europa durante o Renascimento que se inventaram esquemas para burlar o estudo das frequências. Estas incluíam:

• O uso alternativas para as letras mais comuns. Assim, por exemplo, as letras X e Y encontradas no texto cifrado poderiam significar E no texto plano.
• Cifra polialfabética, é o uso de vários alfabetos para a cifra. Leone Alberti parece ser o primeiro a sugerir esta técnica.
• Substituição poligráfica, esquemas onde pares ou trios de letras eram cifradas como uma única unidade. Por exemplo, a cifra de Playfair, inventada por Charles Wheatstone em meados do século XIX.

Uma desvantagem de todos estes modos de derrotar a análise de frequências é que complicavam tanto a cifra como a decifração dos textos, provocando erros.

As máquinas de rotores da primeira metade do século XX (por exemplo, a Máquina Enigma) eram essencialmente imunes à análise de frequências directa, embora outros tipos de análise conseguissem descodificar as mensagens de tais máquinas.

Ligações externas

• Frequência de ocorrência de letras no Português
• Ferramenta on-line - para análise de frequência.

Bibliografia

• Hemar Godinho. Mantendo Segredos com a ajuda da Matemática. Unb: 2002.
• Kahn, David. The Codebreakers”. The Macmillan Company. New York, 1967.
• Koblitz, N. A Course in Number Theory and Criptography. Springer-Verlag: 1987.
• Shokranian, S., Soares, M., Godinho, H. ”Teoria dos Números”. Editora UnB: 1994.
• PET/UnB(1/98). ”Corpos Finitos: Teoria e Aplicações”. Trabalhos de Graduação em Matemática no. 1/98.