Cifras de Substituição: 26! Chaves, Quebradas a Contar Letras

Um excerto de um conto de Sherlock Holmes foi cifrado com uma chave desconhecida. Numa cifra de César, experimente as 25 chaves uma a uma e observe a barra do qui-quadrado de cada tentativa. Numa substituição completa, associe as letras mais frequentes do texto cifrado às do inglês e ajuste os pares à medida que for lendo as palavras resultantes.

Exemplo resolvido — Cifras de Substituição: 26! Chaves, Quebradas a Contar Letras

Chaves possíveis	25
Letras na mensagem	120
Resultado do ataque (menor χ²)	23,3
Segundo menor	445,8
É a chave correta?	Sim

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

A teoria — Cifras de Substituição: 26! Chaves, Quebradas a Contar Letras

Uma cifra de substituição substitui cada letra da mensagem por outra letra, sempre a mesma, de acordo com uma chave: uma permutação do alfabeto, havendo portanto 26! ≈ 4,03 × 10²⁶ chaves possíveis. A cifra de César é o caso particular em que todas as letras avançam o mesmo número de posições no alfabeto, o que deixa apenas 25 chaves. A análise de frequências ataca ambas as cifras comparando a frequência de cada letra cifrada com a frequência habitual das letras na língua original.

O que significa cada símbolo

χ²: qui-quadrado: o somatório, ao longo das 26 letras, de (O − E)² / E. Quanto mais baixo for o resultado, mais as contagens da decifração se assemelham ao inglês padrão
O: número de ocorrências de uma letra na decifração avaliada
E: número de ocorrências esperadas num texto da mesma extensão com as frequências de The Dancing Men

Pressupõe: Apenas as 26 letras do alfabeto são cifradas. Os espaços e os sinais de pontuação permanecem intactos, o que revela de imediato o comprimento de cada palavra — tal como os homens dançantes faziam com as respetivas bandeiras. Por «inglês» entende-se a contagem de letras de um conto de Holmes com 39.859 letras, e as mensagens da própria página foram extraídas de outro conto distinto, evitando comparações circulares. As simulações utilizam um excerto aleatório de The Solitary Cyclist e uma chave gerada por uma semente fixa, garantindo valores rigorosamente idênticos a cada repetição.

Vinte e cinco chaves testam-se num instante; saber qual resultou exige cerca de 30 letras 🖖

Uma cifra de César tem apenas 25 chaves, poucas o suficiente para se testarem à mão. O verdadeiro trabalho está em decidir qual das decifrações é inglês autêntico. A página encarrega dessa triagem o qui-quadrado de Pearson, que soma, letra a letra, a distância entre as contagens da decifração e o perfil previsto por The Dancing Men para um texto daquele tamanho. Ao longo de 20.000 excertos aleatórios de outro conto de Holmes, a pontuação mais baixa indica a chave correta em 85,0% das vezes com 12 letras e em 99,1% com 31. Prima César, 11 letras para ver um engano: o deslocamento 7 obtém um valor menor do que a chave autêntica e produz dan reoep swo, leitura que qualquer leitor descartaria de imediato, mas perante a qual a estatística nada pode fazer.

A contagem encontra o e, e quase nada mais 🖖

Numa mensagem de 600 letras, ordenar as letras por frequência coloca o e na posição certa em 96,5% de 400 ensaios aleatórios. As letras seguintes têm frequências demasiado próximas para que a respetiva ordem resista num texto breve: em The Dancing Men, as letras a, o, i, n, h e s situam-se todas entre 6,3% e 8,0%, bastando algumas oscilações do acaso para as baralhar. Ao ordenar todas as letras obtêm-se, em média, 6,3 das 23,5 letras presentes, o equivalente a um terço do texto. O próprio Holmes, ao decifrar os bonecos dançantes nesse conto, explica o fenómeno: «A ordem das letras inglesas a seguir ao E não é, de modo algum, evidente; qualquer preponderância observada na média de uma página impressa pode inverter-se numa única frase curta.» Holmes preferiu aguardar por mais mensagens e decifrar palavras.

Um conto inteiro cifrado continua a deixar cinco letras erradas 🖖

Mais texto cifrado estabiliza as contagens, mas fá-las convergir para os valores da história que está a ser lida — e dois contos do mesmo autor nunca concordam em absoluto. Prima Substituição, conto todo: todas as 32.725 letras de The Solitary Cyclist, ordenadas segundo as frequências de The Dancing Men, acertam em 21 letras e erram em cinco (h, i, n, f e y), traduzindo-se em 76,1% de texto decifrado com sucesso. O conto da ciclista usa o h (6,69%) ligeiramente mais do que o i (6,67%) e o n (6,34%); já o dos bonecos coloca o i e o n à frente do h. Holmes apresenta a ordem como T, A, O, I, N, S, H, R, D, L, mas no próprio conto em que o afirma, o H surge à frente do S.

Problema resolvido na íntegra

Onde a contagem termina e a leitura começa 4 passos
Prima Substituição, 600 letras. Quanto tempo demoraria um computador capaz de testar mil milhões de chaves por segundo a percorrê-las todas? Depois, decifre a mensagem: o que nos revela a contagem e o que nos revelam as palavras mais comuns?

Abrir este problema na ferramenta
1. Existem 26! = 403.291.461.126.605.635.584.000.000 chaves, cerca de 4,03 × 10²⁶. A 10⁹ por segundo, seriam precisos 4,03 × 10¹⁷ segundos. Um ano tem 3,16 × 10⁷ segundos, o que resulta em 1,28 × 10¹⁰ anos: 12,8 mil milhões de anos.
  
  $26! = 403291461126605635584000000 \approx 4.03 \times 1 0^{26}, \frac{4.03 \times 1 0 ^{26}}{1 0 ^{9} \times 3.16 \times 1 0 ^{7}} = 1.28 \times 1 0^{10} years$
2. A letra cifrada mais frequente é o I, com 80 ocorrências em 600 (13,3%). Em The Dancing Men, o e representa 12,44%, pelo que I corresponde a e. As três letras seguintes, O, N e X, registam 49, 47 e 45 ocorrências — valores demasiado próximos para uma seriação segura —, e a ordenação associa-as a t, a e o, errando as três. A tabela de resultados mostra o custo: confiar apenas na ordenação por frequência acerta em somente 3 das 23 letras, ou seja, 14,2% do texto.
  
  $\frac{80}{600} = 13.3% \approx 12.44% : I \to e, 49, 47, 45 for O, N, X$
3. Olhemos agora para as palavras. As sequências de três letras OBJ e XDI ocorrem cinco vezes cada; como XDI termina em I, que é o nosso e, a palavra tem de ser the, revelando que X é t e D é h. Sendo assim, OBJ é com quase toda a certeza and: O é a, B é n e J é d. A palavra de duas letras mais frequente, PK, surge oito vezes e encaixa em of; com isso, XP (cinco ocorrências) lê-se como to, confirmando a dedução.
  
  $XDI \to t h e, OBJ \to an d, PK \to o f, XP \to t o$
4. Introduza essas oito letras nas caixas. e, t, h, a, n, d, o e f perfazem 321 das 600 letras (53,5%), e a primeira linha passa a ler-se como f·o· the ·ea·· 1894 to 1901. A contagem de frequências deu tudo o que podia dar. Antes de um intervalo de anos, f·o· só pode ser from, o que nos revela o r e o m. A partir deste ponto, o método dá lugar à leitura.
  
  $\frac{321}{600} = 53.5% of the message from 8 letters$
Resposta

12,8 mil milhões de anos para testar todas as chaves. A contagem dá apenas uma letra, o e; três palavras comuns revelam mais sete, e essas oito letras já decifram 53,5% da mensagem.

$1.28 \times 1 0^{10} years; 8 letters \to 53.5%$

Percurso de aprendizagem

Como se quebram os códigos

Referências (1)

Both passages the page counts, and Holmes's words quoted in the second and third insights: Arthur Conan Doyle, "The Adventure of the Dancing Men" and "The Adventure of the Solitary Cyclist," in The Return of Sherlock Holmes. Project Gutenberg eBook #108.

Pela equipa 42Math · Verificado com fontes publicadas. Correções bem-vindas.