Razpršitev v kriptografiji

Ali želite izvedeti več o zgoščevanju v kriptografiji? Če se, potem ste prišli na pravo mesto.

V tem članku bomo raziskali več o zgoščevanju.

Razprševanje je tehnika računalništva za prepoznavanje predmetov ali vrednosti iz skupine predmetov ali vrednosti.

Sliši se zmedeno?

Poskusimo razumeti z zgledom.

No, fakultete in šole zagotavljajo enolično dodeljeno številko vsakemu od svojih študentov. Ta edinstvena številka je tisto, kar identificira študenta in informacije, povezane z njim. Metoda, ki se uporablja za ustvarjanje enolične številke, je razpršitev.

Drug priljubljen primer so knjižnice, kjer boste na policah našli na tone knjig. Vsaka knjiga ima svojo enolično identifikacijsko številko, tako da jo je mogoče najti v ogromni knjižnici!

Sodoben primer razprševanja bi bili igralci, ki se registrirajo za igro. Valorant je brezplačna igra, ki jo je uvedel Riot. Brezplačna igra pomeni, da jo bodo igrali milijoni ljudi.

Vsak igralec se identificira z uporabo edinstvene identifikacijske vrednosti, ustvarjene z uporabo algoritma zgoščevanja.

Poskusimo ga podrobneje razumeti spodaj.

 

Kaj je Hashing?

Kot je navedeno zgoraj, je razprševanje metoda prepoznavanja predmeta iz skupine.

Vsak predmet dobi enkratno identifikacijsko številko, ko je enkrat zgoščen.

Toda, kaj to tehnično pomeni?

Tehnično matematična funkcija generira izhod s fiksno dolžino iz katerega koli vhodnega niza katere koli dolžine.

Bitcoin transakcije so zgoščene, če transakcije dobijo edinstvene ID-je.

Če vnesete »Zdravo, svet!« v SHA-256 algoritem razprševanja, dobili boste naslednji izhod:

Vhod: Pozdravljen, svet!

Izhod: dffd6021bb2bd5b0af676290809ec3a53191dd81c7f70a4b28688a362182986f

Tu SHA256 generira izhod iz danega vhoda. Kot lahko vidite, smo uporabili algoritem razprševanja funkcije varnega razprševanja (SHA-256). To je ena izmed priljubljenih metod razprševanja, vključno s funkcijo Message Direct (MD5) in funkcijo varnega razprševanja (SHA1)..

Zaradi ključnih lastnosti zgoščevalne funkcije je zanesljiva. Naštejmo jih spodaj.

  • Deterministično → To pomeni, da bo izhod za enak vhod v vseh okoliščinah enak.
  • Odporen na podobo → Funkcija odpornosti na podobo zagotavlja, da vrednost zgoščevanja ni uporabna za generiranje vhodne vrednosti.
  • Računalniško učinkovito → Razpršilne funkcije so učinkovite in za njihovo izvajanje niso potrebne velike računske vire.
  • Ni mogoče razveljaviti → Funkcije razprševanja ni mogoče razveljaviti.
  • Odporna na trke → Odpornost proti trkom zagotavlja, da noben vhod nima enakega izhoda.

Tu smo že pokrili kriptografsko razpršitev za začetnike. Preverite tam: Kriptografsko razprševanje: vodnik za začetnike. 

Če pa ste tukaj zaradi naprednih stvari, ne boste razočarani.

 

Kaj je funkcija razpršitve in razpršilne tabele? In kako delujejo?

V tem razdelku bomo podrobneje raziskali zgoščevalno funkcijo in zgoščevalne tabele. Glede zgoščevanja obstajajo zgoščevalne funkcije. Te funkcije so odgovorne za pretvorbo velikih vhodov v majhne fiksne vhode. Hash tabele shranjujejo izhode.

V procesu razprševanja se predmeti porazdelijo v matriko na podlagi njihovih parov ključ / vrednost. Torej, če matriko elementov prenesete v zgoščevalne funkcije, boste dobili izhod matrike, kjer ima vsak element zdaj pritrjen ključ. Par ključ / vrednost je zelo koristen pri dostopu do elementov v realnem času, saj ponuja impresiven čas O (1).

Za izvedbo zgoščevalnih funkcij lahko odstranite dva najprimernejša pristopa.

  • Prvi pristop je uporaba zgoščene funkcije za pretvorbo elementa v celo število. Nato lahko s celoštevilskim izhodom dostopate do elementa pri vstavljanju razpršene tabele.
  • Drugi korak je, da element postavimo v razpršilno tabelo in ga nato pridobimo s pomočjo zgoščene tipke.

Pri 2. metodi bodo funkcije naslednje:

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

Tu so velikosti zgoščene in matrike medsebojno neodvisne. Vrednost indeksa se izračuna na podlagi velikosti polja. Operater Modulo (%) nam omogoča izračun vrednosti.

Poenostavljeno povedano je lahko zgoščevalno funkcijo definirano kot funkcijo, ki lahko preslika poljuben nabor podatkov velikosti na nabor podatkov določene velikosti. Nastali nabor podatkov s fiksno velikostjo lahko shranite v razpršeno tabelo. Vrednostim, ki jih vrne hash-funkcija, je podeljenih veliko imen. Lahko jih imenujemo hash vrednosti, hashi, hash seštevki in hash kode.

 

Pisanje dobre funkcije razpršitve

Če želite ustvariti dobro razpršilno funkcijo ali mehanizem, morate razumeti osnovne zahteve za njeno ustvarjanje. Naštejmo jih spodaj:

  • Hash funkcijo mora biti enostavno izračunati. To pomeni, da za izvedbo ne bi bilo treba vzeti veliko virov.
  • Razpršena funkcija mora biti enakomerno porazdeljena. S tem se zgoščevalne tabele uporabljajo za shranjevanje zgoščenih vrednosti, tako da se gručiranje ne bo zgodilo.
  • Zadnja zahteva je, da je trčenja manj ali ga sploh ni. Nobeno trčenje ne pomeni, da se en izhod preslika na dva vhoda.

Tehnično so trki del zgoščevalne funkcije in je preprosto ni mogoče odstraniti iz zgoščevalne funkcije. Cilj je ustvariti zgoščevalno funkcijo, ki lahko ponudi dobre rezultate razprševalne tabele in razreši trk s pomočjo tehnik reševanja trkov.

 

Zakaj potrebujemo dobro funkcijo razpršitve?

Da bi razumeli potrebo po uporabni funkciji zgoščevanja, si oglejmo spodnji primer.

Predpostavimo, da želimo ustvariti razpredelnico Hash s tehniko razprševanja, kjer bodo vhodni nizi naslednji: {“agk”, “kag”, “gak”, “akg”, “kga”, “gka”}

Zdaj ustvarimo zgoščevalno funkcijo, ki preprosto doda vrednost ASCII a (97), g (103) in k (107) in nato naredi modul vsote za 307.

Jasno je, da je vsota treh števil tudi 307. To pomeni, da če prestavimo vsa števila in nato izvedemo modulo operacijo, bomo dobili enak rezultat. Končni rezultat bi bil shranjevanje vseh nizov na isto indeksno številko. Tudi algoritemski čas za zgoščevalno funkcijo bi bil O (n) zapletenost, kar ni zaželeno. Z lahkoto lahko ugotovimo, da zgoščena funkcija, ki smo jo opisali, ni optimalna za resnične scenarije.

Če želite popraviti zgoščevalno funkcijo, lahko razmestimo vsoto vrednosti ASCII vsakega elementa z drugim prostim številom, 727. S tem bomo za dani niz vhodnih nizov dobili drugačen izhod.

 

Spoznavanje razpršilnih tabel

Hash tabele so zelo koristne pri shranjevanju rezultata zgoščevalne funkcije, ki izračuna indeks in nato shrani vrednost proti njemu. Končni rezultat bi bil hitrejši računski postopek z zapletenostjo O (1).

Hash tabele so tradicionalno dobra izbira pri reševanju problemov, ki zahtevajo O (n) čas.

Torej, če vzamete niz fiksne dolžine in nato poskusite izvedeti pogostost znakov niza.

Torej, če je string = “aacddce”, je splošen pristop, da gre skozi niz večkrat in shrani vsako frekvenco.

# Navedite vhodni niz in preštejte pogostost znakov v tem nizu

# Algoritem je 0 (n) čas zahtevnosti

temp_list = [] začetek = "a" str = "ababcddefff" def alpha_zeta (): alpha = ‘a’ za i v obsegu (0,26): temp_list.append (alpha) alpha = chr (ord (alpha) + 1) return temp_list temp_list = alpha_zeta () #print (temp_list) def frekvenca_znaka (str, temp_list): za vsako v temp_list: freq = 0 za i v str: if (i == vsak): freq = freq + 1 print (vsak, freq) frekvenca_znaka (str, temp_list)

Rezultat zgornjega programa bo naslednji:

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

Zdaj pa uvedimo razpršilno tabelo v C ++ in preštejmo frekvenco znakov.

#include z uporabo imenskega prostora std; int frekvenca [26]; int hashFunc (char c) {return (c – ‘a’); } void countFre (niz S) {for (int i = 0; i< S. dolžina (); ++ i) {int indeks = hashFunc (S [i]); Frekvenca [indeks] ++; } Za (int i = 0; i<26; ++ i) {cout << (char) (i + ‘a’) << ” << Frekvenca [i]<< endl; }} Int main () {cout<<"Pozdravljen, svet"; countFre ("abbaccbdd"); }

Rezultat programa bi bil naslednji:

a 2 b 3 c 2 d 2

Zapletenost O (N) algoritma je hitrejša v primerjavi z drugimi linearnimi pristopi.

Kako rešiti trke

Obstajajo edinstveni načini za reševanje trkov v zgoščevalnih funkcijah. Eden od priljubljenih načinov je ločeno veriženje, ki je znano tudi kot odprto razprševanje. Izvaja se s povezanim seznamom, pri čemer je vsak element v verigi sam povezan seznam. Ta pristop omogoča shranjevanje elementov in zagotavljanje, da so nekateri elementi le del specifičnega povezanega seznama, ki reši trčenje. To pomeni, da ne moreta imeti dve vhodni vrednosti enake izhodne zgoščene vrednosti.

 

Raziskovanje hasha v Pythonu

V tem razdelku bomo hitro preučili hash v Pythonu. Razlog, da se odločimo za Python, je ta, da ga je enostavno brati in ga lahko brez večjih težav uporablja vsak.

Ker je zgoščevanje pogosta funkcija, je že implementirano v knjižnici Python. Z uporabo modula lahko vnesete objekt kot njegov vhod in nato vrnete zgoščeno vrednost.

Sintaksa hash metode je:

hash (objekt)

Kot lahko vidite, zajema en parameter, ki je objekt. Predmet je lahko celo število, float ali niz.

Vrnjena vrednost metode hash () je odvisna od vnosa. Za celo število lahko vrne isto številko, medtem ko bi bili decimalni in niz različni.

Oglejmo si nekaj primerov spodaj.

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

Rezultat zgornje kode je naslednji:

Vendar zgoščevanja ni mogoče uporabiti za vse vrste predmetov. Na primer, če se spomnite, da smo v našem prvem programu ustvarili seznam od a do z. Če ga poskušamo razpršiti, bo izhodno okno skozi TypeError: unhashable type: ‘list’

Če želite na seznam predmetov uporabiti zgoščevanje, morate uporabiti tuple.

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

Razpršitev v kriptografiji

Razprševanje je koristno za kriptografijo. Bitcoin uporablja razprševanje za ustvarjanje in upravljanje dreves Merkle

Tudi razprševanje je že dolgo časa del kriptografije. Vendar je najboljši primer zgoščevanja gesla in jih shraniti. 

Merkle drevesa

Drevo Merkle je podatkovna struktura, ki je koristna pri varnem preverjanju podatkov v velikem podatkovnem področju. Tako Bitcoin kot Ethereum uporabljata drevesa Merkle za reševanje številnih tehnoloških ovir pri shranjevanju in dostopu do podatkov v odprtem omrežju.

Vsakemu centraliziranemu omrežju ni treba skrbeti za shranjevanje in dostop do podatkov, saj obstaja samo en vir za dostop in shranjevanje podatkov. Vendar se enačba spremeni, ko obstaja decentralizirano omrežje, saj je zdaj treba podatke kopirati med stotine sodelujočih vrstnikov.

Drevesa Merkle rešijo težavo z zagotavljanjem zaupanja vrednega in učinkovitega načina za izmenjavo in preverjanje podatkov med vrstniki.

Primer drevesa Merkle

Zakaj pa tukaj razpravljamo o drevesih Merkle? Drevesa Merkle uporabljajo heš kot osnovno funkcionalnost za povezovanje različnih vozlišč in podatkovnih blokov.

Merkle drevesa je obrnjeno drevo, ki lahko povzame celoten sklop transakcij.

Če želite izvedeti več o drevesih Merkle in kako uporablja razprševanje v kriptografiji, si oglejte naš podroben vodnik:

Vodnik po drevesih Merkle. Tam smo razpravljali o tem, kako se drevesa Merkle izvajajo v bitcoinih in drugih primerih uporabe.

Rudarski proces

Postopek rudarjenja izkorišča tudi zgoščevanje. Ko gre za rudarjenje bitcoinov, se bloku doda nov blok, ko je povpraševanje po njem.

Za dodajanje bloka v verigo blokov je treba uporabiti metodo. Vrednost zgoščene vrednosti se ustvari glede na vsebino bloka, ko prispe nov blok. Če je ustvarjena zgoščena velikost večja od težav z omrežjem, se začne postopek dodajanja bloka v verigo blokov.

Ko končate, vsi vrstniki v omrežju potrdijo dodajanje novega bloka.

Toda to je redko, saj je težava z omrežjem v večini primerov vedno večja v primerjavi z ustvarjenim zgoščevanjem. Obstaja še en vidik, ki ima odločilno vlogo v rudarskem procesu. To je nonce.

Nonce je dodano v razpršitev bloka in je poljuben niz. Ko končate, se združeni niz primerja s stopnjo težavnosti. Če je težavnostna stopnja nižja od združenega niza, se nonce spremeni, dokler težavnostna stopnja ne bo višja.

Postopek lahko povzamemo v naslednjih korakih:

  • Vsebina se zgosti, da se ustvari nova vrednost zgoščevanja, kadar koli se ustvari ali vzame nov blok,
  • Nova vrednost nonce se generira in doda v razpršitev
  • Postopek razpršitve poteka na novem nizu, na katerega ste vzpostavili stik 
  • Nato se končna vrednost zgoščene vrednosti primerja s stopnjo težavnosti omrežja
  •  če je končna zgoščena vrednost nižja od nonce, se postopek ponovi. Proces se ustavi šele, ko je zgoščena vrednost večja od nonce.
  • Block se pridruži verigi, ko je stopnja težavnosti višja
  • Nato rudarji prevzamejo odgovornost za kopanje novega bloka in si nagrade delijo med seboj.

Od tu prihaja tudi izraz “hitrost razpršitve”. Hash stopnja je hitrost, s katero potekajo postopki razprševanja. Višja hitrost razpršitve pomeni, da bi rudarji potrebovali več računske moči za sodelovanje v rudarskem procesu.

 

Zaključek

To nas pripelje do konca poglobljenega vodenja v kriptografiji. Podrobno smo obravnavali razprševanje in raziskali tudi kodo, ki stoji za tem.

Torej, kaj vi mislite o tem? Komentirajte spodaj in nam sporočite.

 

#FAQ

Kaj je zgoščevanje v kriptografiji?

V kriptografiji je razprševanje metoda za pretvorbo podatkov v edinstven niz besedila z učinkovito metodo. Prav tako ni omejitev glede vrste podatkov ali njihove velikosti – razprševanje deluje na vse.

Kako se zgoščevanje uporablja v kriptografiji?

Kriptografija uporablja zgoščevanje za razprševanje gesel ali ustvarjanje enoličnih identifikacijskih številk.

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