Хеш функция

Хеш функция или раздробяваща функция (на английски: hash-function – насичаща функция) е еднопосочна, математическа функция, която служи за „раздробяване“, сгъстяване на дадено множество. Входният масив от данни с произволна дължина се преобразува в изходен низ с фиксирана дължина. Друга дефиниция е компактно представяне на входната последователност, което наричаме още цифрова сигнатура, отпечатък или извлечение (message digest, digital fingerprint).^[1]

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

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

Приложение в криптографията

Хеш функциите се използват много често за удостоверяване на източника (Message Authentication Codes – MAC) или за удостоверяване на целостта на данните (Message Detection Codes – MDC), като изпращачът хешира (шифрира) съобщението, предава кодираното число по обикновена, нешифрирана връзка и накрая получателят де-хешира (дешифрира) полученото число.

Пример за хеш функция, която кодира имена с цели числа от 0 до 15. Вижда се съвпадението между ключовете John Smith и Sandra Dee.

Сред множеството хеш функции тези, които са подходящи за прилагане в криптографията, трябва да отговарят на следните критерии:

• еднопосочност – за дадена хеш ${\displaystyle h}$ да е трудно да бъде изчислено съобщение ${\displaystyle m}$, такова че ${\displaystyle h=hash(m)\,.}$
• втора еднопосочност (слабо отбягване на съвпадения) – за дадено съобщение м1 е трудно да се намери друго съобщение м2 със съвпадащи изходни стойности ${\displaystyle hash(m1)\neq hash(m2).}$, т.е да няма съвпадения.
• отбягване на съвпадения (силно отбягване на съвпадения) – трудно е да се намерят две различни съобщения със съвпадаща хеш стойност ${\displaystyle hash(m1)\neq hash(m2).}$.

Видове хеш функции

Съществуват множество алгоритми за хеширане с различни характеристики (разрядност, изчислителна сложност, крипто-устойчивост и т.н.). Изборът на конкретната хеш функция се определя от спецификата на решаваната задача. Като най-прост пример за хеш функция могат да служат контролна сума или CRC.

Други видове са:

• удостоверяващи източника MD5-MAC, DES in CBC mode, MAA
• удостоверяващи целостта на данните MD4, MD5, SHA-1, ГОСТ Р 34.11-94

Източници

1. Доц. Стефка Буюклиева. Криптографски хеш-функции (хеш-алгоритми) (PDF) // Лекции по криптография, ВТУ. Архивиран от оригинала на 2013-12-28.

Външни препратки

• Хеширане, eadvise.info
• Хеш таблици, openfmi.net Архив на оригинала от 2009-02-10 в Wayback Machine.

Вижте също

• Хеш таблица