Método Kasiski
Na criptoanálise, o método Kasiski (também conhecido como teste de Kasiski) é um método de ataque a cifras de substituição polialfabética, como a cifra de Vigenère.[1][2] Foi publicado pela primeira vez por Friedrich Kasiski em 1863,[3] mas parece ter sido descoberto de maneira independente por Charles Babbage já em 1846.[4][5]
Como funciona[editar | editar código-fonte]
Em cifras de substituição polialfabéticas em que os alfabetos de substituição são escolhidos pelo uso de uma palavra-chave, o método Kasiski permite que um criptoanalista deduza o comprimento da palavra-chave. Uma vez descoberto o comprimento da palavra-chave, o criptoanalista alinha o texto cifrado em n colunas, onde n é o comprimento da palavra-chave. Em seguida, cada coluna pode ser tratada como o texto cifrado ou criptografado de uma cifra de substituição monoalfabética . Assim, cada coluna pode ser atacada com análise de frequência.[6] Da mesma forma, onde uma máquina de codificação de fluxo foi usada, esse método pode permitir a dedução do comprimento de rotores individuais.
O método Kasiski envolve a procura de cadeias de caracteres que são repetidas na mensagem cifrada. As strings devem ter três caracteres ou mais para que o método seja eficaz. Logo, as distâncias entre ocorrências consecutivas das cadeias de caracteres provavelmente serão múltiplos do comprimento da palavra-chave. Assim, encontrar strings mais repetidas reduz os comprimentos possíveis da palavra-chave, pois podemos obter o maior divisor comum de todas as distâncias.
O motivo que torna esse teste eficaz é 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 forma com ambas ocorrências da cadeia de caracteres. 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 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 criptografarão diferentes textos cifrados e o método Kasiski não revelará nada. No entanto, com uma palavra-chave de 5 caracteres "abcde " (5 divide em 20):
abcdeabcdeabcdeabcdeabcdeabcdeabc crypto is short for cryptography.
ambas ocorrências de "crypto" alinham com "abcdea”. As duas instâncias serão criptografadas para o mesmo texto cifrado e o método Kasiski será eficaz.
Um ataque baseado em string[editar | editar código-fonte]
A dificuldade de usar o método de Kasiski está em encontrar sequências repetidas. Esta é uma tarefa muito difícil de executar manualmente, mas os computadores podem torná-la muito mais fácil. Mas ainda é necessário cuidado, pois algumas sequências repetidas podem ser apenas coincidência, de modo que algumas das distâncias repetidas são enganosas. O criptoanalista deve descartar as coincidências para encontrar o comprimento correto. Então, é claro, os textos cifrados monoalfabéticos resultantes devem ser criptoanalisados.
- Um criptoanalista procura por 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 FGXTHJAQWNFGXQ, a distância entre os trigramas FGX é 10. O analista registra as distâncias para todos os grupos repetidos no texto.
- Em seguida, o analista 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 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 cadeias de caracteres correspondentes longas. As letras-chave são repetidas em múltiplos do comprimento da chave, portanto, a maioria das distâncias encontradas na etapa 1 provavelmente serão 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 jogo. Se a palavra-chave tiver N letras, então cada letra N deve ter sido codificada usando a mesma letra do texto-chave. Agrupando cada enésima letra, o analista tem N "mensagens", cada uma criptografada usando uma substituição de um alfabeto, e cada peça pode então ser atacada usando 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.
- Depois que o interceptador conhece a palavra-chave, esse conhecimento pode ser usado para ler outras mensagens que usam a mesma chave.
Sobreposição[editar | editar código-fonte]
Kasiski realmente usou "sobreposição" para resolver a cifra de Vigenère. Ele começou encontrando o comprimento da chave, como acima. Então 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 visualizar.
Os ataques modernos contras as cifras polialfabéticas são essencialmente idênticos aos descritos acima, com uma melhoria na contagem de coincidências. Em vez de procurar por grupos repetidos, um analista moderno pegaria duas cópias da mensagem e colocaria uma sobre a outra.
Os analistas modernos usam computadores, mas essa 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., percorrendo toda a mensagem a cada vez e contando o número de vezes que a mesma letra aparece na mensagem superior e inferior.
- O número de "coincidências" aumenta acentuadamente quando a mensagem inferior é deslocada por um múltiplo do comprimento da chave, porque as letras adjacentes estão no mesmo idioma usando 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[editar | editar código-fonte]
- ↑ Rodriguez-Clark, Daniel, Kasiski Analysis: Breaking the Code, consultado em 30 de novembro de 2014
- ↑ R. Morelli, R. Morelli, Historical Cryptography: The Vigenere Cipher, Trinity College Hartford, Connecticut, consultado em 4 de junho de 2015
- ↑ Kasiski, F. W. 1863. Die Geheimschriften und die Dechiffrir-Kunst. Berlin: E. S. Mittler und Sohn
- ↑ Franksen, O. I. 1985 Mr. Babbage's Secret: the Tale of a Cipher—and APL. Prentice Hall
- ↑ Singh, Simon (1999), The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography, ISBN 1-85702-879-1, London: Fourth Estate, p. 78
- ↑ Kasiski's Method, Michigan Technological University, consultado em 1 de junho de 2015