Detalhes

Categoria: Criptoanálise

Atualização: Segunda, 26 Janeiro 2009 20:40

Autor: vovó Vicki

Acessos: 6717

Na criptoanálise das cifras clássica, uma das primeiras primeiras providências que precisamos tomar é determinar a classe da cifra, ou seja, tentar descobrir se se trata de uma transposição ou de uma cifra de substituição.

Revendo a diferença fundamental entre cifras de substituição e cifras de transposição, observa-se que:

• Nas cifras de substituição os valores normais ou convencionais das letras do texto claro são alterados, porém as posições relativas das letras permanecem na sua sequência original.
• Nas cifras de transposição apenas as posições relativas das letras do texto claro são alteradas, enquanto que os valores convencionais das letras são mantidos.

DFU

O termo Distribuição de Frequência Uniliteral - DFU (Uniliteral Frequency Distribution - UFD) é utilizado para identificar uma cifra de substituição simples.

Observação: é uniLITERAL e não unilateral. Uni de "um" e literal, que significa "expresso por letras". Daí, uniliteral = expresso por apenas uma letra.

Três propriedades podem ser observadas através de uma DFU aplicada a um texto cifrado de tamanho médio composto apenas por letras:

• Se a cifra pertence à classe de substituição ou à classe de transposição.
• Se for da classe de substituição, se é mono- ou polialfabética.
• Se for monoalfabética, se é padrão (direta ou reversa) ou mista.

Organograma da Criptologia

Classe de Cifra

Como a cifra de transposição rearranja o texto original sem alterar as entidades do mesmo, o número de vogais (A, E, I, O, U, Y), de consoantes de alta frequência (C, D, N, M, R, S, T), de consoantes de frequência média (B, F, G, H, L, P, Q, V) e, especialmente as consoantes de baixa frequência (J, K, W, X, Z), são exatamente as mesmas no texto cifrado e no texto original (as letras se referem a um texto em inglês). Numa cifra de substituição, as porcentagens convencionais de vogais e consoantes estão alteradas no texto cifrado.

À medida que o tamanho das mensagens cifradas diminui, existe uma maior probabilidade de desvios da proporção normal de vogais e consoantes. À medida que o tamanho dos textos cifrados aumenta, os desvios se tornam cada vez menores. Com 1.000 letras ou mais, praticamente não existe diferença entre as proporções teóricas e as reais. Friedman criou uma tabela mostrando a expectativa normal para vogais, consoantes de frequência alta, média e baixa, além da expectativa de brancos (blanks).

Em português, por exemplo, numa mensagem de 100 letras devem existir cerca de 48 vogais(A, E, I, O, U, Y), aproximadamente 37 consoantes de alta frequência (S, R, N, D, M, T, C) e cerca de 13 consoantes de frequência média (L, P, V, G, H, Q, B, F). Ainda se espera 2 consoantes de frequência baixa (Z, J, X, K, W).

Uma classe de cifra é considerada como de transposição se o texto cifrado estiver dentro dos limites acima citados. Será considerada como sendo de substituição se os valores encontrados estiverem fora dos limites convencionados para o comprimento da mensagem. [Friedman1/ p32-39]

Distribuição de Frequência Uniliteral - DFU

A distribuição de frequência uniliteral (DFU) pode ser utilizada para indicar a monoalfabeticidade. A distribuição normal mostra cristas (elevações) e vales (depressões) devido a dois fatores:

• Sons elementares representados por símbolos são usados com mais frequência. Esta é uma das características mais marcantes de qualquer linguagem alfabética.
• Exceto por poucas exceções, cada som é representado por um único símbolo.

O mapeamento da correspondência um-para-um entre a mensagem original e a mensagem cifrada mostrará uma DFU deslocada, com posições absolutas das cristas e vales diferentes do normal.

Cristas e vales evidentes na DFU de um criptograma é indicativo de que se trata de uma cifra monoalfabética. Este é um dos testes para a cifra de substituição mono/polialfabética.

Numa DFU, a ausência de cristas e vales evidentes indica uma forma complexa de substituição. O aspecto achatado da distribuição é um dos critérios para a rejeição da hipótese de uma substituição monoalfabética.

Teste Phi para monoalfabeticidade

Este teste compara o valor PHI(o) observado para a distribuição que esteja sendo testada com o valor PHI(r) randômico e o valor PHI(p) esperado no texto original. Para textos militares em inglês os valores são:

• PHI(r) = 0.0385N(N-1)
• PHI(p) = 0.0667N(N-1)

onde N é o número de elementos na distribuição. A constante .0385 é o equivalente decimal de 1/26 e a constante .0667 é a soma dos quadrados das probabilidades de ocorrência de cada uma das letras no texto original em inglês. [Friedman3]

Exemplo 1

Teste PHI do seguinte criptograma:

OWQWZ AEDTD QHHOB AWFTZ WODEQ
TUWRQ BDQRO XHQDA GTBDH PZRDK

Onde:

• N = número de letras = soma de fi = 50
• PHI(o) = soma [fi(fi-1)] = 154
• PHI(r) = .0358N(N-1) = .0385 x 50 x 49 = 94
• PHI(p) = .0667N(N-1) = .0667 x 50 x 49 = 163

Como valor observado PHI(o) = 154 se aproxima mais do valor esperado no texto original PHI(p) = 163 do que do valor randômico PHI(r) = 94, existe uma corroboração matemática da hipótese de que o texto cifrado seja monoalfabético.

Exemplo 2

Na distribuição do texto cifrado indicada abaixo:

• N = 25 letras
• PHI(o) = 18
• PHI(r) = .0385 x 25 x 24 = 23
• PHI(p) = .0667 x 25 x 24 = 40

Como o valor observado PHI(o) está mais próximo do valor randômico PHI(r), então esta distribuição de letras NÃO é monoalfabética.

Antes de tirar conclusões apressadas e considerar este teste como perfeito, faça o PHI com "a quick brown fox jumps over the lazy dog".

• N = 33 letras
• PHI(o) = 20
• PHI(r) = .0385 x 33 x 32 = 41
• PHI(p) = .0667 x 33 x 32 = 70

Como o valor observado PHI(o) é menos que a metade do valor randômico PHI(r), isto sugere que as letras desta frase não poderiam estar em texto original e inteligível em qualquer língua. E agora? Se você não encontrou uma explicação racional para este último exemplo, aguarde a derivação simplificada de Sinkov.

TABELAS DE KULLBACK

Textos monoalfabéticos e digrâmicos para oito línguas:

Índice de Coincidência ou Teste Kappa de Friedman

É de Friedman o famoso Índice de Coincidência. É mais um método para expressar a monoalfabeticidade de um criptograma. Compara-se o I.C. teórico com o I.C. obtido.

O I.C. é definido como sendo a razão entre PHI(o)/PHI(r). Utilizando o exemplo 1 descrito acima, pode-se calcular o I.C.=154/94=1.64. O I.C. teórico para o Inglês é 1.73 (ou .0667/.0385). O I.C. de um texto randômico é igual a 1 (ou .0385/.0385).

Em 1920 Friedman escreveu um texto intitulado "O Índice de Coincidência e sua Aplicação na Criptografia" ("The Index of Coincidence and Its Application in Cryptography") que é, talvez, o tratado mais importante na história da criptografia. [Friedman2]

Alfabetos Cifrantes - Padrão ou Desordenados

Partindo de premissa de que uma DFU seja monoalfabética, observa-se as cristas e os vales da distribuição. Se as cristas e os vales ocuparem posições deslocadas em relação à DFU normal, então o alfabeto tem toda probabilidade de ser ordenado ou padrão (A, B, C,...). Se isto não ocorrer, o texto cifrado foi preparado utilizando-se um alfabeto desordenado. A direção em que as cristas e vales progredirem, da esquerda para a direita ou da direita para a esquerda, indica se o alfabeto é padrão ou reverso (Z, Y, X, ...)

Referências