Mostrar código-fonte de Função hash

[[Imagem:Hash table 4 1 1 0 0 1 0 LL.svg|thumb|240px|direita|Uma função hash que mapeia nomes para inteiros de 0 a 15. Existe um colisão entre a chaves "John Smih" e "Sandra Dee".]]

Uma '''função ''hash''''' é um [[algoritmo]] que mapeia [[Dados (computação)|dados]] de comprimento variável para dados de comprimento fixo. Os valores retornados por uma função ''hash'' são chamados '''valores ''hash''''', '''códigos ''hash''''', '''somas ''hash''''' ('''''hash sums'''''), '''''checksums''''' ou simplesmente '''''hashes'''''. Um uso é uma [[estrutura de dados]] chamada de [[tabela hash|tabela ''hash'']], amplamente usada em ''software'' de [[computador]] para consulta de dados rápida. Funções ''hash'' aceleram consultas a tabelas ou [[Banco de dados|bancos de dados]] por meio da detecção de registros duplicados em um arquivo grande. Um exemplo é encontrar trechos similares em sequências de DNA. Eles também são úteis em [[criptografia]]. Uma [[função hash criptográfica|função ''hash'' criptográfica]] permite verificar facilmente alguns mapeamentos de dados de entrada para um valor ''hash'' fornecido, mas se os dados de entrada são desconhecidos, é deliberadamente difícil reconstruí-lo (ou alternativas equivalentes) conhecendo o valor do ''hash'' armazenado. Isto é usado para assegurar a [[Integridade de dados|integridade]] de dados transmitidos e é o bloco de construção para [[HMAC]]s, que fornecem [[autenticação de mensagem]].

Funções ''hash'' estão relacionadas a (e frequentemente confundidas com) [[Soma de verificação|somas de verificação]] (''checksums''), [[Dígito verificador|dígitos verificadores]], [[Impressão digital (computação)|impressões digitais]], [[Compressão com perda de dados|compressão com perdas]], [[Função de aleatorização|funções de aleatorização]], códigos de correção de erros e cifras. Apesar desses conceitos se sobreporem até certo ponto, cada um tem seus próprios usos e requisitos e são projetados e otimizados de maneiras diferentes. O banco de dados [[HashKeeper]], mantido pelo American National Drug Intelligence Center, por exemplo, é mais apropriadamente descrito como um catálogo de arquivos de impressões digitais do que de valores de hash.

== Descrição ==
Um ''hash'' (ou escrutínio) é uma sequência de [[bit|''bits'']] geradas por um [[algoritmo de dispersão]], em geral representada em base [[hexadecimal]], que permite a visualização em letras e [[número]]s (0 a 9 e A a F), representando um [[nibble|''nibble'']] cada. O conceito teórico diz que "''hash'' é a transformação de uma grande quantidade de dados em uma pequena quantidade de informações".

Essa sequência busca identificar um arquivo ou informação unicamente. Por exemplo, uma mensagem de [[E-mail|correio eletrônico]], uma senha, uma [[Chave (criptografia)|chave criptográfica]] ou mesmo um [[arquivo]]. É um método para transformar dados de tal forma que o resultado seja (quase) exclusivo. Além disso, funções usadas em criptografia garantem que não é possível a partir de um valor de ''hash'' retornar à informação original.

Como a sequência do ''hash'' é limitada, muitas vezes não passando de 512 bits, existem colisões (sequências iguais para [[dados]] diferentes). Quanto maior for a dificuldade de se criar colisões intencionais, melhor é o [[algoritmo]].

Uma [[função (matemática)|função]] de ''hash'' recebe um valor de um determinado tipo e retorna um código para ele. Enquanto o ideal seria gerar identificadores únicos para os valores de entrada, isso normalmente não é possível: na maioria dos casos, o [[Função (matemática)#Domínio, contradomínio e imagem|contradomínio]] de nossa função é muito menor do que o seu domínio, ou seja, <math>x</math> (o tipo de entrada) pode assumir uma gama muito maior de valores do que <math>\operatorname{hash}(x)</math> (o resultado da função de hash).

Os algoritmos de ''hash'' mais usados são os de 16 [[byte]]s (ou 128 bits, tamanho do ''message digest'') [[MD4]] e [[MD5]] ou o [[SHA-1]], de 20 bytes (160 bits). Características de alguns algoritmos:
# [[MD4]]: Desenvolvido em 1990/91 por [[Ronald Rivest|Ron Rivest]]<nowiki>, vários ataques foram detectados, o que fez com que o algoritmo fosse considerado frágil. Descrito na RFC 1320</nowiki><ref>{{citar web|URL = https://www.ietf.org/rfc/rfc1320.txt|título = The MD4 Message-Digest Algorithm|data=abril de 1992|acessodata=16-01-2015|autor = |publicado = }}</ref>{{Carece de fontes|ciência=sim|data=Dezembro de 2008}}
# [[MD5]]: O MD5 (Message-Digest algorithm 5) é um algoritmo de ''hash'' de 128 bits unidirecional desenvolvido pela RSA Data Security, Inc., descrito na RFC 1321, e muito utilizado por ''softwares'' com protocolo par a par ([[P2P]], ou Peer-to-Peer, em inglês), verificação de integridade e logins. Existem alguns métodos de ataque divulgados para o MD5.<ref>STEVENS, Marc. On Collisions for MD5. Junho 2007. Mestrado. Eindhoven University of Technology, The Netherlands. (http://www.win.tue.nl/hashclash/On%20Collisions%20for%20MD5%20-%20M.M.J.%20Stevens.pdf)</ref><ref>DAUM, Magnus & LUCKS, Stefan. (2005) Hash Collisions (The Poisoned Message Attack). <http://th.informatik.uni-mannheim.de/people/lucks/HashCollisions/ {{WebCite|url=https://www.webcitation.org/6IIGCxYaC?url=http://th.informatik.uni-mannheim.de/People/lucks/HashCollisions/ |date=20130722042230 |dateformat=iso }}>. Acessado em 25 de março de 2008</ref>
# [[SHA-1]] (''Secure Hash Algorithm''): Desenvolvido pelo [[NIST]] e [[NSA]]. Já foram exploradas falhas no SHA.<ref>Bruce Schneier, Schneier on Security <http://www.schneier.com/blog/archives/2005/02/sha1_broken.html>. Acessado em 23 de outubro de 2008.</ref>
# [[Whirlpool (criptografia)|WHIRLPOOL]]: função criptográfica de ''hash'' desenvolvida por [[Paulo S. L. M. Barreto]] e por [[Vincent Rijmen]] (coautor do [[Criptografia de chave pública|AES]]). A função foi recomendada pelo projeto [[NESSIE]] (Europeu). Foi também adotado pelo [[Normas ISO|ISO]] e [[IEC]] como parte do padrão internacional [[ISO 10118-3]].
O processo é unidirecional e impossibilita descobrir o conteúdo original a partir do ''hash''. O valor de conferência ("[[soma de verificação]]") muda se um único ''bit'' for alterado, acrescentado ou retirado da mensagem.

== Ver também ==
* [[Tabela de dispersão]]
* [[Tratamento de colisões através de encadeamento]]
* [[Criptografia de chave pública]]
* [[Chave privada]]
* [[Criptografia]]

{{Referências}}
{{Criptografia}}
{{Portal3|Tecnologias de informação}}

{{controle de autoridade}}

[[Categoria:Criptografia]]
[[Categoria:Algoritmos de busca]]
[[Categoria:Detecção e correção de erros]]