Хэш — функция сжатия данных¶
Хэш (от англ. hash — «рубленое мясо», «каша») — это функция преобразования входных данных произвольной длины в фиксированную последовательность битов, называемую хэш-значением или дайджестом. Хэш-функция является основным инструментом криптографии, информационной безопасности и структур данных: она применяется для проверки целостности файлов, хранения паролей, цифровых подписей, блокчейнов и построения хеш-таблиц.
¶Основные свойства
Хэш-функция обладает набором математических свойств, определяющих её применимость:
- Детерминированность — одни и те же входные данные всегда дают один и тот же хэш.
- Необратимость — вычислить исходные данные по хэшу практически невозможно (односторонняя функция).
- Аваланчный эффект — изменение одного бита входных данных приводит к радикальному изменению хэш-значения.
- Устойчивость к коллизиям — найти два разных входных сообщения с одинаковым хэшем должно быть вычислительно нецелесообразно.
- Фиксированная длина выхода — независимо от размера входа, хэш имеет постоянную длину (например, 128, 256 или 512 бит).
¶Классификация
Хэш-функции делятся на две основные группы:
¶Криптографические хэш-функции
Обладают высокой устойчивостью к взлому и используются в системах безопасности. Основные стандарты:
| Алгоритм | Год | Длина хэша (бит) | Статус |
|---|---|---|---|
| MD5 | 1992 | 128 | Небезопасен, взломан |
| SHA-1 | 1995 | 160 | Взломан (2017) |
| SHA-2 (SHA-256, SHA-512) | 2001 | 256/512 | Актуален |
| SHA-3 (Keccak) | 2015 | 224–512 | Актуален |
| BLAKE2 / BLAKE3 | 2012 / 2020 | до 512 | Актуален |
MD5 и SHA-1 были взломаны методом коллизий, поэтому в криптографических приложениях они не используются, но остаются в применении для контрольных сумм файлов.
¶Некриптографические хэш-функции
Применяются там, где важна скорость, а не стойкость к взлому: в хеш-таблицах, дедупликации данных, случайных генераторах. Примеры: CRC32, MurmurHash, xxHash, CityHash.
¶Как работает хэш-функция
Внутренне криптографические хэш-функции устроены по принципу «мертвого кольца» (Merkle–Damgård construction): входное сообщение разбивается на блоки фиксированного размера, каждый блок последовательно «сжимается» вместе с предыдущим состоянием. В результате цепочки преобразований получается итоговый дайджест.
Алгоритм SHA-256, например, обрабатывает данные блоками по 512 бит и за 64 раунда побитовых операций (сложение по модулю 2, сдвиги, логические функции) формирует 256-битный хэш.
¶Применение
¶Целостность данных
Хэш позволяет обнаружить изменение файла. Пользователь скачивает файл и его хэш-сумму с официального сайта, вычисляет хэш локально и сравнивает: совпадение означает, что файл не повреждён и не подделан.
¶Хранение паролей
В современных системах пароли не хранятся в открытом виде — вместо них сохраняется хэш с добавлением соли (случайного значения). При входе пароль хэшируется и сравнивается с сохранённым значением. Для паролей применяют медленные функции (bcrypt, scrypt, Argon2), затрудняющие перебор.
¶Цифровые подписи
Подпись сообщения основана на вычислении хэша и его шифровании закрытым ключом. Проверяющая сторона вычисляет хэш полученного сообщения и сверяет с расшифрованным значением.
¶Блокчейн
В технологии блокчейн хэш-функции (например, SHA-256 в Bitcoin) используются для связывания блоков, доказательства работы (Proof of Work) и адресации транзакций. Адрес кошелька — это хэш публичного ключа.
¶Хеш-таблицы
Структура данных, обеспечивающая поиск за время O(1). Ключ преобразуется в хэшом, который определяет позицию элемента в массиве.
¶Интересные факты
- Слово «хэш» происходит от английского to hash — «рубить, мелко нарезать», что отражает суть процесса: данные «измельчаются» до компактной формы.
- Хэш-функции используются для генерации отпечатков (fingerprints) в системах контроля версий, например, Git хранит объекты по их SHA-1/SHA-256 хэшам.
- В 2017 году исследователи Google и CWI Amsterdam продемонстрировали первую практическую коллизию для SHA-1 (проект SHAttered), что ускорило переход на SHA-2 и SHA-3.
¶Источники
- Справочник RFC 6234: US Secure Hash Algorithms
- Stallings W. Cryptography and Network Security: Principles and Practice
- Меркле Р. «Схемы защиты информации» (Merkle–Damgård construction)
- NIST FIPS 180-4: Secure Hash Standard
