Fundamentos da criptomoeda: noções básicas de hashing e história

Uma História de Hashing

Uma função hash genérica é um tipo especial de função de programação usada para mapear dados de tamanho arbitrário para dados de um tamanho fixo. Funções de hash originadas de uma necessidade de comprimir dados para reduzir a quantidade de memória necessária para armazenar arquivos grandes. O caso de uso mais popular para uma função hash é para outra estrutura de dados específica chamada de mesa de hash, que é amplamente usado para pesquisa rápida de dados. As funções de hash ajudam a acelerar uma consulta de tabela ou banco de dados, detectando quaisquer dois hashes exatamente iguais.

Eles também ajudam a reduzir as marcas de arquivos enormes, como mp3s, PDFs ou imagens, para tornar gerenciável o trabalho com esses tipos de arquivos grandes. Para uma identificação rápida, um requisito fundamental das funções hash é que elas produz uma string de comprimento fixo de caracteres alfanuméricos.

Embora a razão principal para o início de uma função hash tenha vindo da necessidade de compactar o conteúdo, um benefício secundário logo se tornou um grampo do hash: identificadores únicos. O ideal é que, ao fazer hash de várias mensagens, duas mensagens diferentes nunca retornem o mesmo hash. Duas mensagens de hash diferentes resultando no mesmo hash de saída são chamadas de colisão.

Do ponto de vista do gerenciamento de banco de dados, isso significaria que dois objetos diferentes acabam sendo armazenados na mesma célula – não adianta se alguém está procurando definir identificadores únicos. Se considerarmos uma função hash com entradas infinitas (o que significa que podemos hash qualquer string), podemos derivar exatamente porque as colisões são de fato inevitável.

Princípio Pigeonhole

Dentro da criptografia matemática, existe um conceito chamado de princípio do escaninho que afirma que se ajustarmos (n) elementos em (m) espaços onde n > m, então, por princípio, existe pelo menos um espaço (m) ocupado por mais de dois elementos (n).

Por exemplo, cinco pessoas verificam seus casacos em um dos três cubículos disponíveis. Pelo princípio do escaninho, uma vez que o número de casacos armazenados (n) é maior do que os cubículos disponíveis (m), é garantido que pelo menos um cubículo contenha mais de um casaco.

Normalmente, os engenheiros de software estão interessados ​​em funções hash com um domínio infinito (isto é, eles tomam como entrada strings de todos os comprimentos possíveis) e um alcance finito. Novamente seguindo o princípio do escaninho, uma vez que nosso intervalo (n) é menor do que nosso domínio (m), segue-se que em deve existir pelo menos uma colisão. Uma função hash eficaz, portanto, busca apenas minimizar o número de colisões – por que isso se tornará mais claro em um momento, mas por agora, vamos voltar à história dos hashes.

Embora as funções hash tenham origem estritamente na manutenção do banco de dados & necessidades de gerenciamento, que favoreciam a velocidade acima de tudo, sua utilidade evoluiu rapidamente. Um ramo especial de funções hash que favorecia a privacidade, segurança, & a transparência logo entrou em campo; um ramo de funções de hash que permanecerá o foco deste artigo: funções de hash criptográficas.

Hashing criptográfico

As funções de hashing criptográfico, como o nome indica, favorecem a preservação de mensagens absolutamente ininterruptas. Embora minimizar as colisões seja uma boa prática para outras funções hash, especificamente para funções criptográficas, minimizar as colisões é uma requerimento. Em vez de maximizar a utilidade para um cenário de consulta rápida de banco de dados ou tabela, as funções de hash criptográficas são criadas com um cenário adversário em mente: um em que um decifrador de código (criptoanalista) está tentando ativamente causar uma colisão. Agora definiremos as notações de função hash padrão & estabelecer princípios de função hash dentro da perspectiva da criptografia.

Notação de função hash

Uma função hash criptográfica genérica tem duas entradas: a mensagem que vai compactar ou hash (x) & uma (s) chave (s) pública (s) que representa a saída de comprimento fixo de nosso hash em caracteres alfanuméricos. Nosso resultado hash é denominado resumo da mensagem ou simplesmente resumo (x *). Isso se parece com o seguinte:


H (s, x) = x *

Vamos encobrir essa notação percorrendo um exemplo da vida real como hash de uma string usando uma função de hash padrão anterior chamada MD5. Digamos que queremos usar MD5 para fazer o hash de um “Hello World!” fragmento. Também sabemos que, por padrão, o MD5 sempre produz uma sequência de 128 bits (0’s & 1’s). Essa notação seria a seguinte:

H (128, x) = ed076287532e86365e841e92bfc50d8c

Na verdade, se você for em frente & tente fornecer a função hash MD5 “Hello World!” você deve ver exatamente o mesmo hash resultante. Impressionante. Agora, vamos definir a notação para uma colisão; além das variáveis ​​anteriores H, s, x, & x * agora apresentamos uma segunda mensagem (x ‘). Numericamente, ocorre uma colisão ao fazer hash de duas mensagens distintas (x & x ’) resulta exatamente no mesmo resumo da mensagem (x *):

Se H (128, x) = H (128, x ’), nossa função hash (H) é considerada como tendo uma colisão em x & x ’.

Agora definimos a notação para o padrão atual de criptografia de função hash; se um adversário pode (em termos computacionais) causar uma colisão, uma função hash não é mais considerada praticamente segura.

Reflexões finais até a próxima vez

A última definição matemática é onde vive o fascinante catch-22 para a praticidade da função hash. Funções de hash originadas de uma necessidade de compactar & saída de dados uniformes padronizados para conveniência de armazenamento, o que significa que eles cuspem strings pseudo-aleatórias de um comprimento fixo. No entanto, para criar um completamente resistente à colisão função hash, cada mensagem (x) teria que ter uma saída hash do mesmo comprimento da entrada. Sem hashes de comprimento fixo, perdemos nossa capacidade de usá-los como uma estrutura de dados conveniente, mas, ao atribuir um comprimento fixo, renderizamos nossa função hash não completamente livre de colisões.

PS – Tenho certeza de que alguns de vocês cookies inteligentes notaram que em nosso exemplo MD5 notamos uma função hash que retorna uma string de comprimento 128, ainda nosso “Hello World!” hash retornou um 32 seqüência de caracteres alfanuméricos. Volte na próxima vez & vamos nos aprofundar nas funções hash para explicar de onde vem essa diferença.

Mike Owergreen Administrator
Sorry! The Author has not filled his profile.
follow me
Like this post? Please share to your friends:
Adblock
detector
map