• Szerző: Sallai András
• Copyright © 2014, Sallai András
• Szerkesztve: 2025
• Licenc: CC BY-SA 4.0
• Web: https://szit.hu

A hash jelentése zagyvalék, vagdalék, de elegánsabban úgy szoktuk fordítani az informatikában, hogy hasítás. Esetünkben természetesen adatok hasításáról van szó. Az informatikában a hasítást mindig egy függvénnyel végezzük, így ezen túl hasítófüggvényekről beszélünk.

Az informatika két területén is használjuk a hasítófüggvényeket. Az egyik biztonság, a másik az adattárolás területe. Az adattárolás területén már az 1950-es évek elejétől ismerős ez a fogalom. A biztonság területén csak 1980-as évek végétől használjuk.

Ha általánosítjuk a hasítást, az életben is találhatunk hasonló jelenséget. Ha például informatikai könyveket keresek egy könyvtárban, akkor egyenest az informatikai polcokhoz megyek, és nem nézem egyenként végig az összes polc, összes könyvét, mert tudom hol kell keresni.

A számítógép memóriájában is ehhez hasonlóan szeretnénk adatokat tárolni. Ha keresünk egy adatot ne kelljen végig menni az összes adaton. A hasítótáblák hatékonysága O(1). Vagyis az adatok számának növekedése nem jár több művelettel. Összehasonlítva a láncolt lista O(n), a bináris keresőfák O(log n) hatékonyságúak.

A hasítófüggvényeknek nagy hasznát vesszük szótárak megvalósításánál, ahol alapvetően három művelet van, új elem hozzáadása, keresés és törlés.

A hasító függvények egy értékből egy hasítóértéket állítanak elő. A hasító érték megmutatja az érték helyét a hasítótáblában.

Legyen például néhány főnév, amit szeretnénk tárolni és amelyben szeretnénk keresni. Az egyszerűség kedvéért most ezek csak az angol ábécé betűit tartalmazzák.

• hal
• kutya
• ablak
• akta
• atka
• akna
• ajak
• kaja
• alga
• talaj

Számozzuk meg az ábécé betűit:

Vegyünk egy nagyon nagyon egyszerű hasító függvényt. Egy szó kulcsának meghatározásához adjuk össze a hozzátartozó számokat.

A hal szó kulcsa például:

8 + 1 + 12 = 21

A kutya ugyanezt az algoritmust követve:

11 + 21 + 20 + 25 + 1 = 68

Az ablak szó kulcsa:

1 + 2 + 12 + 1 + 11 = 25

A hasítófüggvényünk úgy tűnik kielégítően működik, a sok üres hely azonban szembetűnő.

Jó lenne ha szűkíteni tudnánk a kulcsok tartományát. Ezt egy maradékképzéses osztással megtehetjük. Az összeadás végét osszuk el az elemek számával.

A hal szó kulcsa:

8 + 1 + 12 = 21
21 % 10 = 1

A kutya szó kulcsa:

11 + 21 + 20 + 25 + 1 = 78
78 % 10 = 8

Az ablak szó kulcsa:

1 + 2 + 12 + 1 + 11 = 27
27 % 10 = 7

Az atka és kaja eredménye viszont megegyezik. Az összeadás eredménye ugyan különböző, de 10-zel osztva mindkét esetben 3-t kapunk:

kaja:

11 + 1 + 10 + 1 =23
23 % 10 = 3

atka:

1 + 20 + 11 + 1 = 33
33 % 10 = 3

Ezért célszerűbb címterületet 10-ről valamelyik közeli prímszámra változtatni. Legyen 13. Az osztás újra elvégezve a 13-as értékkel a következő helyeket kapjuk:

A következő problémát az anagrammák okozzák. Vegyük az akta szót. A maradékos osztás mellett ütközést kapunk. Az ütközés oka, hogy a betűk egyeznek, csak más a sorrendjük. Az eddigi algoritmusunk nem veszi figyelembe a sorrendet.

akta:

1 + 11 + 20 + 1 = 23
23 % 13 = 10

atka:

1 + 20 + 11 + 1 = 23
23 % 13 = 10

Mindkettő kulcsa egyezik.

A Java nyelv java.lang.String osztályának hashCode() metódusa 31-gyel való szorzással oldja meg problémát. Minden elemhez, csak úgy adjuk a következő értéket, hogy előtte megszorozzuk 31-gyel.

Legyen címtér 43. Ekkor 43-mal kell maradékos osztást végezni.

hal:

(8 * 31 + 1) * 31 + 12 = 7731
7731 % 43 = 13

kutya:

(((11 * 31 + 21) * 31 + 20) * 31 + 25) * 31 + 1 = 10804338
10804338 % 43 = 29

ablak:

((1 * 31 + 12) * 31 + 1) * 31 + 11 = 994677
994677 % 43 = 1

akta:

((1 * 31 + 11) * 31 + 20) * 31 + 1 = 40983
40983 % 43 = 4

atka:

((1 * 31 + 20) * 31 + 11) * 31 + 1 = 49353
49353 % 43 = 32

Ezzel az 5 szóval persze a 11 prímszám is megfelelne, de a többi 5 esetén már ismétlődést tapasztalnánk.

A táblázat kihasználtsága nagyon rossz. A tábla mérete 43 és 10 értéket tárolunk benne.

(10 / 43) * 100 = 23 %

Megkeressük a következő szabad helyet. A következő szó az akna. Az akna a 9-es számot generálja, mint a hal szó. Az akna szó számára megkeressük a következő szabad helyet, ami a 10:

A 9-es index után a 10-es szabad.

A következő szó a kaja. A kaja ütközik az atka szóval. Mindkettő a 7-es helyen lenne. A kaja számára megkeressük a következő szabad helyet. A táblázat végéig nincs üres hely. A táblázat elejéről kezdem a keresést.

Az első hely szabad, ezért ott elhelyeztük.

Ez már működik. A hatékonyság a O(1) viszont tart a O(n)-be.

Ha ütközés van, egyszerűen hozzáfűzöm a már meglévő adathoz az újabbat. A technikát láncolásnak vagy vödörmódszernek is hívják, mivel egymás után láncoljuk az értékeket, illetve vödrökbe rakjuk azokat.

Most foglalkozzunk az adatok integritásával.

Szeretnénk ellenőrizni, hogy egy adat megváltozott-e. Ha van egy potenciálisan nagy mennyiségű adat, szeretnénk hozzárendelni egy azt reprezentáló értéket. Például egy egy program változott-e. A másik lehetőség, hogy jelszót szeretnénk tárolni.

A jó hash függvény követelményei:

• Determinisztikus: Ugyanarra a bemenetre ugyanazt a kimenetet kell kapjuk, vagyis determinisztikusnak kell lennie.
• Fix kimenet: Bármilyen hosszú a bemeneti szöveg, a kimeneti szöveg hosszának mindig ugyanolyan hosszúnak kell lennie.
• Lavinahatás (Avalanche effect): Ha csak egyetlen betűt is megváltoztatsz, a kimenetnek teljesen másnak kell lennie.
• Irreverzibilitás: A bemeneti szövegre nem lehet visszakövetkeztetni.

Adott értékekből szeretnénk egy kivonatot készíteni. Ilyen lehet az összegzés.

Adott az „ABC” szöveg.

Vegyük a szövegünk karaktereinek ASCII kódját:

• A → 65
• B → 66
• C → 67

65+66+67=198

Nem a legjobb algoritmus, mert például CBA kimenete is 198.

Daniel J. Bernstein által, 1991-ben kitalált algoritmus.

calc_hash.js

function calc_hash() {
    var hash = 5381; //bűvös szám
    for (var i = 0; i < this.length; i++) {
        char = this.charCodeAt(i);
               //hash * 33 + char
        hash = ((hash<<5)+hash)+char;
    }
    return hash;
}
 
String.prototype.hash = calc_hash;
 
 
console.log('abc'.hash())
console.log('cba'.hash())

Futtatás:

nolde calc_hash.js

A hash<<55 a szorzás 33-mal másként leírva. Így azonban sokkal gyorsabb.

Az 5381 Bernstein választása. A tapasztalok alapján jó eredményt, mivel kevés az ütközés.

1991-ben Ronald Rivest (RSA társalpító) készítette.

Sokkal összetettebb egyszerű szorzásoknál:

• Blokkokra bontás: A bemeneti adatot nem karakterenként, hanem fix, 512 bites blokkokban dolgozza fel.
• 4 körös feldolgozás: Minden blokkon 64 műveletet hajt végre.
• Logikai függvények: Használ bitenkénti ÉS, VAGY, NEM és XOR műveleteket, amik jól összekeverik a biteket.
• Konstansok: Beépítettek bele „bűvös számokat”, amik a szinusz függvényen alapulnak, hogy ne legyen benne semmilyen könnyen felismerhető matematikai minta.

Az MD5-t már nem tekintjünk biztonságosnak.

• Ütközések: 2004-ben rájöttek, hogy lehet két teljesen különböző fájlt készíteni, aminek MD5 hash értéke ugyanaz.
• Gyorsaság: Mivel a számítógépek manapság nagyon gyorsak, egy modern videókártyával több milliárd MD5 hash-t lehet generálni másodpercenként. Így a feltörése (brute-force) vagy szivárványtáblák segítségével pillanatok műve.

Manapság szabvány. Az SHA a Secure Hash Algorithm rövidítése.

Az adatokat rögzített méretű blokkokra bontjuk, majd azokat egymás után dolgozzuk fel.

Kifejezetten jelszavak tárolására tervezett algoritmus.

Szándékosan lassú és erőforrásigényes.

Linuxon jó ideje lecserélték az SHA-512-t is yescrypt algoritmusra. Offline törésekkel szemben ellenállóbb.

Az SHA-256 és SHA-512 fájlok ellenőrzésére kiváló és biztonságos. Jelszavak tárolására azonban a yescripty ajánlott.

• https://www.openwall.com/yescrypt/

A hackerek ma már nem szimpla processzorokat használnak jelszavak törésére.

Amit használnak:

• GPU (videókártyák): egyszerre többezer jelszót tudnak tesztelni.
• ASIC (célhardverek): MD5 vagy SHA-256 számolásra tervezettek, és nagyon hatékonyak.

A yescrypt-et ezek ellen tervezték.

A yescrypt fő fegyverei:

• Memória-éhség (Memory-hard).
• GPU-ellenség (GPU unfriendliness)
• Rugalmasság (Scalability)

A yescrpyt megdolgoztatja a processzorokat is, de még nagyobb a memóriaigényük. A videókártyákés az ASIC-oknak szok magjuk van a számításokhoz, de kevés gyors memóriájuk van. A hacker nem tud egyszerre több ezer próbálkozást futtatni.

A GPU-ellenség, mivel a a yescrypt egymásra épülő (szekvenciális) lépésekkel dolgozik, amiben a videókártyák nem teljesítenek jól. A videókártyák akkor erősek, ha sok független dolgot kell egyszerre csinálniuk. A yescripyt esetén a videókártyák szimpla irodaigépekre lassulnak.

A yescrypt rugalmas, mivel számítógépek fejlődése esetén, állíthatók a mennyi időt és memóriát használjanak. Így az üzemeltetőnek nem szükséges új algoritmust keresnie.