Хеширование

Хеширование (иногда «хэширование», англ. hashing) — преобразование по детерминированному алгоритму входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или сводкой сообщения (англ. message digest).

wikipedia

Хеширование широко применяется в информационных технологиях — для построения достаточно уникальных идентификаторов наборов данных, контрольного суммирования с целью обнаружения случайных или намеренных ошибок при хранении или передаче, для хранения паролей в системах защиты (в этом случае доступ к области памяти, где находятся пароли, не позволяет восстановить сам пароль) и т.п.

Хэш-функция  предназначена для сжатия входного массива данных произвольной длины в битовую строку заранее заданного размера (нескольких десятков или сотен бит).

Хэш-функция h принимает в качестве аргумента входной массив данных (документ) X произвольной длины и возвращает хэш-значение h(X)=Н фиксированной длины. Обычно хэшированная информация является сжатым двоичным представлением основного сообщения произвольной длины называемым дайджестом сообщения (message digest). Следует отметить, что значение хэш-функции h(X) сложным образом зависит от документа X и не позволяет восстановить сам документ из хэш-значения Н (однонаправленная хэш-функция).

Вообще под однонаправленностью понимают не невозможность, а высокую сложность восстановления сообщения по его хэшу, так как на данный момент нет используемых хэш-функций с доказанной однонаправленностью.

Теоретически существует массив данных Y, для которого h(X) = h(Y). Эти пары X,Y называют коллизиями. Основное требование, предъявляемое криптографическими приложениями к хэш-функциям, состоит в отсутствии эффективных алгоритмов поиска коллизий.

Схемы электронной подписи — одна из сфер применения хэш-функций.

При формировании электронной подписи на практике часто подписывается не само сообщение, а его хеш-образ.

В процессе цифрового подписания система ЭЦП обрабатывает исходное сообщение (прообраз)  криптографически стойким односторонним хэш-алгоритмом. Эта операция приводит к генерации дайджеста сообщения.

Затем система зашифровывает полученный дайджест закрытым ключом отправителя, создавая «электронную подпись», и прикрепляет её к прообразу. По получении сообщения, адресат при помощи системы ЭЦП заново вычисляет дайджест подписанных данных, расшифровывает ЭЦП открытым ключом отправителя, тем самым сверяя, соответственно, целостность данных и их источник; если вычисленный адресатом и полученный с сообщением дайджесты совпадают, значит информация после подписания не была изменена.

В системах ЭЦП могут использоваться различные хэш-функции, но они  должны удовлетворять ряду условий:

1. хэш-функция должна быть чувствительна к всевозможным изменениям в тексте, таким как вставки, выбросы, перестановки и т.п.;
2. хэш-функция должна обладать свойством необратимости, то есть задача подбора документа, который обладал бы требуемым значением хэш-функции, должна быть вычислительно неразрешима;
3. вероятность коллизий, то-есть того, что значения хэш-функций двух различных документов (вне зависимости от их длин) совпадут, должна быть ничтожно мала.