Що е то хеширане и за какво се използва

0
718

Още една магическа дума – „хеш“.

Тази статия се появи в резултат от една дискусия на форума в която стана ясно, че всички са чували думата, но малко от начинаещите програмисти знаят какво точно означава и каква полза можем да имаме от тези техники в програмирането.
Основната цел на статията е да изясни на начинаещите същността на нещата. От там нататък е много лесно да се намерят подробности и конкретни реализации използвайки Google

На английски: „hash, hashing“. Превежда се буквално като „кълцам“ или „бъркотия“. Понякога се използва: „message digest“, което може да се преведе буквално като „смляно съобщение“ или „извлечение от съобщение“. Друг път ще го срещнете като „digital fingerprint“ – буквално, цифров пръстов отпечатък.

Какво обаче означава това, отнесено към компютрите и информатиката?

Най-общо хеширащите алгоритми получават на входа си някаква поредица от данни с произволна дължина – най-често стринг от символи, но може да са и други данни, а на изхода се получава едно число или стринг с фиксирана дължина, което характеризира „уникално“ цялото входно съобщение. Пиша „уникално“ в кавички, защото както ще видим по-нататък това не е точно така.
За да стават нещата по-ясни, по-нататък в статията ще предполагаме, че входните данни са текстов стринг, а изходната стойност е число.
За един добър хеширащ алгоритъм е задължително да отговаря на няколко условия:

1. Да е необратим – тоест да не съществува алгоритмичен начин за възстановяване на изходният стринг от хеш стойността. (Казвам „алгоритмичен“, защото винаги съществува начина с „груба сила“ – тоест изброяваме всички възможни комбинации от входни данни и пробваме за всяка от тях докато намерим решението.)

2. Да дава възможно най-равномерно разпределение на стойностите в допустимият диапазон, за типичните представители навходният стринг. Най-общото правило тук е, че при малки разлики във входните стрингове, хеш функцията трябва да дава големи разлики във изходните си стойност. По това свойство, хеш функциите много приличат на генераторите на случайни числа.

3. Хеш функцията трябва по възможност да се изпълнява бързо. Това не е абсолютно задължителност, но повече скорост никога не вреди

Криптиране ли е хеширането?

В най-общият смисъл на думата „криптиране“, се предполага, че ако се разполага с нужните ключове, обратната операция е възможно, тоест от криптираното съобщение, използвайки ключа, можем да получим изходното съобщение.
В случая със хеш функциите, това въобще не е така.
Някои използват термина „еднопосочно криптиране“, който според мене също не е особенно точен, тък като в думата „криптиране“ винаги се подразбира двупосочност и използването и с думата „еднопосочно“ крие логическо противоречие.
Според мене, най-точното описание на хеширането е „еднопосочно преобразование“ или „необратимо преобразование“.

Уникални ли са хеш стойностите?
Не се заблуждавайте. Хеш стойностите не са уникални за даден входен стринг!
В зависимост от дължината на хеш стойността и алгоритъма на хеширане има по-голяма или по-малка вероятност за т.н. хеш колизии – това е когато два различни стринга имат една и съща хеш стойност.
При някои алгоритми тази вероятност е по-голяма при друга по-малка, но никога не е нула. Като пример ще дам елементарният (но все още използван тук-там) алгоритъм – хеш стойността се получава като се сумират един след друг всички символи на стринга. Очевидно е, че при произволна размяна на символите във стринга, ще се получи стринг, който има същият хеш.
При по-сложните хеш функции, намирането на втори стринг със същата хеш функция не е тривиална задача, но това не значи, че хеш стойностите никога няма да съвпаднат. Самият факт, че хеш стойността е винаги по-малка от стринга гарантира съвпадения на хешовете за някои входни стойности.
Правилото е такова – колкото дължината на хеша е по-голяма, толкова по-рядко стават колизии. Ако дължината на хеша е по-голяма от най-дългият стринг, може да се намери такава функция, която никога няма да дава колизии, но разбира се, използването не толкова дълги хеш стойности е допустимо само за много специфични задачи.

За какво се използва?

Има няколко главни сфери на приложение на хеширането. Тъй като са доста различни, ще ги разгледаме поотделно:

1. Търсене на стрингове в големи масиви. Хеш таблици.

Да предположим, че имаме някакъв голяма таблица (масив) със произволни, уникални стрингове и имаме нов стринг, който искаме да разберем има ли го в таблицата или не. Тривиалното решение е да сканираме масива елемент по елемент и да сравняваме нашият стринг със всеки стринг в таблицата.
Това решение обаче е крайно неефективно. Наистина, сравняването на стрингове е много скъпа операция, която вътрешно се реализира със цикли, и сравняване символ по символ на двата стринга. От друга страна, сравняването на числа е евтина операция, която се реализира с 1, 2 инструкции на процесора.
Как можем да заменим сравняването на стрингове със сравняване на числа?
Да предположим, че когато запълваме масива, заедно със всеки стринг, изчисляваме и записваме и неговата хеш стойност.
Тогава при търсенето, можем да изчислим хеша на търсеният стринг и да сканираме масива, сравнявайки не директно стринговете, а хеш стойностите им. Разбира се задължително трябва да предвидим колизиите – ако хешовете съвпадат, трябва да направим задължително сравнение директно между стринговете, за да сме сигурни че търсеният стринг е намерен – но тук имаме само едно сравнение, а не хиляди.
Това решение веднага може да ни даде значително увеличаване на скоростта на търсенето. Но все пак остава сканиране на масива, макар и сравнявайки числа, а не стрингове.
Скоростта на алгоритъма е O(n) – тоест времето нараства линейно с увеличаване на размера на масива.
Можем ли да се отървем и от това сканиране и да направим скоростта да не зависи от размера на масива, а да бъде константа?
Да, можем, и това всъщност е най-голямото предимство на хеширането.
Да кажем, че имаме хеш функция, която дава като резултат еднобайтово число, тоест за всеки входен стринг се получава стойност 0..255
Създаваме си масив със 256 елемента, които съдържат указатели към стрингове или 0 – това ще бъде нашата „хеш таблица“, ще я обозначаваме със HashTable[0..255].
При попълването на масива в който ще търсим, изчисляваме хеш стойността на всеки стринг и записваме в съответният елемент от хеш таблицата, указател към стринга:

Код:


h := Hash(NewString);
HashTable[h] := ptr(NewString);

След това, ако имаме стринг, който искаме да потърсим в таблицата, ще е достатъчно да изчислим хеш стойността му и да видим, дали на съответната позиция има 0 или указател. Това ще изглежда така:

Код:


h :=  Hash(SearchString);
if Hash[h] = 0 then "Стринга не е в масива"
              else "Стринга е намерен."

Никога не трябва да забравяме за колизиите! Това е особенно добре видно в горният пример. В най-добрият случай, ако искаме да добавим повече от 256 стринга, таблицата ще се препълни и поне 2 различни стринга ще имат еднакви хеш стойности.
Обикновенно колизии настъпват значително по-рано. Основното правило е да не се допуска напълване на хеш таблицата повече от половината. Тоест, ако искаме да работим с максимум 1000 стринга,трябва да изберем хеш таблица с поне 2000 елемента.

Това не значи, че в такава таблица няма да има колизии! Ще има. Просто, достатъчният размер на таблицата ще държи колизиите в допустими граници, които не се отразяват на скоростта на алгоритъма.

Справяне с колизиите.
Справянето с колизиите се състои от две части:
1. Намаляване на вероятността за възникване на колизии.
2. Справяне с колизиите, които все пак възникват.

За точка 1 – избираме по-голям хеш, избираме подходяща хеш функция, която дава по-малко колизии за типичните входни данни.

За точка 2 – има няколко начина да се справим с колизиите. Всички те имат предимства и недостатъци и най-общо трябва да се избира в зависимост от конкретната задача. Тук ще разгледаме няколко такива:

а. Затворено хеширане
Идеята е, че се използва само наличната хеш таблица, без да се отделя повече място в паметта за решаване на колизиите.
Това намалява използваната памет, но очевидно в такава таблица можем да добавим ограничен брой стрингове – точно колкото е размера на таблицата.
Когато при добавяне на стринг в хеш таблицата се стигне до колизия (тоест на мястото където искаме да запишем стринга има вече друг стринг със същият хеш), просто записваме новият стринг на следващото свободно място в таблицата.
При търсене, алгоритъмът е същият: Ако на мястото в таблицата има записан стринг, но той не е този който търсим, поглеждаме на следващият елемент. Ако и там не е нашият стринг – на следващият и така нататък, докато открием нашият стринг или 0 – което ще значи, че този стринг го няма в масива.
Забелязахте ли как, при наличие на колизия, този алгоритъм се превръща в обикновенно сканиране. Това може драстично да свали скоростта на целият алгоритъм. Затова колизиите са толкова вредни и трябва да се вземат всички мерки за недопускането им.

б. Отворено хеширане
Идеята е, че когато се получи колизия, на съответното място в таблицата, записваме не указател към стринг, а указател към списък от стрингове, където записваме различните стрингове с еднакви хешове.
Това позволява да се записват неограничено количество стрингове в таблицата. Разбира се при търсене, ако срещнем колизия – тоест указател към списък, този списък пак ще трябва да го сканираме елемент по елемент (или по накакъв друг начин – например с двоично търсене) за да установим има ли го нашият стринг или не.

в. Двойно хеширане.
Идеята е – при попълване на таблицата, ако срещнем колизия, изчисляваме втора хеш стойност със друг алгоритъм и хешираме стринга във втора таблица. При търсене, ако стринга записан във първата таблица не съвпада, изчисляване вторият хеш за търсеният стринг и гледаме във втората таблица.
Разбира се във втората таблица също ще са възможни колизии и те трябва да се решат с някакъв друг метод. Но такива колизии ще възникват значително по-рядко и затова ще влияят слабо на скоростта на алгоритъма.

г. Динамично изграждане на хеш таблицата

Като най-общо правило,(сигурно сте забелявали вече) винаги се стремим да използваме най-големият възможен размер на хеш таблиците, за да избегнем колизиите и деградирането на скоростта.
От друга страна обаче сме ограничени от размера на наличната памет, а и тъй като огромната хеш таблица е обикновенно пълна с много нули и малко данни – чувството, че прахосваме памет е особенно силно.
Можем да опитаме малко по нетривиално решение: Избираме голям размер на хеша (например 32бита или 64 бита) но не създаваме хеш таблицата в паметта (че как бихме могли? – за упражнение можете да пресметнете колко памет изисква 32битова хеш таблица, ако всеки елемент е указател), а я изграждаме в процеса на добавяне на стрингове в нея, като в паметта записваме само частта от таблицата, която е запълнена в момента.
Как става това: Сканираме хеша на стринга бит по бит, като всеки бит служи за разклонение на съответното ниво на едно двоично дърво. На последният ред на дървото имаме указатели към стринговете. Възли в дървото прибавяме само когато възникне нужда от тях, така че в паметта винаги имаме само частта на таблицата, която е запълнена с данни.

Този алгоритъм осигурява също константно време за търсене независещо от броя на стринговете в масива, защото претърсването на дървото е винаги постоянно и зависи само от дължината на хеш стойността = дълбочината на дървото. Разбира се това време е по-голямо отколкото директна проверка в таблицата, но по-голямата дължина на хеша – съответно малкият брой колизии, компенсират това забавяне с голяма печалба ако броят на стринговете в таблицата е много голям.

Алгоритми за хеширане
Изборът на „правилен“ алгоритъм за хеширане е много отговорна задача от която до голяма степен зависи ефективността на програмите.

Пример от практиката: Парсерът на FASM (flatassembler) използва хеш функция с дължина 32бита за бързо търсене в списъка с етикети по време на компилацията. При първата реализация (до версия 1.51 – ако си спомням добре) се използваше директно търсене в списъка с етикети, като се сравняваха хеш стойностите.
При компилиране на големи сорсове с много етикети, бързодействието бързо започваше да пада и по същество времето за компилация зависеше от квадрата на броя редове в програмата.
Когато тези ефекти се появиха (при появяването на достатъчно големи програми, написани на FASM), Томаш Гриштар (автора на FASM), смени алгоритъма за търсене с описаният по-горе алгоритъм с двоично хеш дърво.
Това увеличи скоростта на парсера 4 до 5 пъти.
Следващата стъпка беше наистина впечатляваща: След замяна на предишната хеш функция в компилатора с нова (по алгоритъма FNV-1a), скоростта на парсера се увеличи 25 пъти на някои тестове.
От този момент, работата на парсера стана толкова бърза, че при всички практически случаи съставлява малка част от цялото време на компилацията.
Можете да погледнете цялата дискусия свързана с тази история тук: Дискусия за промените във FASM 1.51 (en)

Ето и като пример, сорса на алгоритъма FNV-1a, използван във FASM (flatassembler), а също и в проекта Fresh

Код:


;-------------------------------------------------
; function StrHash
;   Computes 32 bit hash value from the string.
;   The function is compatible with FASM hash
;   function if OrMask = 0.
; Algorithm: FNV-1a
;
; Arguments:
;   hString - handle/pointer of the string.
;   OrMask  - every byte from the string will be ORed
;             with this value (byte)
; Return:
;   eax - 32bit hash value.
;-------------------------------------------------
proc StrHash, hString, OrMask
begin
       push    esi edi ebx ecx edx

       stdcall StrPtr, [hString]
       mov     esi, eax

       xor     ebx, ebx
       mov     eax,2166136261
       xor     ecx, ecx
       mov     edi, 16777619
.hashloop:
       mov     cl, [esi+ebx]
       jecxz   .endstring
       inc     bl
       or      cl, byte [OrMask]
       xor     al,cl
       mul     edi
       jmp     .hashloop

.endstring:
       mov     edx,eax
       and     eax,0FFFFFFh
       shr     edx,24
       xor     eax,edx
       shl     ebx,24
       or      eax,ebx
       pop     edx ecx ebx edi esi
       return
endp

Кода е без обяснения, защото всъщност алгоритмите за хеширане не могат да се обясняват. Просто се сканира стринга и със ASCII кода на всеки символ се правят някакви сложни аритметични или логически дествия, с цел да се направи изходното число да бъде по възможност зависимо от всички входни символи. Често се използват ротация и умножения на прости числа и т.п. Всеки алгоритъм си е сам за себе си…

2. Пароли, идентификация
Другата голяма област на приложение на хеш функциите е идентификацията на потребители и разпознаване на пароли. Тук се използва свойството на хеша, че е необратим. Тоест няма алгоритмичен начин по хеш стойността да определим началният стринг.
При използване на хеширането в тази област, колизиите нямат значение, защото можем да използваме хешове с произволна дължина, дори и такава по-голяма от входният стринг. Тук не се гони бързодействие, а сигурност. А знаем, че ако дължината на хеша е по-голяма от тази на входният стринг, е възможно да се намери такава функция, която да не дава колизии за целият диапазон на входните стрингове.

Как въобще става разпознаването на потребители по парола?
Най-простият начин е да пазим паролите в масив, заедно със имената на потребителите и директно да ги сравняваме с тези, които потребителят въвежда.
Този метод е безкрайно ненадежден обаче. Всеки който има достъп до файла с паролите, ще може да ги види и използва.
При предаване на тези пароли по интернет, нещата са още по-зле, защото може да ги прихване всеки.
Използването на криптиране на файловете с пароли също не е решение, защото всеки криптиращ алгоритъм може да се декриптира.
Всъщност правилното решение е просто – не пазим въобще паролите на потребителите, а пазим само хеш стойността от тази
парола. При искане на достъп до някой ресурс, потребителя въвежда някаква дума, която се хешира и така получената стойност се сравнява с базата данни за даденият потребител. Ако хеш стойностите съвпадат, потребителя се пуска.
Дори и някой да има достъп до базата данни, той няма да може да разбере какви са паролите на потребителите, защото хеш функцията не може да се инвертира.
Както вече казахме, колизиите тук нямат значение, защото се избират хешове с голяма дължина (MD5 например е 16 байта – 128бита дълъг)
Изобщо, приложението на хеш функциите в тази област е тривиално и сравнително лесно, а основният акцент е върху качеството на самите хеш алгоритми.

Автор: John Found, Call Power
Екипа на kaldata.com благодари на Call Power и BG Development за предоставената статия

СПОДЕЛИ
Предишна новинаWinRAR 3.40 Beta 3
Следваща новинаSkype 1.0.0.10 Final
Калин Карабойчев е управител на Kaldata.com - най-големият български IT портал. Повече от 15 години се занимава активно с разработка и популяризация на услуги в българския интернет.

ДОБАВИ КОМЕНТАР

Коментирай това преди всички други

Извести ме за
avatar
wpDiscuz