Trabalho final de Algoritmos e Estrutura de Dados II

Relatório sobre hash - Trabalho final de Algoritmos e Estrutura de Dados II

Lucas Brandão Rodrigues1

Autor Segundo deste Artigo^[a] 2

Maykon Adriell Dutra 3

Murilo de Oliveira Guimarães 4

VICTOR EMANUEL DA SILVA MONTEIRO5

UFG – Universidade Federal de Goiás

INF – Instituto de Informática

Cx. Postal 131 – CEP 74690-900  Goiânia (GO)

[e-mail]

2h^[b]

[e-mail]

[e-mail]

[e-mail]

Resumo: Este relatório apresenta uma análise sobre o que é hash, como funciona a utilização de algumas funções em um banco de dados comparando os resultados de experimentos realizados com as funções de hash utilizados com uma análise crítica do desempenho.

Palavras Chaves: tabela, hash, função, algoritmos, estrutura de dados, criptografia, matriz, dados, manipulação, inserção, pesquisa.

1. Introdução

Ao utilizar grandes conjuntos de dados que apresentam correlações entre si, pode se tornar difícil armazenar, acessar ou recuperar informações de forma eficiente e rápida. A fim de permitir o gerenciamento dessa grande quantidade de dados relacionais, existem estruturas de dados que realizam a manipulação, a inserção e pesquisa no código [1].

Suponhamos a existência de um dado chave que se relaciona diretamente com outro dado presente no dataset. Uma das alternativas para integrar o relacionamento entre essas duas partes de informação é a de utilizar dicionário composto por um relacionamento chave/valor. É possível implementar esse dicionário usando árvores de pesquisa binárias balanceadas e listas duplamente ligadas, por exemplo. Neste estudo, foi abordado o uso de tabelas e funções hash, que é considerado o método mais rápido das implementações de dicionário, capaz de executar inserção, exclusão e pesquisa de forma mais eficiente comparada com as outras implementações [2].

1. Função Hash

Hash é uma função matemática utilizada para converter um arquivo em um conjunto alfanumérico com comprimento fixo de caracteres dados. Utiliza-se, geralmente, para indexar e recuperar informações em um banco de dados. Uma outra maneira de pensar sobre isso é: dado uma chave brasileira e uma matriz, a função hash pode fazer uma sugestão de onde o índice da chave deve ser armazenado na matriz.

Pode-se dizer que uma função hash é considerada segura se for difícil encontrar dois valores de entrada que produzam o mesmo valor de hash. Essa propriedade é importante para garantir que os dados armazenados em um banco de dados sejam recuperados de forma confiável. A segurança de uma função hash, portanto, vai depender da implementação do valor de hash de 32 bits (4 bytes), pois esse pode pode ser quebrado usando um ataque de força bruta, enquanto um valor de hash de 128 bits (16 bytes) é considerado seguro contra esse tipo de ataque [3].

As funções de hash também são usadas no armazenamento de senhas, pois quando um usuário cria uma nova senha, a função hash é usada para gerar um valor de hash da senha, que fica armazenado em vez da própria senha. Quando o usuário tenta fazer login, a função de hash é usada para gerar um valor de hash da senha inserida. Se os dois valores de hash corresponderem, o usuário é autenticado.

[pic 1]

Figura 1: Funcionamento do hash simplificado

Por fim, podemos considerar as características da função hash como sendo:

• Saída de tamanho fixo: apresenta uma saída de tamanho fixo;
• Eficiência de operação: a função não pode ser complexa ao ponto de comprometer a velocidade de processamento;
• Determinística: um valor de entrada sempre possuirá a mesma casa.

1. Tabela Hash

Tabela hash, também conhecida como tabela de dispersão, é uma estrutura de dados especial que armazena os valores gerados a partir das funções de hash [1]. Através de uma matriz os pares de chave e valor são distribuídos uniformemente e armazenados. Consequentemente, é possível usar uma chave e encontrar o valor desejado ao fazer uma busca rápida.

Para calcular um índice em uma matriz na qual o elemento será pesquisado ou inserido na tabela, uma função hash é utilizada. Com isso, transforma-se a chave em um endereço de uma tabela. A implementação pode ser realizada de duas maneiras, usando um vetor ou uma lista encadeada.

Ao utilizar o um vetor como uma tabela hash, é preciso introduzir um processo de inserção e busca. Cada um dos números guardados nesse vetor serão chamados de chave. Em um exemplo utilizando o número 618396, escolhemos uma função de espalhamento para descobrir onde essa chave será armazenada. Podemos usar uma função simples, que é obter o resto valor a ser inserido pelo tamanho da tabela, por exemplo, se a tabela tiver o tamanho 100, a posição em que o número será inserido é a 96 [5].

Ao construir uma tabela com vetor de listas encadeadas, cada posição da tabela apresenta um ponteiro para uma lista encadeada e cada elemento é inserido nessa lista, mesmo se apresentar colisão, conforme ilustra a figura 2.

[pic 2]

Figura 2: Tabela hash com vetor de listas encadeadas [4]

1. Funções desenvolvidas

Neste estudo foram utilizadas cinco funções hash, que foram implementadas para posterior análise e comparação.

4.1        MD5

A MD5, ou algoritmo de resumo de mensagem,  é uma função criptográfica que permite receber como entrada mensagens de qualquer comprimento e retorna como saída um string de 32 caracteres. Inicialmente, ele era usado para criptografia de dados e foi desenvolvido para uso em máquinas 32-bit, porém, segundo a Carnegie Mellon University Software Engineering Institute, o seu uso deve ser evitado pois é considerado um algoritmo criptograficamente defasado. Por esses motivos, atualmente o MD5 é utilizado apenas para autenticação [6].