Hash függvény

A hash függvény ( angol hash függvény a hash -ból - "turn to darált hús", "hash" [1] ) vagy a konvolúciós függvény egy olyan függvény, amely tetszőleges hosszúságú bemeneti adatok tömbjét egy kimeneti bitsorozattá alakítja beállított hossz, egy bizonyos algoritmus által végrehajtva . A hash függvény által végrehajtott transzformációt kivonatolásnak nevezzük . A bemeneti adatokat bemeneti tömbnek, " kulcsnak " vagy " üzenetnek " nevezik. Az átalakítás eredményét „ hash ”, „ hash kód ”, „ kivonatösszeg ” , „ üzenetösszegzés ” nevezik .

A hash függvények a következő esetekben használatosak:

asszociatív tömbök készítésekor ;
amikor az adatkészletek sorozataiban másolatokat keres;
az adatkészletek egyedi azonosítóinak létrehozásakor;
az adatokból (jelekből) ellenőrző összegek kiszámításakor az adatok tárolása és/vagy továbbítása során fellépő (véletlen vagy szándékosan bevitt) hibák későbbi észlelésére;
a jelszavak biztonsági rendszerekben történő mentése során hash kód formájában (a jelszó hash kóddal történő visszaállításához olyan függvényre van szükség, amely fordított a használt hash funkcióval);
elektronikus aláírás generálásakor (a gyakorlatban gyakran nem magát az üzenetet írják alá, hanem annak „hash képét”);
satöbbi.

Általános esetben ( a Dirichlet-elv szerint ) nincs egy az egyhez megfelelés a hash kód és az eredeti adatok között. A hash függvény által visszaadott értékek kevésbé változatosak, mint a bemeneti tömb értékei. Azt az esetet, amikor egy hash függvény egynél több bemeneti tömböt alakít át azonos összegzésekké, " ütközésnek " nevezzük. Az ütközési valószínűséget a hash függvények minőségének értékelésére használják.

Számos különböző tulajdonságú kivonatolási algoritmus létezik. Példák az ingatlanokra:

Az egyik vagy másik hash-függvény kiválasztását a megoldandó probléma sajátosságai határozzák meg. A hash függvény legegyszerűbb példája az adatok ciklikus redundancia kóddal ( CRC , ciklikus redundancia kód ) történő keretezése .

Történelem

Az üzenetek titkosítását az egyértelmű visszafejtés lehetősége nélkül, de csak a szerző prioritásának megerősítése érdekében használják régóta.

Galileo Galilei megfigyelte a Szaturnusz gyűrűit , amelyeket összetévesztett "fülekkel". Nem lévén biztos, de érvényesíteni akarta elsőbbségét, üzenetet tett közzé a betűkkel átrendezve: smaismrmilmepoetaleumibunenugttauiras . 1610-ben felfedte az eredeti kifejezést: Altissimum planetam tergeminum obseruaui , ami latinul azt jelenti, hogy "hármasban figyelte meg a legmagasabb bolygót". Így az első üzenet közzétételekor az eredeti mondatot nem hozták nyilvánosságra, de lehetőség nyílt annak későbbi megerősítésére.

Az 1650-es évek közepén Christian Huygens meglátta a gyűrűket, és kiadott egy üzenetet ábécé sorrendbe rendezett betűkkel: aaaaaaacccccdeeeeeghiiiiiiiillllmmnnnnnnnnnooooppqrrsttttuuuuuu . Egy idő után az eredeti mondat is megjelent: Annulo cingitur, tenui plano, nusquam cohaerente, ad eclipticam inclinato - "Vékony, lapos gyűrű veszi körül, sehol nincs felfüggesztve, az ekliptikához hajlik ". Ez az eset csak annyiban tér el a hash függvény használatától, beleértve azt a célt is, hogy később megerősítsenek valamilyen feloldatlan üzenetet, csak annyiban, hogy a kimeneti üzenetnek nincs fix hossza, hanem a bemenet hossza határozza meg. Valójában az eredeti üzenet betűinek abc-besorolása valami hash függvény, de csak nem rögzített hosszúságú eredménnyel.

1953 januárjában Hans Peter Luhn ( németül Hans Peter Luhn ) (az IBM alkalmazottja ) javasolta a "hash kódolást". Donald Knuth Hansnak tartja az elsőt, aki előterjesztette a "hashing" szisztematikus ötletét.

1956 - ban Arnold Dumey a Számítógépek és automatizálás című művében elsőként írta le a "kivonatolás" fogalmát, ahogyan azt a legtöbb programozó ma ismeri. Dumi a "kivonatolást" a "szótárprobléma" megoldásának tekintette, és a prímszámmal való osztás maradékának használatát javasolta "kivonatcímként" [2] .

1957 -ben W. Wesley Peterson az IBM Journal of Research and Development folyóiratban publikált egy cikket a nagy fájlok szövegének megtalálásáról . Ezt a munkát tekintik az első "komoly" munkának a "kivonatolásról". A cikkben Wesley meghatározta a "nyílt címzést", rámutatva a teljesítmény csökkenésére a törléskor. Hat évvel később jelent meg Werner Buchholz ( németül Werner Buchholz ) munkája, amelyben a "hash függvények" kiterjedt tanulmányozását végezték el. A következő néhány évben a "hashing"-et széles körben alkalmazták, de jelentősebb munka nem jelent meg.

1967 -ben Herbert Hellermann Principles of Digital Computing Systems [3] című könyve említi a mai értelemben vett "kivonatolást" . 1968- ban Robert Morris egy nagy felmérést tett közzé a "kivonatolásról" a Communications of the ACM folyóiratban . Ez a munka „ kulcsfontosságú ” kiadványnak számít, amely bevezeti a „hashing” fogalmát a tudományos forgalomba, és rögzíti a korábban csak szakemberek által használt „hash” kifejezést ( zsargon ).

Az 1990-es évek elejéig az orosz nyelvű irodalomban Andrej Petrovics Ershov munkáinak köszönhetően az „elrendezés” szót a „kivonatolás” kifejezés megfelelőjeként használták, a „konfliktus” pedig az „ ütközések ” kifejezést. ( A.P. Ershov 1956 óta használt „elrendezést” ). Niklaus Wirth Algorithms and Data Structures című könyvének 1989 -es orosz nyelvű kiadása is használja az "elrendezés" kifejezést. Azt is javasolták, hogy a módszert egy másik orosz szóval nevezzék el: " okroshka ". Azonban egyik lehetőség sem honosodott meg, és az orosz irodalomban túlnyomórészt a "hashing" kifejezést használják [4] .

A "hash függvények" típusai

Egy "jó" hash függvénynek két tulajdonságnak kell megfelelnie :

gyors számítás;
az " ütközések " minimális száma .

Bemutatjuk a jelölést:

$K$ - a "kulcsok" száma (bemeneti adatok);
$h(k)$ egy hash függvény, amelynek legfeljebb különböző értékei (kimeneti adatok) vannak. $M$

Azaz:

\forall k\in [0;\,K):h(k)<M

Példaként a "rossz" hash függvényre idézhetjük a függvényt , amely egy tízjegyű természetes számhoz illeszkedik a szám húszjegyű négyzetének közepéből kiválasztott három számjegyből . Úgy tűnik, hogy a "hash kódok" értékeit egyenletesen kell elosztani " 000 " és " 999 " között, de a " valós " adatokra ez csak akkor igaz, ha a " kulcsok " nem rendelkeznek "nagy" számmal. nullák a bal vagy a jobb oldalon [4 ] . $M=1000$ $K$ $K$

Tekintsünk néhány egyszerű és megbízható "kivonatoló függvény" megvalósítást.

"Hash függvények" osztás alapján

1. "Kivonatkód" az összes lehetséges "kivonat" számával való osztás maradékaként

A hash függvény ki tudja számítani a "hash"-t a bemenet elosztásának maradékaként : $M$

h(k)=k\mod M

ahol az összes lehetséges hash (kimeneti adat) száma. $M$

Ugyanakkor nyilvánvaló, hogy páros esetén a függvény értéke páros és páratlan - páratlan esetén páros lesz . Ezenkívül ne használja a számítógép számrendszerét alapfokként , mivel a "kivonatkód" csak a jobb oldalon található szám néhány számjegyétől függ , ami nagyszámú ütközéshez vezet . A gyakorlatban általában egy egyszerűt választanak ; a legtöbb esetben ez a választás elég kielégítő. $M$ $k$ $k$ $M$ $k$ $M$

2. "Kivonatkód", mint az eredményül kapott polinom együtthatóinak halmaza

A hash függvény végrehajthatja a bemeneti adatok egy polinommal való modulo-két osztását. Ebben a módszerben ennek kettős hatványnak kell lennie, és a bináris kulcsok ( ) polinomokként vannak ábrázolva, "hash kódként" a polinom együtthatóinak értékei, amelyeket a bemeneti adatok egy előjellel való osztásának maradékaként kapunk. -a kiválasztott fokszámú polinomot "leveszi" : $M$ $K=k_{{n-1}}k_{{n-2}}...k_{{0}}$ $K$ $P$ $m$

{\displaystyle K(x)\mod P(x)=h_{m-1}x^{m-1}+\dots +h_{1}x+h_{0))

{\displaystyle h(x)=h_{m-1}...ó_{1}ó_{0))

A megfelelő választással garantált a majdnem azonos billentyűk közötti ütközések elkerülése [4] . $P(x)$

Szorzáson alapuló "kivonatoló függvények"

A szimbólummal jelöljük a gépszóval ábrázolható számok számát . Például az IBM PC-vel kompatibilis 32 bites számítógépek esetén . $w$ $w=2^{32}$

Válasszunk egy állandót úgy, hogy az együttprím legyen a -val . Ekkor egy szorzást használó hash függvény így nézhet ki: $A$ $A$ $w$

h(K)=\left[M\left\lfloor {\frac {A}{w}}*K\right\rfloor \right]

Ebben az esetben egy bináris számrendszerrel rendelkező számítógépen a kettő hatványa, és a szorzat jobb felének magas bitjeiből áll . $M$ $h(K)$ $A*K$

Az osztáson és szorzáson alapuló hash függvények egyik előnye a valós kulcsok véletlenszerűségének előnyös kihasználása. Például, ha a kulcsok egy aritmetikai sorozat (például a "Név 1", "Név 2", "Név 3" nevek sorozata), a szorzást használó hash függvény az aritmetikai folyamatot hozzávetőlegesen aritmetikai sorozatra képezi le. különböző hash értékek, ami csökkenti az ütközések számát egy véletlenszerű helyzethez képest [4] .

Az egyik szorzást használó hash függvény a Fibonacci hash-t használó hash függvény . A Fibonacci hashelés az aranymetszés tulajdonságain alapul . Konstansként itt egy egész számot választunk, amely legközelebb áll a -hoz, és ennek egy prímje , ahol az aranymetszés [4] . $A$ $\varphi ^{{-1}}*w$ $w$ $\varphi$

Változó hosszúságú karakterlánc-kivonat

A fenti módszerek akkor is alkalmazhatók, ha több szóból álló vagy változó hosszúságú billentyűket kell figyelembe venni.

Például a szavakat egyesítheti a modulo összeadással vagy az XOR művelettel . Az egyik ezen az elven működő algoritmus a Pearson hash függvény. $w$

A Pearson hash egy Peter Pearson által javasolt algoritmus 8 bites regiszterekkel rendelkező processzorokhoz , amelyek feladata egy tetszőleges hosszúságú karakterlánc gyors hash kódká alakítása. Bemenetként a függvény egy karakterekből álló szót kap , mindegyik 1 bájt méretű, és egy 0 és 255 közötti értéket ad vissza. Ebben az esetben a hash kód értéke a bemeneti szó minden karakterétől függ. $W$ $n$

Az algoritmus a következő pszeudokóddal írható le, amely egy karakterláncot vesz bemenetként , és egy permutációs táblát használ : $W$ $T$

h := 0 minden c -hez a W hurokindexben := h xor c h := T[index] vége hurok visszatérés h

Az algoritmus előnyei közül:

a számítás egyszerűsége;
olyan bemeneti adatok hiánya, amelyeknél a legnagyobb az ütközés valószínűsége;
az ideális hash függvénnyel való módosítás lehetősége [5] .

A ( ) karakterekből álló kulcsok kivonatolásánál alternatív módszerként kínálhatjuk a számítást $K$ $l$ $K=x_{{1}}x_{{2}}...x_{{l}}$

h(K)=(h_{{1}}(x_{{1}})+h_{{2}}(x_{{2}})+...+h_{{l}}(x_{{ l))))\mod M

[négy]

Tökéletes hash

Az ideális hash függvény egy olyan függvény , amely a halmaz minden kulcsát egész számok halmazára képezi le ütközések nélkül . A matematikában az ilyen transzformációt injektív leképezésnek nevezik . $S$

Leírás

Egy függvényt ideális hash függvénynek nevezünk, ha injektív -on . $h(k)\colon U\to [m]$ $S\subseteq U$ $S$
Egy függvényt minimum ideális hash függvénynek nevezünk, ha tökéletes hash függvény és . $h(k)\colon U\to [m]$ $S\subseteq U$ $m=n=|S|$
Egész szám esetén a függvényt -tökéletes hash függvénynek (k-PHF) nevezzük, ha mindegyikhez van . $k\geq 1$ $h(k)\colon U\to [m]$ $k$ $S\subseteq U$ $j\in[m]$ $|\{x\in S|h(x)=j\}|\leq k$

Az ideális kivonatolás akkor használatos, ha egyedi azonosítót kell hozzárendelni egy kulcshoz anélkül, hogy a kulccsal kapcsolatos információkat tárolnánk. Példa az ideális (vagy inkább ideális) kivonat használatára: a nagy és lassú memóriában tárolt adatokhoz tartozó hash-ek elhelyezése kis és gyors memóriában. A blokk mérete úgy választható meg, hogy a lassú memóriából egy kérésben kiolvassák a szükséges adatokat. Hasonló megközelítést alkalmaznak például a hardveres útválasztóknál . Szintén ideális hash-t használnak az algoritmusok gráfokon történő munkájának felgyorsítására, ha a gráfábrázolás nem fér el a fő memóriában [6] . $k$

Univerzális hash

Az univerzális kivonatolást kivonatolásnak nevezzük, amelyben nem egy meghatározott hash -függvényt használunk, hanem egy véletlenszerű algoritmus alapján kiválasztunk egy hash-függvényt egy adott családból. Az univerzális hash-t általában az ütközések alacsony száma jellemzi, például hash táblák megvalósításában és a kriptográfiában használják.

Leírás

Tegyük fel, hogy kulcsokat akarunk leképezni a térből a számokra . A bemeneten az algoritmus adatokat kap bizonyos dimenziókészletekből . A készlet nem ismert előre. Általános szabály, hogy az algoritmusnak a legkevesebb ütközést kell biztosítania , amit nehéz elérni bármilyen hash függvény használatával. Az ütközések száma csökkenthető, ha véletlenszerűen választ ki egy hash függvényt minden alkalommal, amikor kivonatolni kell. A hash függvényt az univerzális családnak nevezett hash függvények meghatározott halmazából választjuk ki [7] . $U$ $[m]$ $S\in U$ $n$ $H=\{h:U\to [m]\}$

Módszerek az ütközések kezelésére

Az ütközés (néha ütközés [2] vagy ütközés) olyan eset, amikor egy hash függvény különböző bemeneti blokkokhoz ugyanazokat a hash kódokat adja vissza.

Technikák az ütközések kezelésére hash táblákban

A kivonatolást leíró első írások többsége a hash-táblázatokban előforduló ütközések kezelésének módszereivel foglalkozott. Ezután a hash függvényeket használták, amikor szöveget kerestek nagy fájlokban. Két fő módszer létezik a hash táblák ütközésének kezelésére:

láncmódszer (direkt link módszer);
nyílt cím módszer.

A láncolási módszer használatakor a hash tábla a " linked key list" - "hash code" párokat tárolja. Minden kulcshoz egy hash kódot számít ki a hash függvény; ha a hash kódot korábban szerezték be (egy másik kulcshoz), akkor a kulcs hozzáadódik a hash kóddal párosított kulcsok meglévő listájához; ellenkező esetben egy új "kulcslista" - "hash kód" pár jön létre, és a kulcs hozzáadódik a létrehozott listához. Általában, ha vannak kulcsok és listák, a hash-tábla átlagos mérete . Ebben az esetben a táblázatban való kereséskor a szekvenciális kereséshez képest az átlagos munkamennyiség körülbelül egy faktorral csökken. $N$ $M$ ${\frac {N}{M}}$ $M$

A nyílt címzési módszer használatakor a hash tábla kulcs-hash kód párokat tárol. Minden kulcshoz egy hash kódot számít ki a hash függvény; a "kulcs" - "hash kód" pár a táblázatban tárolódik. Ebben az esetben a táblázatban való kereséskor a hivatkozott listák használatához képest nem használnak hivatkozásokat, a „kulcs” - „hash kód” párok szekvenciális felsorolása történik, a felsorolás a kívánt kulcs után megáll. található. Azt a szekvenciát, amelyben a táblázat celláit vizsgálják, próbasorozatnak nevezzük [4] .

Kriptográfiai só

A jelszavak és a digitális aláírások hamisítás elleni védelmére számos módszert hoztak létre, amelyek akkor is működnek, ha a kriptoanalizátor tudja, hogyan kell ütközéseket létrehozni a használt hash függvényhez. Az egyik ilyen módszer az, hogy a bemeneti adatokhoz egy úgynevezett kriptográfiai „sót” adunk – egy véletlenszerű adatsort; néha a "sót" is hozzáadják a hash kódhoz. A véletlenszerű adatok hozzáadása sokkal nehezebbé teszi az eredményül kapott hash táblák elemzését. Ez a módszer például a jelszavak UNIX-szerű operációs rendszerekben való mentésekor használatos .

A hash függvények alkalmazásai

A hash függvényeket széles körben használják a kriptográfiában.

A hash-t kulcsként használják számos adatszerkezetben – hash-táblázatokban , Bloom-szűrőkben és derékszögű fákban .

Kriptográfiai hash függvények

A számos létező hash függvény közül szokás kiemelni a kriptográfiailag biztonságosakat , amelyeket a kriptográfiában használnak , mivel ezekre további követelmények vonatkoznak. Ahhoz, hogy egy hash-függvényt titkosításilag biztonságosnak lehessen tekinteni, három alapvető követelménynek kell megfelelnie, amelyeken a legtöbb titkosítási hash-függvény alapul: $H$

irreverzibilitás : adott m hash érték esetén számításilag lehetetlennek kell lennie olyan adatblokkot találni , amelyhez ; $x$ $H(X)=m$
az első típusú ütközésekkel szembeni ellenállás : egy adott M üzenethez számításilag lehetetlennek kell lennie másik N üzenetet találni , amelyre nézve ; $H(N)=H(M)$
2-es típusú ütközésekkel szembeni ellenállás : számítási szempontból lehetetlennek kell lennie olyan üzenetpár felvétele, amelynek azonos hash-je van. ${\megjelenítési stílus (M,M')}$

Ezek a követelmények nem függetlenek:

a megfordítható funkció instabil az első és második típusú ütközésekre;
egy funkció, amely instabil az első típusú ütközésekre, instabil a második típusú ütközésekre; fordítva nem igaz.

Nem bizonyított olyan irreverzibilis hash függvények létezése, amelyeknél egy adott hash érték bármely előképének kiszámítása elméletileg lehetetlen. Általában a reciprok megtalálása csak számításilag nehéz feladat.

A születésnapi támadás lehetővé teszi, hogy ütközéseket találjon egy hash függvényhez átlagosan n bit hosszúságú értékekkel, körülbelül a hash függvény számításai során. Ezért egy n bites hash függvény biztonságosnak tekinthető, ha az ütközések keresésének számítási bonyolultsága közel van a -hoz . $2^{{n/2}}$ $2^{{n/2}}$

A kriptográfiai hash függvényeknek lavinahatást kell kifejteniük – az argumentum legkisebb változtatásával a függvény értéke nagymértékben megváltozik. Különösen a hash érték nem szivároghat ki információt még az argumentum egyes bitjeiről sem. Ez a követelmény a kulcsa a kulcs megszerzéséhez a felhasználó jelszavát kivonatoló kivonatoló algoritmusok kriptográfiai erősségének [8] .

A kivonatolást gyakran használják a digitális aláírási algoritmusokban, ahol nem magát az üzenetet titkosítják, hanem annak hash kódját, ami csökkenti a számítási időt és növeli a kriptográfiai erősséget is. Ezenkívül a legtöbb esetben a hash kódok értékeit tárolják jelszavak helyett.

Ellenőrző összegek

Az ellenőrzőösszeg-számítási algoritmusok egyszerű, gyors és könnyen megvalósítható hardveres algoritmusok, amelyek megvédik az adatokat a nem szándékos torzulásoktól, beleértve a hardverhibákat is. A matematika szempontjából az ilyen algoritmusok a vezérlőkódot kiszámító hash függvények. A vezérlőkód az információ továbbítása és tárolása során előforduló hibák észlelésére szolgál.

Az ellenőrző összegek kiszámítására szolgáló algoritmusok tízszer és százszor gyorsabbak, mint a kriptográfiai hash függvények, és sokkal egyszerűbbek a hardveres végrehajtásban.

Az ilyen nagy sebesség ára a kriptográfiai erősség hiánya - az üzenet könnyen „illeszthetősége” egy előre ismert ellenőrző összeghez. Ezenkívül az ellenőrző összegek bitszélessége (tipikus szám: 32 bit) általában kisebb, mint a kriptográfiai kivonatok bitszélessége (tipikus számok: 128, 160 és 256 bit), ami azt jelenti, hogy nem szándékos ütközések fordulhatnak elő.

Az ellenőrző összeg kiszámításának legegyszerűbb algoritmusa az, hogy az üzenetet (bemeneti adatot) 32 vagy 16 bites szavakra osztjuk, majd összeadjuk a szavakat. Ilyen algoritmust használnak például a TCP / IP protokollokban .

Az ellenőrzőösszeg-algoritmusoknak általában tipikus hardverhibákat kell észlelniük, például több egymást követő bithibát is észlelniük kell egy adott hosszúságig. Az úgynevezett „ ciklikus redundanciakód ” algoritmuscsalád kielégíti ezeket a követelményeket. Ezek közé tartozik például az Ethernet eszközökben használt CRC32 algoritmus és a ZIP adattömörítési formátum .

Az ellenőrző összeg például a fő szöveggel (adatokkal) együtt továbbítható a kommunikációs csatornán. A fogadó oldalon az ellenőrző összeg újraszámítható és összehasonlítható a továbbított értékkel. Ha eltérést talál, az átvitel elrontott, és újraküldést lehet kérni.

A hashelés mindennapi használatára példa a poggyászban szállított bőröndök számának megszámlálása. A bőröndök biztonságának ellenőrzéséhez nem szükséges minden egyes bőrönd biztonságát ellenőrizni, elegendő a bőröndök számát megszámolni a be- és kirakodás során. Az egyező számok azt jelentik, hogy egyetlen bőrönd sem vész el. Vagyis a bőröndök száma egy hash kód.

Ez a módszer kiegészíthető a továbbított információk hamisítás elleni védelmére ( MAC módszer ). Ebben az esetben a kivonatolást egy biztonsági funkció végzi az üzeneten, kombinálva egy titkos kulccsal, amelyet csak az üzenet küldője és címzettje ismer. A kriptoanalizátor, miután elfogta az üzenetet és a hash függvény értékét, nem tudja visszaállítani a kódot, vagyis nem tudja meghamisítani az üzenetet (lásd imitációs védelem ).

Geometriai hash

A geometriai kivonatolás a számítógépes grafikában és a számítási geometriában széles körben alkalmazott módszer síkon vagy háromdimenziós térben történő problémák megoldására, például ponthalmazok közül a legközelebbi pontpárok megtalálására vagy azonos képek keresésére. A hash függvény ebben a módszerben általában némi metrikus helyet foglal el bemenetként , és felosztja azt, létrehozva egy cellarácsot. A hash-tábla ebben az esetben egy két vagy több indexet tartalmazó tömb, amelyet "rácsfájlnak" ( angolul grid file ) neveznek. A geometriai kivonatolást a távközlésben használják többdimenziós jelekkel való munka során [9] .

Az adatok visszakeresésének felgyorsítása

A hash tábla egy olyan adatstruktúra , amely lehetővé teszi a "kulcs" - "hash kód" formátumú párok tárolását, és támogatja az elemek keresését, beszúrását és törlését. A hash táblák a keresések felgyorsítására szolgálnak, például amikor szöveges mezőket írunk egy adatbázisba, akkor azok hash kódja kiszámítható, és az adatok ennek a hash kódnak megfelelő szakaszba helyezhetők. Ekkor az adatok keresésekor először ki kell számítani a szöveg hash kódját, és azonnal kiderül, hogy melyik részben kell keresni. Vagyis nem a teljes adatbázisban, hanem csak annak egyik szakaszában kell keresni, és ez felgyorsítja a keresést.

Ebben az esetben a hashelés mindennapi analógja lehet a szavak ábécé szerinti elhelyezése a szótárban. A szó első betűje a hash kódja, és kereséskor nem a teljes szótárat keresi ki, hanem csak a kívánt betűvel kezdődő szavakat.

Jegyzetek

↑ Virt2, 2010 , p. 257.
↑ 1 2 Wirth, 1989 .
↑ Herbert Hellerman. A digitális számítógépes rendszer alapelvei. NY: McGraw-Hill, 1967, 424 pp.
↑ 1 2 3 4 5 6 7 Knuth, 2007 .
↑ Pearson, Peter K. (1990. június), Fast Hashing of Variable-Length Text Strings , Communications of the ACM 33 (6): 677, doi : 10.1145/78973.78978 , < http://epaperpress.com/vbha download/p677-pearson.pdf >
↑ Djamal Belazzougui, Fabiano C. Botelho, Martin Dietzfelbinger. Kivonat , kiszorítás és tömörítés (neopr.) . — Springer Berlin / Heidelberg, 2009.
↑ Miltersen, Peter Bro Universal Hashing ( PDF). Archiválva az eredetiből 2009. június 24-én.
↑ Schneier, 2002 .
↑ Wolfson, HJ & Rigoutsos, I (1997). Geometriai kivonatolás: áttekintés. IEEE Computational Science and Engineering, 4(4), 10-21.

Irodalom

Bruce Schneier . Alkalmazott kriptográfia. Protokollok, algoritmusok, forrásszövegek C nyelven. - M . : Triumph, 2002. - ISBN 5-89392-055-4 .
Donald Knuth . A programozás művészete. 3. kötet. Rendezés és keresés = The Art of Computer Programming, vol.3. Rendezés és keresés. — 2. kiadás. - M . : " Williams ", 2007. - S. 824. - ISBN 0-201-89685-0 .
Niklaus Wirth . Algoritmusok és adatstruktúrák. - M . : " Mir ", 1989. - ISBN 5-03-001045-9 .
Niklaus Wirth . Algoritmusok és adatstruktúrák. Új verzió az Oberonhoz. - M . : "DMK Press", 2010. - ISBN 978-5-94074-584-6 .

Linkek

Információ az elektronikus digitális aláírásról

Hash függvények
Általános rendeltetésű	Adler-32 CRC Fletcher ellenőrző összeg FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH – Hash Tree jenkins hash hash összeg
Kriptográfia	Stribog GOST R 34.11-94 Öv BLAKE BMW CubeHash VISSZHANG edonkey2k FSB Fúga Grostl HAVAL Hamsi JH Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Bőr Snefru Tigris Örvény
Kulcsgenerálási funkciók	bcrypt PBKDF2 scrypt Argon2 Lyra2
Csekkszám ( összehasonlítás )	Ellenőrző összeg Verhouff algoritmusa Hold algoritmus Damm algoritmus Vonalkód bankszámlák bankkártyák VAN SNILS OKPO ÓN OKATO ISBN OGRN és OGRNIP VIN
Hashes	A csekkszámok összehasonlítása Hitelesítési protokollok Vonalkód összehasonlítás Kriptográfia Mágneses kapcsolat Merkle aláírása ed2k URNA

Titkosító szoftver

E-mail kliensek

Apple Mail
Automatikus titkosítás
Claws Mail
Enigmail
GPG ( Gpg4win )
kapcsolatba lépni
Outlook
p≡p
PGP
Sylpheed
Thunderbird

Biztonságos kommunikáció

OTR	Adium BitlBee Centericq ChatSecure climm jitsi Kopete MCabber Jövedelmezőség
SSH	Dropbear lsh OpenSSH Gitt SecureCRT WinSCP wolfSSH
TLS és SSL	Ugrálóvár BoringSSL Botan cryptlib GnuTLS JSSE LibreSSL MatrixSSL NSS OpenSSL mbed TLS RSA BSAFE Csatorna SSLeay elkábítani csapatjegyzet wolfSSL
VPN	Check Point VPN-1 Hamachi Openswan openvpn Softether VPN erősHattyú cink huzalvédő
ZRTP	CSipSimple jitsi Linphone Jami zfone
P2P	Bitüzenet Vadrózsa retroshare Tox
DRA	mátrix OMEMO Cryptocat ChatSecure Proteus ülés Jelprotokoll facebook messenger Google Allo Google Messages jel TextSecure WhatsApp SimpleX

Lemeztitkosítás
( összehasonlítás )

BestCrypt
bitlocker
CrossCrypt
Cryptoloop
DiskCryptor
dm-kripta
DriveSentry
E4M
eCryptfs
Fájl Vault
FreeOTFE
GBDE
geli
LUKS
PGPDisk
Privát lemez
scramdisk
Sentry 2020
TrueCrypt
- Történelem
VeraCrypt

Névtelenség

GNUnet
I2P
Java Anon Proxy
Tor
Vidalia
retroshare
Geller
Wickr

Fájlrendszerek ( lista )

EncFS
EFS
eCryptfs
LUKS
PEFS
gumitömlő
StegFS
Tahoe-LAFS

biztonságközpontú operációs rendszer

FRAKK
Qubes

Szolgáltatók

Nevelési

CrypTool

Kapcsolódó témák

A kriptográfia vázlata
A kriptográfia idővonala
hash függvény
- kriptográfiai hash függvény
- A hash függvények listája
Végpontok közötti titkosítás
S/MIME

Kategória
Commons