quarta-feira, 23 de dezembro de 2009

Funções de Hash

Funções de Hash são utilizadas em programação para avaliar uma entrada, que pode ser, por exemplo, uma string, e a partir desta gerar um código numérico. Esse código é guardado para no futuro utilizado para verificar a integridade do original.

No dia a dia, usamos códigos de Hash o tempo todo em operações como, por exemplo, a transmissão de um arquivo ISSO com o MD5 anexado, para que o download possa ser verificado ou na comparação dearquivos feitas por softwares de backup para saber se houve alguma alteração nestes.

Propriedades:




y = f(x)
Não existe f -1
X é uma string de bits de tamanho arbitrário.
Y é uma string de bits de tamanho fixo.
Dado y é virtualmente impossível
obter x
Se x diferente de x’ à f(x) diferente f(x’)

Obs.: As duas primeiras propriedades dizem que a partir do arquivo original podemos chegar ao hash, porém a partir do hash não podemos chegar ao arquivo original.

Implementação de uma função de hash:

int HASH (char *s)
{
s-> inteiro (long int)
-> double
s / primo
retorna (resto);
}


Um Exemplo:


#include
#include

long int hash1 (char *s);

void main()
{
char c[200] = "Bola";
clrscr();
printf("teste\n");
printf("\n\n%ld",hash1 (c));

}

long
int hash1 (char *s)
{
char *p;
double x;
int i;
long int
primo=17;
long int b, a;
p=s;
i=0;
x=0.0;
while (*p !='\0')
{
printf("%c ",*p);
x=x+(*p)*(pow(2,i));
p++;
i++;
}
b=(long int) x;
printf("\n%f",x);
a=b%primo;
printf("\n%ld",b);
return(a);
}

Explicando o código acima:
pega-se uma string, por exemplo, BOLA. Multiplica-se cada letra por sua posição, ou seja:

letra: B posição: 3
letra: O posição: 2
letra: L posição: 1
letra: A posição: 0

de modo que:

Ax2^0 + L x 2^1 + O x 2^2 + B x2^3

Aqui o número 2 foi escolhido arbitrariamente, podendo ser qualquer outro número.

No caso da línguagem C, ao se chamar uma variável caracter por %d ao invés de %c, o próprio compilador já faz a conversão da letra para um valor numérico.

Feita multiplicação e a soma, deve-se então dividir o valor por um número primo qualquer. A escolha por um número primo vem de uma característica próprias desses números, que no momento em que dividimos uma quantidade de números quaisquer por um primo encontramos uma diversidade de resultados maior do que os que encontraríamos se fizessemos a divisão por outro número, o que tenderia a concentrar o resultado em alguns valores.

Feito isso pegamos o resto, ou seja, o valor após a vírgula, e esse será o nosso hash.

Nenhum comentário: