Хеш-функция

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

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

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

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

Приложение в криптографията[редактиране | edit source]

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

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

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

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

Видове хеш-функции[редактиране | edit source]

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

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


Препратки[редактиране | edit source]

Източници[редактиране | edit source]

  1. Великотърновски университет.