Introdução a criptografia
Este artigo não descreve algoritmos de criptografia nem ensina a quebrá-los. Trata-se de uma introdução. Se você não sabe a diferença entre chave e senha, ou entre algoritmos simétricos e assimétricos, se não sabe o que é o ataque de força bruta e quantos bits precisa ter para ser seguro, então este artigo poderá lhe ser útil.
Parte 4: Ataque por criptoanálise
O ataque por força bruta é possível em todos os casos. Ainda não existem algoritmos imunes a este ataque, ou seja, ele sempre poderá ser tentado. A questão é o tempo que levará. Deseja-se um algoritmo com tantas possibilidades de chave que o ataque levaria anos ou mesmo milhares de anos, de sorte que ninguém sequer irá tentar este ataque por ser inviável (em tempo: estudos sobre computação quântica sugerem a possibilidade da construção de algoritmos de criptografia imunes ao força bruta).
A cifra de substituição monoalfabética com uma tabela de trocas, citada no capítulo anterior, é um caso de um algoritmo para o qual demonstrou-se que o foça bruta é inviável. Mas existe a criptoanálise.
Simon (ver referências) define a criptografia como a eterna guerra entre criptógrafos e criptoanalistas. Um constrói para que o outro descubra como destruir! No caso mais específico da substituição monoalfabética ela é frágil e sucumbe ao ataque de "Análise de Frequência".
Costumo brincar de forca com meus alunos nesta hora:
Vamos lá. Qual letra você escolheria?
Notoriamente todos começam tentando a letra "A" ou, no máximo, indo pelas vogais. Porque? Ora, pelo simples fato de que em um texto em português a letra "A" é a letra que mais se repete! É improvável que um texto não possua uma boa quantidade de letras "A"s. Isto é análise de frequência.
Se estou tentando quebrar uma cifra monoalfabética (onde uma letra trocou por outra), sabendo que o texto é em português a primeira coisa que faço é contar as letras. Se, e ao contar, descubro que a mais repetida é o "W" é provável que o "W" está substituindo a letra "A". Onde tem "W" coloco "A" e vou brincando até o texto fazer algum sentido para mim. No caso da forca, ao colocar a letra "A" ficaria assim:
Vamos ver quem posta o primeiro comentário dizendo qual é a palavra!
Todo o algoritmo de substituição monoalfabético é vulnerável ao ataque de análise de frequência. Se o texto for em inglês, sabe-se que a letra que mais se repete é o "E".
Mas entenda que substituição monoalfabética não quer dizer apenas letras assim como análise de frequência não se aplica somente a letras que mais se repetem! Posso cifrar o arquivo binário com uma tabela de 256 trocas, onde o byte 00000000 será trocado por 00110110, por exemplo, e assim por diante.
Ainda é considerado substituição monoalfabética. No caso, se era um executável, posso realizar análise de frequência nele, descobrir quais os bytes mais presentes em um EXE típico e usar o mesmo princípio! Fabricantes de processadores fazem isto para descobrir as instruções mais usadas em programas a fim de otimizá-las.
Logo, foi para o brejo nosso algoritmo perfeito: ele perece pelo ataque de "Análise de Freqüência".
Alternativas interessantes ao longo da história foram usadas para melhorar a cifra monoalfabética como variar a troca para os mais frequêntes. Como exemplo, a letra "A", sendo a que mais se repete, pode ser trocada por "X", por "#" ou por "*". Isto, se bem usado, evita a análise de freqüência, mas impõe alguns problemas, como o fato do alfabeto de troca ter que possuir mais símbolos que o original. Enfim, a cifra de Viginère resolveu de forma criativa este problema e ficou inquebrável por séculos até que Babage a quebrou usando, pasmem, Análise de freqüência (Simon).
Ainda existem outras técnicas de criptoanálise como por exemplo as colas. Chama-se de cola quando um atacante tem uma vaga ideia de trechos da mensagem. Na segunda guerra mundial os alemães pisaram na bola neste sentido, pois toda a comunicação tinha a saudação nazista, logo ao menos um trecho da mensagem era previsível (Simon). Hoje os modernos algoritmos de cifras devem ser imunes as colas, ou seja, mesmo que eu lhe dê centenas de textos cifrados e as suas centenas de textos originais correspondentes, ainda assim você não deve ser capaz de descobrir qual chave eu usei (esta propriedade é muito interessante e parece utópica, mas não é).
A cifra de substituição monoalfabética com uma tabela de trocas, citada no capítulo anterior, é um caso de um algoritmo para o qual demonstrou-se que o foça bruta é inviável. Mas existe a criptoanálise.
Simon (ver referências) define a criptografia como a eterna guerra entre criptógrafos e criptoanalistas. Um constrói para que o outro descubra como destruir! No caso mais específico da substituição monoalfabética ela é frágil e sucumbe ao ataque de "Análise de Frequência".
Costumo brincar de forca com meus alunos nesta hora:
Notoriamente todos começam tentando a letra "A" ou, no máximo, indo pelas vogais. Porque? Ora, pelo simples fato de que em um texto em português a letra "A" é a letra que mais se repete! É improvável que um texto não possua uma boa quantidade de letras "A"s. Isto é análise de frequência.
Se estou tentando quebrar uma cifra monoalfabética (onde uma letra trocou por outra), sabendo que o texto é em português a primeira coisa que faço é contar as letras. Se, e ao contar, descubro que a mais repetida é o "W" é provável que o "W" está substituindo a letra "A". Onde tem "W" coloco "A" e vou brincando até o texto fazer algum sentido para mim. No caso da forca, ao colocar a letra "A" ficaria assim:
Todo o algoritmo de substituição monoalfabético é vulnerável ao ataque de análise de frequência. Se o texto for em inglês, sabe-se que a letra que mais se repete é o "E".
Mas entenda que substituição monoalfabética não quer dizer apenas letras assim como análise de frequência não se aplica somente a letras que mais se repetem! Posso cifrar o arquivo binário com uma tabela de 256 trocas, onde o byte 00000000 será trocado por 00110110, por exemplo, e assim por diante.
Ainda é considerado substituição monoalfabética. No caso, se era um executável, posso realizar análise de frequência nele, descobrir quais os bytes mais presentes em um EXE típico e usar o mesmo princípio! Fabricantes de processadores fazem isto para descobrir as instruções mais usadas em programas a fim de otimizá-las.
Logo, foi para o brejo nosso algoritmo perfeito: ele perece pelo ataque de "Análise de Freqüência".
Alternativas interessantes ao longo da história foram usadas para melhorar a cifra monoalfabética como variar a troca para os mais frequêntes. Como exemplo, a letra "A", sendo a que mais se repete, pode ser trocada por "X", por "#" ou por "*". Isto, se bem usado, evita a análise de freqüência, mas impõe alguns problemas, como o fato do alfabeto de troca ter que possuir mais símbolos que o original. Enfim, a cifra de Viginère resolveu de forma criativa este problema e ficou inquebrável por séculos até que Babage a quebrou usando, pasmem, Análise de freqüência (Simon).
Ainda existem outras técnicas de criptoanálise como por exemplo as colas. Chama-se de cola quando um atacante tem uma vaga ideia de trechos da mensagem. Na segunda guerra mundial os alemães pisaram na bola neste sentido, pois toda a comunicação tinha a saudação nazista, logo ao menos um trecho da mensagem era previsível (Simon). Hoje os modernos algoritmos de cifras devem ser imunes as colas, ou seja, mesmo que eu lhe dê centenas de textos cifrados e as suas centenas de textos originais correspondentes, ainda assim você não deve ser capaz de descobrir qual chave eu usei (esta propriedade é muito interessante e parece utópica, mas não é).
http://www.vivaolinux.com.br/artigo/Criptografia-chave-simetrica-de-bloco-e-de-fluxo