8

Gostaria de entender como se relacionam a função hash de criptografia (na qual se encripta por exemplo senhas), com a hash chave-valor em programação (também conhecida como 'dicionário' em Python por exemplo).

1
  • 2
    Pelo que entendi das respostas, o hash é o resultado de um cálculo ou algoritmo aplicado sobre um valor que deve sempre gerar o mesmo resultado quando aplicado ao mesmo valor. No caso do dicionário, serve para gerar um identificador que vai determinar o endereço de um item e no caso da senha serve para gerar um valor cujo propósito é dispensar o conhecimento ou armazenamento e dificultar a determinação da senha original.
    – Caffé
    Commented 1/03/2017 às 16:24

3 Respostas 3

10
+100

A função hash, de forma geral, é uma função que recebe dados de tamanho arbitrários e transforma esses dados num valor alfa numérico.

Como você percebeu, a função hash é usada em diferentes contextos dentro da computação. Cada contexto exige que a função hash obedeça(ou não) determinados tipos de propriedades.

Entre essas propriedades encontram-se o determinismo, definição de intervalos, uniformidade, invertibilidade e tratamento de colisões.

  1. Determinismo

Uma função hash sempre deve gerar o mesmo valor para uma entrada. Dessa forma, a função hash se aproxima muito do modelo de função matemática.

Algumas versões de python não obedecem essa propriedade. Isso acontece porque python gera um seed(aleatório) que será utilizado no hashing. Esse tipo de situação deve ser evitada caso alguém queira trabalhar com persistência (escrever no disco). Pois, os valores que foram salvos numa execucao para um dado serão diferentes dos valores gerados em uma nova execução.

  1. Intervalos

Algumas aplicações exigem que a função hash gere valores dentro de um intervalo numérico fixo. Um exemplo desse tipo de aplicação é o algoritmo de criptografia SHA-1 que gera um valor de 160 bits.

Outras exigem que o intervalo seja dinâmico. O dicionário de python, que usa o valor gerado pela função hash como índice de um array, expande a medida que novos pares chave-valor são inseridos.

  1. Uniformidade

Funções hashing com intervalo definido devem garantir que cada posição do intervalo tenha igual probabilidade de ser gerada. O motivo disso é que podem ocorrer o caso de dois dados diferentes gerarem um mesmo valor (colisão). Colisões são operações custosas de serem tratadas. Dependendo do caso, elas nem precisam ser tratadas.

  1. Invertibilidade

Aplicações de criptografia exigem que seja difícil de encontrar um dado a partir do valor gerado por uma função hashing.

A implementação de uma função hash varia muito dependendo do problema que ela deve solucionar.

Um exemplo simples de HashCode é o que foi implementado para geração de um valor hash em strings no Java (Útil para utilizar em mapas/dicionário):

public int hashCode() {
   int hash = 0;
   for (int i = 0; i < s.length(); i++)
      hash = (hash * 31) + charAt(i);
   return hash;
}

O valor 31 foi escolhido por ser fácil de implementar utilizando lógica de baixo nível (shifts) e ser um numero primo (por algum motivo desconhecido números primos têm um numero menor de colisões).

Voce também pode dar uma olhada no algoritmo de rabin-karp para ver a aplicação de hashing num algoritmo de busca de padrões num texto.

Na sua pergunta você fala da função hash usada em criptografia para "encriptar senhas". Entretanto, note que encriptar é um processo diferente do hashing. Ao utilizar hashing, o objetivo é receber um dado e gerar um valor alfa numérico para esse dado (um determinado valor pode ser gerado por dados diferentes). No caso de encriptação, você vai modificar o dado para torna-lo ilegível para quem desconhece o método utilizado na hora de encriptar. Ou seja, encriptar sempre tem ida e volta garantida (para quem conhecer a senha).

1
  • 1
    Ótima resposta, +1. Só um detalhe: a saída de um hash não é necessariamente um dado alfanumérico - essa é somente uma das representações possíveis dessa saída (outra muito usada é a base64, e há ainda funções de hash que incorporam na saída o sal utilizado e talvez outras informações importantes). E quanto ao uso de hashes na proteção de senhas, a pergunta "Como fazer hash de senhas de forma segura?" tem mais informações úteis.
    – mgibsonbr
    Commented 28/03/2017 às 3:15
5

O hash é um algoritmo matemático que vai pegar uma string e transformar em outra, de forma que não seja possível reverter. O hash normalmente é usado na criptografia para salvar senhas, como você já deve ter percebido.

Quanto a relação de hash de criptografia com o dicionário do python é que um utiliza o outro em sua estrutura.

Um dicionário de dados é uma estrutura dinâmica que permite armazenar valores através de uma chave (geralmente string). Para armazenar estes valores ele faz um hash, ou seja, pega a chave string e aplica o algoritmo de hash da criptografia, e descobre a posição em que o valor está.

Um exemplo bem simples de armazenamento em dicionário:

function buscaNoDicionario(string chave) {
  /* assumimos neste exemplo que a chaveReal será um valor numérico, indicando uma posição de memória */
  int chaveReal = algoritmoHash(chave);

  return arrayInterno[chaveReal];
}

Pode parecer estranho existir uma função que faça estes cálculos, mas isso normalmente é gerenciado pela própria linguagem. No seu dia-a-dia você deve escrever algo como:

meuDicionario["nome"] = "Jean"
meuDicionario["idade"] = 5000

E na hora de executar o programa o compilador traduz isso para algo como:

adicionaNoDicionario(meuDicionario, "nome", "Jean")
adicionaNoDicionario(meuDicionario, "idade", 5000)

Note que o hash utilizado no dicionário tem requerimentos muito diferentes do que é utilizado na criptografia. Posso destacar alguns pontos:

  • Geralmente vai gerar como saída um valor numérico, indicando uma posição de memória;
  • Tem que fazer o máximo possível para não ter colisões, isto é, duas entradas diferentes não podem gerar uma mesma saída;
  • Deve ser rápido, pois a ideia não é manter uma informação segura, e sim melhorar a forma de acessar os dados.
4

O dicionário é uma tabela de hashes. Cada hash é obtido através de uma função que calcula seu valor para determinar em qual bucket deve ser inserido. O hash é só uma forma para facilitar a localização do que deseja de forma rápida. O valor real que foi usado para calcular, a chave, precisa ser armazenado também, se precisar conhecê-lo.

A criptografia calcula o hash e apenas o armazena, sem o conteúdo real, afinal queremos esconder o dado real.

Para cada necessidade o tamanho do hash variará e até por isso, mas não só, a fórmula de cálculo é um pouco diferente.

Você deve fazer log-in para responder a esta pergunta.