Hash, porovnanie reťazcov - MATLAB

Hash, porovnanie reťazcov - MATLAB
pridal deadawp 6.3. 2021 o 20:17 (naposledy upravené 2.3. 2022 o 10:22)

Hash, alebo hashovacia funkcia je jednocestná funkcia, ktorá vstupnému reťazcu vytvorí výstup s pevnou dĺžkou. Totožné vstupné reťazce majú rovnaký hash. Hash môže slúži ako kontrólna hodnota pri súbore, integrite dát (hashom vieme overiť, že reťazec nebol pozmenený). Pri dátovo objemných reťazcoch môžeme mať daný reťazec uložený iba v podobe hashu.

Dnes budeme riešiť problém týkajúci sa hashovania a percentuálnej zhody hashov. Vytvoríme si tabuľku s vlastným profilom, ktorá bude reprezentovať údaje:

Meno - N0
Práca - N1
Adresa DOMA - N2
Adresa PRÁCA - N3
Obchod 1 - N7
Obchod 2 - N5
Číslo autobusovej linky - N6
ID zariadenia - N7

Vyplnený reťazec môže vyzerať v prostredí MATLAB napríklad takto
['DEADAWP','Programátor','SNP','Gorkeho','Obchodný dom Fórum','Obchodné centrum Rača','108','123 456 789']

Obdobne vytvoríme 5 tabuliek pre rovnaké entity pre ďalšie osoby. V každej tabuľke z príslušného stĺpca (reprezentovaná v poli) vyberieme hodnotu spoločke s indexom pri N a vytvoríme hash ľubovoľnou hashovacou funkciou. MATLAB má vstavané hashovacie funkcie, avšak dokáže importovaním balíka použiť aj hashovacie funkcie obsiahnuté v Jave, prípadne .NET. Tabuľky vieme v prostredí MATLAB vypísať do konzolovej aplikácie cez table() - viz Reference.

Príklad vypísaných profilov do tabuliek (Referenčný / cudzí profil):

Pre ľahkú demonštráciu využijeme hashovaciu funkciu SHA1. V hexadecimálnej reprezentácii je hash ľubovoľného reťazca o dĺžke 20B. Reťazec hashu nadobúda hodnoty 0 až F. Textový reťazec (vstup) je však treba pretypovať na char, aby ho bolo možné použiť v hashovacej funkcii. V našej programovej implementácii tak máme 8 hashov pre 8 hodnôt z profilu Autora. Pokračujeme vytvorením hashov aj z ostatných profilov.

Príklad reprezentácie profilov v poliach v prostredí MATLAB:

Hash reťazce z pôvodného profilu budeme používať ako referenčné. Ostatné hashe zo zostávajúcich 5-tich profilov sa budú využívať pre kontrolu overenia a zhody. Porovnávanie hashov je dosť komplikované, nakoľko čo i len rozdiel pôvodného reťazca v jednom znaku úplne pretvorí hash. Pre porovnanie som tak využil konzervatívnu metódu porovnávania hashov po bajtoch. Ako z prechádzajúceho popisu vieme, výsledkom SHA1 funkcie je 20-bajtový hash v HEX reprezentácii.

Každý bajt tak bude mať 5% váhu finálnej zhody. Porovnávame bajty pod sebou (prvý s prvým, druhý s druhým...). Finálne percento zhody je tak súčet váh všetkých zhodných bajtov. Miera zhody bajtu je 6.25% pri možných kombináciách 0 až F (1/16).

Výsledná reprezentácia vyzerá napríklad takto:

Reprezentácia poukazuje na mieru zhody Referenčného profilu s 5-timi profilmi cudzích osôb. Ak si všimneme reprezentáciu zhodnosti adries domov, vidíme, že sa s referenčný profilom zhoduje na 100% - identickosť Profil č. 1. Ak si preskúmame obe hodnoty v tabuľke vyššie, vidíme adresu domov - SNP, teda i výsledné hashe SHA1 sa rovnajú vo všetkých porovnávaných bajtoch. V prípade ostatných hodnôt je nižšia, nakoľko inde v systéme neexistujú totožné reťazce pre určitú hodnotu. Tento typ overenia zhody hashov je vhodný pre spôsob overenia identickosti údajov v tabuľke.