Índice de Coincidência

Esta calculadora online calcula o índice de coincidência (IC, IOC) para o texto fornecido

Aqui está a calculadora que calcula o índice de coincidência, ou IOC (IC) para o texto fornecido. Você pode ler o que é o índice de coincidência e como ele é calculado abaixo da calculadora.

PLANETCALC, Índice de Coincidência

Índice de Coincidência

Dígitos após o ponto decimal: 4
Índice de Coincidência
 
Índice de Coincidência Normalizado
 

O índice de coincidência

O índice de coincidência é a probabilidade de duas letras selecionadas aleatoriamente serem iguais. William F. Friedman propôs essa métrica pela primeira vez em 1922 na Publicação Revierbank Número 22 intitulada "O índice de coincidência e suas aplicações na criptografia." Em 1967, o historiador David Kahn escreveu.

Publicação Revierbank Número 22, escrita em 1920, quando Friedman tinha 28 anos. Ela deve ser considerada a publicação mais importante na criptografia. Levou a ciência para um novo mundo. 1

Tendo a definição acima, é possível formar a fórmula para IOC.
Seja N o comprimento do texto.
Seja n o tamanho do alfabeto.
Seja a_i a i-ª letra do alfabeto.
Seja F_i o número de ocorrências da i-ª letra no texto.

Então, a probabilidade de ter dois a_i selecionados é p_i=\frac{F_i*(F_i-1)}{N*(N-1)}
A probabilidade total (que é o IOC) é a soma das probabilidades para cada letra:
IOC=\frac{1}{N*(N-1)}*\sum^{n}_{i=1}F_i*(F_i-1)

Observe que às vezes o IOC é "normalizado". Isso geralmente é feito através da multiplicação do resultado por n - o tamanho do alfabeto.
IOC_{normalizado}=\frac{n}{N*(N-1)}*\sum^{n}_{i=1}F_i*(F_i-1)

A calculadora abaixo analisa o texto e calcula o IOC utilizando as fórmulas acima. Você também pode ler por que isso é tão importante abaixo da calculadora.

Por que o Índice de Coincidência é tão importante?

É importante porque conseguimos calcular o índice de coincidência esperado para um determinado idioma usando a frequência de letras do idioma. Com a frequência da letra como p_i podemos aproximar o F_i como p_i*N. O que nos dá o seguinte:
IOC_{esperado}=\frac{1}{N*(N-1)}*\sum^{n}_{i=1}F_i*(F_i-1)\\=\frac{1}{N*(N-1)}*\sum^{n}_{i=1}(p_i*N)*(p_i * N - 1)\\=\sum^{n}_{i=1}p_i*\frac{p_i*N-1}{N-1}
Se N for grande o suficiente, podemos aproximar a fração \frac{p_i*N-1}{N-1} como p_i, que nos dá o
IOC_{esperado}=\sum^{n}_{i=1}p_i^2

Além disso, conseguimos calcular o índice de coincidência esperado para um texto totalmente aleatório - todas as letras têm a mesma frequência 1/n. Realmente é 1/n.

Tendo um índice de coincidência esperado, você consegue estimar rapidamente o texto cifrado se suspeitar que ele foi produzido por uma das cifras "clássicas". Se o índice de coincidência for alto e próximo ao IC esperado para o idioma, o texto provavelmente foi criptografado utilizando cifra de transposição ou cifra de substituição simples (monoalfabética). Caso contrário, se o índice de coincidência for baixo e próximo ao IC esperado para um texto aleatório, o texto provavelmente foi criptografado usando uma cifra polialfabética.

De acordo com a Wikipédia,

O índice de coincidência é útil na análise de texto simples em linguagem natural e análise de texto cifrado (criptoanálise). Até mesmo quando o único texto cifrado está disponível para teste e as identidades das letras do texto simples estão disfarçadas, as coincidências no texto simples subjacente podem causar coincidências no texto cifrado. Esta técnica é utilizada para criptanálise da cifra de Vigenère, por exemplo. Para uma cifra polialfabética de chave repetida organizada em uma matriz, a taxa de coincidência dentro de cada coluna geralmente será maior quando a largura da matriz for um múltiplo do comprimento da chave, e este fato pode ser usado para determinar o comprimento da chave, que é o primeiro passo para quebrar o sistema. A contagem de coincidências pode ajudar a determinar quando dois textos estão escritos no mesmo idioma usando o mesmo alfabeto. (Esta técnica foi usada para examinar o suposto código da Bíblia). A contagem de coincidência causal para tais textos será distintamente maior do que a contagem de coincidência acidental para textos em diferentes idiomas, textos usando diferentes alfabetos ou textos sem sentido.2


  1. David Kahn, The Code Breakers (Os Quebradores de Código), Macmillan, 1967. 

  2. Índice de Coincidência 

URL copiado para a área de transferência
PLANETCALC, Índice de Coincidência

Comentários