Criptografia Numaboa
Como calcular o Índice de Coincidência (Kappa)
Seg 26 Jan 2009 21:49 |
- Detalhes
- Categoria: Criptoanálise
- Atualização: Segunda, 26 Janeiro 2009 22:52
- Autor: vovó Vicki
- Acessos: 16546
O Índice de Coincidência (IC) de Friedman indica a probabilidade de dois caracteres de um texto cifrado, tomados ao acaso, corresponderem à mesma letra. Em 1920, Friedman publicou "The Index of Coincidence and Its Application in Cryptography", sendo este, provavelmente, o tratado mais importante na história da criptografia.
O IC é utilizado para se determinar a monoalfabeticidade de um texto. Quando seu valor estiver ao redor de 0.762, a probabilidade do texto claro ter sido submetido a uma substituição monoalfabética é muito grande. Se o índice for significantemente menor, então o texto claro deve ter sido submetido a uma substituição polialfabética.
Cada idioma possui um IC próprio por que a frequência da ocorrência das letras é peculiar a cada um deles o que, obviamente, altera o índice.
O cálculo do IC
O cálculo do IC é feito em duas etapas. Inicialmente calcula-se a probabilidade de quantas letras do texto cifrado correspondem a A, B, ..., Z. Depois, realiza-se a soma destas probabilidades para se obter o IC.
Tomemos como exemplo o texto cifrado plsual tlroao crqcoc auiser emmoir anstoi ozaend roabio rmrcaa ocsnen idtliu annvdu epranr etqeeu sscepx texrae xemxot ssiedt, composto por 108 caracteres. A frequência da ocorrência das letras deste texto é a seguinte:
f | 11 | 1 | 6 | 4 | 13 | 7 | 4 | 4 | 7 | 10 | 3 | 2 | 10 | 8 | 7 | 5 | 1 | 4 | 1 | |||||||
TC | 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 |
Primeira Etapa
A fórmula abaixo permite calcular a probabilidade da ocorrência de cada uma das letras do alfabeto num texto cifrado. n1 corresponde a A e n ao número total de letras do texto analisado. Repete-se o cálculo com n2 para B até n26 para Z.
Não é preciso se assustar com a simplificação da fórmula obtida por Friedman. Com apenas um exemplo fica tudo claro. Inicialmente tomemos o A como exemplo: esta letra ocorre 11 vezes no texto, portanto basta calcular 11 x (11 - 1) = 11 x 10 = 110. Agora vamos calcular n(n-1) = 108 x (108 - 1) = 108 x 107 = 11.556. Conforme a fórmula, basta dividir um pelo outro, ou seja, 110/11556 = 0.0095. Repetindo o cálculo para todas as outras letras obtemos os seguintes resultados:
A | 0.00951 | N | 0.00363 | |
B | O | 0.00779 | ||
C | 0.00260 | P | 0.00052 | |
D | 0.00104 | Q | 0.00017 | |
E | 0.01350 | R | 0.00779 | |
F | 0.00104 | S | 0.00485 | |
G | T | 0.00363 | ||
H | U | 0.00173 | ||
I | 0.00363 | V | ||
J | W | |||
K | X | 0.00104 | ||
L | 0.00104 | Y | ||
M | 0.00104 | Z |
Segunda Etapa
Basta somar os valores obtidos e teremos os IC do texto: 0.0645. Este valor está arredondado porque foram usadas apenas 5 casas decimais após a vírgula. O resultado no javascript abaixo é um pouco diferente porque mais casas decimais são consideradas.
A fórmula da somatória dos índices de coincidência de cada letra para se obter o Índice de Coincidência do texto está abaixo:
A fórmula final do Índice de Coincidência
Esta é, portanto, a fórmula final que permite calcular o Índice de Coincidência de um texto, seja claro ou cifrado.
Confira o Índice
Referências
[FRIEDMAN1] | Friedman, William F. and Callimahos, Lambros D., Military Cryptanalytics Part I - Volume 1, Aegean Park Press, Laguna Hills, CA, 1985. |
[FRIEDMAN2] | Friedman, William F., The Index of Coincidence and Its Applications In Cryptography, Publication 22, The Riverbank Publications, Aegean Park Press, Laguna Hills, CA, 1979. |
[POMMERENING] | Kryptologie - Koinzidenzindizes nach FRIEDMAN |