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 3: Ataque por força bruta
Neste tipo de ataque testa-se todas as possibilidades de chave possíveis, até encontrar uma que sirva.
Voltando ao infantil método de César com a modificação e presença do k, se B quisesse muito saber o que escrevi para A, ele poderia tentar usar os possíveis valores de k até que a mensagem faça sentido. Neste caso k pode assumir uma variedade limitada de valores. Ele pode ser 0 (onde "A" seria trocado pelo mesmo "A". Ridículo, mas matematicamente é uma chave viável), pode ser 1, 2, 3, ... 25, sendo que neste último o "A" seria trocado pelo "Z".
Veja que existem apenas 26 possíveis valores para k neste método. Um ataque por força bruta não exigiria mais que 26 tentativas.
Matematicamente se usa a estatística aqui, sendo que ninguém é tão sortudo para acertar na primeira tentativa e nem tão azarado para acertar na última! Na média se considera que o ataque terá sucesso em 13 tentativas.
Logo, neste caso, um ataque por força bruta terá um esforço médio de 13 tentativas. Se eu usar papel e caneta (como devia ser no tempo de César) e conseguir testar no ritmo de uma tentativa por minuto, levaria 13 minutos em média para quebrar o algoritmo. Este seria o esforço de um ataque de força bruta à Cifra de César, o que o torna, como disse, infantil.
Mas se eu mudasse a cifra monoalfabética um pouco. Se ao invés de ter que trocar uma letra por uma k vizinha eu usasse uma tabela de trocas:
Um ataque de força bruta sempre é possível, a questão é quanto tempo em média ele levaria. O tempo é de acordo com as possíveis combinações de chave. Neste caso de um algoritmo monoalfabético com uma tabela de troca, cada letra pode ser uma das outras 25, sem poder repetir, ou seja, se já decidi que "A" troca pelo "X", ninguém mais poderá ser trocado pelo "X". A matemática nos ensina que neste caso haverão 26! possibilidades (fatorial de 26) para a chave.
As aparências enganam, pois fatorial de 26 resulta em 403.291.461.126.605.635.584.000.000 possíveis valores para chave e isto é muito, mas muito mesmo.
Como calcular este fatorial no Linux? Usando bc, uma alternativa bem criativa é com o comando:
$ seq -s '*' 1 26|bc
O comando seq irá gerar a sequência: 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20*21*22*23*24*25*26
que será avaliada pelo bc.
Se eu tivesse um computador capaz de realizar 1 bilhão de tentativas por segundo (1.000.000.000) e tiver 1 bilhão destes computadores para uso, o ataque de força bruta ainda levaria 201.645.730 segundos, ou aproximadamente 6 anos de processamento!
Verifique você mesmo no bash:
echo "403291461126605635584000000 / 2 / 1000000000 / 1000000000 / 60 / 60 / 24 / 365" | bc
Divido o número de tentativas por 2, pois na média se acerta na metade das tentativas, divido pela quantidade de quebras por segundo de um computador, que é um bilhão, divido pelo número de computadores que tenho. Depois divido por 60 para transformar segundos em minutos, por 60 novamente para transformar em horas, por 24 tem-se dias e dividindo por 365 tem em anos.
Logo, por força bruta, este algoritmo de substituição monoalfabética é infalível e inquebrável, apenas com o desconforto de ter que memorizar uma k que é uma tabela.
Costumo instigar meus alunos neste momento perguntando-lhes se está aí o algoritmo perfeito e inquebrável! Então?
Por força bruta, SIM, eis um algoritmo ideal. Só que existem outros meios de se quebrar um algoritmo de cifra que é através da criptoanálise.
Voltando ao infantil método de César com a modificação e presença do k, se B quisesse muito saber o que escrevi para A, ele poderia tentar usar os possíveis valores de k até que a mensagem faça sentido. Neste caso k pode assumir uma variedade limitada de valores. Ele pode ser 0 (onde "A" seria trocado pelo mesmo "A". Ridículo, mas matematicamente é uma chave viável), pode ser 1, 2, 3, ... 25, sendo que neste último o "A" seria trocado pelo "Z".
Veja que existem apenas 26 possíveis valores para k neste método. Um ataque por força bruta não exigiria mais que 26 tentativas.
Matematicamente se usa a estatística aqui, sendo que ninguém é tão sortudo para acertar na primeira tentativa e nem tão azarado para acertar na última! Na média se considera que o ataque terá sucesso em 13 tentativas.
Logo, neste caso, um ataque por força bruta terá um esforço médio de 13 tentativas. Se eu usar papel e caneta (como devia ser no tempo de César) e conseguir testar no ritmo de uma tentativa por minuto, levaria 13 minutos em média para quebrar o algoritmo. Este seria o esforço de um ataque de força bruta à Cifra de César, o que o torna, como disse, infantil.
Mas se eu mudasse a cifra monoalfabética um pouco. Se ao invés de ter que trocar uma letra por uma k vizinha eu usasse uma tabela de trocas:
Letra A B C D E F G H I J K L M ... troca X J M A F W C N O K B E T ...Será que um ataque de força bruta seria possível com este novo algoritmo?
Um ataque de força bruta sempre é possível, a questão é quanto tempo em média ele levaria. O tempo é de acordo com as possíveis combinações de chave. Neste caso de um algoritmo monoalfabético com uma tabela de troca, cada letra pode ser uma das outras 25, sem poder repetir, ou seja, se já decidi que "A" troca pelo "X", ninguém mais poderá ser trocado pelo "X". A matemática nos ensina que neste caso haverão 26! possibilidades (fatorial de 26) para a chave.
As aparências enganam, pois fatorial de 26 resulta em 403.291.461.126.605.635.584.000.000 possíveis valores para chave e isto é muito, mas muito mesmo.
Como calcular este fatorial no Linux? Usando bc, uma alternativa bem criativa é com o comando:
$ seq -s '*' 1 26|bc
O comando seq irá gerar a sequência: 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20*21*22*23*24*25*26
que será avaliada pelo bc.
Se eu tivesse um computador capaz de realizar 1 bilhão de tentativas por segundo (1.000.000.000) e tiver 1 bilhão destes computadores para uso, o ataque de força bruta ainda levaria 201.645.730 segundos, ou aproximadamente 6 anos de processamento!
Verifique você mesmo no bash:
echo "403291461126605635584000000 / 2 / 1000000000 / 1000000000 / 60 / 60 / 24 / 365" | bc
Divido o número de tentativas por 2, pois na média se acerta na metade das tentativas, divido pela quantidade de quebras por segundo de um computador, que é um bilhão, divido pelo número de computadores que tenho. Depois divido por 60 para transformar segundos em minutos, por 60 novamente para transformar em horas, por 24 tem-se dias e dividindo por 365 tem em anos.
Logo, por força bruta, este algoritmo de substituição monoalfabética é infalível e inquebrável, apenas com o desconforto de ter que memorizar uma k que é uma tabela.
Costumo instigar meus alunos neste momento perguntando-lhes se está aí o algoritmo perfeito e inquebrável! Então?
Por força bruta, SIM, eis um algoritmo ideal. Só que existem outros meios de se quebrar um algoritmo de cifra que é através da criptoanálise.
http://www.vivaolinux.com.br/artigo/Criptografia-chave-simetrica-de-bloco-e-de-fluxo