Exame Kasiski - Kasiski examination
Na criptoanálise , o exame de Kasiski (também conhecido como teste de Kasiski ou método de Kasiski ) é um método de atacar cifras de substituição polialfabéticas , como a cifra de Vigenère . Foi publicado pela primeira vez por Friedrich Kasiski em 1863, mas parece ter sido descoberto independentemente por Charles Babbage já em 1846.
Como funciona
Em cifras de substituição polialfabéticas em que os alfabetos de substituição são escolhidos pelo uso de uma palavra - chave , o exame Kasiski permite que um criptanalista deduza o comprimento da palavra-chave. Depois que o comprimento da palavra-chave é descoberto, o criptanalista alinha o texto cifrado em n colunas, onde n é o comprimento da palavra-chave. Então, cada coluna pode ser tratada como o texto cifrado de uma cifra de substituição monoalfabética . Como tal, cada coluna pode ser atacada com análise de frequência . Da mesma forma, onde uma máquina de cifragem de fluxo de rotor foi usada, este método pode permitir a dedução do comprimento de rotores individuais.
O exame Kasiski envolve a procura de cadeias de caracteres que se repetem no texto cifrado . As sequências devem ter três caracteres ou mais para que o exame seja bem-sucedido. Então, as distâncias entre ocorrências consecutivas das strings são provavelmente múltiplos do comprimento da palavra-chave. Assim, encontrar mais strings repetidas reduz os comprimentos possíveis da palavra-chave, uma vez que podemos obter o maior divisor comum de todas as distâncias.
A razão pela qual este teste funciona é que se uma string repetida ocorrer no texto simples , e a distância entre os caracteres correspondentes for um múltiplo do comprimento da palavra-chave, as letras da palavra-chave serão alinhadas da mesma maneira com ambas as ocorrências da string. Por exemplo, considere o texto simples:
crypto is short for cryptography.
" crypto " é uma string repetida e a distância entre as ocorrências é de 20 caracteres. Se alinharmos o texto simples com uma palavra-chave de 6 caracteres " abcdef " (6 não se divide em 20):
abcdefabcdefabcdefabcdefabcdefabc crypto is short for cryptography.
a primeira instância de " crypto " se alinha com " abcdef " e a segunda instância se alinha com " cdefab ". As duas instâncias serão criptografadas em diferentes textos cifrados e o exame Kasiski não revelará nada. No entanto, com uma palavra-chave de 5 caracteres " abcde " (5 se divide em 20):
abcdeabcdeabcdeabcdeabcdeabcdeabc crypto is short for cryptography.
ambas as ocorrências de " criptografia " alinham-se com " abcdea ". As duas instâncias serão criptografadas no mesmo texto cifrado e o exame Kasiski será eficaz.
Um ataque baseado em string
A dificuldade de usar o exame Kasiski está em encontrar cordas repetidas. Esta é uma tarefa muito difícil de realizar manualmente, mas os computadores podem torná-la muito mais fácil. No entanto, ainda é necessário cuidado, uma vez que algumas cordas repetidas podem ser apenas coincidências, de modo que algumas das distâncias repetidas são enganosas. O criptanalista deve descartar as coincidências para encontrar o comprimento correto. Então, é claro, os textos cifrados monoalfabéticos resultantes devem ser criptoanalisados.
- Um criptanalista procura grupos repetidos de letras e conta o número de letras entre o início de cada grupo repetido. Por exemplo, se o texto cifrado fosse FGX THJAQWN FGX Q , a distância entre os grupos FGX é 10. O analista registra as distâncias para todos os grupos repetidos no texto.
- O analista a seguir fatora cada um desses números. Se algum número for repetido na maioria dessas fatorações, é provável que seja o comprimento da palavra-chave. Isso ocorre porque os grupos repetidos são mais prováveis de ocorrer quando as mesmas letras são criptografadas usando as mesmas letras-chave do que por mera coincidência; isso é especialmente verdadeiro para longas strings correspondentes. As letras-chave são repetidas em múltiplos do comprimento da chave, então a maioria das distâncias encontradas na etapa 1 são provavelmente múltiplos do comprimento da chave. Um fator comum geralmente é evidente.
- Uma vez que o comprimento da palavra-chave é conhecido, a seguinte observação de Babbage e Kasiski entra em ação. Se a palavra-chave tiver N letras, cada N- ésima letra deve ter sido criptografada usando a mesma letra do texto-chave. Agrupando cada N- ésima letra, o analista tem N "mensagens", cada uma criptografada usando uma substituição de um alfabeto, e cada parte pode então ser atacada usando a análise de frequência .
- Usando a mensagem resolvida, o analista pode determinar rapidamente qual era a palavra-chave. Ou, no processo de resolução das peças, o analista pode usar suposições sobre a palavra-chave para ajudar a quebrar a mensagem.
- Uma vez que o interceptor conhece a palavra-chave, esse conhecimento pode ser usado para ler outras mensagens que usam a mesma chave.
Sobreposição
Na verdade, Kasiski usou "sobreposição" para resolver a cifra de Vigenère. Ele começou encontrando o comprimento da chave, como acima. Em seguida, ele pegou várias cópias da mensagem e as colocou uma sobre a outra, cada uma deslocada para a esquerda pelo comprimento da chave. Kasiski então observou que cada coluna era composta de letras criptografadas com um único alfabeto. Seu método era equivalente ao descrito acima, mas talvez seja mais fácil de imaginar.
Os ataques modernos às cifras polialfabéticas são essencialmente idênticos aos descritos acima, com o único aprimoramento da contagem de coincidências . Em vez de procurar grupos repetidos, um analista moderno pegaria duas cópias da mensagem e colocaria uma sobre a outra.
Os analistas modernos usam computadores, mas esta descrição ilustra o princípio que os algoritmos de computador implementam.
O método generalizado:
- O analista desloca a mensagem inferior uma letra para a esquerda, depois mais uma letra para a esquerda, etc., cada vez percorrendo toda a mensagem e contando o número de vezes que a mesma letra aparece na mensagem superior e inferior.
- O número de "coincidências" aumenta drasticamente quando a mensagem inferior é deslocada por um múltiplo do comprimento da chave, porque então as letras adjacentes estão no mesmo idioma e usam o mesmo alfabeto.
- Tendo encontrado o comprimento da chave, a criptoanálise prossegue conforme descrito acima, usando a análise de frequência .
Referências