Hashing u kriptografiji

Želite li saznati više o raspršivanju u kriptografiji? Ako to učinite, onda ste došli na pravo mjesto.

U ovom ćemo članku istražiti više o raspršivanju.

Hashing je tehnika računalnih znanosti za identificiranje predmeta ili vrijednosti iz skupine predmeta ili vrijednosti.

Zvuči zbunjujuće?

Pokušajmo razumjeti na primjeru.

Pa, fakulteti i škole daju jedinstveno dodijeljeni broj svakom od svojih učenika. Ovaj jedinstveni broj identificira učenika i informacije povezane s njim. Metoda koja se koristi za generiranje jedinstvenog broja je Hashing.

Još jedan popularan primjer su knjižnice u kojima ćete na policama pronaći tone knjiga. Svaka knjiga tamo ima svoj jedinstveni identifikacijski broj kako bi se mogla nalaziti u ogromnoj knjižnici!

Suvremeni primjer raspršivanja bili bi igrači koji se registriraju za igru. Valorant je besplatna igra koju je pokrenuo Riot. Biti slobodan za igru ​​znači da će milijuni ljudi igrati tu igru.

Svaki se igrač identificira pomoću jedinstvene identifikacijske vrijednosti generirane pomoću algoritma za raspršivanje.

Pokušajmo to detaljnije razumjeti u nastavku.

 

Što je hashiranje?

Kao što je gore rečeno, raspršivanje je metoda identificiranja predmeta iz skupine.

Svaki objekt dobiva jedinstveni identifikacijski broj jednom raspršenim.

Ali, što to tehnički znači?

Tehnički, matematička funkcija generira izlaz fiksne duljine iz bilo kojeg ulaznog niza bilo koje duljine.

Bitcoin transakcije se raspršuju tamo gdje transakcije dobivaju jedinstvene ID-ove.

Ako stavite “Hello, World!” u an SHA-256 algoritam raspršivanja, dobit ćete sljedeći izlaz:

Ulazni: Pozdrav svijete!

Izlaz: dffd6021bb2bd5b0af676290809ec3a53191dd81c7f70a4b28688a362182986f

Ovdje SHA256 generira izlaz iz datog ulaza. Kao što vidite, koristili smo algoritam za hashiranje funkcije sigurnog raspršivanja (SHA-256). To je jedan od popularnih načina raspršivanja, uključujući Message Direct (MD5) i Secure Hash Function (SHA1).

Ključna svojstva hash funkcije čine je pouzdanom. Navedimo ih u nastavku.

  • Deterministički → To znači da će izlaz biti isti za zadani ulaz u bilo kojim okolnostima.
  • Otporan na predodžba → Značajka otpornosti na sliku osigurava da vrijednost raspršivanja nije korisna za generiranje ulazne vrijednosti.
  • Računalno učinkovit → Hash funkcije su učinkovite i za njihovo izvršavanje nisu potrebni ogromni računski resursi.
  • Ne može se obrnuti inženjering → Funkcija raspršivanja ne može se poništiti.
  • Otporan na sudar → Otpornost na sudar osigurava da niti jedan ulaz ne rezultira istim izlazom.

Ovdje smo već obradili kriptografsko hashiranje za početnike. Pogledajte tamo: Kriptografsko raspršivanje: Vodič za početnike. 

Ali, ako ste ovdje zbog naprednih stvari, nećete biti razočarani.

 

Što je hash funkcija i tablice hasha? I kako rade?

U ovom ćemo odjeljku detaljnije istražiti hash funkciju i hash tablice. Što se tiče raspršivanja, postoje hash funkcije. Te su funkcije odgovorne za pretvaranje velikih ulaza u male fiksne ulaze. Hash tablice pohranjuju izlaze.

U procesu raspršivanja, objekti se distribuiraju na temelju njihovih parova ključ / vrijednost u polje. Dakle, ako proslijedite niz elemenata u hash funkcije, dobit ćete izlaz niza u kojem je svaki od elemenata sada povezan s ključem. Par ključ / vrijednost vrlo je koristan kada je riječ o pristupu elementima u stvarnom vremenu, jer nudi impresivno O (1) vrijeme.

Da biste implementirali hash funkcije, možete skinuti dva preferirana pristupa.

  • Prvi pristup je uporaba hash funkcije za pretvaranje elementa u cijeli broj. Dalje, cjelobrojni izlaz može se koristiti za pristup elementu prilikom stavljanja tablice raspršivanja.
  • Sljedeći je korak staviti element u tablicu raspršivanja, a zatim ga dohvatiti pomoću raspršene tipke.

U 2. metodi, funkcije će biti sljedeće:

hash = hash_function (ključ) indeks = hash% array_size

Ovdje su veličine hasha i polja neovisne jedna o drugoj. Vrijednost indeksa izračunava se na temelju veličine polja. Modulo operator (%) omogućuje nam izračunavanje vrijednosti.

Jednostavno rečeno, hash funkcija može se definirati kao funkcija koja može preslikati proizvoljni niz podataka u skup podataka fiksne veličine. Rezultirajući skup podataka fiksne veličine može se pohraniti u tablicu raspršivanja. Vrijednostima koje vraća hash funkcija daju se mnoga imena. Mogu se nazvati hash vrijednostima, hashovima, hash zbrojevima i hash kodovima.

 

Pisanje dobre funkcije raspršivanja

Ako želite stvoriti dobru hash funkciju ili mehanizam, morate razumjeti osnovne zahtjeve za stvaranje hash funkcije. Navedimo ih u nastavku:

  • Funkcija raspršivanja mora biti jednostavna za izračunavanje. To znači da za izvršenje ne bi trebalo biti potrebno puno resursa.
  • Hash funkcija mora biti jednoliko raspoređena. Na taj se način hash tablice koriste za spremanje hash vrijednosti, tako da se grupiranje neće dogoditi.
  • Posljednji je uvjet imati manji ili nikakav sudar. Nema sudara znači da niti jedan izlaz nije preslikan na dva ulaza.

Tehnički, sudari su dio hash funkcije i jednostavno se ne može ukloniti iz hash funkcije. Cilj je stvoriti hash funkciju koja može ponuditi dobre performanse hash tablice i riješiti koliziju tehnikama rješavanja sudara.

 

Zašto nam treba dobra hash funkcija?

Da bismo razumjeli potrebu za korisnom hash funkcijom, prođimo kroz primjer u nastavku.

Pretpostavimo da želimo stvoriti tablicu raspršivanja pomoću tehnike raspršivanja gdje će ulazni nizovi biti sljedeći, {“agk”, “kag”, “gak”, “akg”, “kga”, “gka”}

Sada kreiramo hash funkciju koja jednostavno dodaje ASCII vrijednost a (97), g (103) i k (107), a zatim vrši modul zbroja za 307.

Jasno je da je zbroj triju brojeva također 307. To znači da ćemo, ako permutiramo sve brojeve i zatim izvršimo modulo operaciju, dobiti isti rezultat. Krajnji rezultat bio bi spremanje svih nizova na isti indeksni broj. Algoritamsko vrijeme za hash funkciju također bi bilo O (n) složenost, što nije poželjno. Lako možemo zaključiti da hash funkcija koju smo opisali nije optimalna za stvarne scenarije.

Da bismo popravili hash funkciju, možemo rasporediti dijeljenje zbroja ASCII vrijednosti svakog elementa s drugim prostim brojem, 727. Čineći to, dobit ćemo drugačiji izlaz za zadani niz ulaznih nizova.

 

Učenje o hash tablicama

Hash tablice su vrlo korisne za pohranu rezultata hash funkcije, koja izračunava indeks, a zatim sprema vrijednost prema njemu. Krajnji rezultat bio bi brži računski postupak s složenošću O (1).

Hash tablice tradicionalno su dobar izbor u rješavanju problema koji zahtijevaju O (n) vrijeme.

Dakle, ako pokupite niz fiksne duljine, a zatim pokušate naučiti frekvenciju znakova niza.

Dakle, ako je string = “aacddce”, tada je generički pristup proći niz više puta i pohraniti svaku frekvenciju.

# Navedite ulazni niz i prebrojite učestalost znakova u tom nizu

# Algoritam je vrijeme složenosti 0 (n)

privremeni_popis = [] početak = "a" str = "ababcddefff" def alpha_zeta (): alpha = ‘a’ za i u rasponu (0,26): temp_list.append (alpha) alpha = chr (ord (alpha) + 1) return temp_list temp_list = alpha_zeta () #print (temp_list) def frekvencija_znaka (str, privremeni_popis): za svaki na popisu privremenih: freq = 0 za i u str: if (i == svaki): freq = freq + 1 ispis (svaki, frekv.) frekvencija_znaka (str, privremeni_popis)

Rezultat gornjeg programa bit će sljedeći:

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

Sada, implementirajmo hash tablicu u C ++ i izbrojimo frekvenciju znakova.

#include using namespace std; frekvencija int [26]; int hashFunc (char c) {return (c – ‘a’); } void countFre (string S) {for (int i = 0; i< S.dužina (); ++ i) {int indeks = hashFunc (S [i]); Frekvencija [indeks] ++; } Za (int i = 0; i<26; ++ i) {cout << (char) (i + ‘a’) << ” << Učestalost [i]<< endl; }} Int main () {cout<<"Pozdrav svijete"; countFre ("abbaccbdd"); }

Rezultat programa bio bi sljedeći:

a 2 b 3 c 2 d 2

Složenost O (N) algoritma čini ga bržim u usporedbi s drugim linearnim pristupima.

Kako riješiti kolizije

Postoje jedinstveni načini za rješavanje sudara u hash funkcijama. Jedan od popularnih načina je odvojeno ulančavanje lanca koje je poznato i kao otvoreno raspršivanje. Provodi se s povezanim popisom gdje je svaki od elemenata u lancu sam povezan popis. Ovaj pristup omogućuje pohranu elemenata i osigurava da su određeni elementi samo dio specifičnog povezanog popisa, rješavajući koliziju. To znači da niti dvije ulazne vrijednosti ne mogu imati istu izlaznu hash vrijednost.

 

Istraživanje hasha na Pythonu

U ovom ćemo odjeljku brzo pogledati hash u Pythonu. Razlog zašto smo odabrali Python je taj što ga je lako čitati i može ga koristiti svatko bez puno problema.

Kako je hashiranje uobičajena funkcija, već je implementirano u Python knjižnici. Korištenjem modula možete objekt dati kao ulaz, a zatim vratiti hashiranu vrijednost.

Sintaksa hash metode je:

hash (objekt)

Kao što vidite, uzima jedan parametar, a to je objekt. Objekt može biti cjelobrojni, plutajući ili niz.

Vraćena vrijednost metode hash () ovisi o ulazu. Za cijeli broj može vratiti isti broj, dok se za decimalni niz i niz razlikuju.

Pogledajmo nekoliko primjera u nastavku.

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

Izlaz gornjeg koda je kao u nastavku:

Međutim, raspršivanje se ne može primijeniti na sve vrste objekata. Na primjer, ako se sjećate da smo u našem prvom programu stvorili popis od a do z. Ako ga pokušamo hashirati, izlazni prozor će proći kroz TypeError: unhashable type: ‘list’

Da biste primijenili raspršivanje na popis objekata, trebate upotrijebiti tuple.

samoglasnici = (‘a’, ‘e’, ​​’i’, ‘o’, ‘u’) print (hash (samoglasnici)) Izlaz ⇒ -5678652950122127926

Hashing u kriptografiji

Hashing je koristan za kriptografiju. Bitcoin koristi raspršivanje za stvaranje i upravljanje stablima Merkle

Također, raspršivanje je dio kriptografije već dosta dugo. Međutim, najbolji slučaj heširanja je heširanje lozinki i njihovo spremanje. 

Merkle drveće

Merkle stablo je struktura podataka koja je korisna kada je riječ o sigurnoj provjeri podataka u velikom spremištu podataka. I Bitcoin i Ethereum koriste Merkle stabla za rješavanje mnogih tehnoloških prepreka prilikom pohrane i pristupa podacima u otvorenoj mreži.

Bilo koja centralizirana mreža ne mora se brinuti o spremanju i pristupu podacima jer postoji samo jedan izvor za pristup i pohranu podataka. Međutim, jednadžba se mijenja kada postoji decentralizirana mreža jer sada podatke treba kopirati među stotinama vršnjaka koji sudjeluju.

Stabla merkle rješavaju problem pružajući pouzdan i učinkovit način dijeljenja i provjere podataka među vršnjacima.

Primjer stabla Merkle

Ali, zašto ovdje raspravljamo o stablima Merkle? Merkle stabla koriste hash kao osnovnu funkcionalnost za povezivanje različitih čvorova i podatkovnih blokova.

Merkle Trees je naopako stablo koje može sažeti cijeli skup transakcija.

Ako želite saznati više o stablima Merkle i kako koristi raspršivanje u kriptografiji, pogledajte naš detaljni vodič:

Vodič za drvce Merkle. Tamo smo razgovarali o tome kako se drveće Merkle vrši u bitcoinima i drugim slučajevima korištenja.

Proces rudarstva

Proces rudarenja također koristi hashiranje. Što se tiče rudarenja bitcoina, novi blok dodaje se blockchainu kada za njim postoji potražnja.

Potrebno je slijediti metodu za dodavanje bloka u blockchain. Vrijednost raspršivanja generira se ovisno o sadržaju bloka kada stigne novi blok. Također, ako je generirano hash više od mrežne poteškoće, započinje postupak dodavanja bloka u blockchain.

Nakon završetka, svi vršnjaci u mreži prepoznaju dodavanje novog bloka.

No, to je rijetko slučaj jer je mrežna poteškoća u većini slučajeva uvijek veća u odnosu na generirano hash. Postoji još jedan aspekt koji igra presudnu ulogu u rudarskom procesu. To je nonce.

Nonce se dodaje u hash bloka i proizvoljan je niz. Nakon završetka, spojeni niz zatim se uspoređuje s razinom težine. Ako je razina težine niža od spojenog niza, tada se nonce mijenja dok razina težine ne bude veća.

Proces se može sažeti u sljedeće korake:

  • Sadržaj se raspršuje kako bi se stvorila nova vrijednost raspršivanja kad god se generira ili uzima novi blok,
  • Nova vrijednost nonce generira se i dodaje hešu
  • Proces raspršivanja odvija se na novom kontaktiranom nizu 
  • Zatim se uspoređuje konačna vrijednost hasha s razinom težine mreže
  •  ako je konačna vrijednost raspršivanja niža od izuzetaka, postupak se ponovno ponavlja. Proces se zaustavlja samo kada je vrijednost hasha veća od nonce.
  • Blok se pridruži lancu kada je razina težine veća
  • Tada rudari preuzimaju odgovornost za miniranje novog bloka i dijele nagrade među sobom.

Izraz “brzina raspršivanja” također dolazi odavde. Stopa raspršivanja je stopa kojom se odvijaju operacije raspršivanja. Veća brzina raspršivanja znači da bi rudarima bilo potrebno više računarske snage da bi sudjelovali u rudarskom procesu.

 

Zaključak

To nas dovodi do kraja našeg raspršivanja u dubinskom vodiču za kriptografiju. Detaljno smo obradili raspršivanje i istražili kod koji stoji iza toga.

Pa, što vi mislite o tome? Komentirajte u nastavku i javite nam.

 

#PITANJA

Što je heširanje u kriptografiji?

U kriptografiji je raspršivanje metoda za pretvaranje podataka u jedinstveni niz teksta pomoću učinkovite metode. Također, nema ograničenja na vrstu podataka ili njihovu veličinu – raspršivanje djeluje na sve njih.

Kako se heširanje koristi u kriptografiji?

Kriptografija koristi hashiranje za heširanje lozinki ili generiranje jedinstvenih identifikacijskih brojeva.

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