Força bruta – Wikipédia a enciclopédia livre

Prévia do material em texto

Força bruta
Origem: Wikipédia, a enciclopédia livre.
Em ciência da computação, força bruta (ou busca exaustiva) é uma algoritmo trivial mas de uso muito geral
que consiste em enumerar todos os possíveis candidatos de uma solução e verificar se cada um satisfaz o
problema.
Por exemplo, um algoritmo para encontrar os divisores de um número natural é enumerar todos os inteiros de
1 a , e verificar para cada um se ele dividido por resulta em resto 0.
Esse algoritmo possui uma implementação muito simples, e sempre encontrará uma solução se ela existir.
Entretanto, seu custo computacional é proporcional ao número de candidatos a solução, que, em problemas
reais, tende a crescer exponencialmente. Portanto, a força bruta é tipicamente usada em problemas cujo
tamanho é limitado, ou quando há uma heurística usada para reduzir o conjunto de candidatos para uma espaço
aceitável. Também pode ser usado quando a simplicidade da implementação é mais importante que a
velocidade de execução, como nos casos de aplicações críticas em que os erros de algoritmo possuem em
sérias consequências.
Índice
1 Aplicação na ordenação
2 Aplicação em problemas avançados
3 Exemplo de ataque
4 Referências
Aplicação na ordenação
Um exemplo clássico de aplicação de algoritmos da classe da força bruta é a ordenação, que pode ser aplicada
nos mais diferentes tipos de dados.
Por exemplo, uma das formas de resolver o problema consiste em procurar o menor elemento e colocá-lo na
primeira posição, operando sucessivamente com os demais elementos da lista a ser classificada até finalizar a
operação, um método conhecido como ordenação por inserção.
Outro exemplo é a busca de padrões. Dada uma cadeia de caracteres de tamanho (o "texto") e outra cadeia
com tamanho menor ou igual chamada "padrão". É realizada uma procura no "texto" pelo "padrão",
verificando-se todo o texto em busca de múltiplas ocorrências. O funcionamento da busca de padrão é simples:
se o primeiro caractere é idêntico à um referente no texto, todos os sucessores devem ser idênticos também,
até finalizar o padrão. Caso ocorra que um caractere não seja igual, desloca-se o padrão em um caractere até
chegar ao fim do texto ou encontrar o padrão.
rotina BuscaPadrao(texto[0 ... n-1], padrao[0 ... m-1])
 para i ← 0 até n – m faça
 j ← 0
 enquanto j < m e padrao[j] = texto[i + j] faça
 j ← j + 1
 se j = m então
 retorne i
 retorne -1
Note que o algoritmo desloca-se após a comparação do primeiro caractere, porém nem sempre é assim. O
pior caso é "muito pior": o algoritmo tem que comparar todos os caracteres antes de se deslocar, e isso
pode ocorrer para cada uma das tentativas. Portanto, o pior caso para este algoritmo está em 
. Para textos de linguagem natural, o caso médio é melhor (pois ocorre nas primeiras comparações).
Até em textos aleatórios, o comportamento se mostra linear, .
Aplicação em problemas avançados
Um exemplo é o problema do par mais próximo, que consiste em achar os dois pontos mais próximos em um
conjunto de pontos. Para o exemplo a seguir, por simplicidade se assume o plano cartesiano, de forma que a
distância é calculada pela distância euclidiana. O algoritmo de força bruta percorrerá o conjunto, e selecionará
o par com menor distância, ignorando pontos na mesma posição.
rotina ParProximo(P)
 dmin ← ∞
 para i ← 1 até n – 1 faça
 para j ← i + 1 até n faça
 d ← raiz((xi - xj)² + (yi – yj)²)
 se d < dmin
 dmin ← d
 ind1 ← i
 ind2 ← j
 retorne ind1, ind2
Exemplo de ataque
O grupo que gerencia o programa 7-Zip criou um exemplo de quanto tempo demoraria para um atacante burlar
um sistema através de força bruta, segue abaixo a tradução do problema:
Ataque de acordo com o número de caractere da senha
Isto é uma estimativa de tempo requerido para um exaustivo ataque de senha (força bruta), sendo que a
senha é uma seqüencia aleatória de letras minúsculas latinas.
Vamos supor que um usuário possa controlar 10 senhas por segundo e que uma organização com um
orçamento de $1 bilhão (mil milhões) de dólares possa controlar 1 bilhão de senhas por segundo. Também
supomos que o processador em uso duplica seu desempenho a cada dois anos, assim, cada letra latina que
acrescentarmos será adicionada 9 anos de um exaustivo ataque de senha.
O resultado é esta estimativa de tempo para ter sucesso num ataque:
Tamanho da senha Ataque de um usuário comum Ataque da organização
1 letra minúscula latina 2 segundos 1 segundo
[1]
2 1 minuto 1s
3 30 min 1s
4 12 horas 1s
5 14 dias 1s
6 1 ano 1s
7 10 anos 1s
8 19 anos 20s
9 26 anos 9 min
10 37 anos 4 horas
11 46 anos 4 dias
12 55 anos 4 meses
13 64 anos 4 anos
14 73 anos 13 anos
15 82 anos 22 anos
16 91 anos 31 anos
17 100 anos 40 anos
Observação: O exemplo abrange apenas uma senha com letras latinas minúsculas, ou seja, uma
senha que possua apenas letras de " a - f ". Ao colocar a possibilidade de existir letras maiúsculas
e símbolos especiais aumentará ainda mais o tempo para se realizar todas as possibilidades de um
ataque.
Referências
1. ↑ O conteúdo original pode ser encontrado na seção "7z format" da "General Information" do arquivo de ajuda
do programa "7-Zip" na versão "4.58", sendo que o mesmo se encontra sob a licença GNU LGPL, tendo assim
a permissão para a copia e modificação do texto sem aviso prévio do grupo compositor do mesmo. (em inglês)
Obtida de "http://pt.wikipedia.org/w/index.php?title=Força_bruta&oldid=28809380"
Categorias: Algoritmos Criptografia
Menu de navegação
Esta página foi modificada pela última vez à(s) 00h52min de 10 de fevereiro de 2012.
Este texto é disponibilizado nos termos da licença Atribuição-Partilha nos Mesmos Termos 3.0 não
Adaptada (CC BY-SA 3.0); pode estar sujeito a condições adicionais. Consulte as condições de uso
para mais detalhes.