Хеш-функция (англ. hash function от hash — «превращать в фарш», «мешанина»), или функция свёртки — функция, преобразующая массив входных данных произвольного размера в выходную битовую строку определённого (установленного) размера в соответствии с определённым алгоритмом. Преобразование, выполняемое хеш-функцией, называется хешированием. Исходные (входные) данные называются входным массивом, «ключом», «сообщением». Результат преобразования (выходные данные) называется «хешем», «хеш-кодом», «хеш-суммой», «сводкой сообщения», «свёрткой».
Хеш-функции применяются в следующих случаях:
при построении ассоциативных массивов;
при поиске дубликатов в последовательностях наборов данных;
при построении уникальных идентификаторов для наборов данных;
при вычислении контрольных сумм от данных (сигнала) для последующего обнаружения в данных ошибок (возникших случайно или внесённых намеренно), возникающих при хранении и/или передаче данных;
при сохранении паролей в системах защиты в виде хеш-кода (для восстановления пароля по хеш-коду требуется функция, являющаяся обратной по отношению к использованной хеш-функции);
при создании (выработке) электронной подписи (на практике подпись часто создаётся не для сообщения, а для «хеш-образа» сообщения);
и в других случаях.
В общем случае (согласно принципу Дирихле) не существует однозначного соответствия между выходными данными (хеш-кодом, значениями, возвращёнными хеш-функцией) и входными данными (исходными данными). Выходные данные (возвращаемые хеш-функцией значения) менее разнообразны, чем входные данные (значения входного массива). Случай, при котором хеш-функция преобразует более чем одни входные данные (один массив входных данных) в одинаковые выходные данные (сводки), называется «коллизией». Вероятность возникновения коллизий используется для оценки качества хеш-функций.
Существует множество алгоритмов хеширования, различающихся свойствами. Примеры свойств:
разрядность;
вычислительная сложность;
криптостойкость.
Выбор той или иной хеш-функции определяется спецификой решаемой задачи. Простейшим примером хеш-функции может служить «обрамление» данных циклическим избыточным кодом (англ. CRC, cyclic redundancy code).
View More On Wikipedia.org