A análise de frequência ou análise de frequência é um método de criptoanálise cuja descrição mais antiga é realizada por Al-Kindi , no IX th século . Consiste em examinar a frequência das letras usadas em uma mensagem criptografada . Este método é freqüentemente usado para decodificar mensagens criptografadas por substituição, um exemplo muito simples disso é a cifra de César .
A análise de frequência é baseada no fato de que em cada idioma certas letras ou combinações de letras aparecem com certa frequência. Por exemplo, em Francês, o e é a letra mais utilizado, seguido pela um e os s . Por outro lado, w é pouco usado.
Essas informações permitem que os criptanalistas façam suposições sobre o texto não criptografado, desde que o algoritmo de criptografia mantenha a distribuição de frequências, o que é o caso das substituições monoalfabéticas e polialfabéticas.
Uma segunda condição necessária para a aplicação dessa técnica é o comprimento do criptograma . Na verdade, um texto muito curto não reflete necessariamente a distribuição geral das frequências das letras. Além disso, se a chave tiver o mesmo comprimento da mensagem, não poderá haver repetição de letras e a análise de frequência se tornará impossível.
Al-Kindi , no IX th século é a descrição mais antiga da análise de frequência. É muito provável que esta análise tenha surgido do trabalho realizado para reconstruir a cronologia das revelações do Alcorão . Ele então expõe os fundamentos desse método de criptoanálise em seu tratado intitulado Manuscrito sobre a descriptografia de mensagens criptográficas . Isso mostra que uma mensagem criptografada mantém o controle da mensagem simples original, mantendo as frequências de aparecimento de certas letras.
Podemos ver que dependendo do idioma, um texto incluirá uma distribuição particular de frequências de letras. Por exemplo em francês, as letras mais frequentes, ou seja, as letras mais encontradas, são o E , seguido do A , do I e do S ... Obtemos assim a frequência de distribuição das letras seguintes ( dentro%):
| NO | B | VS | D | E | F | G | H | eu | J | K | eu | M | NÃO | O | P | Q | R | S | T | você | V | C | X | Y | Z | |
| francês | 9,42 | 1.02 | 2,64 | 3,39 | 15,87 | 0,95 | 1.04 | 0,77 | 8,41 | 0,89 | 0,00 | 5,34 | 3,24 | 7,15 | 5,14 | 2,86 | 1.06 | 6,46 | 7,90 | 7,26 | 6,24 | 2,15 | 0,00 | 0,30 | 0,24 | 0,32 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| inglês | 8,08 | 1,67 | 3,18 | 3,99 | 12,56 | 2,17 | 1,80 | 5,27 | 7,24 | 0,14 | 0,63 | 4,04 | 2,60 | 7,38 | 7,47 | 1,91 | 0,09 | 6,42 | 6,59 | 9,15 | 2,79 | 1,00 | 1,89 | 0,21 | 1,65 | 0,07 |
Isso dá a seguinte ordem para o idioma francês:
| E | NO | eu | S | T | NÃO | R | você | eu | O | D | M | P | VS | V | Q | G | B | F | J | H | Z | X | Y | K | C |
Esta distribuição de frequências de letras é apenas aproximada, depende de muitos parâmetros como o nível de linguagem do texto, bem como o estilo de escrita (por exemplo, uma mensagem militar usará muitas abreviaturas). Também podemos analisar a frequência em um texto de dígrafos , ou seja, grupos de duas letras. Isso trará pistas importantes para descriptografar um texto cifrado, pois sabemos que não conseguiremos encontrar dígrafos como XK ou WX no texto não criptografado.
Aplicativo para o jogo ScrabblePodemos notar que essas frequências correspondem mais ou menos às distribuições das letras no jogo Scrabble , esta rendendo mais ou menos pontos de acordo com a frequência de uso. Na verdade, a distribuição das letras com o número correspondente de pontos é a seguinte:
| A 1 | B 3 | C 3 | D 2 | E 1 | F 4 | G 2 | H 4 | Eu 1 | D 8 | K 10 | L 1 | H 2 | No. 1 | O 1 | P 3 | Q 8 | R 1 | S 1 | T 1 | U 1 | V 4 | W 10 | X 10 | Y 10 | Z 10 |
| 9 | 2 | 2 | 3 | 15 | 2 | 2 | 2 | 8 | 1 | 1 | 5 | 3 | 6 | 6 | 2 | 1 | 6 | 6 | 6 | 6 | 2 | 1 | 1 | 1 | 1 |
A distribuição das cartas da primeira cópia do jogo Scrabble também foi feita por análise estatística do New York Times .
A distribuição de frequências obtida pode ser usada para descriptografar uma mensagem codificada por meio de um sistema de substituição. Na verdade, se descobrirmos uma letra muito frequente na mensagem criptografada, será sem dúvida a letra E na mensagem simples, porque é a letra mais comum em francês. Podemos então deduzir as outras letras estudando todas as frequências das letras da mensagem criptografada. Por exemplo, considere a seguinte mensagem criptografada:
É, portanto, necessário calcular as frequências de aparecimento de cada uma das letras da mensagem cifrada, a fim de as comparar com a distribuição normal das frequências das cartas em francês. A seguinte distribuição de frequências (em%) é obtida para esta mensagem criptografada:
| Letras | NO | B | VS | D | E | F | G | H | eu | J | K | eu | M | NÃO | O | P | Q | R | S | T | você | V | C | X | Y | Z | Total |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Ocorrências | 12 | 0 | 1 | 0 | 7 | 1 | 1 | 1 | 1 | 3 | 4 | 4 | 0 | 4 | 1 | 7 | 2 | 1 | 1 | 0 | 1 | 0 | 3 | 0 | 4 | 3 | 62 |
| Frequências | 19,4 | 0 | 1,6 | 0 | 11,3 | 1,6 | 1,6 | 1,6 | 1,6 | 4,8 | 6,5 | 6,5 | 0 | 6,5 | 1,6 | 11,3 | 3,2 | 1,6 | 1,6 | 0 | 1,6 | 0 | 4,8 | 0 | 6,5 | 4,8 | 100 |
Podemos ver, portanto, que a letra A é a mais frequente na mensagem criptografada. Este, portanto, tem uma boa chance de representar a letra E na mensagem simples, porque é a letra mais comum em francês. O E e P também são comuns no texto cifrado, portanto, eles certamente representam as letras I ou A em texto não criptografado. Essas suposições nos levam a encontrar parte do texto não criptografado, o que nos permitirá deduzir dessas poucas letras parte da chave. No caso de uma substituição figura monoalfabético, que pode ser lida com uma cifra de César, então obtém-se, neste caso, um 4 letras deslocar desde que foi assumido Um = E . Com esta chave, podemos decifrar o resto da mensagem, o que nos dá:
Esta mensagem é consistente, nossas suposições iniciais estavam corretas.
A análise de frequência também está envolvida, combinada com outros métodos, para a criptoanálise de cifras mais complexas. Por exemplo, a análise de cifras polialfabéticas como a cifra de Vigenère são reduzidas a uma cifra por substituição, após uma busca por coincidências no texto cifrado.
Um dígrafo é um grupo de 2 letras. Na tabela abaixo, os dígrafos são duas letras pertencentes à mesma palavra tiradas ao acaso de textos franceses.
| Digrams | Percentagens |
|---|---|
| ES | 3,15% |
| A | 2,46% |
| DENTRO | 2,42% |
| DE | 2,15% |
| RÉ | 2,09% |
| NT | 1,97% |
| NÓS | 1,64% |
| VOCÊS | 1,63% |
| ER | 1,63% |
| SE | 1,55% |
A análise de frequência só pode ser usada para códigos de substituição simples, por exemplo, é ineficaz contra os métodos de criptografia RSA e DES . Não funciona para os chamados códigos de transposição, que alteram o lugar das letras ou símbolos na mensagem. Para saber se estamos lidando com um código de substituições, podemos usar o índice de coincidência antes da análise de frequência. Também ajuda ter um comprimento de palavra-chave recomendado que pode ser usado como base para análises estatísticas.
A análise de freqüência também não pode ser utilizada se o comprimento da mensagem for muito curto, pois a chave se repetirá muito pouco e não poderemos observar nenhuma peculiaridade na freqüência das letras. É também por essa razão que não se pode descriptografar uma mensagem codificada com um comprimento de chave igual ao da mensagem. A mesma mensagem criptografada pode então corresponder a qualquer mensagem clara, uma vez que há tantas chaves quanto não há chaves claras. Não podemos, portanto, neste caso específico, determinar o sentido geral da mensagem, é o princípio da máscara descartável que garante uma mensagem verdadeiramente indecifrável.
Para se proteger contra a criptoanálise por análise de frequência, os criptógrafos inventaram várias soluções usadas em algoritmos de cifra. Podemos usar um número que atribui vários símbolos para uma única letra, dependendo de sua frequência (por exemplo, usaremos 4 ou 5 símbolos para o E, mas apenas um para o K ). Então dizemos que usamos um código homofônico.
Também é possível usar a sobre-criptografia , que consiste em recodificar o texto cifrado por outro tipo de criptografia de modo a não permitir suposições sobre as letras mais frequentes. Para uma combinação bem escolhida de cifras, o texto supercifrado será, portanto, mais difícil de decifrar.
A análise de frequência é uma técnica de criptanálise frequentemente relatada na ficção . Pode ser encontrada, por exemplo, em The Gold-Bug de Edgar Allan Poe ou The Dancing Men , uma aventura de Sherlock Holmes escrita por Arthur Conan Doyle . Neste último enigma, as mensagens foram codificadas com diferentes símbolos, na forma de personagens dançantes.