Usando arvores binarias para criar e manipular wordlists
NOTA: O CODIGO QUE SE ENCONTRA NESTE ARTIGO E *APENAS* PARA SISTEMAS LINUX!
POREM A WORDLIST CRIADA COM O PROGRAMA E UM "PLAIN TEXT FILE".
Aqui ha tempos perguntaram-me se havia "no mercado", algum programa que
dado um simples ficheiro de texto com palavras correntes, o convertia para
uma wordlist! A principio parecia-me mais uma ideia para criar mais uma
wordlist,... porem pensando melhor e uma ideia com grande interesse!!
Primeiro quero dizer que se nao sabe o que e uma wordlist, ou nao entendeu
nada do que foi dito ate aqui,...o melhor e comecar a pensar em dedicar-se a
outra coisa qualquer,...(a costura e um bom hobbie!).
Este pequeno programa faz basicamente uma coisa:
Por exemplo, se tivermos o seguinte texto:
Ou seja, alem de dividir as frases por palavras, convertendo as maiusculas
para minusculas, e substituindo as vogais acentudas, pelas suas "congeneres"
nao acentuadas (ex. ->a, ->e, etc...), e tambem as consoantes cedilhadas,
o proprio programa ignora as palavras cujo comprimento seja inferior a quatro
que em principio nao sao aceites pelo sistema. Este valor pode ser alterado,
caso seja desejavel,...basta alterar o #define STR_LEN x, para o valor x.
O programa tambem ordena a wordlist pela ordem lexicografica das strings!
Outra utilidade e que tambem retira todas as repeticoes que possam ocorrer
no texto!
*Este programa tambem pode ser usado para ordenar e retirar repeticoes que
ocorram numa wordlist, no problem :)!*
O output do programa e para o stdout, portanto convem redirecionar para
um ficheiro, nao e?
E pronto, aqui temos mais uma wordlist pronta a dar dores de cabecas aos
administradores mais zelosos!
Agora como vamos falar da parte de programacao do programa, os que nao
percebem um cu do assunto e pensam que hacking e utilizadar o que os outros
fazem podem passar ao artigo seguinte! Quem realmente esta a ler isto por
amor a arte e por querer realmente aprender ca vai:
Primeiro o que o programa faz e pegar numa linha de texto e submete-la a
funcao divide, que vai retornando palavra a palavra, e manipula as palavras
de maneira a retirar todas as acentuacoes e cedilhas que possam ocorrer, que
como se sabe sao caracteres nao aceites para formarem passwords, e tambem
converter as maiusculas para minusculas, que de uma vez por todas basta somar
o valor 32 a uma maiuscula para obter o lower-case ('A' + 32 = 'a'), e nao e
ter de construir uma "base de dados" que contemple todos os casos, como ja
ouvi dizer!!:)) (e que caso nao saibam, a tabela ASCII segue uma certa logica
...nao foi convencionada ao acaso).
Depois de obtermos a string final esta e colocada numa arvore binaria de
pesquisa, isto e:
Exemplo de uma implementacao:
Isto permite-nos obter por exemplo algoritmos de pesquisa de O(log n)
(ordem logaritmo de n) sendo n o numero de valores existentes na arvore!
Como se pode ver torna-se muito mais eficiente do que os usuais algoritmos de
pesquisa sequencial, de O(n) usados em vectores desordenados e em listas
ligadas!
MAS A MAIOR VANTAGEM deste metodo e que permite que nao hajam repeticoes
na arvore, e como se vai ver mais adiante permite-nos obter uma lista de
palavras ordenadas.
Como e que isso acontece?
E pronto, ca esta um programa que eu considero util, que foi feito a pensar
ser eficiente, que prova que a recursividade e uma coisa maravilhosa.
Mas melhor que ler isto, para aprender nada como dar uma olhada ao codigo!
(utilitario)
-------------------------------------------------------------------------
by Elektro
Ficara qualquer coisa como:
struct arvore{
int valor;
struct arvore *esq;
struct arvore *dir:
}
Uma arvore binaria de PESQUISA e uma arvore que satisfaz a seguinte ordem:
" Para qualquer no, todos os conteudos da sub-arvore esquerda (se houver
algum) sao menores ou iguais ao conteudo desse no e todos os conteudos da
sub-arvore direita (se houver algum) sao maiores que o conteudo desse no."
Isto pode nao ser facil de visualizar, mas se pensarmos que isto ocorre
tudo de uma forma recursiva, vemos que primeiro sao imprimidos os valores da
sub-arvore esquerda, que contem os elementos mais pequenos seguidos pela raiz
(primeiro no da arvore) que se pode dizer que e o valor mais ou menos
intermedio, e por fim a sub-arvore direita que contem os valores mais
elevados!
Alias este e um metodo muito usado para a ordenacao de vectores: