Hashing na criptografia

Você está procurando aprender sobre hashing em criptografia? Se você fizer isso, você veio ao lugar certo.

Neste artigo, exploraremos mais sobre hashing.

Hashing é uma técnica de ciência da computação para identificar objetos ou valores de um grupo de objetos ou valores.

Parece confuso?

Vamos tentar entender por exemplo.

Bem, faculdades e escolas fornecem um número exclusivamente atribuído a cada um de seus alunos. Este número único é o que identifica um aluno e as informações relacionadas a ele. O método usado para gerar o número único é o Hashing.

Outro exemplo popular são as bibliotecas onde você encontrará toneladas de livros nas prateleiras. Cada livro tem seu número de identificação único para que possa ser localizado na enorme biblioteca!

Um exemplo moderno de hashing seria os jogadores que se registram no jogo. Valorant é um jogo gratuito lançado pela Riot. Ser gratuito significa que milhões de pessoas jogarão o jogo.

Cada jogador é identificado usando um valor de identificação único gerado usando um algoritmo de hash.

Vamos tentar entender em mais detalhes abaixo.

 

O que é Hashing?

Como afirmado acima, Hashing é o método de identificar um objeto de um grupo.

Cada objeto recebe um número de identificação único, uma vez que o hash.

Mas o que isso significa tecnicamente?

Tecnicamente, uma função matemática gera uma saída de comprimento fixo de qualquer string de entrada de qualquer comprimento.

As transações Bitcoin são hash, onde as transações obtêm IDs exclusivos.

Se você colocar “Hello, World!” em um Algoritmo de hash SHA-256, você obterá a seguinte saída:

Entrada: Olá Mundo!

Resultado: dffd6021bb2bd5b0af676290809ec3a53191dd81c7f70a4b28688a362182986f

Aqui, o SHA256 gera a saída da entrada fornecida. Como você pode ver, usamos o algoritmo de hashing Secure Hash Function (SHA-256). É um dos métodos de hash populares que existem, incluindo Message Direct (MD5) e Secure Hash Function (SHA1).

As principais propriedades da função hash a tornam confiável. Vamos listá-los abaixo.

  • Determinístico → Isso significa que a saída será a mesma para a entrada dada em qualquer circunstância.
  • Resistente à pré-imagem → O recurso de resistência à pré-imagem garante que o valor hash não seja útil para gerar o valor de entrada.
  • Computacionalmente eficiente → As funções hash são eficientes e não requerem grandes recursos computacionais para executar.
  • Não pode ser invertido com engenharia → A função hash não pode ser invertida com engenharia.
  • Resistente à colisão → A resistência à colisão garante que duas entradas não resultem na mesma saída.

Já cobrimos o Hashing criptográfico para iniciantes aqui. Confira lá: Hashing criptográfico: um guia para iniciantes. 

Mas, se você está aqui para coisas avançadas, não ficará desapontado.

 

O que é função de hash e tabelas de hash? E como eles funcionam?

Nesta seção, exploraremos a função hash e as tabelas hash com mais detalhes. Em termos de hashing, existem funções hash. Essas funções são responsáveis ​​por converter grandes entradas em pequenas entradas fixas. As tabelas de hash armazenam as saídas.

No processo de hashing, os objetos são distribuídos com base em seus pares de chave / valor para o array. Portanto, se você passar um array de elementos para as funções hash, obterá uma saída de array em que cada um dos elementos agora tem uma chave anexada a ele. O par chave / valor é muito útil quando se trata de acessar elementos em tempo real, pois oferece um tempo O (1) impressionante.

Para implementar funções hash, você pode tirar as duas abordagens preferidas.

  • A primeira abordagem é usar uma função hash para converter um elemento em um inteiro. Em seguida, a saída de inteiro pode ser usada para acessar o elemento ao colocar na tabela de hash.
  • Outra etapa é colocar o elemento na tabela hash e, em seguida, recuperá-lo usando a chave hash.

No 2º método, as funções serão as seguintes:

hash = hash_function (chave) index = hash% array_size

Aqui, o hash e os tamanhos do array são independentes um do outro. O valor do índice é calculado com base no tamanho da matriz. O operador de módulo (%) nos permite calcular o valor.

Em termos simples, uma função hash pode ser definida como uma função que pode mapear um conjunto de dados de tamanho arbitrário para um conjunto de dados de tamanho fixo. O conjunto de dados de tamanho fixo resultante pode ser armazenado na tabela hash. Muitos nomes são dados aos valores retornados pela função hash. Eles podem ser chamados de valores de hash, hashes, somas de hash e códigos de hash.

 

Escrevendo uma boa função Hash

Se você deseja criar uma boa função ou mecanismo de hash, precisa entender os requisitos básicos para criar um. Vamos listá-los abaixo:

  • A função hash precisa ser fácil de calcular. Isso significa que não devem ser necessários muitos recursos para executar.
  • A função hash precisa ser distribuída uniformemente. Ao fazer isso, as tabelas de hash são utilizadas para armazenar os valores de hash para que o clustering não aconteça.
  • O último requisito é ter menos ou nenhuma colisão. Sem colisão significa que nenhuma saída única é mapeada para duas entradas.

Tecnicamente, as colisões são parte de uma função hash e simplesmente não podem ser removidas de uma função hash. O objetivo é criar uma função hash que possa oferecer um bom desempenho da tabela hash e resolver a colisão por meio de técnicas de resolução de colisão.

 

Por que precisamos de uma boa função de hash?

Para entender a necessidade de uma função hash útil, vejamos um exemplo abaixo.

Vamos supor que queremos criar uma tabela Hash usando uma técnica de hashing onde as strings de entrada serão as seguintes, {“agk”, “kag”, “gak”, “akg”, “kga”, “gka”}

Agora, criamos uma função hash que simplesmente adiciona o valor ASCII de a (97), g (103) ek (107) e, em seguida, faz um módulo da soma por 307.

Claramente, a soma dos três números também é 307. Isso significa que se permutarmos todos os números e, em seguida, fizermos uma operação de módulo, obteremos o mesmo resultado. O resultado final seria armazenar todas as strings com o mesmo número de índice. O tempo algorítmico para a função hash também seria de complexidade O (n), o que não é desejável. Podemos facilmente concluir que a função hash que descrevemos não é ideal para cenários da vida real.

Para corrigir a função hash, podemos implantar a divisão da soma dos valores ASCII de cada elemento por outro número primo, 727. Fazendo isso, obteremos uma saída diferente para nossa matriz de strings de entrada fornecida.

 

Aprendendo sobre tabelas de hash

As tabelas de hash são muito úteis para armazenar o resultado de uma função de hash, que calcula o índice e, em seguida, armazena um valor em relação a ele. O resultado final seria um processo computacional mais rápido com complexidade O (1).

Tabelas de hash são tradicionalmente uma boa escolha para resolver problemas que requerem tempo O (n).

Então, se você pegar uma corda de comprimento fixo e, em seguida, tentar aprender a frequência de caracteres da corda.

Portanto, se string = “aacddce”, uma abordagem genérica é percorrer a string várias vezes e armazenar cada frequência.

# Forneça uma string de entrada e conte a frequência de caracteres nessa string

# O algoritmo é tempo de complexidade 0 (n)

temp_list = [] start = "uma" str = "ababcddefff" def alpha_zeta (): alpha = ‘a’ para i no intervalo (0,26): temp_list.append (alpha) alpha = chr (ord (alpha) + 1) return temp_list temp_list = alpha_zeta () #print (temp_list) def character_frequency (str, temp_list): para cada em temp_list: freq = 0 para i em str: if (i == each): freq = freq + 1 impressão (each, freq) character_frequency (str, temp_list)

O resultado do programa acima será o seguinte:

a 2 b 2 c 1 d 2 e 1 f 3 g 0 h 0 i 0 .. ..

Agora, vamos implementar uma tabela hash em C ++ e contar a frequência de caracteres.

#include using namespace std; Frequência int [26]; int hashFunc (char c) {return (c – ‘a’); } void countFre (string S) {for (int i = 0; i< S.length (); ++ i) {índice interno = hashFunc (S [i]); Frequência [índice] ++; } Para (int i = 0; i<26; ++ i) {cout << (char) (i + ‘a’) << ” << Frequência [i]<< endl; }} Int main () {cout<<"Olá Mundo"; countFre ("abbaccbdd"); }

A saída do programa seria a seguinte:

a 2 b 3 c 2 d 2

A complexidade O (N) do algoritmo torna-o mais rápido em comparação com outras abordagens lineares.

Como resolver colisões

Existem maneiras exclusivas de resolver colisões em funções hash. Uma das formas mais populares é o encadeamento separado, também conhecido como hashing aberto. É implementado com uma lista encadeada em que cada um dos elementos da cadeia é uma lista encadeada. Essa abordagem permite armazenar elementos e garantir que certos elementos sejam apenas parte da lista vinculada específica, resolvendo a colisão. Isso significa que dois valores de entrada não podem ter o mesmo valor de hash de saída.

 

Explorando Hash em Python

Nesta seção, veremos rapidamente o hash em Python. A razão pela qual escolhemos Python é que ele é fácil de ler e pode ser usado por qualquer pessoa sem muitos problemas.

Como o hashing é uma função comum, já está implementado na biblioteca Python. Ao usar o módulo, você pode fornecer um objeto como sua entrada e, em seguida, retornar o valor com hash.

A sintaxe do método hash é:

hash (objeto)

Como você pode ver, ele leva em um único parâmetro, que é o objeto. O objeto pode ser inteiro, flutuante ou string.

O valor retornado do método hash () depende da entrada. Para um número inteiro, ele pode retornar o mesmo número, enquanto para decimal e string seriam diferentes.

Vejamos alguns exemplos abaixo.

num = 10 deci = 1,23556 str1 = "Nitish" print (hash (num)) print (hash (deci)) print (hash (str1))

A saída do código acima é a seguinte:

No entanto, o hash não pode ser aplicado a todos os tipos de objetos. Por exemplo, se você se lembrar que criamos uma lista de a a z em nosso primeiro programa. Se tentarmos fazer o hash, a janela de saída passará por um TypeError: tipo inalterável: ‘list’

Para aplicar hash a uma lista de objetos, você precisa usar tupla.

vogais = (‘a’, ‘e’, ​​’i’, ‘o’, ‘u’) imprimir (hash (vogais)) Saída ⇒ -5678652950122127926

Hashing na criptografia

O hash é útil para criptografia. Bitcoin utiliza hashing para criar e gerenciar árvores Merkle

Além disso, o hashing faz parte da criptografia há muito tempo. No entanto, o melhor caso de uso de hash é fazer hash de senhas e armazená-las. 

Árvores Merkle

A árvore Merkle é uma estrutura de dados útil quando se trata de fazer a verificação segura de dados em um grande pool de dados. Tanto Bitcoin quanto Ethereum utilizam árvores Merkle para resolver muitas barreiras tecnológicas ao armazenar e acessar dados em uma rede aberta.

Qualquer rede centralizada não precisa se preocupar em armazenar e acessar dados, pois há apenas uma fonte para acessar e armazenar os dados. No entanto, a equação muda quando há uma rede descentralizada, pois agora os dados precisam ser copiados entre centenas de pares participantes.

Árvores Merkle resolvem o problema, fornecendo uma maneira confiável e eficiente de compartilhar e verificar dados entre pares.

Exemplo de Merkle Tree

Mas, por que estamos discutindo árvores Merkle aqui? Árvores Merkle usam o hash como a funcionalidade principal para conectar os diferentes nós e blocos de dados.

Árvores Merkle é uma árvore de cabeça para baixo que pode resumir todo o conjunto de transações.

Se você quiser saber mais sobre árvores Merkle e como ele usa hash na criptografia, verifique nosso guia detalhado:

Um guia para árvores Merkle. Lá, discutimos como os implementos de árvores Merkle são feitos em bitcoin e outros casos de uso.

Processo de Mineração

O processo de mineração também aproveita o hashing. Quando se trata de mineração de bitcoin, um novo bloco é adicionado ao blockchain quando há uma demanda por ele.

Um método precisa ser seguido para adicionar o bloco ao blockchain. Um valor hash é gerado dependendo do conteúdo do bloco quando um novo bloco chega. Além disso, se o hash gerado for mais do que dificuldade de rede, o processo de adicionar o bloco ao blockchain é iniciado.

Uma vez feito isso, todos os pares na rede reconhecem a adição do novo bloco.

Mas, raramente é o caso, pois a dificuldade da rede, na maioria dos casos, é sempre maior em comparação com o hash gerado. Há outro aspecto que desempenha um papel crucial no processo de mineração. É o nonce.

O nonce é adicionado ao hash do bloco e é uma string arbitrária. Uma vez feito isso, a string concatenada é então comparada ao nível de dificuldade. Se o nível de dificuldade for inferior ao da string concatenada, o nonce é alterado até que o nível de dificuldade seja superior.

O processo pode ser resumido nas seguintes etapas:

  • O conteúdo é hash para criar um novo valor de hash sempre que um novo bloco é gerado ou obtido,
  • Um novo valor de nonce é gerado e anexado ao hash
  • O processo de hash ocorre na nova string contatada 
  • O valor final do hash é então comparado com o nível de dificuldade da rede
  •  se o valor final do hash for menor do que o nonce, o processo será repetido novamente. O processo só para quando o valor do hash é maior do que o nonce.
  • Bloco se junta à cadeia quando o nível de dificuldade é mais alto
  • Os mineiros, então, assumem a responsabilidade de minerar o novo bloco e compartilhar as recompensas entre eles.

O termo “taxa de hash” também vem daqui. A taxa de Hash é a taxa na qual as operações de hashing ocorrem. Uma taxa de hash mais alta significa que os mineradores precisariam de mais poder de computação para participar do processo de mineração.

 

Conclusão

Isso nos leva ao fim de nosso guia detalhado de hashing em criptografia. Cobrimos o hash em detalhes e também exploramos o código por trás dele.

Então, o que você acha disso? Comente abaixo e deixe-nos saber.

 

#PERGUNTAS FREQUENTES

O que é hash na criptografia?

Na criptografia, hashing é um método para converter dados em uma string única de texto usando um método eficiente. Além disso, não há limitação quanto ao tipo de dados ou seu tamanho – o hash funciona em todos eles.

Como o hashing é usado na criptografia?

A criptografia utiliza hash para fazer hash de senhas ou gerar números de identificação exclusivos.